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 Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle A x= 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.

Literatur

• Andreas Meister: Numerik linearer Gleichungssysteme. 3. Auflage. Vieweg, 2007, ISBN 3-8348-0431-2

Weblinks

• Noel Black, Shirley Moore: Successive Overrelaxation-Method. In: MathWorld (englisch).
• Implementierung des SOR-Verfahrens (englisch)