NAG FL Interface
c05auf (contfn_brent_interval)
1
Purpose
c05auf 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
Fortran Interface
Integer, Intent (Inout) 
:: 
iuser(*), ifail 
Real (Kind=nag_wp), External 
:: 
f 
Real (Kind=nag_wp), Intent (In) 
:: 
h, eps, eta 
Real (Kind=nag_wp), Intent (Inout) 
:: 
x, ruser(*) 
Real (Kind=nag_wp), Intent (Out) 
:: 
a, b 

C Header Interface
#include <nag.h>
void 
c05auf_ (double *x, const double *h, const double *eps, const double *eta, double (NAG_CALL *f)(const double *x, Integer iuser[], double ruser[]), double *a, double *b, Integer iuser[], double ruser[], Integer *ifail) 

C++ Header Interface
#include <nag.h> extern "C" {
void 
c05auf_ (double &x, const double &h, const double &eps, const double &eta, double (NAG_CALL *f)(const double &x, Integer iuser[], double ruser[]), double &a, double &b, Integer iuser[], double ruser[], Integer &ifail) 
}

The routine may be called by the names c05auf or nagf_roots_contfn_brent_interval.
3
Description
c05auf 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
c05avf. If this search succeeds, then the zero is determined to a userspecified accuracy by a call to
c05ayf. The specifications of routines
c05avf and
c05ayf 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)$\leftx\alpha \right\le {\mathbf{eps}}$,

(ii)$\leftf\left(x\right)\right\le {\mathbf{eta}}$.
4
References
Brent R P (1973) Algorithms for Minimization Without Derivatives Prentice–Hall
5
Arguments

1:
$\mathbf{x}$ – Real (Kind=nag_wp)
Input/Output

On entry: an initial approximation to the zero.
On exit: if
${\mathbf{ifail}}={\mathbf{0}}$ or
${\mathbf{4}}$,
x is the final approximation to the zero.
If
${\mathbf{ifail}}={\mathbf{3}}$,
x is likely to be a pole of
$f\left(x\right)$.
Otherwise,
x contains no useful information.

2:
$\mathbf{h}$ – Real (Kind=nag_wp)
Input

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\times {\mathbf{h}},{\mathbf{x}}+256.0\times {\mathbf{h}}\right]$.
Constraint:
${\mathbf{h}}$ must be sufficiently large that ${\mathbf{x}}+{\mathbf{h}}\ne {\mathbf{x}}$ on the computer.

3:
$\mathbf{eps}$ – Real (Kind=nag_wp)
Input

On entry: the termination tolerance on
$x$ (see
Section 3).
Constraint:
${\mathbf{eps}}>0.0$.

4:
$\mathbf{eta}$ – Real (Kind=nag_wp)
Input

On entry: a value such that if
$\leftf\left(x\right)\right\le {\mathbf{eta}}$,
$x$ is accepted as the zero.
eta may be specified as
$0.0$ (see
Section 7).

5:
$\mathbf{f}$ – real (Kind=nag_wp) Function, supplied by the user.
External Procedure

f must evaluate the function
$f$ whose zero is to be determined.
The specification of
f is:
Fortran Interface
Real (Kind=nag_wp) 
:: 
f 
Integer, Intent (Inout) 
:: 
iuser(*) 
Real (Kind=nag_wp), Intent (In) 
:: 
x 
Real (Kind=nag_wp), Intent (Inout) 
:: 
ruser(*) 

C Header Interface
double 
f_ (const double *x, Integer iuser[], double ruser[]) 

C++ Header Interface
#include <nag.h> extern "C" {
double 
f_ (const double &x, Integer iuser[], double ruser[]) 
}


1:
$\mathbf{x}$ – Real (Kind=nag_wp)
Input

On entry: the point at which the function must be evaluated.

2:
$\mathbf{iuser}\left(*\right)$ – Integer array
User Workspace

