Einführung

Die effiziente und robuste Lösung eines Systems nichtlinearer Gleichungen kann ein sehr schwieriges Problem sein - besonders in Fällen in denen nur wenig a priori Information über die Lösung bekannt ist. Eine sehr hervorragende Methode zum Lösen nichtlinearer Gleichungen ist die Newton-Methode, ein Iterationsschema von dem bekannt ist daß es nahe der Lösung quadratisch konvergiert, jedoch nur wenn die Anfangsschätzung nahe genug bei der Lösung liegt. Um nun den Konvergenzbereich des Newton-Verfahrens auszudehnen sind einige Globalisierungsmethoden gebräuchlich, z.B. gedämpfte Newton-Methoden, Methode des steilsten Abstiegs und Levenberg-Marquardt Verfahren. Basierend auf den zuletzt genannten Methoden wurde einige state-of-the-art Software entwickelt, z.B. die Codes aus IMSL, NAG and MINPACK. Entgegen diesen Codes basieren die hier vorstellten Codes auf den affin-invarianten gedämpten Newton-Techniken nach Prof. Deuflhard. [1], [2],[3] In diesen Algorithmen sind die üblichen lokalen Newton-Techniken kombiniert mit speziellen Dämpfungsstrategien, um global konvergente Newton-Schemata zu erzeugen. Eine wesentliche Eigenschaft dieser Algorithmen - und der zugrunde liegenden Theorie - ist ihre affin-Invarianz. Soweit wie möglich ist diese Eigenschaft der Algorithmen auf die Codes übertragen. Desweiteren sind die Dämpfungsstrategie und die Konvergenz-Überprüfungen in einer Skalierungs-invarianten Form implementiert - eine sehr nützliche Eigenschaft für insbesondere praxisorientierte Anwendungen.

Die hier präsentierten Codes sind überarbeitete und erweiterte Versionen früherer Forschungscodes nach Deuflhard. In den neuen Codes sind die neuesten theoretischen Resultate aus [3] berücksichtigt und außerdem einige neue algorithmische Varianten realisiert. Die hervorragenden neuen Eigenschaften der Implementation sind die interne Arbeitsspeicherverwaltung, ein Optionen-Konzept und die modulare Programmierung. Die neue Schnittstelle ermöglicht einerseits eine einfache Anwendung und andererseits eine einfache Auswahl und Kontrolle spezieller Möglichkeiten der Codes. Die Codes sind noch als Forschungscodes anzusehen, in dem Sinne, daß dem Benutzer zahlreiche algorithmische Optionen zur Verfügung stehen und daß diese hinsichtlich der Performance nicht optimiert sind.

Im Zuge der Newton-Iteration ist eine Folge von linearen Problemen zu lösen. Solange die Dimension n des nichtlinearen Systems in einer moderaten Größenordnung liegt kann dies sehr effizient mittels direkter Methoden, etwa der Gauß Elimination, bewerkstelligt werden. Bei Verwendung spezieller Implementationen der direkten Methoden, wie Bandmodus Elimination oder Sparse Matrix Techniken, können sogar große Systeme mit speziellen Strukturen behandelt werden. Jedoch für sehr umfangreiche Probleme, etwa diskretisierte Partielle Differentialgleichungen, kann eine iterative Lösung der linearen Systeme die einzig mögliche Wahl sein. In diesem Fall hat man zwei ineinander geschachtelte Iterationsprozesse: die Newton-Iteration als äußere Iteration, und die iterative Lösung der auftretenden linearen Systeme als innere Iteration. Unter dem Gesichtspunkt einer effizienten Realisierung ist die Frage der zu fordernden Genauigkeit für das Resultat der inneren Iteration von essentieller Bedeutung. Zu geringe Genauigkeitsanforderungen können die Konvergenz der äußeren (Newton) Iteration ganz zerstören, oder die Konvergenzgeschwindigkeit vermindern. Zu stringente Genauigkeitsanforderungen jedoch führen zu einem drastischen Anwachsen der Rechenzeit, ohne die Konvergenzgeschwindigkeit der äußeren Iteration zu erhöhen. Abgesehen davon ist zu beachten, daß die nur approximative Lösung der linearen Systeme bedeutet, daß lediglich mit einem sogenannten inexakten Newton Schema operiert wird. Die Herleitung einer billig implementierbaren Erweiterung der affin-invarianten Newton-Methode zu einer inexakten Newton-Methode, mit einer Strategie für die Genauigkeitsanforderung, wurde von Deuflhard untersucht [4].

Die oben beschriebenen Techniken wurden in dem Softwarepaket GIANT (mnemotechnisch stehend für Global Inexact Affine invariant Newton Techniques) realisiert. Um einen lauffähigen Code zu erhalten sind zwei iterative lineare Löser in dem GIANT Paket enthalten. Der erste ist der gut bekannte und weit verbreitete "Generalized Minimum Residual" (GMRES) Code nach Brown/Hindmarsh/Seager aus dem SLAP-Paket von Seager/Greenbaum. [9],[6] Da das zugrunde liegende Minimierungsprinzip des GMRES nicht mit dem theoretischen Hintergrund der global affin-invarianten Newton-Methoden übereinstimmt, ist ein kürzlich entwickelter iterativer linearer Löser nach Deuflhard/Freund/Walter [5] implementiert und für den Gebrauch mit GIANT adaptiert worden. Diese schnelle Sekantenmethode GBIT1, die sogenannte "Good Broyden" Updates und ein spezielles, adaptiertes Liniensuchprinzip verwendet, paßt perfekt in den theoretischen Rahmen von GIANT. Beide iterativen Methoden für die Lösung der linearen Systeme können mit Präkonditionierungstechniken kombiniert werden, um die Konvergenzeigenschaften zu verbessern.

Weitere Einzelheiten über den Algorithmus und seine Implementation entnehme man bitte dem Technischen Reports TR90-11 und TR91-10.

ANT - Einführung   Codes - Einführung   NLEQ1   NLEQ1S
NLEQ2                   GIANT                       Literatur