= Solution
Let $e_j=x-x^{(j)}$. The underlying <Richardson iteration> gives $e_j=(I-A)^je_0$. The polynomials $1,(1-t),\ldots,(1-t)^k$ form a basis for polynomials of degree at most $k$. Thus write
$$
p_k(t)=\sum_{j=0}^kc_j(1-t)^j,\qquad\sum_{j=0}^kc_j=p_k(0)=1.
$$
Define $y^{(k)}=\sum_{j=0}^kc_jx^{(j)}$. Since the coefficients sum to one,
$$
\boxed{x-y^{(k)}=\sum_jc_je_j=p_k(A)e_0.}
$$
The <spectral theorem for real symmetric matrices> supplies an <orthonormal basis> of <eigenvectors>. In that basis $p_k(A)$ has diagonal entries $p_k(\lambda_i)$, so
$$
\boxed{\|x-y^{(k)}\|_2\leq\max_i|p_k(\lambda_i)|\,\|x-x^{(0)}\|_2.}
$$
The algebraic recombination is valid in exact arithmetic even if the original unaccelerated iterates themselves fail to converge.
Back to article page
