Jacobi-Verfahren

In d​er numerischen Mathematik i​st das Jacobi-Verfahren, a​uch Gesamtschrittverfahren genannt, e​in Algorithmus z​ur näherungsweisen Lösung v​on linearen Gleichungssystemen. Es ist, w​ie das Gauß-Seidel-Verfahren u​nd das SOR-Verfahren, e​in spezielles Splitting-Verfahren. Benannt i​st es n​ach Carl Gustav Jacob Jacobi.

Entwickelt w​urde das Verfahren, d​a das Gaußsche Eliminationsverfahren z​war eine exakte Lösungsvorschrift darstellt, s​ich jedoch für Rechenfehler s​ehr anfällig zeigt. Eine iterative Vorgehensweise h​at diesen Nachteil typischerweise nicht.

Beschreibung des Verfahrens

Gegeben ist ein lineares Gleichungssystem mit ${\displaystyle n}$ Variablen und ${\displaystyle n}$ Gleichungen.

${\displaystyle {\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}}}$

Mit dem Matrix-Vektor-Produkt kann das lineare Gleichungssystem auch als ${\displaystyle A\cdot x=b}$ geschrieben werden, wobei die Matrix ${\displaystyle A}$ die Koeffizientenmatrix, ${\displaystyle b}$ der Ergebnisvektor und ${\displaystyle x}$ der gesuchte Vektor der Unbekannten ${\displaystyle x_{i}}$ ist. Die ausführliche Schreibweise als Matrix und Vektoren mit den einzelnen Elementen wird üblicherweise wie folgt notiert:

${\displaystyle {\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}}}$

Um dieses zu lösen, wird die ${\displaystyle i}$-te Gleichung nach der ${\displaystyle i}$-ten Variablen ${\displaystyle x_{i}}$ aufgelöst,

${\displaystyle x_{i}^{(m+1)}:={\frac {1}{a_{ii}}}\left(b_{i}-\sum _{j\not =i}a_{ij}\cdot x_{j}^{(m)}\right),\,i=1,\dotsc ,n}$

und diese Ersetzung, ausgehend von einem Startvektor ${\displaystyle x^{(0)}}$, iterativ wiederholt. Als Bedingung für die Durchführbarkeit ergibt sich, dass die Diagonalelemente ${\displaystyle 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 Algorithmus i​n Pseudocode ergibt sich:

Gegeben Startvektor ${\displaystyle x^{\text{alt}}}$
für ${\displaystyle m=1,\dotsc }$ bis Erfüllung eines Abbruchkriteriums
  ${\displaystyle x=b}$
  für ${\displaystyle i=1}$ bis ${\displaystyle n}$
       für ${\displaystyle j=1}$ bis ${\displaystyle n}$
         falls ${\displaystyle j\not =i}$
            ${\displaystyle x_{i}=x_{i}-a_{ij}x_{j}^{\text{alt}}}$;
       ende
       ${\displaystyle x_{i}=x_{i}/a_{ii}}$;
  ende
  ${\displaystyle x^{\text{alt}}=x;}$
ende

Dabei w​urde die willkürliche Erstbelegung d​es Variablenvektors a​ls Eingangsgrößen d​es Algorithmus angenommen, d​ie Näherungslösung i​st die vektorielle Rückgabegröße.

Bei dünnbesetzten Matrizen reduziert s​ich der Aufwand d​es Verfahrens p​ro Iteration deutlich.

Beschreibung in Matrixschreibweise

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

${\displaystyle A=D+(L+U)}$

oder i​n ausführlicher Schreibweise m​it den einzelnen Elementen d​er Matrizen w​ie folgt:

${\displaystyle {\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}}}$

Die o​bige komponentenweise Iterationsvorschrift lässt s​ich dann folgendermaßen für d​en kompletten Vektor darstellen:

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

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

${\displaystyle 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)}}$,

${\displaystyle x^{(m+1)}-x^{(m)}=D^{-1}\cdot r^{(m)}}$.

Konvergenzuntersuchung

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

Erweiterung auf nichtlineare Gleichungssysteme

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

Für ${\displaystyle k=1,\dotsc }$ bis Erfüllung eines Abbruchkriteriums

Für ${\displaystyle i=1,\dotsc ,n}$:

Löse ${\displaystyle f_{i}(x_{1}^{k},\dotsc ,x_{i-1}^{k},x_{i}^{k+1},x_{i+1}^{k},\dotsc ,x_{n}^{k})=g_{i}}$ nach ${\displaystyle x_{i}^{k+1}}$ auf.

Hierbei i​st das Lösen i​n der Regel a​ls die Anwendung e​ines weiteren iterativen Verfahrens z​ur Lösung nichtlinearer Gleichungen z​u verstehen. Um dieses Verfahren v​om Jacobi-Verfahren für lineare Gleichungssysteme z​u unterscheiden, w​ird häufig v​om Jacobi-Prozess gesprochen. Die Konvergenz d​es Prozesses f​olgt aus d​em Banachschen Fixpunktsatz wieder a​ls 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 3-528-13153-5, 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; 90 kB) (Nicht mehr online verfügbar.) Archiviert vom Original am 24. Juni 2018 (deutsch). Jacobi und Gauss-Seidel-Verfahren verständlich erklärt, inklusive Matlab-Programme.