5.1 The Linear Conjugate Gradient Method

The conjugate gradient method is an iterative method for solving a lienar system of equations

\[Ax = b\]

where \(A\) is an \(n \times n\) symmetric positive definite matrix. This problem can be stated equivalently as the following minimization problem

\[\min \phi(x) \stackrel{\text{def}}{=} \frac{1}{2} x^\top Ax - b^\top x\]

For further reference, we note that the gradient of \(\phi\) equals the residual of the linear system

\[\nabla \phi(x) = Ax - b \stackrel{\text{def}}{=} r(x)\]

Conjugate Direction Methods

One of the remarkable properties of the conjugate gradient method is its ability to generate a set of vectors with a property knwon as conjugacy. A set of nonzero vectors \(\{p_0, \dots, p_l\}\) is said to be conjugate with respect to the symmetric positive definite \(A\) if

\[p_k^\top A p_j = 0, \;\;\; \text{for all } i \neq j\]

It is easy to show that such set of vectors is linearly independent.

The importance of conjugacy lies in the fact that we can minimize \(\phi(\cdot)\) in \(n\) steps by successively minimizing it along the individual directions in a conjugate set. We consider the following conjugate direction method. Given a starting point \(x_0 \in \mathbb{R}^n\) and a set of conjugate directions \(\{p_0, \dots, p_{n-1}\}\), we generate the sequence \(\{x_k\}\) by setting

\[x_{k+1} = x_k + \alpha_k p_k\]

where \(\alpha_k\) is the one-dimensional minimizer of the quadratic function \(\phi(k)\) given by

\[\alpha_k = - \frac{r_k^\top p_k}{p_k^\top A p_k}\]

Theorem 5.1. For any \(x_0 \in \mathbb{R}^n\) the sequence \(\{x_k\}\) generated by the conjugate direction algorithm converges to the solution \(x^*\) of the linear system in at most \(n\) steps.