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

Aus Wikiversity
Zur Navigation springen Zur Suche springen

5.1 Konvergenzraten[Bearbeiten]

Die Verfahren, die wir bisher im Zusammenhang mit der Lösung linearer Gleichungssysteme und Ausgleichsprobleme vorgestellt haben, bestimmen in endlich vielen Schritten eine Lösung, welche, wenn man exakt rechnen könnte, immer die exakte Lösung des Problems wäre. In der Praxis lassen sich aber viele mathematische Probleme nur mittels eines Iterationsverfahrens lösen, d. h. mittels wiederholter Anwendung derselben Rechenvorschriften, wobei in der -ten Iteration („Wiederholung“), ausgehend von einer Näherung , eine neue und möglichst genauere Näherung für eine gesuchte Lösung des Problems berechnet wird. Für den Start eines solchen Verfahrens muss man folglich eine Startnäherung vorgeben.

Iterationsverfahren würden im allgemeinen, wenn sie nicht nach endlich vielen Schritten abgebrochen würden, eine unendliche Folge von Iterierten generieren. Aufgabe des Numerikers ist es zu zeigen, dass jede konvergente Teilfolge oder die ganze vom Verfahren erzeugte Folge für jeden Startpunkt aus einer gewissen Menge gegen eine (ja a priori unbekannte!) Lösung des gegebenen Problems konvergiert. In diesem Zusammenhang spricht man von globaler Konvergenz eines Verfahrens, wenn diese Konvergenz für jede Wahl des Startpunktes aus einer wohlbestimmten Menge (z. B. dem ganzen ) gegeben ist, und von lokaler Konvergenz, wenn dies nur für Startpunkte aus einer (im Allgemeinen nicht spezifizierbaren) Umgebung einer Lösung der Fall ist. In der Praxis wird ein Iterationsverfahren natürlich nach einer endlichen Anzahl von Iterationen gestoppt und zwar dann, wenn zum ersten Mal ein Abbruchkriterium erfüllt ist, welches ausreichende Genauigkeit der aktuellen Näherung im Hinblick auf eine Lösung des Problems sicherstellt. Die Angabe eines sinnvollen Abbruchkriteriums kann dabei durchaus ein schwieriges Unterfangen sein.

Für ein gegebenes Verfahren ist neben dem rechnerischen Aufwand, der pro Iteration zu leisten ist, naturgemäß von Interesse, wie schnell es, wenn es nicht abgebrochen würde, gegen eine gesuchte Lösung konvergieren würde und damit, ob im Schnitt nur wenige oder viele Iterationen durchlaufen werden müssen, bis ein gegebenes Abbruchkriterium erfüllt ist. Wir wollen daher als nächstes den Begriff der Konvergenzgeschwindigkeit eines Verfahrens genauer fassen.

Definition 5.1[Bearbeiten]

Sei eine Norm auf dem und eine Folge in mit .
(i) Die Folge konvergiert von (mindestens) der Ordnung (gegen ), wenn mit einem und einem
(5.1)
gilt, wobei für sei. Im Fall spricht man auch von linearer und im Fall von quadratischer Konvergenz.
(ii) Die Folge konvergiert superlinear (gegen ), wenn für ein gilt sowie
(5.2)

Die drei wichtigsten Konvergenzraten bei Algorithmen sind lineare, superlineare und quadratische Konvergenz, so dass wir uns im Folgenden nur auf sie beziehen werden.

Die (praktisch irrelevante) Voraussetzung „ für ein “ bei der Definition der superlinearen Konvergenz kann man vermeiden, indem man diese mit einer Folge von Zahlen mit durch

(5.3)

für ein definiert. Für kann man superlineare Konvergenz der Folge auch durch die Beziehung

ausdrücken und quadratische Konvergenz durch

Beispiel 5.2[Bearbeiten]

Die Folgen und mit

konvergieren für gegen . Man errechnet

Also konvergiert linear, superlinear und quadratisch gegen 1. Die folgende Tabelle demonstriert, was die unterschiedlichen Konvergenzraten praktisch bedeuten.

Quadratische Konvergenz impliziert superlineare Konvergenz und diese wiederum lineare Konvergenz. Denn im Fall quadratischer Konvergenz hat man mit einem und einem

