Jacobi-Verfahren

Studium

x_i^{(k+1)} = \frac{1}{a_{ii}} \Bigl( b_i - \sum_{j \neq 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 Jacobi-Verfahren löst jede Gleichung nach ihrer Diagonalvariablen auf und setzt die alte Näherung für alle anderen ein.

Erklärung

Das Jacobi-Verfahren (auch Gesamtschrittverfahren) löst ein lineares Gleichungssystem $Ax = b$ iterativ. Man löst die $i$ -te Gleichung nach $x_i$ auf und setzt rechts die Werte aus dem vorigen Schritt ein. Alle Komponenten des neuen Vektors werden also gleichzeitig aus dem alten berechnet.

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

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

Konvergenz:

Das Verfahren konvergiert für jeden Startwert genau dann, wenn der Spektralradius der Iterationsmatrix $-D^{-1}(L + R)$ kleiner als $1$ ist. Er bestimmt auch, wie schnell der Fehler schrumpft.
Hinreichend und leicht zu prüfen ist strikte Diagonaldominanz: In jeder Zeile ist $|a_{ii}|$ größer als die Summe der Beträge der übrigen Einträge.

Iterative Verfahren lohnen sich vor allem bei großen, dünn besetzten Matrizen, bei denen das Gauß-Verfahren zu viel Speicher und Rechenzeit braucht. Da jede Komponente unabhängig berechnet wird, lässt sich das Jacobi-Verfahren gut parallelisieren.

Beispiele

Das System

4x_1 + x_2 = 6, \qquad x_1 + 3x_2 = 7

hat die Lösung $x_1 = 1$ , $x_2 = 2$ . Die Matrix ist strikt diagonaldominant ( $4 > 1$ , $3 > 1$ ). Die Iterationsvorschrift lautet

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

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

$k$	$x_1^{(k)}$	$x_2^{(k)}$
1	1,5	2,3333
2	0,9167	1,8333
3	1,0417	2,0278

Die Iterationsmatrix hat die Eigenwerte $\pm\sqrt{1/12} \approx \pm 0{,}2887$ . Der Fehler schrumpft also pro Schritt etwa auf das $0{,}29$ -Fache.

Typische Fehler

Neu berechnete Komponenten schon im selben Schritt verwenden. Das ist das Gauß-Seidel-Verfahren, nicht Jacobi.
Das Verfahren bei einer Null auf der Diagonalen anwenden. Vorher Zeilen tauschen.
Aus fehlender Diagonaldominanz schließen, dass das Verfahren divergiert. Diagonaldominanz ist hinreichend, aber nicht notwendig.
Nach einer festen Zahl von Schritten abbrechen, ohne das Residuum $\|b - Ax^{(k)}\|$ oder die Änderung zwischen zwei Schritten zu prüfen.

Jacobi-Verfahren