SOR procedure

The "Successive Over-Relaxation" method ( over relaxation method ) or SOR method is an algorithm in numerical mathematics for the approximate solution of linear systems of equations . It is, as the Gauss-Seidel method , and the Jacobi method , a special splitting method of the mold with . ${\displaystyle A=B+(A-B)}$ ${\displaystyle B=(1/\omega )D+L}$

Description of the procedure

A quadratic linear system of equations with equations and the unknown is given . Are there ${\displaystyle Ax=b}$ ${\displaystyle n}$ ${\displaystyle x}$

${\displaystyle A={\begin{pmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &a_{nn}\end{pmatrix}},\qquad x={\begin{pmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{pmatrix}},\qquad b={\begin{pmatrix}b_{1}\\b_{2}\\\vdots \\b_{n}\end{pmatrix}}.}$

The SOR method now solves this equation on the basis of a start vector according to the iteration rule ${\displaystyle x_{0}}$

${\displaystyle x_{k}^{(m+1)}=(1-\omega )x_{k}^{(m)}+{\frac {\omega }{a_{kk}}}\left(b_{k}-\sum _{i>k}a_{ki}x_{i}^{(m)}-\sum _{i<k}a_{ki}x_{i}^{(m+1)}\right),\quad k=1,2,\ldots ,n.}$

The real over-relaxation parameter ensures that the method converges faster than the Gauss-Seidel method , which is a special case of this formula . ${\displaystyle \omega \in (0,2)}$ ${\displaystyle \omega =1}$

algorithm

As an algorithm sketch with termination condition is possible:

choose ${\displaystyle x_{0}}$

repeat

${\displaystyle {\text{fehler}}:=0}$

for up ${\displaystyle k=1}$ ${\displaystyle n}$

${\displaystyle x_{k}^{(m+1)}:=(1-\omega )x_{k}^{(m)}+{\frac {\omega }{a_{k;k}}}\left(b_{k}-\sum _{i=1}^{k-1}a_{k;i}\cdot x_{i}^{(m+1)}-\sum _{i=k+1}^{n}a_{k;i}\cdot x_{i}^{(m)}\right)}$

${\displaystyle {\text{fehler}}:=\max({\text{fehler}},|x_{k}^{(m+1)}-x_{k}^{(m)}|)}$

next ${\displaystyle k}$

${\displaystyle m:=m+1}$

to ${\displaystyle {\text{fehler}}<{\text{fehlerschranke}}}$

An error limit was assumed as the input variable for the algorithm; the approximate solution is the vectorial return size . The error barrier measures the size of the last change in the variable vector. ${\displaystyle x^{(m)}}$

In the case of sparsely populated matrices , the effort of the process per iteration is significantly reduced.

Derivation

The SOR method results from relaxation of the Gauß-Seidel method:

${\displaystyle x_{k}^{(m+1)}:=(1-\omega )x_{k}^{(m)}+{\frac {\omega }{a_{k;k}}}\left(b_{k}-\sum _{i=1}^{k-1}a_{k;i}\cdot x_{i}^{(m+1)}-\sum _{i=k+1}^{n}a_{k;i}\cdot x_{i}^{(m)}\right),}$

for you get Gauss-Seidel back. In order to analyze the process, the formulation is suitable as a splitting process, which allows the properties of the process to be analyzed. The matrix is written as the sum of a diagonal matrix and two strict triangular matrices and : ${\displaystyle \omega =1}$ ${\displaystyle A}$ ${\displaystyle D}$ ${\displaystyle L}$ ${\displaystyle R}$

${\displaystyle A=D+L+R}$

With

${\displaystyle D={\begin{pmatrix}a_{11}&0&\cdots &0\\0&a_{22}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &a_{nn}\end{pmatrix}},\quad L={\begin{pmatrix}0&0&\cdots &0\\a_{21}&0&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &0\end{pmatrix}},\quad R={\begin{pmatrix}0&a_{12}&\cdots &a_{1n}\\0&0&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &0\end{pmatrix}}.}$

The system of linear equations is then equivalent to

${\displaystyle (D+\omega L)x=\omega b-(\omega R+(\omega -1)D)x}$

with one . The iteration matrix is then ${\displaystyle \omega >0}$

${\displaystyle M=-(D+\omega L)^{-1}(\omega R+(\omega -1)D)}$

and the method is consistent and converges if and only if the spectral radius is. ${\displaystyle \rho (M)<1}$

The above formulation for the component-wise calculation of the can be obtained from this matrix representation if the triangular shape of the matrix is ​​used . This matrix can be inverted directly by inserting it forward . ${\displaystyle x_{i}^{(m)}}$ ${\displaystyle (D+\omega L)}$

convergence

It can be shown that for a symmetric positive definite matrix the procedure converges for each . In order to accelerate the convergence compared to the Gauss-Seidel method, heuristic values ​​between and are used . The optimal choice depends on the coefficient matrix . Values can be chosen to stabilize a solution that is otherwise slightly divergent. ${\displaystyle A}$ ${\displaystyle \omega \in (0,2)}$ ${\displaystyle 1{,}5}$ ${\displaystyle 2{,}0}$ ${\displaystyle A}$ ${\displaystyle \omega <1}$

Kahan's theorem (1958) shows that there is no longer any convergence outside the interval . ${\displaystyle \omega }$ ${\displaystyle (0,2)}$

It can be shown that the optimal relaxation parameter is given by , where the spectral radius is the method matrix of the Jacobi method . ${\displaystyle \omega _{\text{opt}}={\frac {2}{1+{\sqrt {1-\rho ^{2}}}}}}$ ${\displaystyle \rho }$ ${\displaystyle D^{-1}(L+R)}$

literature

• Andreas Meister: Numerics of linear systems of equations . 3. Edition. Vieweg, 2007, ISBN 3-8348-0431-2

Web links

• Noel Black, Shirley Moore: Successive Overrelaxation Method . In: MathWorld (English).
• Implementation of the SOR method (English)

Individual evidence

1. ^ Thomas Westermann: Modeling and Simulation. Springer, 2010.