Modified Richardson iteration

Modified Richardson iteration is an iterative method for solving a system of linear equationsRichardson iteration was proposed by Lewis Richardson in his work dated 1910. It is similar to the Jacobiand Gauss–Seidel method.
We seek the solution to a set of linear equations, expressed in matrix terms as
The Richardson iteration is
where ω is a scalar parameter that has to be chosen such that the sequence x(k) converges.
It is easy to see that the method is correct, because if it converges, then  and x(k) has to approximate a solution of Ax = b.

Convergence

Subtracting the exact solution x, and introducing the notation for the error , we get the equality for the errors
e(k + 1) = e(k) − ωAe(k) = (I − ωA)e(k).
Thus,
for any vector norm and the corresponding induced matrix norm. Thus, if  the method convergences.
Suppose that A is diagonalizable and that j,vj) are the eigenvalues and eigenvectors of A. The error converges to 0 if | 1 − ωλj | < 1 for all eigenvalues λj. If, e.g., all eigenvalues are positive, this can be guaranteed if ω is chosen such that 0 < ω < 2 / λmax(A). The optimal choice, minimizing all | 1 − ωλj | , is ω = 2 / (λmin(A) + λmax(A)), which gives the simplest Chebyshev iteration.
If there are both positive and negative eigenvalues, the method will diverge for any ω if the initial error e(0) has nonzero components in the corresponding eigenvectors.

1 thought on “Modified Richardson iteration”

1. Excellent site. A lot of useful information here. Iˇm sending it to some friends ans also sharing in delicious. And certainly, thanks for your effort!