2014-05-27

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
 A x = b.\,
The Richardson iteration is
 
x^{(k+1)}  = x^{(k)} + \omega \left( b - A x^{(k)} \right),
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 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)} \approx x^{(k)}-x, we get the equality for the errors
e(k + 1) = e(k) − ωAe(k) = (I − ω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 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.


References

No hay comentarios.: