Jacobi-Verfahren

In der numerischen Mathematik ist das Jacobi-Verfahren, auch Gesamtschrittverfahren genannt, ein Algorithmus zur näherungsweisen Lösung von linearen Gleichungssystemen. Es ist, wie das Gauß-Seidel-Verfahren und das SOR-Verfahren, ein spezielles Splitting-Verfahren. Benannt ist es nach Carl Gustav Jacob 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 VerfahrensBearbeiten

Gegeben ist ein lineares Gleichungssystem mit   Variablen und   Gleichungen.

 

Mit dem Matrix-Vektor-Produkt kann das lineare Gleichungssystem auch als   geschrieben werden, wobei die Matrix   die Koeffizientenmatrix,   der Ergebnisvektor und   der gesuchte Vektor der Unbekannten   ist. Die ausführliche Schreibweise als Matrix und Vektoren mit den einzelnen Elementen wird üblicherweise wie folgt notiert:

 

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

 

und diese Ersetzung, ausgehend von einem Startvektor  , iterativ wiederholt. Als Bedingung für die Durchführbarkeit ergibt sich, dass die Diagonalelemente   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 in Pseudocode ergibt sich:

Gegeben Startvektor  
für   bis Erfüllung eines Abbruchkriteriums
   
  für   bis  
       für   bis  
         falls  
             ;
       ende
        ;
  ende
   
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 MatrixschreibweiseBearbeiten

Die Matrix   des linearen Gleichungssystems   wird hierzu in eine Diagonalmatrix  , eine strikte untere Dreiecksmatrix   und eine strikte obere Dreiecksmatrix   zerlegt, so dass gilt:

 

oder in ausführlicher Schreibweise mit den einzelnen Elementen der Matrizen wie folgt:

 

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

 .

Üblich zur Einbettung als Präkonditionierer in andere iterative Verfahren wie Krylow-Unterraum-Verfahren schreibt man den Präkonditionierer als Matrix  , wobei   eine Approximation an   ist, zu der sich ein lineares Gleichungssysteme   günstig nach   lösen lässt. Es gilt für das Jacobi-Verfahren  . Für das Residuum   ist   gerade die Näherungslösung. Die Beziehung   folgt unmittelbar:

 ,
 .

KonvergenzuntersuchungBearbeiten

Die Konvergenz wird wie bei allen Splitting-Verfahren mittels des banachschen Fixpunktsatzes untersucht. Das Verfahren konvergiert also, wenn der Spektralradius der Iterationsmatrix   kleiner als eins ist. Insbesondere ergibt sich dies, wenn die Systemmatrix   strikt diagonaldominant oder allgemeiner irreduzibel diagonaldominant ist.

Erweiterung auf nichtlineare GleichungssystemeBearbeiten

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

Für   bis Erfüllung eines Abbruchkriteriums
Für  :
Löse   nach   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.

LiteraturBearbeiten

WeblinksBearbeiten