zero_univariate

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,

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 = "#".