Wir möchten ein LGS Ax=b:
$$ \begin{pmatrix} a_{11} & \dotsm & a_{12} \\ \vdots & & \vdots \\ a_{n1} & \dotsm & a_{nn} \end{pmatrix} \begin{pmatrix} x_1 \\\vdots\\x_n \end{pmatrix} = \begin{pmatrix} b_1\\\vdots\\b_n \end{pmatrix} $$
iterativ lösen. Schau dir mal an wie die Komponenten von b bei der Multiplikation von Ax zustande kommen:
$$ b_1 = a_{11} x_1 + \dotsm + a_{1n}x_n $$ ...
$$ b_i = a_{i1} x_1 + \dotsm + a_{in}x_n $$ ...
$$ b_n = a_{n1} x_1 + \dotsm + a_{nn}x_n $$
Also wohl
$$ b_i = \sum_{j=0}^n a_{ij} x_j = a_{ii} x_i + \sum_{\substack{j=0\\j\neq i}}^n a_{ji} x_j\quad \forall i=1,...,n $$
Die Idee von Jacobi ist jetzt: Falls \( a_{ii} \neq 0~ \forall i \) dann ist das äquivalent zu
$$ x_i = \frac{1}{a_{ii}} \left( b_i - \sum_{\substack{j=0\\j\neq i}}^n a_{ji} x_j \right) \quad \forall i=1,...,n $$
Und jetzt iterieren wir einfach:
$$ x_i^{t+1} = \frac{1}{a_{ii}} \left( b_i - \sum_{\substack{j=0\\j\neq i}}^n a_{ji} x_j^{t} \right) \quad \forall i=1,...,n $$
Das heißt, wenn du z.B. \( x_7^5 \) berechnest, verwendest du alle \( x_i^4 \) mit \( i \neq 7 \).
--------
Es stellt sich jetzt natürlich die Frage, ob es nicht sinnvoller ist, z.B. \( x_1^5,...,x_6^5 \) (die kennst du ja schon, da du sie davor berechnet hast) und sonst \(x_i^4 \) für \( i > 7 \) zu verwenden. Also in einer Gleichung ausgedrückt:
$$ x_i^{t+1} = \frac{1}{a_{ii}} \left( b_i - \sum_{\substack{j<i}} a_{ji} x_j^{t+1} - \sum_{\substack{j>i}} a_{ji} x_j^{t} \right) \quad \forall i=1,...,n $$
Und das ist die Idee von Gauß-Seidel. Wir verwenden anders als beim Jacobi-Verfahren immer den aktuellsten Iterationswert der uns vorliegt. In unserem Beispiel also z.B. \( x_1^5 \) statt \( x_1^4 \).
-------
Für das SOR-Verfahren wählen wir uns einen Relaxationsparameter \( \omega \ge 1 \) und bauen damit jetzt auf Gauß-Seidel auf:
$$ \tilde{x}_i^{t+1} = \frac{1}{a_{ii}} \left( b_i - \sum_{\substack{j<i}} a_{ji} x_j^{t+1} - \sum_{\substack{j>i}} a_{ji} x_j^{t} \right), \\ x_i^{t+1} = \omega \tilde{x}_i^t + (1-\omega) x_i^{t-1},\quad \forall i=1,...,n $$
das heißt wir berechnen eine Linearkombination aus dem Gauß-Seidel Ergebnis und dem Ergebnis aus dem letzten Iterationsschritt. Für \( \omega = 1 \) unterscheidet sich das Verfahren deshalb auch nicht vom Gauß-Seidel-Verfahren.
---------------
Fazit:
Jacobi: eigentlich ziemlich straightforward.
Gauß-Seidel: Wir wollen das Jacobi-Verfahren beschleunigen, indem wir stets die aktuellsten Iterationsergebnisse verwenden.
SOR-Vefahren: Wir möchten das Gauß-Seidel durch die Bildung von Linearkombinationen beschleunigen.
