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 Ax=bAx=b. Es ist, wie das Gauß-Seidel-Verfahren und das Jacobi-Verfahren, ein spezielles Splitting-Verfahren.
Gegeben ist ein lineares Gleichungssystem mit nn Variablen mit nn Gleichungen.
a1;1⋅x1+⋯+a1;n⋅xn=b1a2;1⋅x1+⋯+a2;n⋅xn=b2⋮an;1⋅x1+⋯+an;n⋅xn=bn \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 A~=(a~ij)\tilde A = (\tilde a_{ij} ) mit a~ij=−aijaiiw\tilde a_{ij} = { - \dfrac{ {a_{ij} }}{a_{ii} } w} falls i≠ji \ne j, bzw. a~ij=1−w\tilde a_{ij}=1-w falls i=ji = j und den Vektor ci=biaiiwc_i = \dfrac{ {b_i }}{a_{ii} }w mit i=1,2,…,ni=1,2,\ldots,n. Dabei ist ww ein reeller Überrelaxationsparameter. Für w=1w=1 erhält man wieder ein Einzelschrittverfahren. Das Verfahren konvergiert für jedes w∈]0,2[w \in ]0,2[, falls AA symmetrisch positiv definit ist. Um das Gleichungssystem zu lösen, wird die ii-te Gleichung nach der ii-ten Variable xix_{i} aufgelöst,
xim+1=∑j=1i−1a~ijxjm+1+∑j=i+1na~ijxjm+cix_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 x0x^0
  • Für m=0,1,…m=0,1,\ldots berechne
    • Für i=1,2,…,ni=1,2,\ldots,n berechne
xim+1=a~iixim+∑j=1i−1a~ijxjm+1+∑j=i+1na~ijxjm+cix_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: A = L+D+RA\,=\,L+D+R; Mω=(D+ω L)−1 ((1−ω) D−ω R)M_\omega=(D+\omega\,L)^{-1}\,((1-\omega)\,D-\omega\,R) und Nω=ω (D+ω L)−1N_\omega=\omega\,(D+\omega\,L)^{-1}.
Zeige: x=A−1 bx=A^{-1}\,b ist ein Fixpunkt von Ψ(x)=Mω x+Nω b\Psi(x)=M_\omega\,x+N_\omega\,b
x=Mω x+Nω bx=M_\omega\,x+N_\omega\,b ⇔(D+ω L) x\Leftrightarrow (D+\omega\,L)\,x=((1−ω) D−ω R) x+ω (D+L+R) x =((1-\omega)\,D-\omega\,R)\,x+\omega\,(D+L+R)\,x=D x+ω L x =D\,x+\omega\,L\,x gilt für alle xx.
 
 

So kann also die Mathematik definiert werden als diejenige Wissenschaft, in der wir niemals das kennen, worüber wir sprechen, und niemals wissen, ob das, was wir sagen, wahr ist.

Bertrand Russell

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е
Datenschutzerklärung

 

Lineare Gleichungssysteme