Conjugate gradient method

Remarks

Clause 1 implies $x_k - x^* = q(A)(x_0 - x^*)$ for the polynomial $q$ of degree at most $k$ with $q(0) = 1$ that minimizes the $A$-norm. So $\norm{x_k - x^*}_A \le \max_\lambda \abs{q(\lambda)} \norm{x_0 - x^*}_A$ for every such $q$, with $\lambda$ over the eigenvalues of $A$. Choosing the scaled Chebyshev polynomial of Chebyshev iteration gives clause 4. Choosing $q$ that vanishes at all eigenvalues shows more: if $A$ has only $m$ distinct eigenvalues, the method stops after at most $m$ steps. Example: for $A$ with rows $(2, 1)$ and $(1, 2)$ and $b = (3, 3)$, start at $x_0 = 0$. Then $r_0 = (3, 3)$ is an eigenvector of $A$ for the eigenvalue $3$, so $\alpha_0 = 1/3$ and $x_1 = (1, 1) = x^*$ after one step. Without symmetry or positive definiteness the coefficients can break down, and the minimization property is lost.

Going deeper

For a student

Conjugate gradients is the standard iterative method for large sparse symmetric positive definite systems, such as those from discretized elliptic equations. In floating point the finite termination of clause 3 is lost, and the method is used as an iterative method with the rate of clause 4. The rate depends on $\sqrt{\kappa}$, where $\kappa$ is the condition number, so one usually applies it to a preconditioned system. With a symmetric positive definite preconditioner $P$, such as an incomplete Cholesky factorization, the same bounds hold with $P^{-1} A$ in place of $A$. The method is due to Hestenes and Stiefel.