Page 258 - Compact Numerical Methods For Computers

Conjugate gradients method in linear algebra 245
T T T T
v= (t At) (x Bx) - (x Ax) (t Bt) (19.39)
T
T
T
T
w =(x At) (x Bx)-(x Ax) (x Bt). (19.40)
Note that by symmetry
T
T
x At=t Ax (19.41)
and
T
T
x Bt=t Bx. (19.42)
Therefore, only six inner products are needed in the evaluation of u, v and w.
These are
T T T
(x Ax) (x At) and (t At)
and
T T T
(x Bx) (x Bt) and (t Bt).
The quadratic equation (19.37) has two roots, of which only one will correspond to
a minimum. Since
2 2
y (k)=0·5D ( dR/dk) = uk + v k + w (19.43)
we get

(19.44)

At either of the roots of (19.37), this reduces to
2
2
2
0·5D ( d R/ dk )=2uk+v (19.45)
2 2
so that a minimum has been found if d R/dk is positive, or
2uk+v > 0 . (19.46)
Substitution of both roots from the quadratic equation formula shows that the
desired root is
2 ½
k = [ -v + (v - 4u w) ] / ( 2u) . (19.47)
If v is negative, (19.47) can be used to evaluate the root. However, to avoid digit
cancellation when v is positive,
2
k = - 2w / [v + (v - 4u w) ½ ] (19.48)
should be used. The linear search subproblem has therefore been resolved in a
straightforward manner in this particular case.
The second aspect of particularising the conjugate gradients algorithm to the
minimisation of the Rayleigh quotient is the generation of the next conjugate
direction. Note that the gradient of the Rayleigh quotient at x is given by
T
g= 2 (Ax- RBx) / (x Bx) (19.49)
and the local Hessian by
T T T
H= 2 (A-RB-Bxg - gx B) / (x Bx). (19.50)