Jacobi- und SOR-Verfahren

• Das Jacobi- und das SOR-Verfahren sind zwei der bekanntesten iterativen Lösungsverfahren für lineare Gleichungssysteme. Bei beiden Verfahren wird das lineare Gleichungssystem Ax=b durch eine sogenanntes Matrixsplitting in eine Fixpunktgleichung überführt, die dann mit der Methode der direkten Iteration gelöst werden soll. Unter bestimmten, recht restriktiven Voraussetzungen an die Matrix A erhält man tatsächlich Konvergenz.
• Das Jacobi-Verfahren wird auch Gesamtschrittverfahren genannt, während das SOR-Verfahren aus dem sogenannten Einzelschrittverfahren (Gauss-Seidel) durch Einführung eines künstlichen Parameters omega hervorgeht.
• Dieser sogenannte Relaxationsparameter omega, geeignet gewählt, kann die Konvergenzrate erhöhen. Für den Fall omega = 1 ist das Verfahren identisch mit dem Gauß-Seidel-Verfahren.
• Angewendet werden beide Methoden nur bei großen Gleichungssystemen, wenn direkte Löser, wie der Gauß-Algorithmus, einen zu großen Aufwand bedeuten.
• Die Konvergenzrate des Jacobiverfahrens ist dabei im Allgemeinen schlechter als die des SOR-Verfahrens und auch die Klasse der Matrizen, für die man überhaupt Konvergenz erzielt, ist bei letzterem grösser. Die Konvergenzgschwindigkeit hängt von der Kondition der Matrix ab.
• Gesamt- und Einzelschrittverfahren werden auch als Basisverfahren in den Mehrgittermethoden zur Lösung der Gleichungssysteme eingesetzt, die bei Diskretisierungsverfahren für partielle Differentialgleichungen entstehen.

Die Eingaben

• Zur Veranschaulichung der Iterationsfolge beider Methoden soll ein 2x2-Gleichungssystem dienen.
• Es kann zwischen dem Jacobi- und dem SOR-Verfahren ausgewählt werden. Im Falle des SOR-Verfahrens ist ein Relaxationsparameter omega mit 0 < omega < 2 zu wählen.
• Die Elemente des 2x2-Gleichungssystems werden zeilenweisen mit rechter Seite eingegeben und durch Leerzeichen bzw. Kommata getrennt. Erlaubt sind die Zahlendarstellungen der Programmiersprache FORTRAN. Falls die Matrix Matrix zu schlecht konditioniert ist, d.h. hier Betrag (groesstes Element/Determinante)>100000, ist die Rechnung hier nicht sinnvoll und wird nicht durchgeführt. Ist die Konditionszahl schlecht, erscheinen in der Grafik die beiden Geraden, deren Schnitt die gesuchte Lösung x^* ist, als eine einzige!
• Der Startpunkt der Iteration.
• Die geforderte Genauigkeitsschranke 1.E-8 <= eps <= 1.E-3 für die Änderung in der Näherung.
• Die maximale Anzahl von Iterationen.
• Ein Faktor, der die Rechenbox ||x-x^*||_inf <= (1+factor*||x⁰-x^*||_inf) definiert. Dabei ist x^* die Lösung des Problems. (Die Festlegung der Rechenbox braucht man, um eine vernünftige Grafik zu erhalten, denn die Konvergenz ist in der Maximumnorm in der Regel nicht monoton.) Falls omega > omega_opt, dann muß factor > 1 gewählt werden. Für omega <= 1 genuegt factor = 1. Wichtig: 1.0 <= factor <= 1.E3 !

Die Ausgaben

• Das Gleichungssystem Ax=b.
• Die Iterationsfolge in beiden Komponenten und der Norm der Residuums r=Ax-b.
• Eine Graphik, die die Iterationsfolge veranschaulicht. Man beachte, daß beim Jacobiverfahren beide Koordinatenkorrekturen gleichzeitig ausgeführt werden, die Iterationsfolge verfolgt also keinen achsenparallelen Weg.

Fragen ?!

• Wann konvergiert welches Verfahren, und wann divergiert es ?
• Wie kann man im Falle von Divergenz zur Konvergenz kommen (nur im 2x2 Falle) ?
• Was bewirkt der Relaxationsparameter ?
• Wann muß man factor groß wählen ? Was bedeutet dies für die Norm, in der man monotone Konvergenz erhält ?
• Wie hängt die Konvergenzgeschwindigkeit von der Konditionszahl der Matrix ab?

Das Eingabeformular

Zurück: Lineare Gleichungssysteme