Modified 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

$A x = b.\,$

The Richardson iteration is

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

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

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

Convergence

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

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

Thus,

$\|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 $\|I-\omega A\|<1$, the method converges.

Suppose that $A$ is diagonalizable and that $(\lambda_j, v_j)$ are the eigenvalues and eigenvectors of $A$. The error converges to $0$ if $| 1 - \omega \lambda_j |< 1$ for all eigenvalues $\lambda_j$. If, e.g., all eigenvalues are positive, this can be guaranteed if $\omega$ is chosen such that $0 < \omega < 2/\lambda_{max}(A)$. The optimal choice, minimizing all $| 1 - \omega \lambda_j |$, is $\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 $\omega$ if the initial error $e^{(0)}$ has nonzero components in the corresponding eigenvectors.

Equivalence to gradient descent

Consider minimizing the function $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 ($\nabla F(x) = 0$) which gives rise to the equation

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

Define $A=\tilde{A}^T\tilde{A}$ and $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

$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 $t=\omega$.

See also

• Richardson extrapolation

References

• 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.
• Vyacheslav Ivanovich Lebedev (2002). "Chebyshev iteration method". Springer. Retrieved 2010-05-25. Appeared in Encyclopaedia of Mathematics (2002), Ed. by Michiel Hazewinkel, Kluwer - ISBN 1-4020-0609-8