c05 Chapter Contents
c05 Chapter Introduction
NAG C Library Manual

# NAG Library Function Documentnag_zero_cont_func_brent_rcomm (c05azc)

## 1  Purpose

nag_zero_cont_func_brent_rcomm (c05azc) locates a simple zero of a continuous function in a given interval by using Brent's method, which is a combination of nonlinear interpolation, linear extrapolation and bisection. It uses reverse communication for evaluating the function.

## 2  Specification

 #include #include
 void nag_zero_cont_func_brent_rcomm (double *x, double *y, double fx, double tolx, Nag_ErrorControl ir, double c[], Integer *ind, NagError *fail)

## 3  Description

You must supply x and y to define an initial interval $\left[a,b\right]$ containing a simple zero of the function $f\left(x\right)$ (the choice of x and y must be such that $f\left({\mathbf{x}}\right)×f\left({\mathbf{y}}\right)\le 0.0$). The function combines the methods of bisection, nonlinear interpolation and linear extrapolation (see Dahlquist and Björck (1974)), to find a sequence of sub-intervals of the initial interval such that the final interval $\left[{\mathbf{x}},{\mathbf{y}}\right]$ contains the zero and $\left|{\mathbf{x}}-{\mathbf{y}}\right|$ is less than some tolerance specified by tolx and ir (see Section 5). In fact, since the intermediate intervals $\left[{\mathbf{x}},{\mathbf{y}}\right]$ are determined only so that $f\left({\mathbf{x}}\right)×f\left({\mathbf{y}}\right)\le 0.0$, it is possible that the final interval may contain a discontinuity or a pole of $f$ (violating the requirement that $f$ be continuous). nag_zero_cont_func_brent_rcomm (c05azc) checks if the sign change is likely to correspond to a pole of $f$ and gives an error return in this case.
A feature of the algorithm used by this function is that unlike some other methods it guarantees convergence within about ${\left({\mathrm{log}}_{2}\left[\left(b-a\right)/\delta \right]\right)}^{2}$ function evaluations, where $\delta$ is related to the argument tolx. See Brent (1973) for more details.
nag_zero_cont_func_brent_rcomm (c05azc) returns to the calling program for each evaluation of $f\left(x\right)$. On each return you should set ${\mathbf{fx}}=f\left({\mathbf{x}}\right)$ and call nag_zero_cont_func_brent_rcomm (c05azc) again.
The function is a modified version of procedure ‘zeroin’ given by Brent (1973).

## 4  References

Brent R P (1973) Algorithms for Minimization Without Derivatives Prentice–Hall
Bus J C P and Dekker T J (1975) Two efficient algorithms with guaranteed convergence for finding a zero of a function ACM Trans. Math. Software 1 330–345
Dahlquist G and Björck Å (1974) Numerical Methods Prentice–Hall

## 5  Arguments

