Kurs:Numerik I/5 Numerische Lösung nichtlinearer Gleichungssysteme

5.4 Das Newton-Verfahren im

Bearbeiten

4.1 Grundlagen

Bearbeiten

Es sei   eine offene Menge und   eine Funktion mit

 

und stetigen partiellen Ableitungen    , es sei also  . Die zu   gehörige Jacobi-Matrix bezeichnen wir mit

 

Mit   ist im ganzen Abschnitt 5.4 wieder die Euklidische Norm auf dem   bzw. die durch sie induzierte Spektralnorm gemeint.

Schließlich werden wir von dem folgenden Lemma Gebrauch machen.

Lemma 5.17

Bearbeiten
Sei   eine stetige vektorwertige Funktion, sei   für   und sei   der Vektor mit den Komponenten  . Dann gilt:
 

Es sei  . Dann kann man unter Verwendung des Standardskalarprodukts

 

auf dem   und der Cauchy-Schwarz-Ungleichung abschätzen:

 
 

q.e.d.

5.4.2 Das Verfahren

Bearbeiten

Es sei wieder   eine offene Menge und es sei   mit

 

und Jacobi- bzw. Funktionalmatrix   gegeben. Es soll nun das Newton-Verfahren zur Bestimmung einer Lösung   des Gleichungssystems

 

vorgestellt und seine Konvergenz untersucht werden. Für   hatten wir dies bereits in Abschnitt 5.2.4 getan.

Die Iterationsvorschrift des Newton-Verfahrens lautete im Fall  

 

wobei sich   als Nullstelle einer linearen Approximation von  , der Tangente bei   an  , ergab. Ähnlich kann man für eine Funktion   mit beliebigem   das Newton-Verfahren dadurch motivieren, dass man   als Nullstelle der linearen Approximation von   bei  

 

wählt. Dieses Vorgehen führt zu der allgemeinen Iterationsvorschrift

(5.23)  

des Newton-Verfahrens. Wir gehen hier implizit davon aus, dass die Jacobi-Matrix   des Systems für jedes   nichtsingulär ist. Da man, wenn immer möglich, die Berechnung der Inversen einer Matrix vermeiden sollte, geht man praktisch bei der Berechnung von   von der zu (5.23) äquivalenten Gleichung

 

aus und bestimmt man die eindeutige Lösung   des linearen Gleichungssystems

 

Anschließend setzt man

 

Das Newton-Verfahren lautet somit wie folgt:

Algorithmus 9 (Newton-Verfahren)

Bearbeiten
(0) Wähle   und ein  . Berechne   und setze  .
(1) Berechne   und bestimme die eindeutige Lösung   von
(5.24)  
(2) Setze   und berechne  .
(3) Falls  , stop!
(4) Setze   und gehe nach (1).

Der folgende Satz besagt, dass das Newton-Verfahren unter geeigneten Voraussetzungen durchführbar, d. h. für alle   insbesondere   und   nichtsingulär ist und dass es superlinear bzw. quadratisch konvergiert.

Satz 5.18

Bearbeiten
Es sei   offen und  . Ferner existiere ein  , für welches   und   nichtsingulär sei. Dann gibt es eine Umgebung   von   für ein  , so dass das Newton-Verfahren, Algorithmus 9, für jeden Startpunkt   durchführbar ist und die durch ihn ohne das Abbruchkriterium (3) erzeugte Iteriertenfolge   superlinear gegen   konvergiert. Gilt mit einem  
(5.25)  
so konvergiert   gegen   sogar quadratisch.

Wegen der Stetigkeit von   auf   können wir zunächst   so klein wählen, dass gilt:

 

Für   ergibt sich damit und mit   gemäß Korollar 2.21 die Invertierbarkeit der Matrix

 

sowie die Abschätzung

(5.26)  

Sei nun

 

die Iterationsfunktion des lokalen Newton-Verfahrens, die nach dem Gezeigten auf   wohldefiniert ist. Mit   und den Identitäten

 

schließen wir als nächstes

 
 
 

Für

(5.27)  

leiten wir daraus unter Anwendung von Lemma 5.17 mit (5.26) die folgende Abschätzung ab:

(5.28)  

Wegen der Stetigkeit von   auf   existiert ein  , so dass   auf   ist und damit gilt:

 

Beginnend mit  , liegt folglich mit   auch   in   und konvergiert die Folge   linear gegen  . Die Konvergenz von   impliziert weiter die Konvergenz    . Da gemäß (5.28)

(5.29)  

für alle k gilt, folgt schließlich die superlineare Konvergenz von  .

Gilt nun (5.25) auf  , dann liegt für jedes   mit   und   auch   für alle   in   und folgt somit

 

Aus (5.27) gewinnt man damit für alle   die Abschätzung

 

Letzteres zeigt zusammen mit (5.29) die quadratische Konvergenz der Folge  .

q.e.d.

Beispiel 5.19

Bearbeiten

Gesucht sei die Lösung   der beiden Gleichungen

(5.30)  

für die   gilt, wobei wir hier keine Abbruchschranke   angeben. Die Jacobi-Matrix von   lautet

 

Für   erhält man somit das lineare Gleichungssystem (5.24)

 

Dieses besitzt die Lösung

 

so dass sich

 

ergibt mit dem Defekt

 

Mit   verfährt man nun analog usw. Für die ersten vier Iterationen ergibt sich insgesamt die folgende Tabelle:

 

Das Newton-Verfahren, Algorithmus 9, ist invariant gegenüber affin-linearen Transformationen (Übung!). Dies bedeutet, wenn   eine beliebige reguläre Matrix und   irgendein Vektor: Ist   die durch das lokale Newton-Verfahren für den Startpunkt   erzeugte Iteriertenfolge zur Bestimmung einer Lösung des Gleichungssystems  , so erzeugt das Verfahren bei Anwendung auf das System

 

