Stationäre und Relaxationsmethoden

Stationäre iterative Methoden lösen ein lineares System, indem sie die Matrix aufteilen und wiederholt eine feste Aktualisierungsregel anwenden; die klassischen Jacobi-, Gauss-Seidel- und sukzessiven Überrelaxationsverfahren sind die grundlegenden Beispiele.

Definition

Eine stationäre iterative Methode ist eine, deren Aktualisierung bei jedem Schritt dieselbe Iterationsmatrix anwendet, die aus einer Aufteilung der Koeffizientenmatrix in einen leicht invertierbaren Teil und einen Rest abgeleitet ist; die Konvergenz wird durch den Spektralradius der resultierenden Iterationsmatrix bestimmt.

Scope

Dieses Thema behandelt den Matrix-Splitting-Rahmen, die Jacobi- und Gauss-Seidel-Iterationen, die sukzessive Überrelaxation und die Wahl des optimalen Relaxationsparameters, das Spektralradiuskriterium für die Konvergenz und die Rolle, die diese einfachen Iterationen heute als Glätter innerhalb von Multigrid und als Vorkonditionierer spielen.

Core questions

• Wie führt die Aufteilung der Matrix zu einer Fixpunktiteration für das lineare System?
• Wie unterscheiden sich die Jacobi- und Gauss-Seidel-Methoden, und warum ist Gauss-Seidel in der Regel schneller?
• Wie beschleunigt die Überrelaxation die Konvergenz, und wie wird der optimale Parameter gewählt?
• Unter welchen Bedingungen an die Matrix konvergieren diese Iterationen?

Key theories

Matrix-Splitting und das Spektralradiuskriterium

Das Schreiben der Matrix als einen leicht invertierbaren Teil minus einem Rest definiert eine stationäre Iteration, deren Fehler bei jedem Schritt mit einer Iterationsmatrix multipliziert wird; die Iteration konvergiert für jede Startschätzung genau dann, wenn der Spektralradius dieser Iterationsmatrix kleiner als eins ist.

Sukzessive Überrelaxation

Durch Überschreiten der Gauss-Seidel-Korrektur mit einem Relaxationsfaktor kann die sukzessive Überrelaxation den Spektralradius stark reduzieren; für bestimmte strukturierte Matrizen ist ein optimaler Relaxationsparameter analytisch bekannt und führt zu einer dramatischen Beschleunigung.

Mechanisms

Die Jacobi-Methode aktualisiert jede Unbekannte gleichzeitig unter Verwendung nur der Werte des vorherigen Durchlaufs, was der Aufteilung der Diagonalen entspricht. Gauss-Seidel verwendet die zuletzt aktualisierten Werte innerhalb desselben Durchlaufs und teilt den unter-dreieckigen Teil ab, was typischerweise schneller konvergiert. Die sukzessive Überrelaxation bildet einen gewichteten Durchschnitt des alten Wertes und der Gauss-Seidel-Aktualisierung, gesteuert durch einen Relaxationsparameter; die Wahl dieses Parameters größer als eins beschleunigt die Konvergenz für geeignete Matrizen. Die Konvergenz für alle drei ist für Klassen wie streng diagonaldominante oder symmetrisch positiv definite Matrizen garantiert und wird durch den Spektralradius der Iterationsmatrix quantifiziert.

Clinical relevance

Obwohl sie in der Regel zu langsam sind, um als eigenständige Löser für große Systeme wettbewerbsfähig zu sein, bleiben stationäre Methoden als Glätter im Herzen von Multigrid, als einfache Vorkonditionierer für Krylov-Methoden und als leicht parallelisierbare Bausteine wichtig; insbesondere Gauss-Seidel und gewichtetes Jacobi sind in modernen Multilevel-Lösern allgegenwärtig.

History

Die Jacobi- und Gauss-Seidel-Iterationen stammen aus dem neunzehnten Jahrhundert, während die sukzessive Überrelaxation und ihre rigorose Konvergenztheorie in den 1950er Jahren von David Young und Richard Varga entwickelt wurden; obwohl später von Krylov- und Multigrid-Methoden als primäre Löser in den Schatten gestellt, wurden diese Iterationen als wesentliche Komponenten von Multilevel- und vorkonditionierten Schemata wiederbelebt.

Key figures

• Carl Friedrich Gauss
• Philipp Ludwig von Seidel
• David M. Young
• Richard S. Varga

Seminal works

• saad2003
• varga2000

Frequently asked questions

Warum ist Gauss-Seidel in der Regel schneller als Jacobi?

Gauss-Seidel verwendet aktualisierte Werte sofort innerhalb desselben Durchlaufs, sodass sich Informationen schneller durch die Unbekannten ausbreiten, was typischerweise die Anzahl der Iterationen im Vergleich zu Jacobi halbiert, das nur Werte aus dem vorherigen Durchlauf verwendet.

Wenn diese Methoden langsam sind, warum werden sie immer noch untersucht?

Sie sind ausgezeichnete Glätter und einfache Vorkonditionierer. Innerhalb von Multigrid entfernen einige Gauss-Seidel- oder gewichtete Jacobi-Durchläufe effizient oszillierende Fehler, was genau die Rolle ist, die Multigrid benötigt, sodass diese klassischen Iterationen als Komponenten schneller moderner Löser weiterleben.