„Jacobi-Verfahren“ – Versionsunterschied
[gesichtete Version] | [gesichtete Version] |
K BKL Konvergenz aufgelöst |
K →Literatur: Literatur ergänzt |
||
Zeile 51: | Zeile 51: | ||
* A. Meister: ''Numerik linearer Gleichungssysteme'', 2. Auflage, Vieweg 2005, ISBN 3528131357 |
* A. Meister: ''Numerik linearer Gleichungssysteme'', 2. Auflage, Vieweg 2005, ISBN 3528131357 |
||
* R. Barrett et al.: [http://www.netlib.org/linalg/html_templates/Templates.html Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods], 2nd Edition, SIAM Philadelphia, 1994 |
* R. Barrett et al.: [http://www.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= |
|||
}} |
|||
== Weblinks == |
== Weblinks == |
Version vom 18. Juli 2009, 22:14 Uhr
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 . 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 n Variablen mit n Gleichungen.
Um dieses zu lösen, wird die i-te Gleichung nach der i-ten Variablen aufgelöst,
- ,
und diese Ersetzung, ausgehend von einer willkürlichen Startbelegung der Variablen, periodisch wiederholt. Als minimale Bedingung lässt sich hier festhalten, dass die Diagonalelemente ai,i von Null verschieden sein müssen. Für die Konvergenz des Verfahrens ist die strikte Diagonaldominanz der Systemmatrix hinreichend.
Als Algorithmusskizze mit c Iterationen und n Zeilen bzw. Spalten ergibt sich:
für m=1 bis c für i=1 bis n für j=1 bis n falls j != i ; end ; end 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 des linearen Gleichungssystems wird zur Vorbereitung in eine Diagonalmatrix , eine strikte untere Dreiecksmatrix und eine strikte obere Dreiecksmatrix zerlegt, so dass gilt:
- .
Die obige komponentenweise Iterationsvorschrift lässt sich dann folgendermaßen für den kompletten Vektor darstellen:
- .
Konvergenzuntersuchung
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 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
- Plato, Robert: Numerische Mathematik Kompakt. Vieweg, 2004, ISBN 3-528-13153-5, S. 262.
Weblinks
- Eric W. Weisstein et al. "Jacobi Method" MathWorld
- Gesamt- und Einzelschrittverfahren bzw. Jacobi- und Gauss-Seidel-Verfahren fuer N = 3 (pdf) Jacobi und Gauss-Seidel-Verfahren verstaendlich erklaert, inklusive Matlab Programme.