NAG Library Routine Document

c05avf (contfn_interval_rcomm)

1
Purpose

c05avf 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

Fortran Interface
Subroutine c05avf ( x, fx, h, boundl, boundu, y, c, ind, ifail)
Integer, Intent (Inout):: ind, ifail
Real (Kind=nag_wp), Intent (In):: fx, boundl, boundu
Real (Kind=nag_wp), Intent (Inout):: x, h, y, c(11)
C Header Interface
#include <nagmk26.h>
void  c05avf_ (double *x, const double *fx, double *h, const double *boundl, const double *boundu, double *y, double c[], Integer *ind, Integer *ifail)

3
Description

You must supply an initial point x and a step h. c05avf attempts to locate a short interval x,y boundl,boundu  containing a simple zero of fx .
(On exit we may have x>y ; x is determined as the first point encountered in a binary search where the sign of fx  differs from the sign of fx  at the initial input point x.) The routine attempts to locate a zero of fx  using h, 0.1×h , 0.01×h  and 0.001×h  in turn as its basic step before quitting with an error exit if unsuccessful.
c05avf returns to the calling program for each evaluation of fx . On each return you should set fx=fx  and call c05avf again.

4
References

None.

5
Arguments

Note: this routine 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:     x – Real (Kind=nag_wp)Input/Output
On initial entry: the best available approximation to the zero.
Constraint: x must lie in the closed interval boundl,boundu  (see below).
On intermediate exit: contains the point at which f must be evaluated before re-entry to the routine.
On final exit: contains one end of an interval containing the zero, the other end being in y, unless an error has occurred. If ifail=4, 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:     fx – Real (Kind=nag_wp)Input
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.
3:     h – Real (Kind=nag_wp)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 h,0.1×h , 0.01×h  and 0.001×h  are used in turn when searching for the zero.
Constraint: either x+h  or x-h  must lie inside the closed interval boundl,boundu .
h must be sufficiently large that x+hx  on the computer.
On final exit: is undefined.
4:     boundl – Real (Kind=nag_wp)Input
5:     boundu – Real (Kind=nag_wp)Input
On initial entry: boundl and boundu must contain respectively lower and upper bounds for the interval of search for the zero.
Constraint: boundl<boundu .
6:     y – Real (Kind=nag_wp)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 fx × fy0.0 . If a value x is found such that fx=0 , y=x . On final exit with ifail=4, x and y are the end points of the largest interval searched.
7:     c11 – Real (Kind=nag_wp) arrayCommunication Array
On initial entry: need not be set.
On final exit: if ifail=0 or 4, c1  contains fy .
8:     ind – IntegerInput/Output
On initial entry: must be set to 1 or -1 .
ind=1
fx need not be set.
ind=-1
fx must contain fx .
On intermediate exit: contains 2 or 3. The calling program must evaluate f at x, storing the result in fx, and re-enter c05avf with all other arguments unchanged.
On final exit: contains 0.
Constraint: on entry ind=-1, 1, 2 or 3.
Note: any values you return to c05avf as part of the reverse communication procedure should not include floating-point NaN (Not a Number) or infinity values, since these are not handled by c05avf. If your code does inadvertently return any NaNs or infinities, c05avf is likely to produce unexpected results.
9:     ifail – IntegerInput/Output
On initial entry: ifail must be set to 0, -1 or 1. If you are unfamiliar with this argument you should refer to Section 3.4 in How to Use the NAG Library and its Documentation for details.
For environments where it might be inappropriate to halt program execution when an error is detected, the value -1 or 1 is recommended. If the output of error messages is undesirable, then the value 1 is recommended. Otherwise, because for this routine the values of the output arguments may be useful even if ifail0 on exit, the recommended value is -1. When the value -1 or 1 is used it is essential to test the value of ifail on exit.
On final exit: ifail=0 unless the routine detects an error or a warning has been flagged (see Section 6).

6
Error Indicators and Warnings

If on entry 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:
ifail=1
On entry, boundl=value and boundu=value.
Constraint: boundl<boundu.
On entry, x=value, boundl=value and boundu=value.
Constraint: boundlxboundu.
On entry, x=value, h=value, boundl=value and boundu=value.
Constraint: either x+h or x-h must lie inside the closed interval boundl,boundu.
ifail=2
On entry, x=value and h=value.
Constraint: h must be sufficiently large that x+hx on the computer.
ifail=3
On entry, ind=value.
Constraint: ind=-1, 1, 2 or 3.
ifail=4
An interval containing the zero could not be found. Try restarting with modified x and h.
ifail=-99
An unexpected error has been triggered by this routine. Please contact NAG.
See Section 3.9 in How to Use the NAG Library and its Documentation for further information.
ifail=-399
Your licence key may have expired or may not have been installed correctly.
See Section 3.8 in How to Use the NAG Library and its Documentation for further information.
ifail=-999
Dynamic memory allocation failed.
See Section 3.7 in How to Use the NAG Library and its Documentation for further information.

7
Accuracy

c05avf is not intended to be used to obtain accurate approximations to the zero of fx  but rather to locate an interval containing a zero. This interval can then be used as input to an accurate rootfinder such as c05ayf or c05azf. 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 fx  near x=x  and on the size of h.

8
Parallelism and Performance

c05avf is not threaded in any implementation.

9
Further Comments

For most problems, the time taken on each call to c05avf will be negligible compared with the time spent evaluating fx  between calls to c05avf. 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 routine, 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 fx  of interest will lie outside boundl,boundu . Alternatively, fx  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 fx , that the zero lies outside boundl,boundu . In this case (ifail=4 on exit), only one of fboundl  and fboundu  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 c05avf again to search the remainder of the original interval.
Though c05avf is intended primarily for determining an interval containing a zero of fx , 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 c05azf 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 c1  on successful exit from c05avf is in the correct form for a call to routine c05azf with ind=-1 .
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.) 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 fx=0.0 , then x must correspond to a multiple zero of f rather than a simple zero.

10
Example

This example finds a sub-interval of 0.0,4.0  containing a simple zero of x2 - 3x+2 . The zero nearest to 3.0 is required and so we set x=3.0  initially.

10.1
Program Text

Program Text (c05avfe.f90)

10.2
Program Data

None.

10.3
Program Results

Program Results (c05avfe.r)