SOR-Verfahren

Das „Successive Over-Relaxation“-Verfahren 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 (A = B + (A − B) mit B = (1/ω)D + L).

Beschreibung des Verfahrens

Gegeben ist ein quadratisches lineares Gleichungssystem $A \mathbf x= \mathbf 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 \mathbf{x} = \begin{pmatrix} x_{1} \\ x_2 \\ \vdots \\ x_n \end{pmatrix} , \qquad \mathbf{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₀ nach der Iterationsvorschrift

$x^{(m+1)}_k = (1-\omega)x^{(m)}_k + \frac{\omega}{a_{kk}} \left(b_k - \sum_{i>k} a_{ki}x^{(m)}_i - \sum_{i<k} a_{ki}x^{(m+1)}_i \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 ω = 1 ist.

Algorithmus

Als Algorithmusskizze mit Abbruchbedingung bietet sich an:

wähle x₀

wiederhole

fehler: = 0

für k = 1 bis n

$x^{(m+1)}_k:=(1-\omega)x_k^{(m)}+\frac{\omega}{a_{k;k}}\left(b_k-\sum_{i=1}^{k-1} a_{k;i}\cdot x^{(m+1)}_i -\sum_{i=k+1}^n a_{k;i}\cdot x^{(m)}_i\right)$

$\text{fehler}:=\max(\text{fehler}, |x^{(m+1)}_k-x^{(m)}_k|)$

nächstes k

m: = m + 1

bis fehler < 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^{(m+1)}_k:=(1-\omega)x_k^{(m)}+\frac{\omega}{a_{k;k}}\left(b_k-\sum_{i=1}^{k-1} a_{k;i}\cdot x^{(m+1)}_i -\sum_{i=k+1}^n a_{k;i}\cdot x^{(m)}_i\right),$

für ω = 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 \qquad \text{mit} \quad 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) \mathbf{x} = \omega \mathbf{b} - (\omega R + (\omega-1) D) \mathbf{x}$

mit einem ω > 0. Die Iterationsmatrix ist dann also

M = − (D + ωL) ^{− 1}(ωR + (ω − 1)D)

und das Verfahren ist konsistent und konvergiert genau dann, wenn der Spektralradius ρ(M) < 1 ist.

Obige Formulierung zur komponentenweisen Berechnung der $x^{(m)}_i$ erhält man aus dieser Matrix-Darstellung, wenn man die Dreiecksgestalt der Matrix (D + ωL) ausnutzt. Diese Matrix lässt sich direkt durch Vorwärtseinsetzen invertieren.

Konvergenz

Man kann zeigen, dass das Verfahren für symmetrisch positiv definites 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 ω < 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 ω außerhalb des Intervalls (0,2) keine Konvergenz mehr vorliegt.

Literatur

• Andreas Meister: Numerik linearer Gleichungssysteme, 3. Auflage, Vieweg 2007, ISBN 3834804312

Weblinks

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