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 mit .

Beschreibung des Verfahrens

Gegeben ist ein quadratisches lineares Gleichungssystem mit Gleichungen und der Unbekannten . Dabei sind

Das SOR-Verfahren löst diese Gleichung nun ausgehend von einem Startvektor nach der Iterationsvorschrift

Der reelle Überrelaxationsparameter sorgt dafür, dass das Verfahren schneller konvergiert als das Gauß-Seidel-Verfahren, das ein Spezialfall dieser Formel mit ist.

Algorithmus

Als Algorithmusskizze mit Abbruchbedingung bietet sich an:

wähle
wiederhole
für bis
nächstes
bis

Dabei wurde eine Fehlerschranke als Eingangsgröße des Algorithmus angenommen; die Näherungslösung ist die vektorielle Rückgabegröße . 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:

für 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 wird dazu als Summe einer Diagonalmatrix sowie zweier strikter Dreiecksmatrizen und geschrieben:

mit

Das lineare Gleichungssystem ist dann äquivalent zu

mit einem . Die Iterationsmatrix ist dann also

und das Verfahren ist konsistent und konvergiert genau dann, wenn der Spektralradius ist.

Obige Formulierung zur komponentenweisen Berechnung der erhält man aus dieser Matrix-Darstellung, wenn man die Dreiecksgestalt der Matrix 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 für jedes konvergiert. Um die Konvergenz gegenüber dem Gauß-Seidel-Verfahren zu beschleunigen, verwendet man heuristische Werte zwischen und . Die optimale Wahl hängt von der Koeffizientenmatrix ab. Werte 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 keine Konvergenz mehr vorliegt.

Es kann gezeigt werden, dass der optimale Relaxationsparameter durch gegeben ist, wobei der Spektralradius der Verfahrensmatrix des Jacobi-Verfahrens ist.[1]

Literatur

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

Weblinks

Einzelnachweise

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