Page 209 - Compact Numerical Methods For Computers

198 Compact numerical methods for computers

Now if q is chosen to be the negative gradient
i
q = -g i (16.5
i
a n d is substituted from (15.18), then we have

(16.6)
Moreover, if accurate line searches have been performed at each of the (i -1)
previous steps, then the function S (still the quadratic form (15.11)) has been
minimised on a hyperplane spanned by the search directions t , j=1, 2, . . . ,
j
(i-l), and g i is orthogonal to each of these directions. Therefore, we have
z =0 for j<(i-1)
i j (16.7)
(16.8)
Alternatively, using

(16.9)

which is a linear combination of g , j=1, 2, . . . , (i-1), we obtain
j
(16.10)
(16.11)

by virtue of the orthogonality mentioned above.
As in the case of variable metric algorithms, the formulae obtained for
quadratic forms are applied in somewhat cavalier fashion to the minimisation of
general nonlinear functions. The formulae (16.8), (16.10) and (16.11) are now no
longer equivalent. For reference, these will be associated with the names: Beale
(1972) and Sorenson (1969) for (16.8); Polak and Ribiere (1969) for (16.10); and
Fletcher and Reeves (1964) for (16.11). All of these retain the space-saving
two-term recurrence which makes the conjugate gradients algorithms so frugal of
storage.
In summary, the conjugate gradients algorithm proceeds by setting
t = -g(b ) (16.12)
1
1
and
t =z i,i - 1 i - 1 -g (b ) (16.13)
t
j
i
i
with
b +l=b +k t (16.14)
j j
j
j
where k j is determined by a linear search for a ‘minimum’ of S(b +k t ) with
j
j j
respect to k .
j
16.2. A PARTICULAR CONJUGATE GRADIENTS ALGORITHM
A program to use the ideas of the previous section requires that a choice be made
of (a) a recurrence formula to generate the search directions, and (b) a linear
search.