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
![{\displaystyle 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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/38b16dd32f3560cf2986da16e3078f2cc79b40b5)
Das SOR-Verfahren löst diese Gleichung nun ausgehend von einem Startvektor
nach der Iterationsvorschrift
![{\displaystyle x_{k}^{(m+1)}=(1-\omega )x_{k}^{(m)}+{\frac {\omega }{a_{kk}}}\left(b_{k}-\sum _{i>k}a_{ki}x_{i}^{(m)}-\sum _{i<k}a_{ki}x_{i}^{(m+1)}\right),\quad k=1,2,\ldots ,n.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b382fcaed528c609884e396e37d62a3e7a664fea)
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
![{\displaystyle x_{0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/86f21d0e31751534cd6584264ecf864a6aa792cf)
- wiederhole
![{\displaystyle {\text{fehler}}:=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d90a478741296c04763d863f0e7e03690cb96386)
- für
bis
![{\displaystyle x_{k}^{(m+1)}:=(1-\omega )x_{k}^{(m)}+{\frac {\omega }{a_{k;k}}}\left(b_{k}-\sum _{i=1}^{k-1}a_{k;i}\cdot x_{i}^{(m+1)}-\sum _{i=k+1}^{n}a_{k;i}\cdot x_{i}^{(m)}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/15994082631209f184ae30f0bc39560475d608ef)
![{\displaystyle {\text{fehler}}:=\max({\text{fehler}},|x_{k}^{(m+1)}-x_{k}^{(m)}|)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/482a783c590f221ca77886b958119fbcd1f6a74f)
- nächstes
![{\displaystyle k}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
![{\displaystyle m:=m+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/70912e69169cb8f7b8c97960c6a80486474de8c9)
- bis
![{\displaystyle {\text{fehler}}<{\text{fehlerschranke}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/36e8dbb7fe143e3cc95d13fb25efacaab5905903)
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:
![{\displaystyle x_{k}^{(m+1)}:=(1-\omega )x_{k}^{(m)}+{\frac {\omega }{a_{k;k}}}\left(b_{k}-\sum _{i=1}^{k-1}a_{k;i}\cdot x_{i}^{(m+1)}-\sum _{i=k+1}^{n}a_{k;i}\cdot x_{i}^{(m)}\right),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f6a7477a5e6cf7b89d53c29314acb0d2ce4fd80f)
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:
![{\displaystyle A=D+L+R}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a622f67645b392e152cbd2546331879dd730167)
mit
![{\displaystyle 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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/69304418f6c4a342d392cbc13c0ac18647da6946)
Das lineare Gleichungssystem ist dann äquivalent zu
![{\displaystyle (D+\omega L)x=\omega b-(\omega R+(\omega -1)D)x}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ecb977355819dbb51941330aebb2c0dd780e87f8)
mit einem
. Die Iterationsmatrix ist dann also
![{\displaystyle M=-(D+\omega L)^{-1}(\omega R+(\omega -1)D)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4a68e392d951064f13779579e9696a2bd37879e2)
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
- Noel Black, Shirley Moore: Successive Overrelaxation-Method. In: MathWorld (englisch).
- Implementierung des SOR-Verfahrens (englisch)
Einzelnachweise
- ↑ Thomas Westermann: Modellbildung und Simulation. Springer, 2010.