was wegen die Bedingung (5.3) impliziert. Ist andererseits (5.2) gegeben, dann existiert zu jedem ein , so dass gilt:

(5.4)

Letztere Beziehung drückt gerade die lineare Konvergenz aus.

Im Fall der superlinearen Konvergenz gilt ja (5.4), d. h. lineare Konvergenz mit einem , so dass man bei der Definition der linearen und superlinearen Konvergenz auf die Voraussetzung verzichten könnte. Denn die Ungleichung (5.1) impliziert im Fall der linearen Konvergenz

und damit wegen auch die Konvergenz . Bei der Definition einer Konvergenzordnung muss man aber, da dort nicht gefordert ist, die Konvergenz der Folge explizit voraussetzen.

Man beachte, dass lineare Konvergenz mit einer Konstanten sehr langsame Konvergenz bedeuten kann.

Beispiel 5.3[Bearbeiten]

Für die gegen 1 konvergierende Folge mit gilt

Die langsame Konvergenz sei mit der Berechnung einiger Folgenglieder gezeigt:

Man hofft also, dass die Konstante in der Praxis im Fall der linearen Konvergenz ist und im Fall der quadratischen Konvergenz nicht allzu groß wird. In letzterem Fall besagt die Ungleichung (5.1) für , dass sich für einen Fehler die Anzahl der korrekten Stellen hinter dem Dezimalpunkt von bezüglich gegenüber der von ungefähr verdoppelt. Denn dann ist

so dass man bei einer Genauigkeit von Stellen hinter dem Dezimalpunkt für bezüglich der Norm im -ten Schritt einen Fehler hat und somit im -ten Schritt einen Fehler

Quadratische Konvergenz ist demnach eine für die Praxis sehr gute Eigenschaft eines Verfahrens und meist die schnellste Konvergenz, die man mit vernünftigen Mitteln erreichen kann.

Es sei jedoch darauf hingewiesen, dass eine gute Konvergenzrate eines Verfahrens alleine nicht dessen Effizienz garantiert. Von einem gegebenen Verfahren ausgehend, kann man ja immer ein noch schnelleres Verfahren erzeugen, indem man mehrere Iterationen des ersten Verfahrens zu einer einzigen zusammenfasst. Neben der Konvergenzgeschwindigkeit eines Verfahrens hat man also bei der Beurteilung eines Verfahrens den numerischen Aufwand pro Iteration und natürlich auch seine Stabilität zu berücksichtigen.

Wir bemerken ferner, dass die Eigenschaften der superlinearen und quadratischen Konvergenz einer Folge gegen einen Punkt im aufgrund der Äquivalenz aller Normen im unabhängig von der gewählten Norm sind. Denn die Äquivalenz zweier Normen und auf dem besagt, dass mit zwei Konstanten und

gilt, so dass z. B. die Beziehung in (5.3) bezogen auf die Norm

impliziert und damit für die Nullfolge mit auch

Ähnlich garantiert quadratische Konvergenz bezüglich der Norm auch die quadratische Konvergenz

bezüglich einer Norm , wobei die Konstante von der Norm abhängt. Dagegen muss lineare Konvergenz einer Folge im bezüglich einer Norm nicht notwendig die lineare Konvergenz hinsichtlich einer anderen Norm auf dem zur Folge haben. Zwar gilt beispielsweise für jede linear bezüglich konvergente Folge auch

mit einer Konstanten für eine Norm , jedoch nicht notwendig . Sprechen wir also von linearer Konvergenz, so müssen wir klarstellen, bezüglich welcher Norm wir dies tun. Wenn nichts Anderes gesagt wird, beziehen wir uns immer auf Konvergenz im Sinne der Euklidischen Norm .

Die hier eingeführten Begriffe der linearen, superlinearen und quadratischen Konvergenz werden gelegentlich auch als -lineare, -superlineare bzw. -quadratische Konvergenz bezeichnet, im Unterschied zur -linearen, -superlinearen bzw. -quadratischen Konvergenz (siehe z. B. das Buch von Ortega und Rheinboldt aus dem Jahre 1970). Das „“ steht dabei für „Quotient“, da die Konvergenzrate in allen Fällen mittels des Quotienten ausgedrückt werden kann (während „“ für engl. „Root“, also „Wurzel“ steht).

5.2 Nullstellenbestimmung reeller Funktionen einer Veränderlichen[Bearbeiten]

Häufig hat man in Anwendungen für eine gegebene Funktion eine Nullstelle, auch Wurzel genannt, zu bestimmen, d. h. einen Punkt mit . So benötigt man für die Bestimmung der Extremalpunkte einer Funktion die Nullstellen von . Um eine möglichst gute Startnäherung für jede solche Nullstelle zu erhalten, hat man dann meistens zunächst ein kleines Intervall in zu ermitteln, in dem ein und zwar möglichst nur ein solches liegt. Dazu berechnet man im Allgemeinen Funktionswerte mit

für ein gegebenes, genügend großes . Die Menge aller bezeichnet man auch als ein Gitter in , die selbst als Gitterpunkte und den Prozess der Auswahl von endlich vielen Punkten aus als Diskretisierung des Intervalls. Sind und (anderenfalls hätte man eine Nullstelle von gefunden) und ist

so muss nach dem Zwischenwertsatz im Intervall eine (einfache) Nullstelle besitzen und können wir und setzen.

Es sind eine Reihe von Verfahren vorgeschlagen worden, die, ausgehend von einem solchen Intervall, unter geeigneten Bedingungen eine genäherte Nullstelle von liefern. Wir betrachten im Folgenden einige dieser Verfahren. Dabei gehen wir davon aus, dass eine Funktion gegeben ist und ein existiert mit , welches bestimmt werden soll.

5.2.1 Das Bisektionsverfahren[Bearbeiten]

Das erste Verfahren, das wir vorstellen wollen, ist das Intervallschachtelungs- oder auch Bisektionsverfahren. Bei diesem wird, beginnend mit dem Intervall , eine Folge von Intervallen erzeugt, so dass und damit gilt. Dieses Verfahren verwendet in jeder Iteration als einzige Information nur die Vorzeichen der Funktionswerte an den Randpunkten des aktuellen Intervalls, so dass keine schnelle Konvergenzgeschwindigkeit zu erwarten ist.

Algorithmus 5 (Bisektionsverfahren)[Bearbeiten]

(0) Gib mit und . Setze .
(1) Berechne und .
(2) Falls , stop!
(3) Falls , setze .
Falls , setze .
(4) Setze und gehe nach (1).

Offenbar gilt für die Länge der bei der Bisektionsmethode erzeugten Intervalle

(5.5)

Wenn Algorithmus 5 nicht abgebrochen wird, folgt damit

Wegen sowie oder hat man weiter mit (5.5)

(5.6)

und demnach

Da und stetig ist, ist daher das Abbruchkriterium in Schritt (2) von Algorithmus 5 nach endlich vielen Schritten erfüllt. Statt dieses Abbruchkriteriums, das beispielsweise im Fall

ungünstig ist, könnte man alternativ oder zusätzlich auch die Abfrage mit einer kleinen Konstante als Abbruchkriterium verwenden.

Beispiel 5.4[Bearbeiten]

Ist , so folgt aus (5.6)

Das Bisektionsverfahren ist ein sicheres und numerisch stabiles Verfahren, aber mit langsamer Konvergenz. Es konvergiert i. a. nicht einmal linear. Für die Fehler zweier aufeinander folgender Iterierter und kann sogar gelten:

Beispiel 5.5[Bearbeiten]

Die Nullstelle der Geraden in werde mit dem Bisektionsverfahren berechnet. Dann hat man wegen und

und demzufolge

5.2.2 Die Regula falsi[Bearbeiten]

Bei der Regula Falsi verwendet man im -ten Schritt die Sekante, welche die Punkte und verbindet. Diese hat die Gleichung

und schneidet die -Achse bei

(5.7)

Der Punkt wird nun als neue Näherung für genommen. Ansonsten verfährt man wie bei der Bisektion.

Algorithmus 6 (Regula Falsi)[Bearbeiten]

(0) Gib mit und . Setze .
(1) Berechne
sowie .
(2) Falls , stop!
(3) Falls , setze .
Falls , setze .
(4) Setze und gehe nach (1).

