Gauß-Seidel-Verfahren

Studium

x_i^{(k+1)} = \frac{1}{a_{ii}} \Bigl( b_i - \sum_{j < i} a_{ij}\,x_j^{(k+1)} - \sum_{j > i} a_{ij}\,x_j^{(k)} \Bigr)

Voraussetzung: $A x = b,$ $a_{ii} \neq 0,$ $i = 1, \ldots, n$

$x_i^{(k)}$: i-te Komponente der Näherung nach k Schritten
$a_{ij}$: Einträge der Koeffizientenmatrix A
$a_{ii}$: Diagonaleinträge von A
$b_i$: Komponenten der rechten Seite b
$n$: Anzahl der Gleichungen und Unbekannten

Das Gauß-Seidel-Verfahren arbeitet wie das Jacobi-Verfahren, verwendet neu berechnete Komponenten aber sofort weiter.

Erklärung

Das Gauß-Seidel-Verfahren (auch Einzelschrittverfahren) löst ein lineares Gleichungssystem $Ax = b$ iterativ. Wie beim Jacobi-Verfahren löst man die $i$ -te Gleichung nach $x_i$ auf. Für die Komponenten $x_1, \ldots, x_{i-1}$ , die im aktuellen Schritt schon neu berechnet wurden, setzt man aber sofort die neuen Werte ein.

Mit $A = D + L + R$ (Diagonale, strikt unteres und strikt oberes Dreieck) lautet ein Schritt

(D + L)\,x^{(k+1)} = b - R\,x^{(k)}

Man löst also in jedem Schritt ein Dreieckssystem, was durch Vorwärtseinsetzen von oben nach unten geschieht.

Konvergenz:

Hinreichend ist, dass $A$ strikt diagonaldominant ist oder symmetrisch positiv definit.
Notwendig und hinreichend ist ein Spektralradius der Iterationsmatrix $-(D + L)^{-1} R$ kleiner als $1$ .
Konvergieren beide Verfahren, ist Gauß-Seidel oft schneller als Jacobi. Nur für konsistent geordnete Matrizen (z.B. tridiagonale Matrizen mit $a_{ii} \neq 0$ ) gilt $\rho_{\text{GS}} = \rho_{\text{J}}^2$ . Dann braucht Gauß-Seidel für dieselbe Genauigkeit etwa halb so viele Schritte. Allgemein gibt es keinen solchen Zusammenhang.

Ein Nachteil: Die Komponenten hängen voneinander ab, das Verfahren lässt sich schlechter parallelisieren. Außerdem hängt das Ergebnis eines Schritts von der Reihenfolge der Gleichungen ab.

Beispiele

Dasselbe System wie beim Jacobi-Verfahren, $4x_1 + x_2 = 6$ , $x_1 + 3x_2 = 7$ , mit Lösung $(1, 2)$ :

x_1^{(k+1)} = \frac{6 - x_2^{(k)}}{4}, \qquad x_2^{(k+1)} = \frac{7 - x_1^{(k+1)}}{3}

Ab $x^{(0)} = (0, 0)$ :

$k$	$x_1^{(k)}$	$x_2^{(k)}$
1	1,5	1,8333
2	1,0417	1,9861
3	1,0035	1,9988

Nach drei Schritten ist der Fehler in $x_1$ etwa $0{,}0035$ , beim Jacobi-Verfahren noch $0{,}0417$ . Der Spektralradius ist hier $\frac{1}{12} \approx 0{,}0833$ , das Quadrat des Jacobi-Wertes $\sqrt{1/12}$ . Die Matrix ist tridiagonal, die Beziehung $\rho_{\text{GS}} = \rho_{\text{J}}^2$ gilt also.

Typische Fehler

Doch die alten Werte verwenden und damit versehentlich das Jacobi-Verfahren rechnen.
Die Reihenfolge der Gleichungen ändern, ohne zu prüfen, ob die Diagonaleinträge dann noch passen. Ein Zeilentausch kann Diagonaldominanz herstellen oder zerstören.
Annehmen, Gauß-Seidel konvergiere immer, wenn Jacobi konvergiert. Das gilt für viele, aber nicht für alle Matrizen.
Bei $a_{ii} = 0$ rechnen. Dann ist die Vorschrift nicht definiert.

Gauß-Seidel-Verfahren