SOR-Verfahren

In der numerischen Mathematik ist das Successive Over Relaxation-Verfahren, auch SOR-Verfahren genannt, ein Algorithmus zur näherungsweisen Lösung von linearen Gleichungssystemen \(\displaystyle Ax=b\). Es ist, wie das Gauß-Seidel-Verfahren und das Jacobi-Verfahren, ein spezielles Splitting-Verfahren.
Gegeben ist ein lineares Gleichungssystem mit \(\displaystyle n\) Variablen mit \(\displaystyle n\) Gleichungen.
\(\displaystyle \begin{matrix} a_{1;1}\cdot x_1+\dots+a_{1;n}\cdot x_n&=&b_1\\ a_{2;1}\cdot x_1+\dots+a_{2;n}\cdot x_n&=&b_2\\ &\vdots&\\ a_{n;1}\cdot x_1+\dots+a_{n;n}\cdot x_n&=&b_n\\ \end{matrix} \)
Der Algorithmus verwendet eine Matrix \(\displaystyle \tilde A = (\tilde a_{ij} )\) mit \(\displaystyle \tilde a_{ij} = { - \dfrac{{a_{ij} }}{{a_{ii} }}w}\) falls \(\displaystyle i \ne j\), bzw. \(\displaystyle \tilde a_{ij}=1-w\) falls \(\displaystyle i = j\) und den Vektor \(\displaystyle c_i = \dfrac{{b_i }}{{a_{ii} }}w\) mit \(\displaystyle i=1,2,\ldots,n\). Dabei ist \(\displaystyle w\) ein reeller Überrelaxationsparameter. Für \(\displaystyle w=1\) erhält man wieder ein Einzelschrittverfahren. Das Verfahren konvergiert für jedes \(\displaystyle w \in ]0,2[\), falls \(\displaystyle A\) symmetrisch positiv definit ist. Um das Gleichungssystem zu lösen, wird die \(\displaystyle i\)-te Gleichung nach der \(\displaystyle i\)-ten Variable \(\displaystyle x_{i}\) aufgelöst,
\(\displaystyle x_i^{m + 1} = \sum\limits\limits_{j = 1}^{i - 1} {\tilde a_{ij} } x_j^{m + 1} + \sum\limits\limits_{j = i + 1}^n {\tilde a_{ij} } x_j^m + c_i\).
 
 

Algorithmus

  • Wähle \(\displaystyle x^0\)
  • Für \(\displaystyle m=0,1,\ldots\) berechne
    • Für \(\displaystyle i=1,2,\ldots,n\) berechne
\(\displaystyle x_i^{m + 1} = {\tilde a_{ii} } x_i^{m} + \sum\limits\limits_{j = 1}^{i - 1} {\tilde a_{ij} } x_j^{m + 1} + \sum\limits\limits_{j = i+1}^n {\tilde a_{ij} } x_j^m + c_i\).

Konsistenzbeweis

Die Widerspruchsfreiheit des Verfahrens wird folgendermaßen bewiesen: \(\displaystyle A\,=\,L+D+R\); \(\displaystyle M_\omega=(D+\omega\,L)^{-1}\,((1-\omega)\,D-\omega\,R)\) und \(\displaystyle N_\omega=\omega\,(D+\omega\,L)^{-1}\).
Zeige: \(\displaystyle x=A^{-1}\,b\) ist ein Fixpunkt von \(\displaystyle \Psi(x)=M_\omega\,x+N_\omega\,b\)
\(\displaystyle x=M_\omega\,x+N_\omega\,b\) \(\displaystyle \Leftrightarrow (D+\omega\,L)\,x\)\(\displaystyle =((1-\omega)\,D-\omega\,R)\,x+\omega\,(D+L+R)\,x\)\(\displaystyle =D\,x+\omega\,L\,x\) gilt für alle \(\displaystyle x\).

Seit die Mathematiker über die Relativitätstheorie hergefallen sind, verstehe ich sie selbst nicht mehr.

Albert Einstein

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel SOR-Verfahren aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе