imported>ConGreif: /* Jacobi-Varianten in HPC-Bibliotheken */

2026-04-30T10:27:40Z

Jacobi-Varianten in HPC-Bibliotheken

Neue Seite

{{Dieser Artikel|behandelt das Verfahren zum Lösen linearer Gleichungssysteme. Für das gleichnamige Verfahren zur Eigenwertberechnung siehe [[Jacobi-Verfahren (Eigenwerte)]].}}

In der [[numerische Mathematik|numerischen Mathematik]] ist das '''Jacobi-Verfahren''' (auch '''Jacobi-Iteration''' oder '''Gesamtschrittverfahren''' genannt), ein [[Algorithmus]] zur näherungsweisen Lösung von [[Lineares Gleichungssystem|linearen Gleichungssystemen]]. Es ist, wie das [[Gauß-Seidel-Verfahren]] und das [[SOR-Verfahren]], ein stationäres [[Splitting-Verfahren]] (äquivalent: eine vorkonditionierte [[Richardson-Iteration]]). Benannt ist es nach [[Carl Gustav Jacob Jacobi]].

Das Jacobi-Verfahren gehört zu den frühen iterativen Alternativen zu direkten Lösern wie [[Gaußsches Eliminationsverfahren|gaußsche Elimination]], welche zwar exakt sind jedoch für [[Rundungsfehler]] anfälliger. Bei iterativen Lösern hingegen wird die Lösung stabil schrittweise angenähert.

== Beschreibung des Verfahrens ==
Gegeben ist ein lineares Gleichungssystem mit <math>n</math> Variablen und <math>n</math> Gleichungen.
:<math>
\begin{matrix}
a_{11}\cdot x_1+\dotsb+a_{1n}\cdot x_n&=&b_1\\
a_{21}\cdot x_1+\dotsb+a_{2n}\cdot x_n&=&b_2\\
&\vdots&\\
a_{n1}\cdot x_1+\dotsb+a_{nn}\cdot x_n&=&b_n\\
\end{matrix}
</math>

Mit dem [[Matrix-Vektor-Produkt]] kann das [[Lineares Gleichungssystem|lineare Gleichungssystem]] auch als <math>A \cdot x = b</math> geschrieben werden, wobei die [[Matrix (Mathematik)|Matrix]] <math>A</math> die [[Koeffizientenmatrix]], <math>b</math> der Ergebnisvektor und <math>x</math> der gesuchte [[Vektor]] der Unbekannten <math>x_i</math> ist. Die ausführliche Schreibweise als [[Matrix (Mathematik)|Matrix]] und Vektoren mit den einzelnen Elementen wird üblicherweise wie folgt notiert:
:<math>\begin{pmatrix}
a_{11} & a_{12} & \cdots & a_{1n}\\
a_{21} & a_{22} & \cdots & a_{2n}\\
\vdots & \vdots & \ddots & \vdots\\
a_{n1} & a_{n2} & \cdots & a_{nn}\\
\end{pmatrix}
\begin{pmatrix} x_1\\ x_2 \\ \vdots \\ x_n\end{pmatrix}
=
\begin{pmatrix} b_1\\ b_2 \\ \vdots \\ b_n\end{pmatrix}</math>

Um dieses zu lösen, wird die <math>i</math>-te Gleichung nach der <math>i</math>-ten Variablen <math>x_i</math> aufgelöst,
:<math>x_i^{(m+1)}:=\frac1{a_{ii}}\left(b_i-\sum_{j\not=i} a_{ij}\cdot x_j^{(m)}\right), \, i=1,\dotsc,n</math>
und diese Ersetzung, ausgehend von einem [[Startvektor]] <math>x^{(0)}</math>, iterativ wiederholt. Als Bedingung für die Durchführbarkeit ergibt sich, dass die Diagonalelemente <math>a_{ii}</math> 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 [[Parallelrechner]]n geeignet.

Als [[Algorithmus]] in [[Pseudocode]] ergibt sich:
Gegeben Startvektor <math>x^\text{alt}</math>
für <math>m=1,\dotsc</math> bis Erfüllung eines Abbruchkriteriums
<math>x=b</math>
für <math>i=1</math> bis <math>n</math>
für <math>j=1</math> bis <math>n</math>
falls <math>j \not= i</math>
<math>x_i=x_i-a_{ij}x_j^\text{alt}</math>;
ende
<math>x_i=x_i/a_{ii}</math>;
ende
<math>x^\text{alt}=x;</math>
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ünnbesetzte Matrix|dünnbesetzten Matrizen]] reduziert sich der Aufwand des Verfahrens pro Iteration deutlich.

=== Beschreibung in Matrixschreibweise ===
Die Matrix <math>A</math> des linearen Gleichungssystems <math>A \cdot x = b</math> wird hierzu in eine [[Diagonalmatrix]] <math>D</math>, eine strikte untere [[Dreiecksmatrix]] <math>L </math> und eine strikte obere Dreiecksmatrix <math>U</math> zerlegt, so dass gilt:
:<math>A = D + (L + U)</math>

oder in ausführlicher Schreibweise mit den einzelnen Elementen der [[Matrix (Mathematik)|Matrizen]] wie folgt:
:<math>\begin{pmatrix}
a_{11} & a_{12} & \cdots & a_{1n}\\
a_{21} & a_{22} & \cdots & a_{2n}\\
\vdots & \vdots & \ddots & \vdots\\
a_{n1} & a_{n2} & \cdots & a_{nn}\\
\end{pmatrix}
=
\begin{pmatrix}
a_{11} & 0 & \cdots & 0\\
0 & a_{22} & \cdots & 0\\
\vdots & \vdots & \ddots & \vdots\\
0 & 0 & \cdots & a_{nn}\\
\end{pmatrix}
+
\begin{pmatrix}
0 & a_{12} & \cdots & a_{1n}\\
a_{21} & 0 & \cdots & a_{2n}\\
\vdots & \vdots & \ddots & \vdots\\
a_{n1} & a_{n2} & \cdots & 0\\
\end{pmatrix}</math>

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

:<math>x^{(m+1)} = D^{-1} \left( b - \left(L + U\right) x^{(m)} \right)</math>.

Üblich zur Einbettung als [[Vorkonditionierung|Präkonditionierer]] in andere iterative Verfahren wie [[Krylow-Unterraum-Verfahren]] schreibt man den Präkonditionierer als Matrix <math>M</math>, wobei <math>M</math> eine Approximation an <math>A^{-1}</math> ist, zu der sich ein lineares Gleichungssysteme <math>M^{-1} \cdot u = v</math> günstig nach <math>u</math> lösen lässt. Es gilt für das Jacobi-Verfahren <math>M = D^{-1}</math>. Für das Residuum <math>r^{(m)} = b - A \cdot x^{(m)}</math> ist <math> x^{(m+1)} - x^{(m)}</math> gerade die Näherungslösung. Die Beziehung <math>M = D^{-1}</math> folgt unmittelbar:

:<math>x^{(m+1)} = D^{-1} \cdot \left( b - \left(L + D + U\right) \cdot x^{(m)} + D \cdot x^{(m)} \right) = D^{-1} \cdot r^{(m)} + x^{(m)}</math>,
:<math> x^{(m+1)} - x^{(m)} = D^{-1} \cdot r^{(m)}</math>.

== Konvergenzuntersuchung ==
Die Konvergenz wird wie bei allen Splitting-Verfahren mittels des [[Fixpunktsatz von Banach|banachschen Fixpunktsatzes]] untersucht. Das Verfahren konvergiert also, wenn der [[Spektralradius]] der Iterationsmatrix <math>D^{-1}(D-A)</math> kleiner als eins ist. Insbesondere ergibt sich dies, wenn die Systemmatrix <math>A</math> [[Diagonaldominanz|strikt diagonaldominant]] oder allgemeiner [[Diagonaldominanz#Irreduzibel diagonaldominante Matrix|irreduzibel diagonaldominant]] ist.

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

:Für <math>k=1, \dotsc</math> bis Erfüllung eines Abbruchkriteriums
::Für <math>i=1,\dotsc,n</math>:
:::Löse <math>f_i(x_1^k,\dotsc, x^k_{i-1},x_i^{k+1},x_{i+1}^k,\dotsc,x_n^k) = g_i</math> nach <math>x_i^{k+1}</math> auf.

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.

== Jacobi-Varianten in HPC-Bibliotheken ==

In großen numerischen Anwendungen kann das klassische Jacobi-Verfahren wenig wirksam sein, wenn die auftretenden Matrizen zwar lokal fast diagonal strukturiert sind, die [[Diagonaldominanz]] aber schwach ist. Betrachtet man dagegen mehrere Freiheitsgrade gemeinsam als Punkt-Blöcke wird die Matrixstruktur besser erfasst.

Daher bezeichnet „Jacobi“ in HPC-Bibliotheken häufig nicht nur das Jacobi-Verfahren mit Punkt-Diagonalvorkonditionierung, sondern eine größere Familie Jacobi-artiger [[Vorkonditionierung|Vorkonditionierer]]. So unterscheidet [[PETSc]] unter anderem zwischen Jacobi (also Punkt-Jacobi), Punkt-Block-Jacobi, variablem Punkt-Block-Jacobi und Block-Jacobi. Dabei werden statt einzelner Diagonaleinträge kleine feste, variable oder größere diagonale Matrixblöcke exakt oder näherungsweise invertiert.

== Literatur ==
* A. Meister: ''Numerik linearer Gleichungssysteme'', 2. Auflage, Vieweg 2005, ISBN 3-528-13135-7
* R. Barrett et al.: [https://netlib.org/linalg/html_templates/Templates.html Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods], 2nd Edition, SIAM Philadelphia, 1994
* {{Literatur
|Autor=Plato, Robert
|Titel=Numerische Mathematik Kompakt
|Verlag=Vieweg
|Jahr=2004
|Seiten=262
|ISBN=3528131535
|Kommentar=
}}
* W. C. Rheinboldt: ''Methods for Solving Systems of Nonlinear Equations'', 2. Auflage, SIAM, 1998, ISBN 0-89871-415-X

== Weblinks ==
* [https://mathworld.wolfram.com/JacobiMethod.html Eric W. Weisstein et al. „Jacobi Method“] MathWorld
* {{Internetquelle|url=https://www.informatik-forum.at/attachment.php?attachmentid=15906&d=1261478854|titel= Gesamt- und Einzelschrittverfahren bzw. Jacobi- und Gauss-Seidel-Verfahren für N = 3 |offline=2021-02-10 |archiv-url=https://web.archive.org/web/20180624204711/https://www.informatik-forum.at/attachment.php?attachmentid=15906&d=1261478854 |archiv-datum=2018-06-24 |abruf=2021-02-10 |format=PDF; 90 kB|sprache=de-DE |abruf-verborgen=1}} Jacobi und Gauss-Seidel-Verfahren verständlich erklärt, inklusive Matlab-Programme.

{{SORTIERUNG:Jacobiverfahren}}
[[Kategorie:Numerische lineare Algebra]]
[[Kategorie:Carl Gustav Jacob Jacobi als Namensgeber]]

Jacobi-Verfahren - Versionsgeschichte

imported>ConGreif: /* Jacobi-Varianten in HPC-Bibliotheken */