SOR-Verfahren

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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

Beschreibung des Verfahrens[Bearbeiten]

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_0 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 \omega=1 ist.

Algorithmus[Bearbeiten]

Als Algorithmusskizze mit Abbruchbedingung bietet sich an:

wähle x0
wiederhole
\text{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 \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[Bearbeiten]

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 \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 \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+\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^{(m)}_i 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[Bearbeiten]

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 \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 ω außerhalb des Intervalls (0,2) keine Konvergenz mehr vorliegt.

Literatur[Bearbeiten]

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

Weblinks[Bearbeiten]