Jacobi-Verfahren

In der numerischen Mathematik ist das Jacobi-Verfahren, auch Gesamtschrittverfahren genannt, (benannt nach Carl Gustav Jakob Jacobi) ein Algorithmus zur näherungsweisen Lösung von linearen Gleichungssystemen Ax=bAx=b. Es ist, wie das Gauß-Seidel-Verfahren und das SOR-Verfahren, ein spezielles Splitting-Verfahren.
Entwickelt wurde das Verfahren, da das Gaußsche Eliminationsverfahren zwar eine exakte Lösungsvorschrift ist, sich für Rechenfehler jedoch sehr anfällig zeigt. Eine iterative Vorgehensweise hat diesen Nachteil typischerweise nicht.

Beschreibung des Verfahrens

Gegeben ist ein lineares Gleichungssystem mit nn Variablen mit nn Gleichungen.
a1;1⋅x1+⋯+a1;n⋅xn=b1a2;1⋅x1+⋯+a2;n⋅xn=b2⋮an;1⋅x1+⋯+an;n⋅xn=bn \begin{matrix} a_{1;1}\cdot x_1+\dots+a_{1;n}\cdot x_n&=&b_1\\ a_{2;1}\cdot x_1+\dots+a_{2;n}\cdot x_n&=&b_2\\ &\vdots&\\ a_{n;1}\cdot x_1+\dots+a_{n;n}\cdot x_n&=&b_n\\ \end{matrix}
Um dieses zu lösen, wird die ii-te Gleichung nach der ii-ten Variablen xix_i aufgelöst,
xi(m+1):=1ai;i(bi−∑j¬=iai,j⋅xj(m))x_i^{(m+1)}:=\dfrac1{a_{i;i}}\left(b_i-\sum\limits_{j\not=i} a_{i,j}\cdot x_j^{(m)}\right),
und diese Ersetzung, ausgehend von einer willkürlichen Startbelegung x(0)x^{(0)} der Variablen, periodisch wiederholt. Als minimale Bedingung lässt sich hier festhalten, dass die Diagonalelemente ai;ia_{i;i} von Null verschieden sein müssen. Für die Konvergenz des Verfahrens ist die strikte Diagonaldominanz der Systemmatrix hinreichend.
Als Algorithmusskizze mit cc Iterationen und nn Zeilen bzw. Spalten ergibt sich:
für k=1 bis cc
für i=1 bis nn
xi=0x_i=0
für j=1 bis nn
falls j != i
xi=xi+ai,jxj(m)x_i=x_i+a_{i,j}x_j^{(m)};
end
xi=(bi−xi)/ai,ix_i=(b_i-x_i)/a_{i,i} ;
end
x(m)=x;x^{(m)}=x;
end
Dabei wurde die willkürliche Erstbelegung des Variablenvektors als Eingangsgrößen des Algorithmus angenommen, die Näherungslösung ist die vektorielle Rückgabegröße.

Beschreibung in Matrixschreibweise

Die Matrix A A\, des linearen Gleichungssystems A⋅x=bA \cdot x = b wird zur Vorbereitung in eine Diagonalmatrix DD, eine strikte untere Dreiecksmatrix LL und eine strikte obere Dreiecksmatrix UU zerlegt, so dass gilt:
A = L+D+UA\,=\, L+D+U.
Die obige komponentenweise Iterationsvorschrift lässt sich dann folgendermaßen für den kompletten Vektor darstellen:
x(m+1)=D−1(b−(A−D)x(m))x^{(m+1)} = D^{-1} \left( b - \left(A - D\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)D^{-1}(D-A) kleiner als eins ist. Insbesondere ergibt sich dies, wenn die Systemmatrix AA strikt diagonaldominant ist.

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
 
 

Nicht etwa, daß bei größerer Verbreitung des Einblickes in die Methode der Mathematik notwendigerweise viel mehr Kluges gesagt würde als heute, aber es würde sicher viel weniger Unkluges gesagt.

Karl Menger

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Jacobi-Verfahren aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Lineare Gleichungssysteme