= Conjugate-gradient residual orthogonality
{c}
For a real <symmetric positive-definite matrix> in exact arithmetic, iteration $m$ of the <conjugate gradient method> satisfies
$$
x_m-x_0\in\mathcal K_m(A,r_0),
\qquad
r_m\perp\mathcal K_m(A,r_0),
$$
and $r_m$ itself lies in $\mathcal K_{m+1}(A,r_0)$. These Galerkin conditions imply finite termination once the Krylov subspace becomes invariant under $A$.
The residual orthogonality is the first-order optimality condition for minimizing the quadratic objective on $x_0+\mathcal K_m(A,r_0)$. Floating-point roundoff can destroy exact residual orthogonality, so the identity is a structural exact-arithmetic result.
Back to article page