Page 248 - Compact Numerical Methods For Computers

Conjugate gradients method in linear algebra 235
In some tests run by S G Nash and myself, the inexact line searches led to very
slow convergence in a number of cases, even though early progress may have
been rapid (Nash and Nash 1977).

19.2. SOLUTION OF LINEAR EQUATIONS AND
LEAST-SQUARES PROBLEMS BY CONJUGATE GRADIENTS
The conjugate gradients algorithm 22 can be modified to solve systems of linear
equations and linear least-squares problems. Indeed, the conjugate gradients
methods have been derived by considering their application to the quadratic form
T
S(b)=½b Hb-c b+(anyscalar) (15.11)
T
where H is symmetric and positive definite. The minimum at b' has the zero
gradient
g =Hb' - c =0 (15.17)

so that b' solves the linear equations
Hb' = c. (19.1)
The linear least-squares problem
(19.2)
can be solved by noting that A A is non-negative definite. For the present
T
purpose we shall assume that it is positive definite. Hestenes (1975) shows that it
is only necessary for H to be non-negative definite to produce a least-squares
solution of (19.1). Thus identification of
H=A A (19.34
T
T
c=A f (19.3b)
permits least-squares problems to be solved via the normal equations.
The particular changes which can be made to the general-purpose minimising
algorithm of §§16.1 and 16.2 to suit these linear systems of equations better are
that (a) the linear search and (b) the gradient calculation can be performed
explicitly and simply. The latter is accomplished as follows. First, if the initial point
is taken to be ( 0 )
b =0
(19.4)
then the initial gradient. from (15.17), is
g, = -c. (19.5)

If the linear search along the search direction t yields a step-length factor k , then
j
j
from (15.18)
g =g +k Ht . (19.6)
j +l j j j
This with (19.5) defines a recurrence scheme which avoids the necessity of
multiplication of b by H to compute the gradient, though Ht j must be formed.
However, this is needed in any case in the linear search to which attention will
now be directed.