# Modified Richardson iteration

(Redirected from Richardson iteration)

Modified Richardson iteration is an iterative method for solving a system of linear equations. Richardson iteration was proposed by Lewis Richardson in his work dated 1910. It is similar to the Jacobi and Gauss–Seidel method.

We seek the solution to a set of linear equations, expressed in matrix terms as

${\displaystyle Ax=b.\,}$

The Richardson iteration is

${\displaystyle x^{(k+1)}=x^{(k)}+\omega \left(b-Ax^{(k)}\right),}$

where ${\displaystyle \omega }$ is a scalar parameter that has to be chosen such that the sequence ${\displaystyle x^{(k)}}$ converges.

It is easy to see that the method has the correct fixed points, because if it converges, then ${\displaystyle x^{(k+1)}\approx x^{(k)}}$ and ${\displaystyle x^{(k)}}$ has to approximate a solution of ${\displaystyle Ax=b}$.

## Convergence

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 diagonalizable and that ${\displaystyle (\lambda _{j},v_{j})}$ are the eigenvalues and eigenvectors 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 <2/\lambda _{max}(A)}$. The optimal choice, minimizing all ${\displaystyle |1-\omega \lambda _{j}|}$, is ${\displaystyle \omega =2/(\lambda _{min}(A)+\lambda _{max}(A))}$, which gives the simplest Chebyshev iteration.

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-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 }$.