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

Ax=b.\,

The Richardson iteration is

x^{{(k+1)}}=x^{{(k)}}+\omega \left(b-Ax^{{(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 $Ax=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 Ae^{{(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$ .

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. JSTOR 90994.
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

Numerical linear algebra

Key concepts	Floating point Numerical stability

Problems	Matrix multiplication (algorithms) Matrix decompositions Linear equations Sparse problems

Hardware	CPU cache TLB Cache-oblivious algorithm SIMD Multiprocessing

Software	BLAS Specialized libraries General purpose software

This article is issued from Wikipedia - version of the 11/14/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Modified Richardson iteration

Convergence

Equivalence to gradient descent

See also

References