Note: this function uses reverse communication. Its use involves an initial entry, intermediate exits and re-entries, and a final exit, as indicated by the argument ind. Between intermediate exits and re-entries, all arguments other than fx must remain unchanged.
1:     xdouble *Input/Output
2:     ydouble *Input/Output
On initial entry: x and y must define an initial interval $\left[a,b\right]$ containing the zero, such that $f\left({\mathbf{x}}\right)×f\left({\mathbf{y}}\right)\le 0.0$. It is not necessary that ${\mathbf{x}}<{\mathbf{y}}$.
On intermediate exit: x contains the point at which $f$ must be evaluated before re-entry to the function.
On final exit: x and y define a smaller interval containing the zero, such that $f\left({\mathbf{x}}\right)×f\left({\mathbf{y}}\right)\le 0.0$, and $\left|{\mathbf{x}}-{\mathbf{y}}\right|$ satisfies the accuracy specified by tolx and ir, unless an error has occurred. If NE_PROBABLE_POLE, x and y generally contain very good approximations to a pole; if NW_TOO_MUCH_ACC_REQUESTED, x and y generally contain very good approximations to the zero (see Section 6). If a point x is found such that $f\left({\mathbf{x}}\right)=0.0$, then on final exit ${\mathbf{x}}={\mathbf{y}}$ (in this case there is no guarantee that x is a simple zero). In all cases, the value returned in x is the better approximation to the zero.
3:     fxdoubleInput
On initial entry: if ${\mathbf{ind}}=1$, fx need not be set.
If ${\mathbf{ind}}=-1$, fx must contain $f\left({\mathbf{x}}\right)$ for the initial value of x.
On intermediate re-entry: must contain $f\left({\mathbf{x}}\right)$ for the current value of x.
4:     tolxdoubleInput
On initial entry: the accuracy to which the zero is required. The type of error test is specified by ir.
Constraint: ${\mathbf{tolx}}>0.0$.
5:     irNag_ErrorControlInput
On initial entry: indicates the type of error test.
${\mathbf{ir}}=\mathrm{Nag_Mixed}$
The test is: $\left|{\mathbf{x}}-{\mathbf{y}}\right|\le 2.0×{\mathbf{tolx}}×\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1.0,\left|{\mathbf{x}}\right|\right)$.
${\mathbf{ir}}=\mathrm{Nag_Absolute}$
The test is: $\left|{\mathbf{x}}-{\mathbf{y}}\right|\le 2.0×{\mathbf{tolx}}$.
${\mathbf{ir}}=\mathrm{Nag_Relative}$
The test is: $\left|{\mathbf{x}}-{\mathbf{y}}\right|\le 2.0×{\mathbf{tolx}}×\left|{\mathbf{x}}\right|$.
Suggested value: ${\mathbf{ir}}=\mathrm{Nag_Mixed}$.
Constraint: ${\mathbf{ir}}=\mathrm{Nag_Mixed}$, $\mathrm{Nag_Absolute}$ or $\mathrm{Nag_Relative}$.
6:     c[$17$]doubleInput/Output
On initial entry: if ${\mathbf{ind}}=1$, no elements of c need be set.
If ${\mathbf{ind}}=-1$, ${\mathbf{c}}\left[0\right]$ must contain $f\left({\mathbf{y}}\right)$, other elements of c need not be set.
On final exit: is undefined.
7:     indInteger *Input/Output
On initial entry: must be set to $1$ or $-1$.
${\mathbf{ind}}=1$
fx and ${\mathbf{c}}\left[0\right]$ need not be set.
${\mathbf{ind}}=-1$
fx and ${\mathbf{c}}\left[0\right]$ must contain $f\left({\mathbf{x}}\right)$ and $f\left({\mathbf{y}}\right)$ respectively.
On intermediate exit: contains $2$, $3$ or $4$. The calling program must evaluate $f$ at x, storing the result in fx, and re-enter nag_zero_cont_func_brent_rcomm (c05azc) with all other arguments unchanged.
On final exit: contains $0$.
Constraint: on entry ${\mathbf{ind}}=-1$, $1$, $2$, $3$ or $4$.
8:     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_INT
On entry, ${\mathbf{ind}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{ind}}=-1$, $1$, $2$, $3$ or $4$.
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_NOT_SIGN_CHANGE
On entry, $f\left({\mathbf{x}}\right)$ and $f\left({\mathbf{y}}\right)$ have the same sign with neither equalling $0.0$: $f\left({\mathbf{x}}\right)=〈\mathit{\text{value}}〉$ and $f\left({\mathbf{y}}\right)=〈\mathit{\text{value}}〉$.
NE_PROBABLE_POLE
The final interval may contain a pole rather than a zero. Note that this error exit is not completely reliable: it may be taken in extreme cases when $\left[{\mathbf{x}},{\mathbf{y}}\right]$ contains a zero, or it may not be taken when $\left[{\mathbf{x}},{\mathbf{y}}\right]$ contains a pole. Both these cases occur most frequently when tolx is large.
NE_REAL
On entry, ${\mathbf{tolx}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{tolx}}>0.0$.
NW_TOO_MUCH_ACC_REQUESTED
The tolerance tolx has been set too small for the problem being solved. However, the values x and y returned may well be good approximations to the zero. ${\mathbf{tolx}}=〈\mathit{\text{value}}〉$.

## 7  Accuracy

The accuracy of the final value x as an approximation of the zero is determined by tolx and ir (see Section 5). A relative accuracy criterion (${\mathbf{ir}}=2$) should not be used when the initial values x and y are of different orders of magnitude. In this case a change of origin of the independent variable may be appropriate. For example, if the initial interval $\left[{\mathbf{x}},{\mathbf{y}}\right]$ is transformed linearly to the interval $\left[1,2\right]$, then the zero can be determined to a precise number of figures using an absolute (${\mathbf{ir}}=1$) or relative (${\mathbf{ir}}=2$) error test and the effect of the transformation back to the original interval can also be determined. Except for the accuracy check, such a transformation has no effect on the calculation of the zero.

For most problems, the time taken on each call to nag_zero_cont_func_brent_rcomm (c05azc) will be negligible compared with the time spent evaluating $f\left(x\right)$ between calls to nag_zero_cont_func_brent_rcomm (c05azc).
If the calculation terminates because $f\left({\mathbf{x}}\right)=0.0$, then on return y is set to x. (In fact, ${\mathbf{y}}={\mathbf{x}}$ on return only in this case and, possibly, when NW_TOO_MUCH_ACC_REQUESTED.) There is no guarantee that the value returned in x corresponds to a simple root 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.

## 9  Example

This example calculates a zero of ${e}^{-x}-x$ with an initial interval $\left[0,1\right]$, ${\mathbf{tolx}}=\text{1.0e−5}$ and a mixed error test.

### 9.1  Program Text

Program Text (c05azce.c)

None.

### 9.3  Program Results

Program Results (c05azce.r)