imported>PerfektesChaos: tk k

2019-09-18T15:09:06Z

tk k

Neue Seite

Das '''„Successive Over-Relaxation“-Verfahren''' (Überrelaxationsverfahren) oder '''SOR-Verfahren''' ist ein [[Algorithmus]] der [[Numerische Mathematik|numerischen Mathematik]] zur näherungsweisen Lösung von [[Lineares Gleichungssystem|linearen Gleichungssystemen]]. Es ist, wie das [[Gauß-Seidel-Verfahren]] und das [[Jacobi-Verfahren]], ein spezielles [[Splitting-Verfahren]] der Form <math>A = B + (A - B)</math> mit <math>B = (1/\omega)D + L</math>.

== Beschreibung des Verfahrens ==
Gegeben ist ein quadratisches lineares Gleichungssystem <math>A x= b</math> mit <math>n</math> Gleichungen und der Unbekannten <math>x</math>.
Dabei sind

: <math>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}.</math>

Das SOR-Verfahren löst diese Gleichung nun ausgehend von einem [[Startvektor]] <math>x_0</math> nach der [[Iteration]]svorschrift

: <math> x^{(m+1)}_k = (1-\omega)x^{(m)}_k + \frac{\omega}{a_{kk}} \left(b_k - \sum_{i>k} a_{ki}x^{(m)}_i - \sum_{i<k} a_{ki}x^{(m+1)}_i \right),\quad k=1,2,\ldots,n. </math>

Der reelle Überrelaxationsparameter <math>\omega \in (0,2)</math> sorgt dafür, dass das Verfahren schneller konvergiert als das [[Gauß-Seidel-Verfahren]], das ein Spezialfall dieser Formel mit <math>\omega=1</math> ist.

== Algorithmus ==
Als Algorithmusskizze mit Abbruchbedingung bietet sich an:

: ''wähle'' <math>x_0</math>
: ''wiederhole''
:: <math>\text{fehler} := 0</math>
:: ''für'' <math>k=1</math> ''bis'' <math>n</math>
::: <math>x^{(m+1)}_k:=(1-\omega)x_k^{(m)}+\frac{\omega}{a_{k;k}}\left(b_k-\sum_{i=1}^{k-1} a_{k;i}\cdot x^{(m+1)}_i -\sum_{i=k+1}^n a_{k;i}\cdot x^{(m)}_i\right)</math>
::: <math>\text{fehler}:=\max(\text{fehler}, |x^{(m+1)}_k-x^{(m)}_k|)</math>
:: ''nächstes'' <math>k</math>
:: <math>m := m+1</math>
: ''bis'' <math>\text{fehler} < \text{fehlerschranke}</math>

Dabei wurde eine [[Fehlerschranke]] als Eingangsgröße des Algorithmus angenommen; die Näherungslösung ist die vektorielle Rückgabegröße <math>x^{(m)}</math>. Die Fehlerschranke misst hier, welche Größe die letzte Änderung des Variablenvektors hatte.

Bei [[Dünnbesetzte Matrix|dünnbesetzten Matrizen]] reduziert sich der Aufwand des Verfahrens pro Iteration deutlich.

== Herleitung ==
Das SOR-Verfahren ergibt sich mittels Relaxation des Gauß-Seidel-Verfahrens:

: <math>x^{(m+1)}_k:=(1-\omega)x_k^{(m)}+\frac{\omega}{a_{k;k}}\left(b_k-\sum_{i=1}^{k-1} a_{k;i}\cdot x^{(m+1)}_i -\sum_{i=k+1}^n a_{k;i}\cdot x^{(m)}_i\right),</math>

für <math>\omega=1</math> 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 <math>A</math> wird dazu als Summe einer [[Diagonalmatrix]] <math>D</math> sowie zweier [[Dreiecksmatrix|strikter Dreiecksmatrizen]] <math>L</math> und <math>R</math> geschrieben:

: <math>A=D+L+R</math>

mit

: <math>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}.</math>

Das lineare Gleichungssystem ist dann äquivalent zu

: <math>(D+\omega L) x = \omega b - (\omega R + (\omega-1) D) x </math>

mit einem <math>\omega > 0</math>. Die [[Iterationsmatrix]] ist dann also

: <math>M=-(D+\omega L)^{-1}(\omega R + (\omega-1) D)</math>

und das Verfahren ist konsistent und konvergiert genau dann, wenn der [[Spektralradius]] <math>\rho(M)<1</math> ist.

Obige Formulierung zur komponentenweisen Berechnung der <math>x^{(m)}_i</math> erhält man aus dieser Matrix-Darstellung, wenn man die Dreiecksgestalt der Matrix <math>(D+\omega L)</math> ausnutzt. Diese Matrix lässt sich direkt durch [[Gaußsches Eliminationsverfahren#Vorwärtseinsetzen|Vorwärtseinsetzen]] invertieren.

== Konvergenz ==
Man kann zeigen, dass das Verfahren für eine [[Symmetrische Matrix|symmetrische]] [[positiv definit]]e Matrix <math>A</math> für jedes <math>\omega \in (0,2)</math> [[Grenzwert (Folge)|konvergiert]]. Um die Konvergenz gegenüber dem Gauß-Seidel-Verfahren zu beschleunigen, verwendet man heuristische Werte zwischen <math>1{,}5</math> und <math>2{,}0</math>. Die optimale Wahl hängt von der Koeffizientenmatrix <math>A</math> ab. Werte <math>\omega < 1</math> können gewählt werden, um eine Lösung zu stabilisieren, die ansonsten leicht divergiert.

Das Theorem von [[William Kahan|Kahan]] (1958) zeigt, dass für <math>\omega</math> außerhalb des Intervalls <math>(0,2)</math> keine Konvergenz mehr vorliegt.

Es kann gezeigt werden, dass der optimale Relaxationsparameter durch <math>\omega_{\text{opt}}=\frac{2}{1+\sqrt{1-\rho^2}}</math> gegeben ist, wobei <math>\rho</math> der [[Spektralradius]] der Verfahrensmatrix <math>D^{-1}(L+R)</math> des [[Jacobi-Verfahren]]s ist.<ref>Thomas Westermann: ''Modellbildung und Simulation.'' Springer, 2010.</ref>

== Literatur ==
* Andreas Meister: ''Numerik linearer Gleichungssysteme''. 3. Auflage. Vieweg, 2007, ISBN 3-8348-0431-2

== Weblinks ==
* {{MathWorld |id=SuccessiveOverrelaxationMethod |title=Successive Overrelaxation-Method |author=Noel Black, Shirley Moore}}
* [http://mathfaculty.fullerton.edu/mathews/n2003/SORmethodMod.html Implementierung des SOR-Verfahrens] (englisch)

== Einzelnachweise ==
<references />

[[Kategorie:Numerische lineare Algebra]]

SOR-Verfahren - Versionsgeschichte

imported>PerfektesChaos: tk k