Für die Regula Falsi ist keine aussagekräftige Fehlerabschätzung erhältlich. Aber sie konvergiert unter gewissen Voraussetzungen mindestens linear (siehe z. B. Stoer). Man beachte, dass wegen keine Auslöschung bei der Berechnung von eintritt, so dass das Verfahren überdies numerisch stabil ist. Die erzeugten Näherungen liegen alle im Ausgangsintervall und können alle auf einer Seite der gesuchten Nullstelle liegen.

5.2.3 Das Sekantenverfahren[Bearbeiten]

Beim Sekantenverfahren wählt man, ähnlich wie bei der Regula Falsi, die Nullstelle einer Sekante als neue Iterierte, wobei jeweils die Sekante, welche die Punkte und verbindet, genommen und mit zwei Startpunkten begonnen wird. Dabei muss nicht notwendig gelten. Die Nullstelle dieser Sekante ist offenbar durch

gegeben (vgl. (5.7)). Das Sekantenverfahren sieht demnach folgendermaßen aus:

Algorithmus 7 (Sekantenverfahren)[Bearbeiten]

(0) Gib und . Berechne sowie und setze .
(1) Berechne
(5.8)
sowie .
(2) Falls , stop!
(3) Setze und gehe nach (1).

Man beachte hier (vgl. (5.8)), dass man die Iterierte im -ten Schritt eines Verfahrens meist als Korrektur der Iterierten im -ten Schritt, also in der Form mit einem schreibt, so dass man bei Konvergenz des Verfahrens (gegen ) zumindest für größere hat.

Während bei dem Bisektionsverfahren und der Regula Falsi sofort einleuchtet, dass diese Verfahren immer konvergieren, ist dies beim Sekantenverfahren nicht offensichtlich und hat man die Konvergenz zu beweisen. Es muss insbesondere nicht bzw. gelten, so dass das Verfahren im Allgemeinen nur lokal konvergiert. Genauer kann man den folgenden Satz beweisen (vgl. Isaacson and Keller):

Satz 5.6[Bearbeiten]

Sei , und es existiere ein mit und . Sind die Anfangsnäherungen und hinreichend nahe bei gewählt, so konvergiert die nach Streichung von Schritt (2) durch Algorithmus 7 erzeugte Folge superlinear gegen von der Ordnung .

Das Sekantenverfahren konvergiert also im Allgemeinen schneller als das Bisektionsverfahren und die Regula Falsi. Anders als diese, neigt es aber zu instabilem Verhalten, da der Fall und damit Auslöschung bei der Berechnung von eintreten kann.

Die schnelle Konvergenz des Sekantenverfahrens soll an einem Beispiel demonstriert werden.

Beispiel 5.7[Bearbeiten]

Es soll berechnet werden. Dies kann man tun, indem man die positive Nullstelle der Funktion z. B. in dem Intervall bestimmt. Der gesuchte Wert lautet auf 12 Stellen hinter dem Dezimalpunkt genau

Die Iterationsvorschrift des Sekantenverfahrens lässt sich hier vereinfachen zu

Man errechnet mit und für

mit und für

usw. Insgesamt erhält man die Iteriertenfolge

wobei die richtigen Ziffern jeweils unterstrichen sind.

Hätte man mit der ursprünglichen Formel (5.8) gearbeitet, wie man das meist in der Praxis zu tun hat, so hätte man 2 Funktionsauswertungen von zur Berechnung von und jeweils eine für die von bis , d. h. insgesamt 5 Funktionsauswertungen zur Berechnung von benötigt.

Funktionsauswertungen sind in vielen Situationen ein gutes praktisches Vergleichskriterium für unterschiedliche Algorithmen zur Lösung eines Problems, da diese häufig die numerisch teuersten Teilaufgaben bei der Problemlösung darstellen.

5.2.4 Das Newton-Verfahren[Bearbeiten]

Es sei nun und die Existenz eines mit vorausgesetzt. Beim Newton-Verfahren benötigt man nur eine Startnäherung für . Ist die Näherung für zu Beginn der -ten Iteration, so wählt man bei diesem Verfahren die Nullstelle der Tangente im Punkt an den Graphen von als nächste Näherung. Die Gleichung dieser Tangente ist offenbar durch

gegeben, so dass man

