Page 162 - Compact Numerical Methods For Computers

One-dimensional problems 151
A grid or equal-interval search is not a particularly efficient method for finding
a minimum. However, it is very simple to program and provides a set of points for
plotting the function along the line. Even a crude plot, such as that produced
using a line printer or teletypewriter, can be used to gain a visual appreciation of
the function studied. It is in this fashion that a grid search can be used most
effectively, not to find the minimum of a function but to carry out a preliminary
investigation of it. Furthermore, if the grid search is used in this way, there is no
necessity that the function be unimodal.
Consider now the case where instead of the interval [u, v], only a starting
position u and a step h are given. If S(u + h) < S(u), the step will be termed a
success, otherwise it will be called a failure. This is the basis of Rosenbrock’s
(1960) algorithm for minimising a function of several variables. Here, however,
the goal will be to find points at which the function value is reduced. A procedure
which does this can be repeated until a minimum is found.
Suppose S(u + h) < S(u), then an obvious tactic is to replace u by (u + h) and
try again, perhaps increasing the step somewhat. If, however, S(u + h) > S(u),
then either the step is too large or it is in the wrong direction. In this case a
possibility is to reduce the size of h and change its sign. (If only the size is
incorrect, two operations of this sort will find a lower function value.)
The above paragraph defines the success-failure algorithm except for the
factors to be used to increase or decrease the size of h. Notice that so far neither
the grid search nor the success-failure algorithm take into account the function
values apart from the fact that one function value is larger than another. How
much larger it is, which indicates how rapidly the function is changing with respect
to h, is not considered. Using the function values can, however, lead to more
efficient minimisation procedures. The idea is to use the function values and their
associated points (as well as the derivatives of the function at these points if
available) to generate some simple function, call it I(b), which interpolates the
function S(b) between the points at which S has been computed. The most
popular choices for I(b) are polynomials, in particular of degree 2 (parabolic
approximation) or degree 3 (cubic approximation). Consider the case where S(b)
is known at three points b , b 1 and b . Then using a parabola to interpolate the
2
0
function requires
for j=0,1,2 (13.5)
which provides three linear equations for the three unknowns A, B and C. Once
these are found, it is simple to set the derivative of the interpolant to zero
dI( b) / db= 2Cb + B = 0 (13.6)
to find the value of b which minimises the interpolating polynomial I(b). This
presumes that the parabola has a minimum at the stationary point, and upon this
presumption hang many ifs, ands and buts, and no doubt miles of computer listing
of useless results. Indeed, the largest part of many procedures for minimising a
function along a line by minimising an interpolant I(b) is concerned with ensuring
that the interpolant has the proper shape to guarantee a minimum. Furthermore
I(b) cannot be used to extrapolate very far from the region in which it has beer