Richardson process

The Richardson method is an iterative algorithm in numerical mathematics for the approximate solution of linear systems of equations . It was developed in 1910 by the British meteorologist Lewis Fry Richardson and, like the Gauss-Seidel method, belongs to the class of splitting methods .

Richardson process

To solve the linear system of equations , the part of the system that is created by splitting the unit matrix from the system matrix ( splitting method with ) is left on the left, everything else is shifted to the right, so that a fixed point equation ${\displaystyle Ax=b}$ ${\displaystyle I}$ ${\displaystyle A}$ ${\displaystyle B=I}$

${\displaystyle x=\Phi (x)}$   With    ${\displaystyle \Phi (x)=b-(A-I)x}$

arises whose solution is based on the iteration

${\displaystyle x_{k+1}=(I-A)x_{k}+b}$

leads. This method converges like every fixed point iteration of this kind if the spectral radius of the iteration matrix is really less than one. ${\displaystyle G:=I-A}$

Relaxed Richardson method

The iteration formula of the relaxed Richardson method is

${\displaystyle x_{k+1}=\left(I-\omega A\right)x_{k}+\omega b}$.

The residual is weighted with a factor in each step . If there is a symmetrically positive definite matrix, then applies to the optimal relaxation parameter ${\displaystyle \omega }$ ${\displaystyle A}$

${\displaystyle \omega _{\mathrm {opt} }={\frac {2}{\lambda _{\mathrm {max} }(A)+\lambda _{\mathrm {min} }(A)}}}$.

And denote the maximum and minimum eigenvalues of . The following applies to the spectral radius of the iteration matrix ${\displaystyle \lambda _{\mathrm {max} }(A)}$ ${\displaystyle \lambda _{\mathrm {min} }(A)}$ ${\displaystyle A}$ ${\displaystyle G_{\omega _{\mathrm {opt} }}}$

${\displaystyle \rho (G_{\omega _{\mathrm {opt} }})={\frac {\kappa _{2}(A)-1}{\kappa _{2}(A)+1}}<1}$,

where denotes the spectral condition of the matrix . The relaxed Richardson method then converges just as “quickly” as the gradient method with symmetrical matrices , for which, however, one does not have to calculate a relaxation parameter. For this, one can use the Richardson method to force convergence even with asymmetrical matrices with complex eigenvalues , as long as their real parts are all positive. ${\displaystyle \kappa _{2}(A)}$ ${\displaystyle A}$

The method is suitable as a smoother in the multi-grid method .

Richardson cyclical method

The convergence can be significantly improved if one considers several steps of the iteration with different parameters . You take steps to do this ${\displaystyle \omega _{k}}$ ${\displaystyle m}$

${\displaystyle x_{k}=x_{k-1}+\omega _{k}(b-Ax_{k-1}),\quad k=1,\ldots ,m}$

cyclically through. The method converges when the spectral radius of the matrix polynomial

${\displaystyle p_{m}(A)=(I-\omega _{1}A)(I-\omega _{2}A)\cdots (I-\omega _{m}A)}$

is smaller than one, and the smaller it is, the better. For a matrix with real and positive eigenvalues , the spectral radius can be estimated by the maximum of the real polynomial in the interval . This maximum becomes particularly small if the relaxation parameters are chosen in such a way that their reciprocal values ​​are precisely the zeros of the appropriately shifted Chebyshev polynomial , ${\displaystyle A}$ ${\displaystyle p_{m}(t)=(1-\omega _{1}t)(1-\omega _{2}t)\cdots (1-\omega _{m}t)}$ ${\displaystyle [\lambda _{\mathrm {min} },\lambda _{\mathrm {max} }]}$

${\displaystyle {\frac {2}{\omega _{k}}}=\lambda _{\mathrm {min} }+\lambda _{\mathrm {max} }+\left(\lambda _{\mathrm {max} }-\lambda _{\mathrm {min} }\right)\cos \left({\frac {2k-1}{2m}}\pi \right),\ k=1,\ldots ,m.}$

Then the convergence result for symmetric matrices and one cycle of length improved to ${\displaystyle m}$

${\displaystyle \rho (p_{m}(A))\leq 2\left({\frac {{\sqrt {\kappa _{2}(A)}}-1}{{\sqrt {\kappa _{2}(A)}}+1}}\right)^{m}.}$

For realistic problems with , this represents a great improvement over the simple relaxed method, since only the root of the condition number is used. ${\displaystyle \kappa _{2}(A)\gg 1}$

For symmetric-definite matrices this method offers hardly any advantages compared to the conjugate gradient method , since it requires the estimation of the eigenvalues . In the asymmetrical case, however, the parameters can also be adapted well for complex eigenvalues, cf. Literature. In most cases, however, the Chebyshev iteration is preferable because it achieves the same error limit for every iteration step and not just for multiples of the cycle length . ${\displaystyle \lambda _{\mathrm {min} },\lambda _{\mathrm {max} }}$ ${\displaystyle k=m,2m,3m,\ldots }$

literature

• Andreas Meister: Numerics of linear systems of equations. 2nd Edition. Vieweg 2005, ISBN 3-528-13135-7
• Bernd Fischer, Lothar Reichel: A stable Richardson iteration method for complex linear systems. In: Numer. Math. 54, 1988, 225-242.