SOR-Verfahren

aus Wikipedia, der freien Enzyklopädie

Das Successive Over-Relaxation-Verfahren 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 ( vgl. A = B + (A − B) mit B = (1/ $ω$ )D + L ).

Gegeben ist ein lineares Gleichungssystem $A x = b$ mit n Variablen mit n Gleichungen.

$\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 $\tilde A = (\tilde a_{ij} )$ mit $\tilde a_{ij} = { - \frac{{a_{ij} }}{{a_{ii} }}w}$ falls $i \ne j$ , bzw. $\tilde a_{ij}=1-w$ falls $i = j$ und den Vektor $c_i = \frac{{b_i }}{{a_{ii} }}w$ mit $i=1,2,\ldots,n$ . Dabei ist $w$ ein reeller Überrelaxationsparameter. Für $w = 1$ erhält man wieder ein Einzelschrittverfahren. Das Verfahren konvergiert für jedes $w \in (0,2)$ , falls A symmetrisch positiv definit ist. Um das Gleichungssystem zu lösen, wird die i-te Gleichung nach der i-ten Variable x_i aufgelöst,

$x_i^{m + 1} = \sum\limits_{j = 1}^{i - 1} {\tilde a_{ij} } x_j^{m + 1} + \sum\limits_{j = i + 1}^n {\tilde a_{ij} } x_j^m + c_i$ .

[Bearbeiten] Algorithmus

Wähle $x 0$
Für berechne
- Für $i=1,2,\ldots,n$ berechne

$x_i^{m + 1} = {\tilde a_{ii} } x_i^{m} + \sum\limits_{j = 1}^{i - 1} {\tilde a_{ij} } x_j^{m + 1} + \sum\limits_{j = i+1}^n {\tilde a_{ij} } x_j^m + c_i$ .

[Bearbeiten] Konsistenzbeweis

Die Widerspruchsfreiheit des Verfahrens wird folgendermaßen bewiesen: $A\,=\,L+D+R$
$M_\omega=(D+\omega\,L)^{-1}\,((1-\omega)\,D-\omega\,R)$
$N_\omega=\omega\,(D+\omega\,L)^{-1}$