= Solution
Let $x_*=A^{-1}b$ and $e^{(k)}=x^{(k)}-x_*$. The <Richardson iteration> gives
$$
e^{(k+1)}=(I-\tau A)e^{(k)},\qquad e^{(k)}=(I-\tau A)^ke^{(0)}.
$$
By the <spectral theorem>, a real symmetric positive definite <matrix> has an <orthonormal eigenbasis> with positive <eigenvalues> $\lambda_1,\ldots,\lambda_n$. The error in the $i$th <eigenvector> direction is multiplied by $(1-\tau\lambda_i)^k$. Thus convergence for every initial vector occurs exactly when $|1-\tau\lambda_i|<1$ for every $i$, or $0<\tau\lambda_i<2$. Since $\rho(A)=\lambda_{\max}$,
$$
\boxed{0<\tau<\frac2{\rho(A)}.}
$$
Necessity also follows from an initial error in an offending <eigenvector> direction. At $\tau=0$ it remains unchanged; at $\tau=2/\rho(A)$ the largest-eigenvalue error alternates sign; outside the interval some error does not decay. Hence neither endpoint can be included.
Back to article page
