NAG Library Function Document
nag_interval_zero_cont_func (c05avc)
1
Purpose
nag_interval_zero_cont_func (c05avc) attempts to locate an interval containing a simple zero of a continuous function using a binary search. It uses reverse communication for evaluating the function.
2
Specification
#include <nag.h> 
#include <nagc05.h> 
void 
nag_interval_zero_cont_func (double *x,
double fx,
double *h,
double boundl,
double boundu,
double *y,
double c[],
Integer *ind,
NagError *fail) 

3
Description
You must supply an initial point
x and a step
h.
nag_interval_zero_cont_func (c05avc) attempts to locate a short interval
$\left[{\mathbf{x}},{\mathbf{y}}\right]\subset \left[{\mathbf{boundl}},{\mathbf{boundu}}\right]$ containing a simple zero of
$f\left(x\right)$.
(On exit we may have
${\mathbf{x}}>{\mathbf{y}}$;
x is determined as the first point encountered in a binary search where the sign of
$f\left(x\right)$ differs from the sign of
$f\left(x\right)$ at the initial input point
x.) The function attempts to locate a zero of
$f\left(x\right)$ using
h,
$0.1\times {\mathbf{h}}$,
$0.01\times {\mathbf{h}}$ and
$0.001\times {\mathbf{h}}$ in turn as its basic step before quitting with an error exit if unsuccessful.
nag_interval_zero_cont_func (c05avc) 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_interval_zero_cont_func (c05avc) again.
4
References
None.
5
Arguments
Note: this function uses
reverse communication. Its use involves an initial entry, intermediate exits and reentries, and a final exit, as indicated by the argument
ind. Between intermediate exits and reentries,
all arguments other than fx must remain unchanged.
 1:
$\mathbf{x}$ – double *Input/Output

On initial entry: the best available approximation to the zero.
Constraint:
x must lie in the closed interval
$\left[{\mathbf{boundl}},{\mathbf{boundu}}\right]$ (see below).
On intermediate exit:
contains the point at which $f$ must be evaluated before reentry to the function.
On final exit: contains one end of an interval containing the zero, the other end being in
y, unless an error has occurred. If
${\mathbf{fail}}\mathbf{.}\mathbf{code}=$ NE_ZERO_NOT_FOUND,
x and
y are the end points of the largest interval searched. If a zero is located exactly, its value is returned in
x (and in
y).
 2:
$\mathbf{fx}$ – doubleInput

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 reentry: must contain
$f\left({\mathbf{x}}\right)$ for the current value of
x.
 3:
$\mathbf{h}$ – double *Input/Output

On initial entry: a basic step size which is used in the binary search for an interval containing a zero. The basic step sizes ${\mathbf{h}},0.1\times {\mathbf{h}}$, $0.01\times {\mathbf{h}}$ and $0.001\times {\mathbf{h}}$ are used in turn when searching for the zero.
Constraint:
either
${\mathbf{x}}+{\mathbf{h}}$ or
${\mathbf{x}}{\mathbf{h}}$ must lie inside the closed interval
$\left[{\mathbf{boundl}},{\mathbf{boundu}}\right]$.
h must be sufficiently large that
${\mathbf{x}}+{\mathbf{h}}\ne {\mathbf{x}}$ on the computer.
On final exit: is undefined.
 4:
$\mathbf{boundl}$ – doubleInput
 5:
$\mathbf{boundu}$ – doubleInput

On initial entry:
boundl and
boundu must contain respectively lower and upper bounds for the interval of search for the zero.
Constraint:
${\mathbf{boundl}}<{\mathbf{boundu}}$.
 6:
$\mathbf{y}$ – double *Input/Output

On initial entry: need not be set.
On final exit: contains the closest point found to the final value of
x, such that
$f\left({\mathbf{x}}\right)\times f\left({\mathbf{y}}\right)\le 0.0$. If a value
x is found such that
$f\left({\mathbf{x}}\right)=0$,
${\mathbf{y}}={\mathbf{x}}$. On final exit with
${\mathbf{fail}}\mathbf{.}\mathbf{code}=$ NE_ZERO_NOT_FOUND,
x and
y are the end points of the largest interval searched.
 7:
$\mathbf{c}\left[11\right]$ – doubleCommunication Array

On initial entry: need not be set.
On final exit: if
${\mathbf{fail}}\mathbf{.}\mathbf{code}=$ NE_NOERROR or
NE_ZERO_NOT_FOUND,
${\mathbf{c}}\left[0\right]$ contains
$f\left({\mathbf{y}}\right)$.
 8:
$\mathbf{ind}$ – Integer *Input/Output

On initial entry: must be set to
$1$ or
$1$.
 ${\mathbf{ind}}=1$
 fx need not be set.
 ${\mathbf{ind}}=1$
 fx must contain $f\left({\mathbf{x}}\right)$.
On intermediate exit:
contains
$2$ or
$3$. The calling program must evaluate
$f$ at
x, storing the result in
fx, and reenter
nag_interval_zero_cont_func (c05avc) with all other arguments unchanged.
On final exit: contains $0$.
Constraint:
on entry ${\mathbf{ind}}=1$, $1$, $2$ or $3$.
Note: any values you return to nag_interval_zero_cont_func (c05avc) as part of the reverse communication procedure should not include floatingpoint NaN (Not a Number) or infinity values, since these are not handled by nag_interval_zero_cont_func (c05avc). If your code inadvertently does return any NaNs or infinities, nag_interval_zero_cont_func (c05avc) is likely to produce unexpected results.
 9:
$\mathbf{fail}$ – NagError *Input/Output

The NAG error argument (see
Section 3.7 in How to Use the NAG Library and its Documentation).
6
Error Indicators and Warnings
 NE_ALLOC_FAIL

