Page 160 - Compact Numerical Methods For Computers

One-dimensional problems 149
Since local maxima also zero the derivative of the function S(b), such solutions
will have to be checked either by ensuring the second derivative S”(b) is positive
or equivalently by examining the values of the function at points near the
supposed minimum.
When the derivative of S is not available or is expensive to compute, a method
for minimisation along a line is needed which depends only on function values.
Obviously, any method which evaluates the function at a finite number of points is
not guaranteed to detect deep, narrow wells in the function. Therefore, some
assumption must be made about the function on the interval [u,v]. Here it will be
assumed that the function S(b) is unimodal in [u, v], that is, that there is only one
stationary value (either a maximum or a minimum) in the interval. In the case
where the stationary value is a maximum, the minimum of the function will be
either at u or at v.
Given that S(b) is unimodal in [u, v], a grid or equal-interval search could be
used to decrease the size of the interval. For instance, the function values could be
computed for each of the points
b = u+jh j = 0, 1, 2, . . . , n (13.3)
j
where
h = (v - u)/n. (13.4)
If the smallest of these values is S(b ), then the minimum lies in the interval
k
[b ,b k+1 ]. Equation (13.3) can be used to compute the endpoints of this
k-l
interval. If S(b ) or S(b ) is the smallest value, then the interval is [u, b ] or
0 n 1
[b n- 1 , u], though for simplicity this could be left out of a program. The search can
now be repeated, noting, of course, that the function values at the endpoints of
the interval have already been computed.

Algorithm 16. Grid search along a line
procedure gridsrch( var 1bound, ubound : real; {the lower and
upper bounds to the interval to be tested}
nint : integer; {the number of grid intervals}
var finin: real; {the lowest function value found}
var minarg: integer; {the grid point in the set
0,1,...,nint at which the minimum function value
was found}
var changarg: integer {the grid point in the set
1,2,...,nint which is nearest the upper bound
ubound such that there has been a sign change
in the function values f(lbound+(changarg-1)*h)
and f(lbound+changarg*h) where h is the step
== (ubound - lbound)/nint} );
{alg16.pas == one-dimensional grid search over function values
This version halts execution if the function is not computable at all
the grid points. Note that it is not equivalent to the version in the
first edition of Compact Numerical Methods.
Copyright 1988 J.C.Nash
}