erhält. Wenn wir beispielsweise voraussetzen ( ist dann eine einfache Nullstelle), können wir dabei zumindest für solche , die nahe bei liegen, annehmen. (Im Fall und hätte die Tangente auch keine Nullstelle.) Das Newton-Verfahren lautet demnach:

Algorithmus 8 (Newton-Verfahren)[Bearbeiten]

(0) Wähle ein und , berechne und setze .
(1) Berechne ,
(5.9)
und .
(2) Falls , stop!
(3) Setze und gehe nach (1).

Bevor wir das Newton-Verfahren weiter untersuchen, betrachten wir sein Verhalten für das Problem in Beispiel 5.7.

Beispiel 5.8[Bearbeiten]

Es sei wieder und damit . Gesucht ist die positive Nullstelle von . Die Iterationsvorschrift des Newton-Verfahrens lässt sich hier schreiben als

Beginnend mit und berechnet man die Iterierten

Bei direkter Verwendung von (5.9) wären für die Berechnung von jeweils 3 Funktionsauswertungen von und , also insgesamt 6 Funktionsauswertungen erforderlich gewesen. Das Newtonverfahren ist also in diesem Fall ein sehr schnelles Verfahren. Bei diesem Beispiel und der Wahl von Startwerten (!) erreicht das Sekantenverfahren aber mit etwas weniger Aufwand sogar etwas höhere Genauigkeit.

Wir wollen uns nun mit der Konvergenz des Newton-Verfahrens beschäftigen. Dazu holen wir etwas weiter aus. Für eine gegebene Funktion nennen wir einen Punkt mit

einen Fixpunkt von . Weiter sprechen wir bei der Iterationsvorschrift

von der Fixpunktiteration mit der Verfahrensfunktion . Ist stetig und konvergiert die Iteriertenfolge, so muss ihr Grenzwert offenbar notwendig ein Fixpunkt von sein. Man beachte in diesem Zusammenhang, dass genau dann Fixpunkt von ist, wenn Nullstelle z. B. der Funktion ist, dass also die Probleme der Bestimmung einer Nullstelle und der eines Fixpunktes einer Funktion äquivalent sind.

Wir beweisen nun folgenden allgemeinen Satz über die lokale Konvergenz der Fixpunktiteration, wobei

eine offene -Umgebung des Punktes bezeichne.

Satz 5.9[Bearbeiten]

Sei gegeben und Fixpunkt von . Weiter sei in -mal differenzierbar mit einem , und es gelte entweder
(5.10)
Dann existiert ein , so dass die durch
erzeugte Iteriertenfolge für jeden Startpunkt gegen konvergiert und zwar mindestens von der Ordnung . Im Fall ist die Konvergenzordnung genau .

Beweis.[Bearbeiten]

Taylorentwicklung von um liefert für beide Fälle in (5.10)

für

Somit hat man

(5.11)

so dass zu einem gegebenen ein existiert und

(5.12)

mit und gilt. Im Fall sei dabei so klein gewählt, dass

ist, was aufgrund der Voraussetzung möglich ist. Für ist es offenbar möglich, so klein zu wählen, dass für alle folgt.

Die Ungleichung (5.12) impliziert nun für auch und damit im Fall auch für alle , so dass man

hat und daraus wegen die Konvergenz von mindestens der Ordnung schließen kann. Ist die Zusatzbedingung erfüllt und wird oben so gewählt, dass gilt, so gilt wegen (5.11)

(5.13)

Daraus folgt die genaue Konvergenzordnung in diesem Fall, denn wäre diese mindestens , so folgte mit (5.13) für ein und ein

und damit im Widerspruch zu Konvergenz von gegen

q.e.d.

In dem folgenden Satz wird nun unter verschiedenen Voraussetzungen eine jeweilige Konvergenzordnung des Newton-Verfahrens angegeben.

Satz 5.10[Bearbeiten]

