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
(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.
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
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 .
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.