Derivation of the conjugate gradient method

Remarks

For clause 1, the function $f(x) = \frac12 \norm{x - x^*}_A^2$ restricted to $x_0 + \operatorname{span}\set{p_0, \dots, p_{k-1}}$ separates into one quadratic in each coordinate, by conjugacy. The step $\alpha_k$ minimizes the quadratic in the $k$-th coordinate, and later steps do not change the earlier coordinates. For clause 2, the residual $r_k$ is orthogonal to $\mathcal{K}_k(A, r_0)$ by clause 1. Since $A p_j \in \mathcal{K}_{j+2}(A, r_0)$, the vector $r_k$ is $A$-orthogonal to $p_j$ for $j < k - 1$. So only the last direction enters the Gram–Schmidt step, and this gives the two-term recurrence. Clause 2 with clause 1 is exactly the conjugate gradient method. Example: with $p_i = e_i$ and $A$ diagonal, the directions are conjugate, and the method of clause 1 solves the $i$-th equation at step $i$.

Going deeper

For a student

There is a second derivation from the Lanczos algorithm. The Arnoldi iteration applied to a symmetric $A$ gives an orthonormal basis of $\mathcal{K}_k(A, r_0)$ in which $A$ becomes a tridiagonal matrix $T_k$. The Galerkin condition $r_k \perp \mathcal{K}_k(A, r_0)$ asks to solve a system with $T_k$. Updating an $L D L^T$ factorization of $T_k$ step by step gives the same recurrences. This view explains the link between conjugate gradients and the Lanczos process for eigenvalues.