Iterative Methoden
Iterative Methoden lösen große lineare (und nichtlineare) Systeme, indem sie eine Sequenz sukzessive besserer Approximationen generieren und dabei die Sparsity (Dünnbesetztheit) nutzen, um Probleme zu behandeln, die für eine direkte Faktorisierung viel zu groß wären.
Definition
Iterative Methoden sind Algorithmen, die die Lösung eines Gleichungssystems annähern, indem sie eine Sequenz von Iterationen erzeugen, die zur Lösung konvergieren, anstatt diese in einer festen endlichen Anzahl von Operationen zu berechnen, wie es eine direkte Methode tut.
Scope
Dieser Bereich umfasst klassische stationäre Iterationen, Krylov-Unterraum-Methoden wie die konjugierten Gradienten und GMRES-Algorithmen, Mehrgitterverfahren sowie die Vorkonditionierungstechniken, die die Konvergenz beschleunigen; er behandelt die Konvergenztheorie, die Rolle des Spektrums und der Konditionszahl sowie die matrixfreien, die Sparsity ausnutzenden Berechnungen, die diese Methoden skalierbar machen.
Sub-topics
Core questions
- Wann sind iterative Methoden direkten Methoden vorzuziehen, und warum begünstigt die Sparsity sie?
- Wie konstruieren Krylov-Unterraum-Methoden optimale Approximationen allein aus Matrix-Vektor-Produkten?
- Wie beeinflusst das Spektrum oder die Konditionszahl der Matrix die Konvergenzgeschwindigkeit?
- Wie transformieren Vorkonditionierung und Mehrgitterverfahren eine langsam konvergierende Iteration in eine schnelle?
Key theories
- Krylov-Unterraum-Approximation
- Krylov-Methoden suchen die beste Approximation der Lösung innerhalb des Unterraums, der durch sukzessive Matrix-Vektor-Produkte, angewendet auf das Residuum, aufgespannt wird. Sie benötigen nur die Wirkung der Matrix und konvergieren in einer Anzahl von Schritten, die durch die spektralen Eigenschaften der Matrix bestimmt wird.
- Konvergenz und Konditionierung
- Die Konvergenzrate iterativer Löser hängt von der Eigenwertverteilung und der Konditionszahl der (vorkonditionierten) Matrix ab; die Clusterbildung von Eigenwerten oder die Reduzierung der Konditionszahl durch Vorkonditionierung beschleunigt die Konvergenz dramatisch.
- Mehrgitter-Beschleunigung
- Mehrgitterverfahren kombinieren Glättung auf feinen Gittern mit Grobgitterkorrekturen, um Fehlerkomponenten auf jeder Skala zu eliminieren, wodurch für viele elliptische Probleme Konvergenzraten erreicht werden, die unabhängig von der Problemgröße sind.
Clinical relevance
Iterative Methoden sind unverzichtbar für die enormen dünnbesetzten linearen Systeme, die bei der Diskretisierung partieller Differentialgleichungen in der Ingenieur- und Physiksimulation sowie in der Optimierung, im maschinellen Lernen, in der Netzwerkanalyse und bei der Bildrekonstruktion entstehen; ihr geringer Speicherbedarf und ihre matrixfreie Arbeitsweise machen sie zum einzig praktikablen Ansatz, wenn Systeme Millionen oder Milliarden von Unbekannten erreichen.
History
Klassische Relaxationsmethoden wurden von Gauss, Seidel und später Southwell untersucht; die Methode der konjugierten Gradienten von Hestenes und Stiefel (1952) und die Entwicklung von GMRES und anderen Krylov-Methoden, Mehrgitterverfahren (Fedorenko, Brandt) sowie die moderne Vorkonditionierung im späten zwanzigsten Jahrhundert etablierten iterative Löser als Standard für große dünnbesetzte Systeme.
Key figures
- Magnus Hestenes
- Eduard Stiefel
- Yousef Saad
- Achi Brandt
Related topics
Seminal works
- saad2003
- greenbaum1997
Frequently asked questions
- Wann sollte eine iterative Methode anstelle einer direkten verwendet werden?
- Iterative Methoden werden für sehr große, dünnbesetzte Systeme bevorzugt, bei denen eine direkte Faktorisierung aufgrund von Fill-in einen unerschwinglichen Speicherbedarf hätte. Sie müssen die Matrix nur auf Vektoren anwenden, nutzen so die Sparsity aus und skalieren auf Probleme mit Millionen von Unbekannten.
- Warum ist Vorkonditionierung so wichtig?
- Die Konvergenzgeschwindigkeit iterativer Löser hängt stark vom Spektrum der Matrix ab. Ein Vorkonditionierer transformiert das System in ein äquivalentes System mit einem günstigeren Spektrum, wodurch eine unpraktisch langsame Iteration oft in eine schnell konvergierende umgewandelt wird.