c05 Chapter Contents
c05 Chapter Introduction
NAG Library Manual

NAG Library Function Documentnag_zero_cont_func_brent_binsrch (c05auc)

1  Purpose

nag_zero_cont_func_brent_binsrch (c05auc) locates a simple zero of a continuous function from a given starting value. It uses a binary search to locate an interval containing a zero of the function, then Brent's method, which is a combination of nonlinear interpolation, linear extrapolation and bisection, to locate the zero precisely.

2  Specification

 #include #include
void  nag_zero_cont_func_brent_binsrch (double *x, double h, double eps, double eta,
 double (*f)(double x, Nag_Comm *comm),
double *a, double *b, Nag_Comm *comm, NagError *fail)

3  Description

nag_zero_cont_func_brent_binsrch (c05auc) attempts to locate an interval $\left[a,b\right]$ containing a simple zero of the function $f\left(x\right)$ by a binary search starting from the initial point $x={\mathbf{x}}$ and using repeated calls to nag_interval_zero_cont_func (c05avc). If this search succeeds, then the zero is determined to a user-specified accuracy by a call to nag_zero_cont_func_brent (c05ayc). The specifications of functions nag_interval_zero_cont_func (c05avc) and nag_zero_cont_func_brent (c05ayc) should be consulted for details of the methods used.
The approximation $x$ to the zero $\alpha$ is determined so that at least one of the following criteria is satisfied:
 (i) $\left|x-\alpha \right|\le {\mathbf{eps}}$, (ii) $\left|f\left(x\right)\right|\le {\mathbf{eta}}$.

4  References

Brent R P (1973) Algorithms for Minimization Without Derivatives Prentice–Hall

5  Arguments

1:     xdouble *Input/Output
On entry: an initial approximation to the zero.
On exit: if ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$ NE_NOERROR or NW_TOO_MUCH_ACC_REQUESTED, x is the final approximation to the zero.
If ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$ NE_PROBABLE_POLE, x is likely to be a pole of $f\left(x\right)$.
Otherwise, x contains no useful information.
2:     hdoubleInput
On entry: a step length for use in the binary search for an interval containing the zero. The maximum interval searched is $\left[{\mathbf{x}}-256.0×{\mathbf{h}},{\mathbf{x}}+256.0×{\mathbf{h}}\right]$.
Constraint: ${\mathbf{h}}$ must be sufficiently large that ${\mathbf{x}}+{\mathbf{h}}\ne {\mathbf{x}}$ on the computer.
3:     epsdoubleInput
On entry: the termination tolerance on $x$ (see Section 3).
Constraint: ${\mathbf{eps}}>0.0$.
On entry: a value such that if $\left|f\left(x\right)\right|\le {\mathbf{eta}}$, $x$ is accepted as the zero. eta may be specified as $0.0$ (see Section 7).
5:     ffunction, supplied by the userExternal Function
f must evaluate the function $f$ whose zero is to be determined.
The specification of f is:
 double f (double x, Nag_Comm *comm)
1:     xdoubleInput
On entry: the point at which the function must be evaluated.
2:     commNag_Comm *
Pointer to structure of type Nag_Comm; the following members are relevant to f.
userdouble *
iuserInteger *
pPointer
The type Pointer will be void *. Before calling nag_zero_cont_func_brent_binsrch (c05auc) you may allocate memory and initialize these pointers with various quantities for use by f when called from nag_zero_cont_func_brent_binsrch (c05auc) (see Section 3.2.1.1 in the Essential Introduction).
7:     bdouble *Output
On exit: the lower and upper bounds respectively of the interval resulting from the binary search. If the zero is determined exactly such that $f\left(x\right)=0.0$ or is determined so that $\left|f\left(x\right)\right|\le {\mathbf{eta}}$ at any stage in the calculation, then on exit ${\mathbf{a}}={\mathbf{b}}=x$.
8:     commNag_Comm *Communication Structure
The NAG communication argument (see Section 3.2.1.1 in the Essential Introduction).
9:     failNagError *Input/Output
The NAG error argument (see Section 3.6 in the Essential Introduction).

6  Error Indicators and Warnings

On entry, argument $⟨\mathit{\text{value}}⟩$ had an illegal value.
NE_INTERNAL_ERROR
An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.
NE_PROBABLE_POLE
Solution may be a pole rather than a zero.
NE_REAL
On entry, ${\mathbf{eps}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{eps}}>0.0$.
NE_REAL_2
On entry, ${\mathbf{x}}=⟨\mathit{\text{value}}⟩$ and ${\mathbf{h}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{x}}+{\mathbf{h}}\ne {\mathbf{x}}$ (to machine accuracy).
NE_ZERO_NOT_FOUND
An interval containing the zero could not be found. Increasing h and calling nag_zero_cont_func_brent_binsrch (c05auc) again will increase the range searched for the zero. Decreasing h and calling nag_zero_cont_func_brent_binsrch (c05auc) again will refine the mesh used in the search for the zero.
NW_TOO_MUCH_ACC_REQUESTED
The tolerance eps has been set too small for the problem being solved. However, the value x returned is a good approximation to the zero. ${\mathbf{eps}}=⟨\mathit{\text{value}}⟩$.

7  Accuracy

The levels of accuracy depend on the values of eps and eta. If full machine accuracy is required, they may be set very small, resulting in an exit with ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$ NW_TOO_MUCH_ACC_REQUESTED, although this may involve many more iterations than a lesser accuracy. You are recommended to set ${\mathbf{eta}}=0.0$ and to use eps to control the accuracy, unless you have considerable knowledge of the size of $f\left(x\right)$ for values of $x$ near the zero.

8  Parallelism and Performance

Not applicable.

The time taken by nag_zero_cont_func_brent_binsrch (c05auc) depends primarily on the time spent evaluating f (see Section 5). The accuracy of the initial approximation x and the value of h will have a somewhat unpredictable effect on the timing.
If it is important to determine an interval of relative length less than $2×{\mathbf{eps}}$ containing the zero, or if f is expensive to evaluate and the number of calls to f is to be restricted, then use of nag_interval_zero_cont_func (c05avc) followed by nag_zero_cont_func_brent_rcomm (c05azc) is recommended. Use of this combination is also recommended when the structure of the problem to be solved does not permit a simple f to be written: the reverse communication facilities of these functions are more flexible than the direct communication of f required by nag_zero_cont_func_brent_binsrch (c05auc).
If the iteration terminates with successful exit and ${\mathbf{a}}={\mathbf{b}}={\mathbf{x}}$ there is no guarantee that the value returned in x corresponds to a simple zero and you should check whether it does.
One way to check this is to compute the derivative of $f$ at the point x, preferably analytically, or, if this is not possible, numerically, perhaps by using a central difference estimate. If ${f}^{\prime }\left({\mathbf{x}}\right)=0.0$, then x must correspond to a multiple zero of $f$ rather than a simple zero.

10  Example

This example calculates an approximation to the zero of $x-{e}^{-x}$ using a tolerance of ${\mathbf{eps}}=\text{1.0e−5}$ starting from ${\mathbf{x}}=1.0$ and using an initial search step ${\mathbf{h}}=0.1$.

10.1  Program Text

Program Text (c05auce.c)

None.

10.3  Program Results

Program Results (c05auce.r)