Es sei gegeben und es existiere mit . Mit einem sei weiter für Aussage (i) und für Aussage (ii) . Dann gilt nach Streichung von Schritt (2) für die durch das Newton-Verfahren (Algorithmus 8) erzeugte Folge :
(i) Ist , dann existiert ein , so dass für jeden Startpunkt gegen konvergiert und zwar mindestens quadratisch. Im Fall konvergiert sogar von einer Ordnung .
(ii) Ist andererseits eine -fache Nullstelle von mit einem , d. h., ist
und ist weiter in zweimal differenzierbar, so ist die Iterationsfunktion
(5.14)
des Newton-Verfahrens differenzierbar in mit
(5.15)
und existiert ein , so dass für jeden Startpunkt (genau) linear gegen konvergiert.

Beweis.[Bearbeiten]

Die Behauptung folgt mit Satz 5.9, wenn man diesen auf in (5.14) anwendet sowie mit den folgenden Darstellungen. Im Fall (i) zeigt man zunächst die Stetigkeit von und in . Man ermittelt dann

so dass also

gilt. Damit folgt die Behauptung.

Im Fall (ii) erhält man

und somit

(5.16)

Wegen folgt damit und ist demzufolge aus (5.14) stetig in . Weiter hat man mit (5.16) wegen

Also ist und damit insbesondere auch .

q.e.d.

Man beachte, dass das Newton-Verfahren pro Iteration zwei Funktionsauswertungen benötigt, während das Sekanten-Verfahren nur eine verlangt. Im Fall, dass der Grenzwert eine einfache Nullstelle ist, konvergiert letzteres Verfahren unter geeigneten Voraussetzungen aber nur superlinear, während das Newton-Verfahren dann mindestens quadratisch konvergiert. Es stellt sich also die Frage, welches der Verfahren in der Praxis effizienter ist. Bemerkenswert ist es daher, dass man zeigen kann, dass das Sekantenverfahren, wenn man zwei Iterationen zu einer zusammenfasst und es damit etwa gleichen Aufwand pro Iteration wie das Newton-Verfahren bekommt, eine Konvergenzrate von mindestens hat, und es folglich lokal schneller als das Newton-Verfahren konvergiert. Allerdings neigt das Sekanten-Verfahren, anders als das Newton-Verfahren, aufgrund von Auslöschungen zu instabilem Verhalten.

5.3 Fixpunktiteration[Bearbeiten]

Wir verallgemeinern zunächst die Fixpunktiteration auf Funktionen , die wir in Abschnitt 5.2.4 für und hinreichend glattes diskutiert hatten. Für die Bestimmung eines Fixpunktes von , d. h. eines Punktes mit , betrachten wir also die Iterationsvorschrift

(5.17)

mit einem gegebenen Startwert . Wir definieren nun zunächst:

Definition 5.11[Bearbeiten]

(i) Sei und eine Norm auf dem . Eine Abbildung heißt Lipschitz-stetig auf mit (Lipschitz-)Konstante , wenn gilt:
(5.18)
(ii) Eine Lipschitz-stetige Abbildung mit Konstante heißt eine Kontraktion auf , wenn ist.

Sei nun speziell für , wobei wir damit eine Funktion mit

und stetigen partiellen Ableitungen für alle meinen. Für ein solches kann man in der Praxis häufig eine Konstante wie in (5.18) mittels der ersten Ableitung von bzw. der Jacobi-Matrix von , welche durch

gegeben ist, gewinnen. Dazu definieren wir:

Definition 5.12[Bearbeiten]

Eine Menge heißt konvex, falls für je zwei Elemente auch die ganze Verbindungsstrecke von nach zu gehört, d. h. falls

Damit lässt sich bekanntlich das folgende Lemma aus dem Mittelwertsatz der Differentialrechnung ableiten.

Lemma 5.13[Bearbeiten]

Es sei für eine offene, konvexe Menge und für eine Konstante gelte
Dann folgt die Abschätzung

Dazu geben wir Beispiele.

Beispiel 5.14[Bearbeiten]

(1) Die Funktion ist auf eine Kontraktion, denn es ist

und mit

(2) Die Funktion ist auf mit nicht Lipschitz-stetig, denn für hat man

und .

Der folgende sog. Banachsche Fixpunktsatz gibt an, dass die Fixpunktiteration (5.17) konvergiert, und zwar für allgemeines und ohne Differenzierbarkeitsforderungen an , wobei als Startvektor alle Elemente der zugrunde gelegten Menge zugelassen sind. Überdies liefert er unter den genannten Voraussetzungen die Existenz eines eindeutigen Fixpunktes. Die geforderte Kontraktionseigenschaft für die Iterationsfunktion ist allerdings eine relativ starke Voraussetzung.

