Jacobi-Verfahren

In der numerischen Mathematik ist das Jacobi-Verfahren, auch Gesamtschrittverfahren genannt, ein Algorithmus zur näherungsweisen Lösung von linearen Gleichungssystemen Ax = b. Es ist, wie das Gauß-Seidel-Verfahren und das SOR-Verfahren, ein spezielles Splitting-Verfahren. Benannt ist es nach Carl Gustav Jakob Jacobi.

Entwickelt wurde das Verfahren, da das Gaußsche Eliminationsverfahren zwar eine exakte Lösungsvorschrift darstellt, sich jedoch für Rechenfehler sehr anfällig zeigt. Eine iterative Vorgehensweise hat diesen Nachteil typischerweise nicht.

Beschreibung des Verfahrens

Gegeben ist ein lineares Gleichungssystem mit n Variablen mit n Gleichungen.

$\begin{matrix} a_{11}\cdot x_1+\dots+a_{1n}\cdot x_n&=&b_1\\ a_{21}\cdot x_1+\dots+a_{2n}\cdot x_n&=&b_2\\ &\vdots&\\ a_{n1}\cdot x_1+\dots+a_{nn}\cdot x_n&=&b_n\\ \end{matrix}$

Um dieses zu lösen, wird die i-te Gleichung nach der i-ten Variablen x_i aufgelöst,

$x_i^{(m+1)}:=\frac1{a_{ii}}\left(b_i-\sum_{j\not=i} a_{ij}\cdot x_j^{(m)}\right), \, i=1,...,n$

und diese Ersetzung, ausgehend von einer willkürlichen Startbelegung x⁽⁰⁾ der Variablen, periodisch wiederholt. Als Bedingung für die Durchführbarkeit ergibt sich, dass die Diagonalelemente a_ii von Null verschieden sein müssen. Da die Berechnung einer Komponente der nächsten Näherung unabhängig von den anderen Komponenten ist, ist das Verfahren, im Gegensatz zum Gauß-Seidel-Verfahren, zur Nutzung auf Parallelrechnern geeignet.

Als Algorithmusskizze mit c Iterationen und n Zeilen bzw. Spalten ergibt sich:

für m = 1 bis c
  für i = 1 bis n
    xi = 0
       für j = 1 bis n
         falls $j \not= i$
            $x_i=x_i+a_{ij}x_j^{(m-1)}$;
       ende
       xi = (bi − xi) / aii;
  ende
  x(m) = x;
ende

Dabei wurde die willkürliche Erstbelegung des Variablenvektors als Eingangsgrößen des Algorithmus angenommen, die Näherungslösung ist die vektorielle Rückgabegröße.

Bei dünnbesetzten Matrizen reduziert sich der Aufwand des Verfahrens pro Iteration deutlich.

Beschreibung in Matrixschreibweise

Die Matrix A des linearen Gleichungssystems $A \cdot x = b$ wird hierzu in eine Diagonalmatrix D, eine strikte untere Dreiecksmatrix L und eine strikte obere Dreiecksmatrix U zerlegt, so dass gilt:

A = L + D + U.

Die obige komponentenweise Iterationsvorschrift lässt sich dann folgendermaßen für den kompletten Vektor darstellen:

$x^{(m+1)} = D^{-1} \left( b - \left(L + U\right) x^{(m)} \right)$.

Konvergenzuntersuchung

Die Konvergenz wird wie bei allen Splitting-Verfahren mittels des banachschen Fixpunktsatzes untersucht. Das Verfahren konvergiert also, wenn der Spektralradius der Iterationsmatrix D ^{− 1}(D − A) kleiner als eins ist. Insbesondere ergibt sich dies, wenn die Systemmatrix A strikt diagonaldominant ist.

Erweiterung auf nichtlineare Gleichungssysteme

Die Idee des Jacobi-Verfahrens lässt sich auf nichtlineare Gleichungssysteme f(x) = g mit einer mehrdimensionalen nichtlinearen Funktion f erweitern. Wie im linearen Fall wird im i-ten Schritt die i-te Gleichung bezüglich der i-ten Variablen gelöst, wobei für die anderen Variablen der bisherige Näherungswert genommen wird:

Für k=1,... bis zur Konvergenz

Für i=1,...,n:

Löse $f_i(x_1^k,\ldots, x^k_{i-1},x_i^{k+1},x_{i+1}^k,...,x_n^k)$ nach $x_i^{k+1}$.

Hierbei ist das Lösen in der Regel als die Anwendung eines weiteren iterativen Verfahrens zur Lösung nichtlinearer Gleichungen zu verstehen. Um dieses Verfahren vom Jacobi-Verfahren für lineare Gleichungssysteme zu unterscheiden, wird häufig vom Jacobi-Prozess gesprochen. Die Konvergenz des Prozesses folgt aus dem Banachschen Fixpunktsatz wieder als linear.

Literatur

• A. Meister: Numerik linearer Gleichungssysteme, 2. Auflage, Vieweg 2005, ISBN 3528131357
• R. Barrett et al.: Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd Edition, SIAM Philadelphia, 1994
• Plato, Robert: Numerische Mathematik Kompakt. Vieweg, 2004, ISBN 3528131535, S. 262.
• W. C. Rheinboldt: Methods for Solving Systems of Nonlinear Equations, 2. Auflage, SIAM, 1998, ISBN 089871415X

Weblinks

• Eric W. Weisstein et al. "Jacobi Method" MathWorld
• Gesamt- und Einzelschrittverfahren bzw. Jacobi- und Gauss-Seidel-Verfahren für N = 3 (pdf) Jacobi und Gauss-Seidel-Verfahren verstaendlich erklaert, inklusive Matlab Programme.