算盤: Modified Richardson iteration

2014-05-27

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 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

A x = 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) - ω A e (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, v j)

are the eigenvalues and eigenvectors of

A

. The error converges to

0

| 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 / λ m a x (A)

. The optimal choice, minimizing all

| 1 - ωλ j |

, is

ω = 2 / (λ m i n (A) + λ m a x (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.

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".Philos. Trans. Roy. Soc. London Ser. A 210: 307–357.
Vyacheslav Ivanovich Lebedev (2002). "Chebyshev iteration method". Springer. Retrieved 2010-05-25. Appeared in Encyclopaedia of Mathematics (2002), Ed. by Michiel Hazewinkel, Kluwer - ISBN 1402006098
Extremal polynomials with application to Richardson iteration for indefinite linear systems (Technical summary report / Mathematics Research Center, University of Wisconsin--Madison)