Wikipedia · einfach zusammengefasst · Stand
SOR-Verfahren
Das „Successive Over-Relaxation“-Verfahren (Überrelaxationsverfahren) oder SOR-Verfahren ist ein Algorithmus der numerischen Mathematik zur näherungsweisen …
Inhalt4 Abschnitte
Grundidee und Iterationsvorschrift
Das Successive-Over-Relaxation-Verfahren, kurz SOR-Verfahren oder Überrelaxationsverfahren, ist ein iterativer Algorithmus der numerischen Mathematik. Es berechnet eine Näherungslösung eines quadratischen linearen Gleichungssystems Ax=b mit n Gleichungen und dem unbekannten Vektor x. Wie das Jacobi- und das Gauß-Seidel-Verfahren gehört es zu den Splitting-Verfahren, bei denen die Koeffizientenmatrix zerlegt wird.
Ausgehend von einem frei gewählten Startvektor x⁽⁰⁾ werden die Komponenten der Näherung nacheinander aktualisiert:
x_k⁽ᵐ⁺¹⁾=(1−ω)x_k⁽ᵐ⁾+(ω/a_kk)(b_k−∑{i>k}a_ki x_i⁽ᵐ⁾−∑{i<k}a_ki x_i⁽ᵐ⁺¹⁾), k=1,2,…,n.
Bei der Berechnung von x_k⁽ᵐ⁺¹⁾ verwendet das Verfahren für die Komponenten mit i<k bereits die neuen Werte aus der laufenden Iteration m+1. Für die noch nicht aktualisierten Komponenten mit i>k verwendet es die alten Werte aus Iteration m.
Der reelle Relaxationsparameter ω steuert, wie stark der neue Wert gegenüber dem bisherigen verändert wird. Üblicherweise gilt ω∈(0,2). Für ω=1 entsteht genau das Gauß-Seidel-Verfahren. Bei einer geeigneten Wahl von ω kann SOR schneller konvergieren, also schneller gegen die gesuchte Lösung streben, als Gauß-Seidel.
Praktischer Ablauf und Abbruch
Der Algorithmus beginnt mit einem Startvektor x⁽⁰⁾. In jeder Iteration werden die n Komponenten der Reihe nach neu berechnet. Gleichzeitig wird die größte Änderung einer Komponente erfasst:
fehler:=max_k |x_k⁽ᵐ⁺¹⁾−x_k⁽ᵐ⁾|.
Nach der Aktualisierung aller Komponenten wird der Iterationszähler erhöht. Das Verfahren wiederholt diesen Ablauf, bis
fehler<fehlerschranke
gilt. Die Fehlerschranke wird als Eingangsgröße vorgegeben. Sie legt fest, wie klein die größte Änderung des Variablenvektors zwischen zwei aufeinanderfolgenden Iterationen sein muss. Als Ergebnis wird der zuletzt berechnete Näherungsvektor x⁽ᵐ⁾ zurückgegeben.
Die verwendete Fehlergröße misst damit die letzte Änderung der Näherung. Sie ist nicht unmittelbar der tatsächliche Abstand zur exakten Lösung. Bei dünnbesetzten Matrizen, also Matrizen mit vielen Nulleinträgen, sinkt der Rechenaufwand pro Iteration deutlich, weil nur die von null verschiedenen Koeffizienten berücksichtigt werden müssen.
Matrixdarstellung und Herleitung
Das SOR-Verfahren entsteht durch Relaxation des Gauß-Seidel-Verfahrens. Dazu wird die Matrix A in drei Teile zerlegt:
A=D+L+R.
D ist die Diagonalmatrix mit den Einträgen a₁₁,…,a_nn. L ist die strikt untere Dreiecksmatrix und enthält die Einträge unterhalb der Hauptdiagonalen. R ist die strikt obere Dreiecksmatrix und enthält die Einträge oberhalb der Hauptdiagonalen.
Für ω>0 lässt sich das Gleichungssystem äquivalent schreiben als
(D+ωL)x=ωb−(ωR+(ω−1)D)x.
Damit besitzt die Iteration die Iterationsmatrix
M=−(D+ωL)⁻¹(ωR+(ω−1)D).
Diese Darstellung entspricht einem Splitting A=B+(A−B) mit B=(1/ω)D+L. Sie dient insbesondere dazu, die Konvergenzeigenschaften zu untersuchen. Das Verfahren ist konsistent und konvergiert genau dann, wenn für den Spektralradius der Iterationsmatrix
ρ(M)<1
gilt. Der Spektralradius ρ(M) ist der größte Betrag der Eigenwerte von M.
Die komponentenweise Iterationsformel folgt aus dieser Matrixdarstellung. Weil D+ωL eine untere Dreiecksmatrix ist, kann das zugehörige Gleichungssystem durch Vorwärtseinsetzen gelöst werden: Die Komponenten werden in der Reihenfolge k=1 bis n berechnet, wobei die bereits aktualisierten Werte sofort in die folgenden Rechnungen eingehen.
Konvergenz und Wahl des Parameters
Ist A symmetrisch und positiv definit, dann konvergiert das SOR-Verfahren für jedes ω∈(0,2). Symmetrisch bedeutet A=Aᵀ; positiv definit bedeutet, dass xᵀAx>0 für jeden Vektor x≠0 gilt.
Für die Bedeutung des Parameters werden drei Fälle unterschieden:
• ω=1 liefert das Gauß-Seidel-Verfahren.
• Werte 1<ω<2 bewirken Überrelaxation. Zur heuristischen Beschleunigung gegenüber Gauß-Seidel werden häufig Werte zwischen 1,5 und 2,0 verwendet.
• Werte ω<1 bewirken Unterrelaxation. Sie können eine Berechnung stabilisieren, die andernfalls leicht divergiert.
Die beste Wahl hängt von der Koeffizientenmatrix A ab. Nach dem Theorem von Kahan aus dem Jahr 1958 liegt für ω außerhalb des Intervalls (0,2) keine Konvergenz vor.
Der optimale Relaxationsparameter kann durch
ω_opt=2/(1+√(1−ρ²))
bestimmt werden. Dabei bezeichnet ρ den Spektralradius der Jacobi-Verfahrensmatrix D⁻¹(L+R). Diese Formel verbindet die optimale Parameterauswahl für SOR mit den Konvergenzeigenschaften des Jacobi-Verfahrens.
