nag_zero_cont_func_brent_rcomm (c05azc) (PDF version)
c05 Chapter Contents
c05 Chapter Introduction
NAG C Library Manual

NAG Library Function Document

nag_zero_cont_func_brent_rcomm (c05azc)

+ Contents

    1  Purpose
    7  Accuracy

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 <nag.h>
#include <nagc05.h>
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 a,b  containing a simple zero of the function fx  (the choice of x and y must be such that fx × fy 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 x,y  contains the zero and x-y  is less than some tolerance specified by tolx and ir (see Section 5). In fact, since the intermediate intervals x,y  are determined only so that fx × fy 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 log2 b-a / δ 2  function evaluations, where δ 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 fx . On each return you should set fx = fx  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 a,b  containing the zero, such that fx × fy0.0 . It is not necessary that x<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 fx×fy0.0 , and x-y  satisfies the accuracy specified by tolx and ir, unless an error has occurred. If fail.code= NE_PROBABLE_POLE, x and y generally contain very good approximations to a pole; if fail.code= 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 fx=0.0 , then on final exit x=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 ind=1 , fx need not be set.
If ind=-1 , fx must contain fx  for the initial value of x.
On intermediate re-entry: must contain fx  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: tolx>0.0 .
5:     irNag_ErrorControlInput
On initial entry: indicates the type of error test.
ir=Nag_Mixed
The test is: x-y2.0×tolx×max1.0,x .
ir=Nag_Absolute
The test is: x-y2.0×tolx .
ir=Nag_Relative
The test is: x-y2.0×tolx×x .
Suggested value: ir=Nag_Mixed.
Constraint: ir=Nag_Mixed, Nag_Absolute or Nag_Relative.
6:     c[17]doubleInput/Output
On initial entry: if ind=1 , no elements of c need be set.
If ind=-1 , c[0]  must contain fy , 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 .
ind=1
fx and c[0]  need not be set.
ind=-1
fx and c[0]  must contain fx  and fy  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 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

NE_BAD_PARAM
On entry, argument value had an illegal value.
NE_INT
On entry, ind=value.
Constraint: 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, fx and fy have the same sign with neither equalling 0.0: fx=value and fy=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 x,y  contains a zero, or it may not be taken when x,y  contains a pole. Both these cases occur most frequently when tolx is large.
NE_REAL
On entry, tolx=value.
Constraint: 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. tolx=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 ( 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 x,y  is transformed linearly to the interval 1,2 , then the zero can be determined to a precise number of figures using an absolute ( ir=1 ) or relative ( 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.

8  Further Comments

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 fx  between calls to nag_zero_cont_func_brent_rcomm (c05azc).
If the calculation terminates because fx=0.0 , then on return y is set to x. (In fact, y=x  on return only in this case and, possibly, when fail.code= 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 fx=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 0,1 , tolx=1.0e−5  and a mixed error test.

9.1  Program Text

Program Text (c05azce.c)

9.2  Program Data

None.

9.3  Program Results

Program Results (c05azce.r)


nag_zero_cont_func_brent_rcomm (c05azc) (PDF version)
c05 Chapter Contents
c05 Chapter Introduction
NAG C Library Manual

© The Numerical Algorithms Group Ltd, Oxford, UK. 2012