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=\left(\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n2}& \cdots & a_{nn}\end{array}\right),x=\left(\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right),b=\left(\begin{array}{c}{b}_1\\ b_2\\ ⋮\\ b_n\end{array}\right).$

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}}(b_k-\sum _{i>k}{a}_{ki}{x}_i^{(m)}-\sum _{i<k}{a}_{ki}{x}_i^{(m+1)}),k=1,2,\dots ,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}}(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)})$

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

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=\left(\begin{array}{cccc}{a}_{11}& 0& \cdots & 0\\ 0& a_{22}& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & a_{nn}\end{array}\right),L=\left(\begin{array}{cccc}0& 0& \cdots & 0\\ a_{21}& 0& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n2}& \cdots & 0\end{array}\right),R=\left(\begin{array}{cccc}0& a_{12}& \cdots & a_{1n}\\ 0& 0& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & 0\end{array}\right).$

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

• Vorlage:MathWorld
• Implementierung des SOR-Verfahrens (englisch)