= Spectral weighting of conjugate gradient error
{title2=$\|p(A)x\|_A^2=\sum_i\alpha_i^2\lambda_i p(\lambda_i)^2$}
For a <symmetric positive-definite matrix>, choose an orthonormal eigenbasis and write the exact solution as $x=\sum_i\alpha_iv_i$. Starting at zero, the <conjugate gradient method> chooses an admissible polynomial $p(0)=1$ of degree at most the iteration count that minimizes the displayed error. The weights depend on both the eigenvalues and the solution coefficients. For two eigenvalues $1,L$, the first polynomial is $1-\eta t$, with $\eta=(\alpha^2+\beta^2L^2)/(\alpha^2+\beta^2L^3)$. Comparable nonzero coefficients and large $L$ give $\eta\approx1/L$, so the high-eigenvalue error is removed first. A sufficiently tiny high-mode coefficient changes this behavior; the spectrum alone does not determine the first step.
Back to article page
