# SOR-Verfahren

Das „Successive Over-Relaxation“-Verfahren (Überrelaxationsverfahren) oder SOR-Verfahren ist ein Algorithmus der numerischen Mathematik zur näherungsweisen Lösung von linearen Gleichungssystemen. Es ist, wie das Gauß-Seidel-Verfahren und das Jacobi-Verfahren, ein spezielles Splitting-Verfahren der Form $A=B+(A-B)$ mit $B=(1/\omega )D+L$.

## Beschreibung des Verfahrens

Gegeben ist ein quadratisches lineares Gleichungssystem $Ax=b$ mit $n$ Gleichungen und der Unbekannten $x$. Dabei sind
    $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}}.$
Das SOR-Verfahren löst diese Gleichung nun ausgehend von einem Startvektor $x_{0}$ nach der Iterationsvorschrift
    $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.$
Der reelle Überrelaxationsparameter $\omega \in (0,2)$ sorgt dafür, dass das Verfahren schneller konvergiert als das Gauß-Seidel-Verfahren, das ein Spezialfall dieser Formel mit $\omega =1$ ist.

## Algorithmus

Als Algorithmusskizze mit Abbruchbedingung bietet sich an:
    wähle $x_{0}$
    wiederhole
       ${\text{fehler}}:=0$
       für $k=1$ bis $n$
          $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)$
          ${\text{fehler}}:=\max({\text{fehler}},|x_{k}^{(m+1)}-x_{k}^{(m)}|)$
       nächstes $k$
       $m:=m+1$
    bis ${\text{fehler}}<{\text{fehlerschranke}}$
Dabei wurde eine Fehlerschranke als Eingangsgröße des Algorithmus angenommen; die Näherungslösung ist die vektorielle Rückgabegröße $x^{(m)}$. Die Fehlerschranke misst hier, welche Größe die letzte Änderung des Variablenvektors hatte.
Bei dünnbesetzten Matrizen reduziert sich der Aufwand des Verfahrens pro Iteration deutlich.

## Herleitung

Das SOR-Verfahren ergibt sich mittels Relaxation des Gauß-Seidel-Verfahrens:
    $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),$
für $\omega =1$ erhält man also Gauß-Seidel zurück. Um das Verfahren zu analysieren, bietet sich die Formulierung als Splitting-Verfahren an, die es erlaubt, die Eigenschaften des Verfahrens zu analysieren. Die Matrix $A$ wird dazu als Summe einer Diagonalmatrix $D$ sowie zweier strikter Dreiecksmatrizen $L$ und $R$ geschrieben:
    $A=D+L+R$
mit
    $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}}.$
Das lineare Gleichungssystem ist dann äquivalent zu
    $(D+\omega L)x=\omega b-(\omega R+(\omega -1)D)x$
mit einem $\omega >0$. Die Iterationsmatrix ist dann also
    $M=-(D+\omega L)^{-1}(\omega R+(\omega -1)D)$
und das Verfahren ist konsistent und konvergiert genau dann, wenn der Spektralradius $\rho (M)<1$ ist.
Obige Formulierung zur komponentenweisen Berechnung der $x_{i}^{(m)}$ erhält man aus dieser Matrix-Darstellung, wenn man die Dreiecksgestalt der Matrix $(D+\omega L)$ ausnutzt. Diese Matrix lässt sich direkt durch Vorwärtseinsetzen invertieren.

## Konvergenz

Man kann zeigen, dass das Verfahren für eine symmetrische positiv definite Matrix $A$ für jedes $\omega \in (0,2)$ konvergiert. Um die Konvergenz gegenüber dem Gauß-Seidel-Verfahren zu beschleunigen, verwendet man heuristische Werte zwischen $1{,}5$ und $2{,}0$. Die optimale Wahl hängt von der Koeffizientenmatrix $A$ ab. Werte $\omega <1$ können gewählt werden, um eine Lösung zu stabilisieren, die ansonsten leicht divergiert.
Das Theorem von Kahan (1958) zeigt, dass für $\omega$ außerhalb des Intervalls $(0,2)$ keine Konvergenz mehr vorliegt.
Es kann gezeigt werden, dass der optimale Relaxationsparameter durch $\omega _{\text{opt}}={\frac {2}{1+{\sqrt {1-\rho ^{2}}}}}$ gegeben ist, wobei $\rho$ der Spektralradius der Verfahrensmatrix $D^{-1}(L+R)$ des Jacobi-Verfahrens ist.