6.7 The Conjugate Gradient Algorithm

The conjugate gradient (CG) algorithm is one of the best known iterative techniques for solving sparse symmetric positive definite (SPD) linear systems. Described in one sentence, the method is a realization of an orthogonal projection technique onto the Krylov subspace ( r ₀, A), where r ₀ is the initial residual. It is therefore mathematically equivalent to FOM. However, because A is symmetric, some simplifications resulting from the three-term Lanczos recurrence will lead to more elegant algorithms.

6.7.1 Derivation and Theory

We first derive the analogue of FOM, or Arnoldi's method, for the case when A is symmetric. Given an initial guess x ₀ to the linear system Ax = b and the Lanczos vectors ? _i, i = 1, , m, together with the tridiagonal matrix T _m, the approximate solution obtained from an orthogonal projection method onto is given by

ALGORITHM 6.16: Lanczos Method for Linear Systems

1. Compute r ₀ = b ? Ax ₀, ? := ? r ₀ ? ₂, and ? ₁ := r ₀/ ?

2. For j = 1, 2, , m, Do

3. w _j = A ? _j ? ? _j ? _j-1 ( If j = 1 set ? ₁ ? ₀ ? 0)

4. ? _j = ( w _j, ? _j)

5. w _j := w