zero_univariate
Finds a zero of a real univariate function.
Synopsis
#include <imsl.h>
void imsl_f_zero_univariate (float fcn(), float *a, float *b, …, 0)
The type double function is imsl_d_zero_univariate.
Required Arguments
float fcn (float x) (Input/Output)
User-supplied function to compute the value of the function of which the zero will be found.
Arguments
float x (Input)
The point at which the function is evaluated.
Return Value
The computed function value at the point x.
float *a (Input/Output)
See b.
float *b (Input/Output)
Two points at which the user-supplied function can be evaluated.
On input, if fcn(a) and fcn(b) are of opposite sign, the zero will be found in the interval [a, b]and on output b will contain the value of x at which fcn(x)= 0. If fcn(a) × fcn(b) > 0, and a ≠ b then a search along the x number line is initiated for a point at which there is a sign change and |b – a| will be used in setting the step size for the initial search. If a = b on entry then the search is started as described in the description section below.
On output, b is the abscissa at which |fcn(x)| had the smallest value. If fcn(b) ≠ 0 on output, a will contain the nearest abscissa to output b at which fcn(x) was evaluated and found to have the opposite sign from fcn(b).
Synopsis with Optional Arguments
#include <imsl.h>
void imsl_f_zero_univariate (float fcn(), float *a, float *b,
IMSL_FCN_W_DATA, float fcn(), void *data,
IMSL_ERR_TOL, float err_tol,
IMSL_MAX_EVALS, int maxfn,
IMSL_N_EVALS, int *n_evals,
0)
Optional Arguments
IMSL_FCN_W_DATA, float fcn (float x, void *data), void *data (Input)
float fcn (
float x,
void *data) (Input)
User supplied function to compute the value of the function of which the zero will be found, which also accepts a pointer to data that is supplied by the user. See
Passing Data to User-Supplied Functions in the introduction to this manual for more details.
Arguments
float x (Input)
The point at which the function is evaluated.
void *data (Input)
A pointer to the data to be passed to the user-supplied function.
Return Value
The computed function value at the point x.
IMSL_ERR_TOL, float err_tol (Input)
Error tolerance. If err_tol > 0.0, the zero is to be isolated to an interval of length less than err_tol. If err_tol < 0.0, an x is desired for which |fcn(x)| is ≤ |err_tol|. If err_tol = 0.0, the iteration continues until the zero of fcn(x) is isolated as accurately as possible.
Default: err_tol = 0.0
IMSL_MAX_EVALS, int maxfn (Input)
An upper bound on the number of function evaluations required for convergence. Set maxfn to 0 if the number of function evaluations is to be unbounded.
Default: maxfn = 0
IMSL_N_EVALS, int *n_evals (Output)
The actual number of function evaluations used.
Description
The function imsl_f_zero_univariate is based on the JPL Library routine SZERO. The algorithm used is attributed to Dr. Fred T. Krogh, JPL, 1972. Tests have shown imsl_f_zero_univariate to require fewer function evaluations, on average, than a number of other algorithms for finding a zero of a continuous function. Let f be a continuous univariate function. imsl_f_zero_univariate will accept any two points a and b and initiate a search on the number line for an x such that f(x) = 0 when there is no sign difference between f(a) and f(b). In either case, b is updated with a new value on each successive iteration. The algorithm description follows.
When f(a) × f(b) >0 at the initial point, iterates for x are generated according to the formula x = xmin + (xmin ‑ xmax) × ρ, where the subscript “min” is associated with the (f, x) pair that has the smallest value for ∣ f ∣, the subscript “max” is associated with the (f, x) pair that has the largest value for ∣ f ∣, and ρ is 8 if r = fmin /(fmax – fmin) ≥ 8, else ρ = max(κ/4, r), where κ is a count of the number of iterations that have been taken without finding f’s with opposite signs. If a and b have the same value initially, then the next x is a distance 0.008 + |xmin|/4 from xmin taken toward 0. (If a = b = 0, the next x is -.008.)
Let x1 and x2 denote the first two x values that give f values with different signs. Let α < β be the two values of x that bracket the zero as tightly as is known. Thus α = x1 or α = x2 and β is the other when computing x3. The next point, x3, is generated by treating x as the linear function q(f) that interpolates the points (f (x1), x1) and (f (x2), x2), and then computing x3 = q(0), subject to the condition that α + ɛ ≤ x3 ≤ β − ɛ, where ɛ = 0.875 × max(err_tol, machine precision). (This condition on x3 with updated values for α and β is also applied to future iterates.)
Let x4, x5, …, xm denote the abscissae on the following iterations. Let a = xm, b = xm-1, and c = xm-2. Either α or β (defined as above) will coincide with a, andβ will frequently coincide with either b or c. Let p(x) be the quadratic polynomial in x that passes through the values of f evaluated at a, b, and c. Let q(f) be the quadratic polynomial in f that passes through the points (f(a), a), (f(b), b), and f(c), c).
Let ζ = α or β, selected so that ζ≠a. If the sign of f has changed in the last 4 iterations and p′(a) × q′(f(a)) and p′(ζ)) × q′(f(ζ)) are both in the interval [1/4, 4], then x is set to q(0). (Note that if p is replaced by f and q is replaced by x, then both products have the value 1.) Otherwise x is set to a – (a−ζ) ( φ/(1+φ)), where φ is selected based on past behavior and is such that 0 < φ. If the sign of f () does not change for an extended period, φ gets large.
Example
This example finds a zero of the function
in the interval [ − 10.0, 0.0].
#include <imsl.h>
#include <stdio.h>
float fcn (float x);
int main() {
int n_evals;
float a=-10.0, b=0.0;
imsl_f_zero_univariate(fcn, &a, &b, IMSL_N_EVALS, &n_evals, 0);
printf("The best approximation to the zero of f is");
printf(" equal to %6.3f\n", b);
printf("The number of function evaluations required");
printf(" was %d\n",n_evals);
}
float fcn (float x) {
return x*x + x - 2.0;
}
Output
The best approximation to the zero of f is equal to -2.0
The number of function evaluations required was 10
Fatal Errors
IMSL_ERROR_TOL_NOT_SATISFIED | The error tolerance criteria was not satisfied. “b” contains the abscissa at which “|fcn(x)|” had the smallest value. |
IMSL_DISCONTINUITY_IDENTIFIED | Apparently “fcn” has a discontinuity between “a” = # and “b” = #. No zero has been identified. |
IMSL_ZERO_NOT_FOUND | “fcn(a)*fcn(b)” > 0 where “a” = #” and “b” = #, but the algorithm is unable to identify function values with opposite signs. |
IMSL_MAX_FCN_EVAL_EXCEEDED | The maximum number of function evaluations, “maxfn” = #, has been exceeded. |
IMSL_STOP_USER_FCN | Request from user supplied function to stop algorithm. User flag = "#". |