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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

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

Einzelnachweise

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