Page 170 - Compact Numerical Methods For Computers

One-dimensional problems 159
A cubic inverse interpolation algorithm requiring both the function and deriva-
tive to be computed, but which employs a convergence test based solely on the
change in the parameter, used considerably more effort to locate a minimum from
t = 10.

Function and derivative
Step length Minimum at evaluations

1 17·2083 38+38
5 17·2082 23+23
10 17·2082 36+36
20 17·2081 38+38

Most of the work in this algorithm is done near the minimum, since the region of
the minimum is located very quickly.
If we can be confident of the accuracy of the derivative calculation, then a
root-finder is a very effective way to locate a minimum of this function. However,
we should check that the point found is not a maximum or saddle. Algorithm 18
gives

*
*RUN200
ROOTFINDER
U= ? 10 V= ? 30
BISECTION EVERY ? 5
TOLERANCE ? 0
F( 10 )=-16.4537 F( 30 )= 32.0994
FP ITN 1 U= 10 V= 30 F( 16.7776 )=-1.01735
FP ITN 2 U= 16.7776 V= 30 F( 17.1838 )=-0.582123
FP ITN 3 U= 17.1838 V= 30 F( 17.207 )=-.00361633
FP ITN 4 U= 17.2307 V= 30 F( 117.2084 )=-2.28882E-04
FP ITN 5 U= 17.2084 V= 30 F( 17.2085 )=-3.05176E-05
BI ITN 6 U= 17.2085 V= 30 F( 23.6042 )= 15.5647
FP CONVERGED
ROOT: F( 17.2085 )=-3.05176E-05
STOP AT 0340
*

Unless otherwise stated all of the above results were obtained using a Data
General ECLIPSE operating in six hexadecimal digit arithmetic.
It may appear that this treatment is biased against using derivative information.
For instance, the cubic inverse interpolation uses a convergence test which does
not take it into account at all. The reason for this is that in a single-precision
environment (with a short word length) it is difficult to evaluate the projection of
a gradient along a line since inner-product calculations cannot be made in
extended precision. However, if the linear search is part of a larger algorithm to
minimise a function for several parameters, derivative information must usually
be computed in this way. The function values may still be well determined, but