Derivation of the conjugate gradient method

In numerical linear algebra, the conjugate gradient method is an iterative method for numerically solving the linear system
where formula_2 is symmetric positive-definite. The conjugate gradient method can be derived from several different perspectives, including specialization of the conjugate direction method for optimization, and variation of the Arnoldi/Lanczos iteration for eigenvalue problems.
The intent of this article is to document the important steps in these derivations.
Derivation from the conjugate direction method.
The conjugate gradient method can be seen as a special case of the conjugate direction method applied to minimization of the quadratic function
The conjugate direction method.
In the conjugate direction method for minimizing
one starts with an initial guess formula_5 and the corresponding residual formula_6, and computes the iterate and residual by the formulae
where formula_8 are a series of mutually conjugate directions, i.e.,
for any formula_10.
The conjugate direction method is imprecise in the sense that no formulae are given for selection of the directions formula_8. Specific choices lead to various methods including the conjugate gradient method and Gaussian elimination.
Derivation from the Arnoldi/Lanczos iteration.
The conjugate gradient method can also be seen as a variant of the Arnoldi/Lanczos iteration applied to solving linear systems.
The general Arnoldi method.
In the Arnoldi iteration, one starts with a vector formula_12 and gradually builds an orthonormal basis formula_13 of the Krylov subspace
by defining formula_15 where
In other words, for formula_17, formula_18 is found by Gram-Schmidt orthogonalizing formula_19 against formula_20 followed by normalization.
Put in matrix form, the iteration is captured by the equation
where
with
When applying the Arnoldi iteration to solving linear systems, one starts with formula_6, the residual corresponding to an initial guess formula_5. After each step of iteration, one computes formula_26 and the new iterate formula_27.
The direct Lanczos method.
For the rest of discussion, we assume that formula_2 is symmetric positive-definite. With symmetry of formula_2, the upper Hessenberg matrix formula_30 becomes symmetric and thus tridiagonal. It then can be more clearly denoted by
This enables a short three-term recurrence for formula_18 in the iteration, and the Arnoldi iteration is reduced to the Lanczos iteration.
Since formula_2 is symmetric positive-definite, so is formula_34. Hence, formula_34 can be LU factorized without partial pivoting into
with convenient recurrences for formula_37 and formula_38:
Rewrite formula_27 as
with
It is now important to observe that
In fact, there are short recurrences for formula_44 and formula_45 as well:
With this formulation, we arrive at a simple recurrence for formula_47:
The relations above straightforwardly lead to the direct Lanczos method, which turns out to be slightly more complex.
The conjugate gradient method from imposing orthogonality and conjugacy.
If we allow formula_44 to scale and compensate for the scaling in the constant factor, we potentially can have simpler recurrences of the form:
As premises for the simplification, we now derive the orthogonality of formula_51 and conjugacy of formula_44, i.e., for formula_10,
The residuals are mutually orthogonal because formula_51 is essentially a multiple of formula_56 since for formula_57, formula_58, for formula_59,
To see the conjugacy of formula_44, it suffices to show that formula_62 is diagonal:
is symmetric and lower triangular simultaneously and thus must be diagonal.
Now we can derive the constant factors formula_64 and formula_65 with respect to the scaled formula_44 by solely imposing the orthogonality of formula_51 and conjugacy of formula_44.
Due to the orthogonality of formula_51, it is necessary that formula_70. As a result,
Similarly, due to the conjugacy of formula_44, it is necessary that formula_73. As a result,
This completes the derivation.