Subtracting the exact solution ${\displaystyle x}$ , and introducing the notation for the error ${\displaystyle e^{(k)}=x^{(k)}-x}$ , we get the equality for the errors

${\displaystyle e^{(k+1)}=e^{(k)}-\omega Ae^{(k)}=(I-\omega A)e^{(k)}.}$ 

Thus,

${\displaystyle \|e^{(k+1)}\|=\|(I-\omega A)e^{(k)}\|\leq \|I-\omega A\|\|e^{(k)}\|,}$ 

for any vector norm and the corresponding induced matrix norm. Thus, if ${\displaystyle \|I-\omega A\|<1}$ , the method converges.

Suppose that ${\displaystyle A}$  is symmetric positive definite and that ${\displaystyle (\lambda _{j})_{j}}$  are the eigenvalues of ${\displaystyle A}$ . The error converges to ${\displaystyle 0}$  if ${\displaystyle |1-\omega \lambda _{j}|<1}$  for all eigenvalues ${\displaystyle \lambda _{j}}$ . If, e.g., all eigenvalues are positive, this can be guaranteed if ${\displaystyle \omega }$  is chosen such that ${\displaystyle 0<\omega <\omega _{\text{max}}\,,\ \omega _{\text{max}}:=2/\lambda _{\text{max}}(A)}$ . The optimal choice, minimizing all ${\displaystyle |1-\omega \lambda _{j}|}$ , is ${\displaystyle \omega _{\text{opt}}:=2/(\lambda _{\text{min}}(A)+\lambda _{\text{max}}(A))}$ , which gives the simplest Chebyshev iteration. This optimal choice yields a spectral radius of

${\displaystyle \min _{\omega \in (0,\omega _{\text{max}})}\rho (I-\omega A)=\rho (I-\omega _{\text{opt}}A)=1-{\frac {2}{\kappa (A)+1}}\,,}$ 

where ${\displaystyle \kappa (A)}$  is the condition number.

If there are both positive and negative eigenvalues, the method will diverge for any ${\displaystyle \omega }$  if the initial error ${\displaystyle e^{(0)}}$  has nonzero components in the corresponding eigenvectors.

Consider minimizing the function ${\displaystyle F(x)={\frac {1}{2}}\|{\tilde {A}}x-{\tilde {b}}\|_{2}^{2}}$ . Since this is a convex function, a sufficient condition for optimality is that the gradient is zero (${\displaystyle \nabla F(x)=0}$ ) which gives rise to the equation

${\displaystyle {\tilde {A}}^{T}{\tilde {A}}x={\tilde {A}}^{T}{\tilde {b}}.}$ 

Define ${\displaystyle A={\tilde {A}}^{T}{\tilde {A}}}$  and ${\displaystyle b={\tilde {A}}^{T}{\tilde {b}}}$ . Because of the form of A, it is a positive semi-definite matrix, so it has no negative eigenvalues.

A step of gradient descent is

${\displaystyle x^{(k+1)}=x^{(k)}-t\nabla F(x^{(k)})=x^{(k)}-t(Ax^{(k)}-b)}$ 

which is equivalent to the Richardson iteration by making ${\displaystyle t=\omega }$ .

• Richardson extrapolation

• Richardson, L.F. (1910). "The approximate arithmetical solution by finite differences of physical problems involving differential equations, with an application to the stresses in a masonry dam". Philosophical Transactions of the Royal Society A. 210: 307–357. doi:10.1098/rsta.1911.0009. JSTOR 90994.
• Lebedev, Vyacheslav Ivanovich (2001) [1994], "Chebyshev iteration method", in Michiel Hazewinkel (ed.), Encyclopedia of Mathematics, EMS Press, ISBN 1-4020-0609-8, retrieved 2010-05-25