Satz 5.15[Bearbeiten]

Sei abgeschlossen und die Abbildung bezüglich der Vektornorm eine Kontraktion mit Konstante . Dann gilt:
(i) besitzt genau einen Fixpunkt .
(ii) Für jeden Startpunkt liefert die Fixpunktiteration
(5.19)
eine Folge in , welche gegen konvergiert und man hat
(5.20)

Beweis.[Bearbeiten]

(i) Sind Fixpunkte von , so gilt

bzw. , was impliziert. Also besitzt höchstens einen Fixpunkt.

(ii) Sei nun der Startvektor beliebig und bezeichne die damit durch die Fixpunktiteration (5.19) erzeugte Folge. Für ist dann offenbar auch in , so dass folgt. Man hat somit weiter

so dass man die folgenden Abschätzungen für erhält:

Also gilt

(5.21)

Demnach ist die Folge eine Cauchy-Folge und hat sie als solche einen Grenzwert . Da nach Voraussetzung (Lipschitz-)stetig ist und die Fixpunktiteration dann, wenn sie konvergiert, gegen einen Fixpunkt konvergiert, ist der (eindeutige) Fixpunkt von . Der Grenzübergang „“ in (5.21) liefert schließlich die Abschätzung (5.20).

q.e.d.

Man beachte, dass man unter den Voraussetzungen des Banachschen Fixpunktsatzes mindestens lineare Konvergenz für die Fixpunktiteration hat, denn dann gilt

wobei ist. Der Ausdruck

in (5.20) kann, nachdem berechnet wurde, für jedes vor Beginn der Iteration bestimmt werden. Er ermöglicht eine a priori Fehlerabschätzung für den Approximationsfehler . Weiter hat man wegen für eine Abbruchschranke

mit

so dass mit (5.21) folgt:

Praktisch ist also spätestens in Schritt mit

(5.22)

die Fehlerabschätzung erfüllt, wobei die kleinste ganze Zahl bezeichnet.

Der mittlere Ausdruck in (5.20) kann im -ten Iterationsschritt bestimmt werden und erlaubt eine a posteriori Fehlerabschätzung für den Approximationsfehler . Praktisch wird für eine gegebene Schranke in Schritt abgebrochen, wenn erstmalig

erfüllt ist. In diesem Fall genügt der Fehlerabschätzung .

Wir geben dazu ein Beispiel.

Beispiel 5.16[Bearbeiten]

Es sei

Dann hat man

für

Diese Nullstelle soll nun approximativ berechnet werden. Mit

gilt offenbar

so dass wir dazu die Fixpunktiteration mit der Iterationsfunktion anwenden wollen.

Dafür müssen wir zunächst die Voraussetzungen von Satz 5.15 überprüfen. Auf dem Intervall ist monoton fallend und somit

sowie

Also ist eine Kontraktion. Die folgende Tabelle liefert für den Startwert ausgewählte Iterierte des Verfahrens:

Die Situation soll nun für genauer betrachtet werden. Die Fehlerabschätzung (5.20) liefert in diesem Fall

Der tatsächliche Fehler

wird also durch die a posteriori Abschätzung um etwa den Faktor 4 und durch die a priori Abschätzung um etwa den Faktor 9 überschätzt.

Das praktische Vorgehen soll nun für die spezielle Fehlerschranke illustriert werden. Der (üblicherweise unbekannte) Approximationsfehler unterschreitet diese Schranke bereits für , denn man hat . Die a posteriori Abschätzung liefert dagegen für

also als Stoppzahl, während die a priori Abschätzung in (5.22) mit

Fehler beim Parsen (Syntaxfehler): {\displaystyle a = \log \left( \frac{(1 - L) \varepsilon}{\|x^1 - x^0\|} \right) / \log(L) = \log \left( \frac{\left( 1 - e^{-1/2} \right) 0.007\ 6}{0.576\ 949\ 81 - 0.55} / \log(e^{-1/2}) \approx 4.397}

die Vorhersage macht.

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:

Beweis.[Bearbeiten]

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.

Beweis.[Bearbeiten]

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