Dynamic memory allocation failed.
See
Section 2.3.1.2 in How to Use the NAG Library and its Documentation for further information.
 NE_BAD_PARAM

On entry, argument $\u2329\mathit{\text{value}}\u232a$ had an illegal value.
 NE_INT

On entry, ${\mathbf{ind}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{ind}}=1$, $1$, $2$ or $3$.
 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.
See
Section 2.7.6 in How to Use the NAG Library and its Documentation for further information.
 NE_NO_LICENCE

Your licence key may have expired or may not have been installed correctly.
See
Section 2.7.5 in How to Use the NAG Library and its Documentation for further information.
 NE_REAL_2

On entry, ${\mathbf{boundl}}=\u2329\mathit{\text{value}}\u232a$ and ${\mathbf{boundu}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{boundl}}<{\mathbf{boundu}}$.
On entry,
h is too small for use as a perturbation of
x:
${\mathbf{x}}=\u2329\mathit{\text{value}}\u232a$ and
${\mathbf{h}}=\u2329\mathit{\text{value}}\u232a$.
 NE_REAL_3

On entry, ${\mathbf{x}}=\u2329\mathit{\text{value}}\u232a$, ${\mathbf{boundl}}=\u2329\mathit{\text{value}}\u232a$ and ${\mathbf{boundu}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{boundl}}\le {\mathbf{x}}\le {\mathbf{boundu}}$.
 NE_REAL_4

On entry, ${\mathbf{x}}+{\mathbf{h}}$ and ${\mathbf{x}}{\mathbf{h}}$ both lie outside the interval $\left[{\mathbf{boundl}},{\mathbf{boundu}}\right]$: ${\mathbf{x}}=\u2329\mathit{\text{value}}\u232a$, ${\mathbf{h}}=\u2329\mathit{\text{value}}\u232a$, ${\mathbf{boundl}}=\u2329\mathit{\text{value}}\u232a$ and ${\mathbf{boundu}}=\u2329\mathit{\text{value}}\u232a$.
 NE_ZERO_NOT_FOUND

An interval containing the zero could not be found.
7
Accuracy
nag_interval_zero_cont_func (c05avc) is not intended to be used to obtain accurate approximations to the zero of
$f\left(x\right)$ but rather to locate an interval containing a zero. This interval can then be used as input to an accurate rootfinder such as
nag_zero_cont_func_brent (c05ayc) or
nag_zero_cont_func_brent_rcomm (c05azc). The size of the interval determined depends somewhat unpredictably on the choice of
x and
h. The closer
x is to the root and the
smaller the initial value of
h, then, in general, the smaller (more accurate) the interval determined; however, the accuracy of this statement depends to some extent on the behaviour of
$f\left(x\right)$ near
$x={\mathbf{x}}$ and on the size of
h.
8
Parallelism and Performance
nag_interval_zero_cont_func (c05avc) is not threaded in any implementation.
For most problems, the time taken on each call to
nag_interval_zero_cont_func (c05avc) will be negligible compared with the time spent evaluating
$f\left(x\right)$ between calls to
nag_interval_zero_cont_func (c05avc). However, the initial value of
x and
h will clearly affect the timing. The closer
x is to the root, and the
larger the initial value of
h then the less time taken. (However taking a large
h can affect the accuracy and reliability of the function, see below.)
You are expected to choose
boundl and
boundu as physically (or mathematically) realistic limits on the interval of search. For example, it may be known, from physical arguments, that no zero of
$f\left(x\right)$ of interest will lie outside
$\left[{\mathbf{boundl}},{\mathbf{boundu}}\right]$. Alternatively,
$f\left(x\right)$ may be more expensive to evaluate for some values of
x than for others and such expensive evaluations can sometimes be avoided by careful choice of
boundl and
boundu.
The choice of
boundl and
boundu affects the search only in that these values provide physical limitations on the search values and that the search is terminated if it seems, from the available information about
$f\left(x\right)$, that the zero lies outside
$\left[{\mathbf{boundl}},{\mathbf{boundu}}\right]$. In this case (
${\mathbf{fail}}\mathbf{.}\mathbf{code}=$ NE_ZERO_NOT_FOUND on exit), only one of
$f\left({\mathbf{boundl}}\right)$ and
$f\left({\mathbf{boundu}}\right)$ may have been evaluated and a zero close to the other end of the interval could be missed. The actual interval searched is returned in the arguments
x and
y and you can call
nag_interval_zero_cont_func (c05avc) again to search the remainder of the original interval.
Though
nag_interval_zero_cont_func (c05avc) is intended primarily for determining an interval containing a zero of
$f\left(x\right)$, it may be used to shorten a known interval. This could be useful if, for example, a large interval containing the zero is known and it is also known that the root lies close to one end of the interval; by setting
x to this end of the interval and
h small, a short interval will usually be determined. However, it is worth noting that once any interval containing a zero has been determined, a call to
nag_zero_cont_func_brent_rcomm (c05azc) will usually be the most efficient way to calculate an interval of specified length containing the zero. To assist in this determination, the information in
fx and in
x,
y and
${\mathbf{c}}\left[0\right]$ on successful exit from
nag_interval_zero_cont_func (c05avc) is in the correct form for a call to function
nag_zero_cont_func_brent_rcomm (c05azc) with
${\mathbf{ind}}=1$.
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.) In this case, there is no guarantee that the value 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 finds a subinterval of $\left[0.0,4.0\right]$ containing a simple zero of ${x}^{2}3x+2$. The zero nearest to $3.0$ is required and so we set ${\mathbf{x}}=3.0$ initially.
10.1
Program Text
Program Text (c05avce.c)
10.2
Program Data
None.
10.3
Program Results
Program Results (c05avce.r)