für den Startpunkt   die Iteriertenfolge   mit

 

Verfahren, die invariant gegenüber affin-linearen Transformationen sind, gelten gegenüber Verfahren, die diese Eigenschaft nicht besitzen, insofern als robuster, als ihre Konvergenzgeschwindigkeit weit weniger von den gerade vorliegenden speziellen Daten abhängt. Anders als z. B. bei dem CG-Verfahren zur Lösung linearer Gleichungssysteme mit symmetrischer, positiv definiter Matrix (s. Kanzow) ändert sich beim lokalen Newton-Verfahren insbesondere durch eine (affin-)lineare Transformation der Variablen die Konvergenzgeschwindigkeit des Verfahrens nicht. Denn ist   eine vorgegebene Abbruchschranke, so gilt aufgrund der oben beschriebenen Invarianz gegenüber affin-linearen Transformationen und der sich daraus ergebenden Identitäten

 

die Äquivalenz

 

Bei Verfahren, die wie die CG-Verfahren nicht invariant gegenüber affin-linearen Transformationen sind, kann man zwar möglicherweise die Konvergenzgeschwindigkeit durch eine geeignete Wahl der Matrix   erheblich beschleunigen, ist es aber häufig nicht vorhersehbar, ob das Verfahren für die aktuellen Daten langsam konvergiert, oder ist es nicht klar, ob gegebenenfalls eine geeignete Transformation zur Konvergenzbeschleunigung gefunden werden kann. Mit

 

lautet die Iterationsvorschrift des Newton-Verfahrens

 

Die Richtung   bezeichnet man dabei auch als Newton-Richtung in  .

Es gibt eine große Zahl von Varianten des Newton-Verfahrens, die zum Ziel haben, den Konvergenzbereich des Verfahrens zu vergrößern und/oder seinen numerischen Aufwand zu reduzieren. So kann man das Newton-Verfahren in gewisser Weise globalisieren, indem man eine geeignete Schrittweite   einführt und

 

definiert. Dabei wählt man   beispielsweise als (Näherungs-)Lösung des Problems

(5.31)  

da ja   möglichst klein werden sollte. Von dem so modifizierten sog. gedämpften Newton-Verfahren kann man unter relativ schwachen Voraussetzungen für jeden Startpunkt   einer geeigneten, hinreichend großen Menge Konvergenz zeigen. (Man hat sich dabei zu überlegen, dass ein solches   existiert und eine positive Zahl ist. Da eine Lösung des globalen Optimierungsproblems (5.31) im Allgemeinen nicht realistisch ist, wählt man die Schrittweite   häufig aber auf eine andere Weise; siehe z. B. Stoer, wo für eine solche andere Schrittweitenwahl auch ein Konvergenzsatz zu finden ist.)

Eine weitere praktisch relevante Modifikation des Newton-Verfahrens besteht darin, die numerisch aufwendig zu berechnende Jacobi-Matrix   im Verfahren durch eine geeignete Näherung   zu ersetzen, wobei   alleine aus den Daten   und   numerisch relativ günstig berechnet werden kann und somit insbesondere keine partiellen Ableitungen benötigt werden. Wir kennen ein solches Vorgehen schon vom Sekantenverfahren her, bei dem der Faktor

 

der eine Näherung für   darstellt, in der Iterationsvorschrift vorkommt. Verfahren dieses Typs werden als Sekanten- oder Quasi-Newton-Verfahren bezeichnet. Das bekannteste ist das Broyden-Verfahren.

Quasi-Newton-Verfahren haben vor allem im Zusammenhang mit der Bestimmung von Extremalpunkten von   und damit der Lösung des Systems   große Bedeutung, da man ja bei Anwendung des Newton-Verfahrens in einem solchen Fall in jeder Iteration die Hesse-Matrix   für  , also etwa   partielle Ableitungen zweiter Ordnung zu berechnen hat. Von solchen Quasi-Newton-Verfahren gibt es eine Reihe von Varianten, die sich durch die Wahl der   unterscheiden, wobei man im Fall der Lösung von Optimierungsaufgaben zusätzlich bestrebt ist, die positive oder negative (Semi-)Definitheit der Hesse-Matrix in einer Umgebung des Extremalpunktes auch für die   zu erreichen. Die verbreitetste Methode ist das BFGS-Verfahren, das nach seinen Erfindern Broyden, Fletcher, Goldfarb und Shanno benannt wurde, die das Verfahren 1970 unabhängig voneinander vorschlugen. Es hat sich herausgestellt, dass dieses unter allen Quasi-Newton-Verfahren das wohl unempfindlichste gegenüber der Schrittweitenwahl ist. (Es gibt Alternativen zu der numerisch teuren Berechnung der Minimumschrittweite in (5.31).)

Von Quasi-Newton-Verfahren kann man keine quadratische Konvergenz erwarten, da sie ja weniger Information der Funktion als das Newton-Verfahren verwenden. Unter geeigneten Voraussetzungen lässt sich aber für sie im Allgemeinen superlineare Konvergenz nachweisen. Die schlechtere Konvergenzrate gegenüber dem Newton-Verfahren wird jedoch durch den pro Iteration erforderlichen, geringeren numerischen Aufwand kompensiert.

Allgemein kann man sagen, dass das Newton-Verfahren wohl das erfolgreichste und verbreitetste Verfahren der Mathematik ist. Es wurde im Hinblick auf die Lösung zahlloser Probleme, auch solcher in unendlich-dimensionalen Räumen, verallgemeinert und modifiziert.