For a real symmetric positive-definite matrix , the conjugate gradient method reaches the exact solution in exact arithmetic after at most the number of distinct eigenvalues active in the initial error, hence after at most steps in dimension .
If those eigenvalues are , the polynomial satisfies and . This is an admissible error polynomial at step . Krylov-space minimization in the energy norm does at least as well, so its error must also be zero. Repeated eigenvalues and absent spectral components can make much smaller than .
The proof assumes exact arithmetic. Roundoff error can spoil exact conjugacy and create residual components absent in the ideal recurrence, so a numerical implementation needs an accuracy-based stopping criterion.

Articles by others on the same topic (0)

There are currently no matching articles.