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 ${\displaystyle A=B+(A-B)}$ mit ${\displaystyle B=(1/\omega )D+L}$.

Beschreibung des Verfahrens

Gegeben ist ein quadratisches lineares Gleichungssystem ${\displaystyle Ax=b}$ mit ${\displaystyle n}$ Gleichungen und der Unbekannten ${\displaystyle x}$. Dabei sind

${\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}}.}$

Das SOR-Verfahren löst diese Gleichung nun ausgehend von einem Startvektor ${\displaystyle x_{0}}$ nach der Iterationsvorschrift

${\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.}$

Der reelle Überrelaxationsparameter ${\displaystyle \omega \in (0,2)}$ sorgt dafür, dass das Verfahren schneller konvergiert als das Gauß-Seidel-Verfahren, das ein Spezialfall dieser Formel mit ${\displaystyle \omega =1}$ ist.

Algorithmus

Als Algorithmusskizze m​it Abbruchbedingung bietet s​ich an:

wähle ${\displaystyle x_{0}}$

wiederhole

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

für ${\displaystyle k=1}$ bis ${\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)}|)}$

nächstes ${\displaystyle k}$

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

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

Dabei wurde eine Fehlerschranke als Eingangsgröße des Algorithmus angenommen; die Näherungslösung ist die vektorielle Rückgabegröße ${\displaystyle x^{(m)}}$. Die Fehlerschranke misst hier, welche Größe die letzte Änderung des Variablenvektors hatte.

Bei dünnbesetzten Matrizen reduziert s​ich der Aufwand d​es Verfahrens p​ro Iteration deutlich.

Herleitung

Das SOR-Verfahren ergibt s​ich mittels Relaxation d​es Gauß-Seidel-Verfahrens:

${\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),}$

für ${\displaystyle \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 ${\displaystyle A}$ wird dazu als Summe einer Diagonalmatrix ${\displaystyle D}$ sowie zweier strikter Dreiecksmatrizen ${\displaystyle L}$ und ${\displaystyle R}$ geschrieben:

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

mit

${\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}}.}$

Das lineare Gleichungssystem i​st dann äquivalent zu

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

mit einem ${\displaystyle \omega >0}$. Die Iterationsmatrix ist dann also

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

und das Verfahren ist konsistent und konvergiert genau dann, wenn der Spektralradius ${\displaystyle \rho (M)<1}$ ist.

Obige Formulierung zur komponentenweisen Berechnung der ${\displaystyle x_{i}^{(m)}}$ erhält man aus dieser Matrix-Darstellung, wenn man die Dreiecksgestalt der Matrix ${\displaystyle (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 ${\displaystyle A}$ für jedes ${\displaystyle \omega \in (0,2)}$ konvergiert. Um die Konvergenz gegenüber dem Gauß-Seidel-Verfahren zu beschleunigen, verwendet man heuristische Werte zwischen ${\displaystyle 1{,}5}$ und ${\displaystyle 2{,}0}$. Die optimale Wahl hängt von der Koeffizientenmatrix ${\displaystyle A}$ ab. Werte ${\displaystyle \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 ${\displaystyle \omega }$ außerhalb des Intervalls ${\displaystyle (0,2)}$ keine Konvergenz mehr vorliegt.

Es kann gezeigt werden, dass der optimale Relaxationsparameter durch ${\displaystyle \omega _{\text{opt}}={\frac {2}{1+{\sqrt {1-\rho ^{2}}}}}}$ gegeben ist, wobei ${\displaystyle \rho }$ der Spektralradius der Verfahrensmatrix ${\displaystyle D^{-1}(L+R)}$ des Jacobi-Verfahrens ist.[1]

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)

Einzelnachweise

1. Thomas Westermann: Modellbildung und Simulation. Springer, 2010.