3:
$\mathbf{ruser}\left(*\right)$ – Real (Kind=nag_wp) array
User Workspace

f is called with the arguments
iuser and
ruser as supplied to
c05auf. You should use the arrays
iuser and
ruser to supply information to
f.
f must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which
c05auf is called. Arguments denoted as
Input must
not be changed by this procedure.
Note: f should not return floatingpoint NaN (Not a Number) or infinity values, since these are not handled by
c05auf. If your code inadvertently
does return any NaNs or infinities,
c05auf is likely to produce unexpected results.

6:
$\mathbf{a}$ – Real (Kind=nag_wp)
Output

7:
$\mathbf{b}$ – Real (Kind=nag_wp)
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 $\leftf\left(x\right)\right\le {\mathbf{eta}}$ at any stage in the calculation, on exit ${\mathbf{a}}={\mathbf{b}}=x$.

8:
$\mathbf{iuser}\left(*\right)$ – Integer array
User Workspace

9:
$\mathbf{ruser}\left(*\right)$ – Real (Kind=nag_wp) array
User Workspace

iuser and
ruser are not used by
c05auf, but are passed directly to
f and may be used to pass information to this routine.

10:
$\mathbf{ifail}$ – Integer
Input/Output

On entry:
ifail must be set to
$0$,
$1\text{or}1$. If you are unfamiliar with this argument you should refer to
Section 4 in the Introduction to the NAG Library FL Interface for details.
For environments where it might be inappropriate to halt program execution when an error is detected, the value
$1\text{or}1$ is recommended. If the output of error messages is undesirable, then the value
$1$ is recommended. Otherwise, if you are not familiar with this argument, the recommended value is
$0$.
When the value $\mathbf{1}\text{or}\mathbf{1}$ is used it is essential to test the value of ifail on exit.
On exit:
${\mathbf{ifail}}={\mathbf{0}}$ unless the routine detects an error or a warning has been flagged (see
Section 6).
6
Error Indicators and Warnings
If on entry
${\mathbf{ifail}}=0$ or
$1$, explanatory error messages are output on the current error message unit (as defined by
x04aaf).
Errors or warnings detected by the routine:
 ${\mathbf{ifail}}=1$

On entry, ${\mathbf{eps}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{eps}}>0.0$.
On entry, ${\mathbf{x}}=\u2329\mathit{\text{value}}\u232a$ and ${\mathbf{h}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{x}}+{\mathbf{h}}\ne {\mathbf{x}}$ (to machine accuracy).
 ${\mathbf{ifail}}=2$

An interval containing the zero could not be found. Increasing
h and calling
c05auf again will increase the range searched for the zero. Decreasing
h and calling
c05auf again will refine the mesh used in the search for the zero.
 ${\mathbf{ifail}}=3$

Solution may be a pole rather than a zero.
 ${\mathbf{ifail}}=4$

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}}=\u2329\mathit{\text{value}}\u232a$.
 ${\mathbf{ifail}}=99$
An unexpected error has been triggered by this routine. Please
contact
NAG.
See
Section 7 in the Introduction to the NAG Library FL Interface for further information.
 ${\mathbf{ifail}}=399$
Your licence key may have expired or may not have been installed correctly.
See
Section 8 in the Introduction to the NAG Library FL Interface for further information.
 ${\mathbf{ifail}}=999$
Dynamic memory allocation failed.
See
Section 9 in the Introduction to the NAG Library FL Interface for further information.
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{ifail}}={\mathbf{4}}$, 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
c05auf is not threaded in any implementation.
The time taken by
c05auf 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\times {\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
c05avf followed by
c05azf 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 routines are more flexible than the direct communication of
f required by
c05auf.
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\u22125}$ starting from ${\mathbf{x}}=1.0$ and using an initial search step ${\mathbf{h}}=0.1$.
10.1
Program Text
10.2
Program Data
None.
10.3
Program Results