Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 2 / 40E / b

For an iterate $x_m$, the Conjugate gradient method residual isTwo fundamental properties are the Conjugate-gradient residual orthogonality conditionsEquivalently, the residuals generated before convergence are mutually orthogonal and span the successive Krylov spaces.

Since $A$ has only $s$ distinct eigenvalues, its minimal polynomial has degree at most $s$. ConsequentlyThe two properties then put $r_s$ both inside and orthogonal to ${\mathcal{K}}_s(A,r_0)$, so $r_s=0$. Hence $A{x}_s=b$, and