Krylow-Unterraum-Methoden

Krylow-Unterraum-Methoden lösen große dünnbesetzte lineare Systeme, indem sie die beste Approximation aus dem Unterraum extrahieren, der durch wiederholte Matrix-Vektor-Produkte erzeugt wird, wobei nur die Wirkung der Matrix und nicht ihre Einträge benötigt werden.

Definition

Eine Krylow-Unterraum-Methode ist ein iteratives Lösungsverfahren, das im m-ten Schritt eine approximative Lösung im m-dimensionalen Krylow-Unterraum sucht, der vom Residuum und seinen sukzessiven Bildern unter der Matrix aufgespannt wird, wobei der Iterationswert durch eine Projektions- oder Minimierungsbedingung gewählt wird.

Scope

Dieses Thema behandelt den Krylow-Unterraum und seine Konstruktion durch die Arnoldi- und Lanczos-Verfahren, die Methode der konjugierten Gradienten für symmetrische positiv-definite Systeme, MINRES und GMRES für symmetrische indefinite und allgemeine Matrizen, Biorthogonalisierungsverfahren wie BiCGSTAB sowie die Konvergenztheorie, die die Iterationszahl mit dem Spektrum und der Konditionszahl verknüpft.

Core questions

• Was ist der Krylow-Unterraum und wie wird eine orthonormale Basis dafür stabil aufgebaut?
• Warum ist die Methode der konjugierten Gradienten optimal und kurz-rekursiv für symmetrische positiv-definite Systeme?
• Wie geht GMRES mit allgemeinen nichtsymmetrischen Systemen um und warum erfordert es einen zunehmenden Speicherbedarf?
• Wie bestimmen die spektralen Eigenschaften der Matrix die Konvergenzrate?

Key theories

Methode der konjugierten Gradienten

Für symmetrische positiv-definite Systeme minimiert die Methode der konjugierten Gradienten die Energienorm des Fehlers über dem Krylow-Unterraum unter Verwendung einer kurzen Dreiterm-Rekursion, die in exakter Arithmetik in höchstens n Schritten konvergiert und wesentlich schneller, wenn Eigenwerte geclustert sind.

GMRES und das Arnoldi-Verfahren

Für allgemeine Matrizen verwendet GMRES das Arnoldi-Verfahren, um eine orthonormale Krylow-Basis aufzubauen, und minimiert die Residuen-Norm über dem Unterraum. Da jedoch im Allgemeinen keine kurze Rekursion existiert, müssen alle Basisvektoren gespeichert werden, was zu neugestarteten Varianten führt.

Mechanisms

Jede Methode multipliziert wiederholt einen Vektor mit der Matrix, um den Krylow-Unterraum zu erweitern, und orthogonalisiert die neue Richtung gegenüber den vorherigen. Bei symmetrischen Matrizen führt das Lanczos-Verfahren zu einer tridiagonalen Projektion und einer kurzen Rekursion, sodass die Methoden der konjugierten Gradienten und MINRES nur wenige Vektoren speichern müssen. Bei nichtsymmetrischen Matrizen erzeugt das Arnoldi-Verfahren eine vollständige obere Hessenberg-Projektion, und GMRES minimiert das Residuum, indem es in jedem Schritt ein kleines Kleinste-Quadrate-Problem löst, auf Kosten der Speicherung der gesamten Basis; ein Neustart begrenzt diese Kosten. Die Konvergenz wird davon bestimmt, wie günstig die Eigenwerte verteilt sind, was durch Vorkonditionierung verbessert werden soll.

Clinical relevance

Krylow-Methoden, insbesondere die vorkonditionierte Methode der konjugierten Gradienten und GMRES, sind die Standardlöser in Finite-Elemente- und Finite-Volumen-Simulationscodes, bei großskaliger Optimierung und im wissenschaftlichen Rechnen im Allgemeinen; ihre matrixfreie Natur ermöglicht es ihnen, Systeme mit Millionen oder Milliarden von Unbekannten zu lösen, die keine direkte Methode faktorisieren könnte.

History

Die Methode der konjugierten Gradienten wurde 1952 von Hestenes und Stiefel eingeführt, und das zugrunde liegende Lanczos-Verfahren 1950; ihre volle Leistungsfähigkeit als iterative Löser wurde in den 1970er Jahren erkannt, und die Entwicklung von GMRES durch Saad und Schultz 1986 sowie von stabilisierten biorthogonalen Methoden erweiterte den Ansatz auf allgemeine nichtsymmetrische Systeme.

Key figures

• Magnus Hestenes
• Eduard Stiefel
• Cornelius Lanczos
• Yousef Saad
• Henk van der Vorst

Seminal works

• saad2003
• greenbaum1997

Frequently asked questions

Warum funktioniert die Methode der konjugierten Gradienten nur für symmetrische positiv-definite Matrizen?

Ihre kurze, effiziente Rekursion und ihre Optimalität in der Energienorm beruhen darauf, dass die Matrix symmetrisch positiv-definit ist. Für symmetrische indefinite oder nichtsymmetrische Matrizen sind andere Methoden wie MINRES oder GMRES erforderlich, die im Allgemeinen mehr Speicher oder Rechenaufwand pro Schritt benötigen.

Warum benötigt GMRES so viel Speicher?

Für eine allgemeine nichtsymmetrische Matrix gibt es keine kurze Rekursion, die die Krylow-Basis orthogonal hält, daher muss GMRES jeden Basisvektor speichern, um das Residuum zu minimieren. Das neu gestartete GMRES begrenzt den Speicher, indem es die Basis periodisch verwirft, auf Kosten einer langsameren Konvergenz.