[ < ] [ globale Übersicht ] [ Kapitelübersicht ] [ Stichwortsuche ] [ > ]

SOR-Verfahren (Überrelaxationsverfahren)

Das SOR-Verfahren gehört zur Klasse der Stationären iterativen Verfahren (von einer [beliebigen] Startlösung schrittweise Näherung an die "echte" Lösung mit immer der selben Verfahrensvorschrift).

Im wesentlichen handelt es sich um eine Erweiterung des Gauß-Seidel-Verfahrens. Der Grundgedanke besteht darin, daß eine einmal eingeschlagene Richtung zur "echten" Lösung hin nicht komplett falsch sein kann und man daher gleich einen etwas größeren Schritt wagen kann. Außerdem läßt man noch den vorhergehenden Iterationsschritt in die Berechnung der neuen Richtung mit einfließen. Man möchte mit diesem Vorgehen die Konvergenzgeschwindigkeit des Gauß-Seidel-Verfahrens deutlich steigern, was auch meistens gelingt.

Erreicht wird das alles mit einem zusätzlichen Parameter w. Im Pseudocode sieht des Verfahren folgendermaßen aus:

  do k = 1, 2, 3, ...
   do i = 1 ... n

$x_i^{(k)}:=w*(b_i-\sum_{j=1}^{i-1}a_{ij}x_j^{(k)}-\sum_{j=i+1}^na_{ij}x_j^{(k-1)})/a_{ii}+(1-w)*x_i^{(k-1)}$
   end do
  if Abbruchkriterium then exit
  end do

Auch hier gilt das selbe wie beim Gauß-Seidel-Verfahren gegenüber dem Jacobi-Verfahren , daß die Reihenfolge der Formelauswertungen nicht mehr beliebig und daher schwer parallelisierbar ist.

Wichtig für dieses Verfahren ist zweifellos der folgende
Satz: Ist A eine symmetrische und positiv definite Matrix, so konvergiert das SOR-Verfahren für jedes w aus dem Intervall (0, 2) und für jeden beliebigen Startvektor.

Die Wahl des Parameters w ist eine heikle Angelegenheit. Ist w = 1, dann entspricht das SOR-Verfahren exakt dem Gauß-Seidel-Verfahren. Mit w < 1 ist schnell zu sehen, daß man die Konvergenzgeschwindigkeit verlangsamen würde (man geht nur einen Bruchteil des Weges zu der "echten" Lösung, dafür aber noch etwas in Richtung der "alten" Iteration); das ist nicht wirklich der Sinn dieses Verfahrens. Man wählt daher meist einen Wert für w, der größer als 1 ist (daher auch der Name "Überrelaxation").
Gute Erfahrungen hat man mit Werten um 1.2 gemacht. Allerdings kann man keine allgemein gültige Aussage über den besten Wert für w machen. Die Konvergenzgeschwindigkeit kann enorm erhöht, aber auch verlangsamt werden. In der Praxis werden daher heuristische Verfahren verwendet, um einen möglichst guten Wert für das optimale w zu schätzen.
Nur für bestimmte Klassen von Matrizen besteht die Möglichkeit, das optimale w auch direkt zu berechnen (z.B. für tridiagonale Blockmatrizen). Oft ist aber die Berechnung der entsprechenden Formel (oder Teilen daraus) mit einem so hohen Rechenaufwand verbunden, daß erst wieder auf heuristische Verfahren zurückgegriffen werden muß.

SSOR-Verfahren (Symmetrisches SOR-Verfahren)

Das SSOR-Verfahren ist nur für symmetrische Ausgangsmatrizen geeignet.

Alle Stationären iterativen Verfahren können auch in der folgenden Matrixnotation geschrieben werden:

x = T(x) = Bx + c ,
wobei T(x) die konstante Iterationsvorschrift bezeichnet, die in die Teile B (eine Matrix) und c (einen Vektor) zerfällt.

Beim SSOR-Verfahren wird nun versucht, auch die Matrix B symmetrisch zu machen. Außerdem wird die innere Schleife des SOR-Verfahrens (der vorläufige Lösungsvektor) einmal von oben nach unten, dann in umgekehrter Reihenfolge durchlaufen ("stabilisiert" die Berechnung).

Eine Effizienzsteigerung gegenüber dem SOR-Verfahren kann damit zwar nicht erreicht werden, die Konvergenz ist meist sogar schlechter als bei optimierten SOR-Verfahren. Die Bedeutung liegt aber vielmehr in der Verwendung als vorkonditionierendes Verfahren für Nichtstationäre iterative Verfahren (Vorkonditionierung: Umwandlung des Ausgangsproblems in ein effizienter lösbares Problem).

[ < ] [ globale Übersicht ] [ Kapitelübersicht ] [ Stichwortsuche ] [ > ]