The Conjugate Gradient Method - Finite Elements: Theory, Fast Solvers, and Applications in Elasticity Theory - page 203

The CG Algorithm

In the conjugate gradient method, the directions d 0 ,d 1 ,...,d n − 1 are not selected
in advance, but are computed from the current gradients g k by addition of a cor-
rection factor. From an algorithmic point of view, this means that we do not need a
complicated orthogonalization process, but instead can use a simple three-term re-
currence formula. 9 We show later that this approach makes sense from an analytic
point of view.

3.4 The Conjugate Gradient Method.
Let x 0 ∈ R

n , and set d 0 =− g 0 = b − Ax 0 .

For k = 0 , 1 , 2 ,... , compute

g k g k
d k Ad k ,
x k + 1 = x k + α k d k ,
g k + 1 = g k + α k Ad k ,

α k =

( 3 . 4 )

g k + 1 g k + 1
g k g k

β k = ,

d k + 1 =− g k + 1 + β k d k ,

while g k = 0.

We note that in the derivation of the above, we initially get

g k d k g k + 1 Ad k

d k Ad k

α k =−

d k Ad k , k =

. ( 3 . 5 )

For quadratic problems, the expressions in (3.4) are equivalent, but are more stable
from a numerical point of view, and require less memory.

3.5 Properties of the CG Method. While g k − 1 = 0 , we have the following:

(1) d k − 1 = 0 .

(2)

span[ g 0 ,Ag 0 ,...,A k − 1 g 0 ]

V k : =

= span[ g 0 ,g 1 ,...,g k − 1 ] = span[ d 0 ,d 1 ,...,d k − 1 ] .

(3) The vectors d 0 ,d 1 ,...,d k − 1 are pairwise conjugate.
(4)

f(x k ) = min

z ∈ V k

f(x 0 + z). ( 3 . 6 )

9 Three-term recurrence relations are well known for orthogonal polynomials. The con-
nection is explored in Problem 3.9.