Preconditiones Arnoldi Methods for Systems of Nonlinear Equations
1st Edition
Published in April 2004
Book
Paperback/Softback
262 pages
978-3-936749-71-7 (ISBN)
Description
Krylov-Raum-Methoden zum Lösen linearer Gleichungssysteme haben die Eigenschaft,
dass sie implizit das minimale Polynom der Systemmatrix in bezug auf den ersten Residuumsvektor bestimmen.
Vektorextrapolationsmethoden werden verwendet, um die Konvergenz von Vektorsequenzen zu beschleunigen. Sie benötigen keine Information, wie eine solche Sequenz erzeugt wurde. Wenn aber die Sequenz durch eine lineare Iteration erzeugt wurde, kann gezeigt werden, dass der extrapolierte Grenzwert einer Vektorextrapolationsmethode die Lösung eines linearen Gleichungssystems ist. Vektorextrapolationsmethoden approximieren explizit die Koeffizienten des minimalen
Polynoms dieses Gleichungssystems ohne Zuhilfenahme der Systemmatrix und des Vektors auf der rechten Seite. Es ist bereits bekannt, dass diese Methoden und Krylov-Raum-Methoden in exakter Arithmetik dieselben Iterierten erzeugen, falls sie zum Lösen von linearen Gleichungssystemen verwendet werden.
Die explizite Bestimmung der Koeffizienten des minimalen Polynoms ist numerisch nicht stabil. Krylov-Raum-Methoden verwenden einen genaueren, impliziten Ansatz. Auf der anderen Seite aber sind Vektorextrapolationsmethoden im Stande, nichtlineare Gleichungssysteme zu lösen, die einen dominanten linearen Anteil in der Nähe des zu extrapolierenden Grenzwertes aufweisen.
Der erzeugende Prozess der Vektorsequenz einer Vektorextrapolationsmethode kann im Krylov-Raum-Kontext als Vorkonditionierer angesehen werden. Unter Verwendung der zentralen Idee von Vektorextrapolationsmethoden (Differenzvektoren der Sequenzvektoren) kann der Vorkonditionierer um eine rekursive Vorschrift erweitert werden, um die Matrix-Vektor-Multiplikation von wiedergestarteten Krylov-Raum-Methoden zu ersetzen. Auf diese Weise können Krylov-Raum-Methoden zum Lösen
linearer Gleichungssysteme auf das Lösen nichtlinearer Gleichungssysteme adaptiert werden. Sie besitzen dann ähnliche Konvergenzeigenschaften wie Vektorextrapolationsmethoden.
Der wissenschaftliche Hauptbeitrag dieser Doktorarbeit ist die Entwicklung und Umsetzung dieses Ansatzes für die allgemeinen Arnoldi-Methoden FOM und GMRES. Dadurch erhalten wir zwei neue Methoden zum Lösen nichtlinearer Gleichungssysteme -vorkonditionierte Arnoldi-Methoden zum Lösen nichtlinearer Gleichungssysteme, die für gewisse Problemstellungen eine bessere Leistung erbringen können als etablierte Methoden wie z.B. inexakte Newton-Methoden. Die neuen Algorithmen wurden anhand der Chandrasekhar H-Gleichung und einem Wärmestrahlungsproblem des Forschungszentrums der Firma ABB in Dättwil, Schweiz getestet.
Ein weiterer Beitrag dieser Doktorarbeit ist die Entwicklung einer allgemeinen Theorie für Vektorextrapolationsmethoden. Diese kann auch auf die neu entwickelten Algorithmen angewendet werden. Die Hauptaussage dieser Theorie ist: Vektorextrapolationsmethoden sind Implementationen der Methode von Henrici (eine Verallgemeinerung der Methode von Steffensen auf Vektorsequenzen).
Neu in dieser Theorie ist die Formulierung eines Kontorovich-Theorems für die Methode von Henrici, das die Bedingungen für ihre Konvergenz festlegt. Aufgrund unserer geometrischen Untersuchengen waren wir ausserdem in der Lage, eine Klasse von skalaren Iterationsvorschriften zu beschreiben, für welche die Schmidt-Shanks-Transformation in nur einem Schritt konvergiert.
In dieser Doktorarbeit werden die wichtigsten herkömmlichen Verfahren zum Lösen nichtlinearer Gleichungssysteme beschrieben. Überdies wird ein Überblick über die Theorie der linearen Krylov-Raum-Methoden gegeben. Beispiele und Graphiken illustrieren unsere Ausführungen.
dass sie implizit das minimale Polynom der Systemmatrix in bezug auf den ersten Residuumsvektor bestimmen.
Vektorextrapolationsmethoden werden verwendet, um die Konvergenz von Vektorsequenzen zu beschleunigen. Sie benötigen keine Information, wie eine solche Sequenz erzeugt wurde. Wenn aber die Sequenz durch eine lineare Iteration erzeugt wurde, kann gezeigt werden, dass der extrapolierte Grenzwert einer Vektorextrapolationsmethode die Lösung eines linearen Gleichungssystems ist. Vektorextrapolationsmethoden approximieren explizit die Koeffizienten des minimalen
Polynoms dieses Gleichungssystems ohne Zuhilfenahme der Systemmatrix und des Vektors auf der rechten Seite. Es ist bereits bekannt, dass diese Methoden und Krylov-Raum-Methoden in exakter Arithmetik dieselben Iterierten erzeugen, falls sie zum Lösen von linearen Gleichungssystemen verwendet werden.
Die explizite Bestimmung der Koeffizienten des minimalen Polynoms ist numerisch nicht stabil. Krylov-Raum-Methoden verwenden einen genaueren, impliziten Ansatz. Auf der anderen Seite aber sind Vektorextrapolationsmethoden im Stande, nichtlineare Gleichungssysteme zu lösen, die einen dominanten linearen Anteil in der Nähe des zu extrapolierenden Grenzwertes aufweisen.
Der erzeugende Prozess der Vektorsequenz einer Vektorextrapolationsmethode kann im Krylov-Raum-Kontext als Vorkonditionierer angesehen werden. Unter Verwendung der zentralen Idee von Vektorextrapolationsmethoden (Differenzvektoren der Sequenzvektoren) kann der Vorkonditionierer um eine rekursive Vorschrift erweitert werden, um die Matrix-Vektor-Multiplikation von wiedergestarteten Krylov-Raum-Methoden zu ersetzen. Auf diese Weise können Krylov-Raum-Methoden zum Lösen
linearer Gleichungssysteme auf das Lösen nichtlinearer Gleichungssysteme adaptiert werden. Sie besitzen dann ähnliche Konvergenzeigenschaften wie Vektorextrapolationsmethoden.
Der wissenschaftliche Hauptbeitrag dieser Doktorarbeit ist die Entwicklung und Umsetzung dieses Ansatzes für die allgemeinen Arnoldi-Methoden FOM und GMRES. Dadurch erhalten wir zwei neue Methoden zum Lösen nichtlinearer Gleichungssysteme -vorkonditionierte Arnoldi-Methoden zum Lösen nichtlinearer Gleichungssysteme, die für gewisse Problemstellungen eine bessere Leistung erbringen können als etablierte Methoden wie z.B. inexakte Newton-Methoden. Die neuen Algorithmen wurden anhand der Chandrasekhar H-Gleichung und einem Wärmestrahlungsproblem des Forschungszentrums der Firma ABB in Dättwil, Schweiz getestet.
Ein weiterer Beitrag dieser Doktorarbeit ist die Entwicklung einer allgemeinen Theorie für Vektorextrapolationsmethoden. Diese kann auch auf die neu entwickelten Algorithmen angewendet werden. Die Hauptaussage dieser Theorie ist: Vektorextrapolationsmethoden sind Implementationen der Methode von Henrici (eine Verallgemeinerung der Methode von Steffensen auf Vektorsequenzen).
Neu in dieser Theorie ist die Formulierung eines Kontorovich-Theorems für die Methode von Henrici, das die Bedingungen für ihre Konvergenz festlegt. Aufgrund unserer geometrischen Untersuchengen waren wir ausserdem in der Lage, eine Klasse von skalaren Iterationsvorschriften zu beschreiben, für welche die Schmidt-Shanks-Transformation in nur einem Schritt konvergiert.
In dieser Doktorarbeit werden die wichtigsten herkömmlichen Verfahren zum Lösen nichtlinearer Gleichungssysteme beschrieben. Überdies wird ein Überblick über die Theorie der linearen Krylov-Raum-Methoden gegeben. Beispiele und Graphiken illustrieren unsere Ausführungen.