Jacobi-Verfahren

Grundidee und Bedeutung

Das Jacobi-Verfahren, auch Jacobi-Iteration oder Gesamtschrittverfahren genannt, ist ein Algorithmus zur näherungsweisen Lösung linearer Gleichungssysteme. Es gehört wie das Gauß-Seidel- und das SOR-Verfahren zu den stationären Splitting-Verfahren und kann gleichwertig als vorkonditionierte Richardson-Iteration aufgefasst werden.

Im Unterschied zu direkten Lösungsverfahren wie der gaußschen Elimination nähert ein iteratives Verfahren die Lösung schrittweise an. Ausgangspunkt ist ein frei wählbarer Startvektor; daraus werden wiederholt neue Näherungsvektoren berechnet, bis ein festgelegtes Abbruchkriterium erfüllt ist. Das Jacobi-Verfahren ist besonders gut parallelisierbar, weil alle Komponenten einer neuen Näherung unabhängig voneinander aus den Komponenten der vorherigen Näherung berechnet werden können. Bei dünnbesetzten Matrizen, also Matrizen mit vielen Nulleinträgen, sinkt zudem der Rechenaufwand pro Iteration deutlich.

Komponentenweise Berechnung

Gegeben ist ein lineares Gleichungssystem mit n Gleichungen und n Variablen. In kompakter Form lautet es A·x = b. Dabei ist A die Koeffizientenmatrix, x der gesuchte Vektor mit den Unbekannten x₁, …, xₙ und b der Ergebnisvektor.

Für die Iteration wird die i-te Gleichung nach der i-ten Variablen xᵢ aufgelöst. Aus dem Näherungsvektor x⁽ᵐ⁾ entsteht die nächste Näherung nach der Vorschrift

xᵢ⁽ᵐ⁺¹⁾ := (1/aᵢᵢ) · (bᵢ − Σⱼ≠ᵢ aᵢⱼ·xⱼ⁽ᵐ⁾), i = 1, …, n.

Für jede neue Komponente werden somit ausschließlich Werte aus der alten Iteration m eingesetzt. Das unterscheidet das Jacobi-Verfahren vom Gauß-Seidel-Verfahren, das bereits neu berechnete Komponenten sofort weiterverwendet. Damit die Division möglich ist, müssen alle Diagonalelemente aᵢᵢ von null verschieden sein.

Der Ablauf beginnt mit einem Startvektor x⁽⁰⁾. In jeder Iteration wird für jede Zeile zunächst von bᵢ die Summe aller Nichtdiagonalanteile aᵢⱼxⱼ der alten Näherung abgezogen. Anschließend wird durch aᵢᵢ geteilt. Erst nachdem sämtliche neuen Komponenten berechnet wurden, ersetzt der neue Vektor den alten. Die Wiederholung endet, sobald das gewählte Abbruchkriterium erfüllt ist; die letzte Näherung wird als Ergebnis ausgegeben.

Matrixform und Vorkonditionierung

Für die Matrixdarstellung wird A in drei Teile zerlegt:

A = D + (L + U).

D ist die Diagonalmatrix mit den Einträgen a₁₁, …, aₙₙ. L ist die strikte untere Dreiecksmatrix und U die strikte obere Dreiecksmatrix; „strikt“ bedeutet, dass ihre Diagonaleinträge null sind. Die vollständige Jacobi-Iteration lautet dann

x⁽ᵐ⁺¹⁾ = D⁻¹(b − (L + U)x⁽ᵐ⁾).

Das Verfahren kann außerdem als Vorkonditionierung anderer iterativer Methoden, etwa von Krylow-Unterraum-Verfahren, verwendet werden. Ein Präkonditionierer M ist dabei eine günstig anwendbare Approximation an A⁻¹. Für das Jacobi-Verfahren gilt M = D⁻¹.

Mit dem Residuum r⁽ᵐ⁾ = b − A·x⁽ᵐ⁾, das die Abweichung der aktuellen Näherung vom Gleichungssystem beschreibt, lässt sich die Iteration umformen zu

x⁽ᵐ⁺¹⁾ = D⁻¹r⁽ᵐ⁾ + x⁽ᵐ⁾

und damit

x⁽ᵐ⁺¹⁾ − x⁽ᵐ⁾ = D⁻¹r⁽ᵐ⁾.

Die Änderung des Näherungsvektors ist also die mit der inversen Diagonalmatrix skalierte Näherungslösung zum Residuum.

Konvergenz

Die Konvergenz wird wie bei anderen Splitting-Verfahren mit dem Banachschen Fixpunktsatz untersucht. Das Jacobi-Verfahren konvergiert, wenn der Spektralradius der Iterationsmatrix D⁻¹(D − A) kleiner als eins ist. Der Spektralradius ist der größte Betrag der Eigenwerte einer Matrix.

Eine insbesondere ausreichende Bedingung ist, dass die Systemmatrix A strikt diagonaldominant ist: In jeder Zeile ist dann der Betrag des Diagonaleintrags größer als die Summe der Beträge aller übrigen Einträge dieser Zeile. Allgemeiner genügt auch eine irreduzibel diagonaldominante Matrix. Sind solche Voraussetzungen nicht erfüllt, ist die Konvergenz des klassischen Verfahrens nicht allgemein gewährleistet.

Nichtlineare Gleichungssysteme

Die Grundidee lässt sich auf nichtlineare Gleichungssysteme f(x) = g übertragen, wobei f eine mehrdimensionale nichtlineare Funktion ist. Für jede Variable wird die zugehörige Gleichung gelöst, während für alle anderen Variablen die Werte der bisherigen Näherung verwendet werden. In der k-ten Iteration wird für i = 1, …, n die Gleichung

fᵢ(x₁ᵏ, …, xᵢ₋₁ᵏ, xᵢᵏ⁺¹, xᵢ₊₁ᵏ, …, xₙᵏ) = gᵢ

nach xᵢᵏ⁺¹ aufgelöst. Dieses Auflösen erfordert in der Regel selbst ein weiteres iteratives Verfahren für nichtlineare Gleichungen. Zur Unterscheidung vom linearen Jacobi-Verfahren wird diese Variante häufig Jacobi-Prozess genannt. Seine Konvergenz folgt ebenfalls aus dem Banachschen Fixpunktsatz und ist linear.

Varianten für große Rechnungen

In großen numerischen Anwendungen, dem High Performance Computing (HPC), kann das klassische Jacobi-Verfahren wenig wirksam sein. Das gilt besonders, wenn eine Matrix zwar lokal fast diagonal aufgebaut ist, aber nur schwach diagonaldominant ist. Werden mehrere zusammengehörige Freiheitsgrade gemeinsam als Blöcke betrachtet, lässt sich die Matrixstruktur besser berücksichtigen.

Der Name „Jacobi“ bezeichnet in HPC-Bibliotheken deshalb häufig eine ganze Familie Jacobi-artiger Vorkonditionierer. PETSc unterscheidet unter anderem:

• Jacobi beziehungsweise Punkt-Jacobi,
• Punkt-Block-Jacobi,
• variables Punkt-Block-Jacobi,
• Block-Jacobi.

Während Punkt-Jacobi einzelne Diagonaleinträge verwendet, arbeiten die Blockvarianten mit kleinen festen, variablen oder größeren diagonalen Matrixblöcken. Diese Blöcke werden exakt oder näherungsweise invertiert. Dadurch können Kopplungen zwischen mehreren Freiheitsgraden erfasst werden, die bei einer reinen Punkt-Diagonalvorkonditionierung unberücksichtigt bleiben.