= Solution
For an iterate $x_m$, the <Conjugate gradient method> residual is
$$
\boxed{r_m=b-Ax_m}.
$$
Two fundamental properties are the <Conjugate-gradient residual orthogonality> conditions
$$
r_m\perp\mathcal K_m(A,r_0),
\qquad
r_m\in\mathcal K_{m+1}(A,r_0).
$$
Equivalently, 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$. Consequently
$$
\mathcal K_{s+1}(A,r_0)=\mathcal K_s(A,r_0).
$$
The two properties then put $r_s$ both inside and orthogonal to $\mathcal K_s(A,r_0)$, so $r_s=0$. Hence $Ax_s=b$, and
$$
\boxed{\text{CG terminates after at most }s\text{ iterations}}.
$$
Back to article page
