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

Beschreibung des Verfahrens

Gegeben ist ein quadratisches lineares Gleichungssystem <math>A x= b</math> mit <math>n</math> Gleichungen und der Unbekannten <math>x</math>. Dabei sind

<math>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}.</math>

Das SOR-Verfahren löst diese Gleichung nun ausgehend von einem Startvektor <math>x_0</math> nach der Iterationsvorschrift

<math> 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. </math>

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

Algorithmus

Als Algorithmusskizze mit Abbruchbedingung bietet sich an:

wähle <math>x_0</math>

wiederhole

<math>\text{fehler} := 0</math>

für <math>k=1</math> bis <math>n</math>

<math>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)</math>

<math>\text{fehler}:=\max(\text{fehler}, |x^{(m+1)}_k-x^{(m)}_k|)</math>

nächstes <math>k</math>

bis <math>\text{fehler} < \text{fehlerschranke}</math>

Dabei wurde eine Fehlerschranke als Eingangsgröße des Algorithmus angenommen; die Näherungslösung ist die vektorielle Rückgabegröße <math>x^{(m)}</math>. 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:

<math>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),</math>

für <math>\omega=1</math> 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 <math>A</math> wird dazu als Summe einer Diagonalmatrix <math>D</math> sowie zweier strikter Dreiecksmatrizen <math>L</math> und <math>R</math> geschrieben:

mit

<math>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}.</math>

Das lineare Gleichungssystem ist dann äquivalent zu

<math>(D+\omega L) x = \omega b - (\omega R + (\omega-1) D) x </math>

mit einem <math>\omega > 0</math>. Die Iterationsmatrix ist dann also

<math>M=-(D+\omega L)^{-1}(\omega R + (\omega-1) D)</math>

und das Verfahren ist konsistent und konvergiert genau dann, wenn der Spektralradius <math>\rho(M)<1</math> ist.

Obige Formulierung zur komponentenweisen Berechnung der <math>x^{(m)}_i</math> erhält man aus dieser Matrix-Darstellung, wenn man die Dreiecksgestalt der Matrix <math>(D+\omega L)</math> 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 <math>A</math> für jedes <math>\omega \in (0,2)</math> konvergiert. Um die Konvergenz gegenüber dem Gauß-Seidel-Verfahren zu beschleunigen, verwendet man heuristische Werte zwischen <math>1{,}5</math> und <math>2{,}0</math>. Die optimale Wahl hängt von der Koeffizientenmatrix <math>A</math> ab. Werte <math>\omega < 1</math> können gewählt werden, um eine Lösung zu stabilisieren, die ansonsten leicht divergiert.

Das Theorem von Kahan (1958) zeigt, dass für <math>\omega</math> außerhalb des Intervalls <math>(0,2)</math> keine Konvergenz mehr vorliegt.

Es kann gezeigt werden, dass der optimale Relaxationsparameter durch <math>\omega_{\text{opt}}=\frac{2}{1+\sqrt{1-\rho^2}}</math> gegeben ist, wobei <math>\rho</math> der Spektralradius der Verfahrensmatrix <math>D^{-1}(L+R)</math> des Jacobi-Verfahrens ist.<ref>Thomas Westermann: Modellbildung und Simulation. Springer, 2010.</ref>

Literatur

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

Weblinks

{{#if: Noel Black, Shirley Moore | Noel Black, Shirley Moore | Eric W. Weisstein }}: Successive Overrelaxation-Method. In: MathWorld (englisch). {{#if: SuccessiveOverrelaxationMethod | {{#ifeq: {{#property:P2812}} | SuccessiveOverrelaxationMethod | | {{#if: {{#property:P2812}} | {{#ifeq: 0 | 0 | }} | {{#ifeq: 0 | 0 | }} }} }} }}
Implementierung des SOR-Verfahrens (englisch)

Einzelnachweise