[WS] Eindimensionale Nullstellenprobleme 2 - Das Newton Verfahren |
17.08.2007, 16:20 | tigerbine | Auf diesen Beitrag antworten » |
[WS] Eindimensionale Nullstellenprobleme 2 - Das Newton Verfahren
|
||
17.08.2007, 16:21 | tigerbine | Auf diesen Beitrag antworten » |
0. Beispiele In der Kurzübersicht der Verfahren würde erwähnt, dass es sich bei dem Newton-Verfahren um ein lokal konvergentes Verfahren handelt. Dazu sollen hier noch 3 weitere Fälle neben dem Beispiel mit der Arcustangens Funktion betrachtet werden.
|
||
17.08.2007, 17:03 | tigerbine | Auf diesen Beitrag antworten » |
1. Konvergente Folge |
||
17.08.2007, 19:21 | tigerbine | Auf diesen Beitrag antworten » |
2. Konvergenzgeschwindigkeiten und Konvergenz Allgemein spricht man bei einem Iterationsverfahren zur Berechnung einer Größe x* von Konvergenz mit der "Ordnung" q, , wenn gilt: Genügt eine Folge dieser Abschätzung, so muß man jedoch erst einmal prüfen, ob wirklich Konvergenz vorliegt. Dazu macht man die folgende Fallunterscheidung:
Im Fall (a), also der linearen Konvergenz sollte noch folgendes bemerkt werden:
|
||
18.08.2007, 18:58 | tigerbine | Auf diesen Beitrag antworten » |
3. Lineare Konvergenzrate bei Fixpunktiterationen stetig differenzierbarer Funktionen Lautet die Iterationsvorschrift einer konvergenten Fixpunktiteration mit einer stetig differenzierbaren Funktion g, so folgt: In einer Grenzwertbetrachtung liefert dies: D.h. hier ist die lineare Konvergenzrate asymptotisch gleich g'(x*). Im Falle g'(x*)=0 liegt also (mindestens) superlineare Konvergenz der Fixpunktiteration vor. |
||
19.08.2007, 00:35 | tigerbine | Auf diesen Beitrag antworten » |
4. Richtige Dezimalstellen Welche Bedeutung haben die Konvergenzordnung und die Konvergenzrate?
|
||
Anzeige | ||
|
||
21.08.2007, 01:22 | tigerbine | Auf diesen Beitrag antworten » |
Newton-Verfahren In den nächsten Abschnitten soll sich mit dem Konvergenzverhalten des Newton-Verfahrens für verschiedene Funktionen befasst werden. |
||
21.08.2007, 02:19 | tigerbine | Auf diesen Beitrag antworten » |
5. Einfache Nullstellen einer C²-Funktion Sei f zweimal stetig differenzierbar (auf [a,b]), mit einer von 0 verschiedenen Ableitung und x* eine einfache Nullstelle in diesem Intervall, d.h. es gilt: Dann gibt es eine Umgebung derart, dass das Newton-Verfahren für jeden Startwert quadratisch gegen x* konvergiert. Beweis: Damit wäre der erste Schritt getan. Obiger Satz enthält ja noch eine Behauptung über die Konvergenzgeschwindigkeit. Die Funktion f ist 2mal stetig differenzierbar, daher lautet ihr Taylorpolynom vom Grad 1 mit dem Restglied von Lagrange wie folgt (Entwicklungspunkt ) Der Index bei soll nur verdeutlichen, dass diese Variable von x abhängt.
Und somit ist die für die quadratische Konvergenz benötigte Abschätzung gefunden. Die verwendete Bezeichnung erklärt sich wie folgt. Hätte man die Konvergenz des Verfahrens nicht über den anziehenden Fixpunkt gezeigt, sondern aus der Abschätzung (#) zeigen müssen, so ist nötig, den Radius r so zu wählen, dass gilt: Dann konvergiert das Verfahren für alle Startwerte aus der Umgebung |
||
21.08.2007, 03:22 | tigerbine | Auf diesen Beitrag antworten » |
6. Einfache Nullstellen einer C-Funktion Sei f einmal stetig differenzierbar (auf [a, b]) und x* eine einfache Nullstelle in diesem Intervall, d.h. es gilt: Dann gibt es eine Umgebung derart, dass das Newtonverfahren für jeden Startwert superlinear gegen x* konverviert. Beweis:
Sei nun f' zusätzlich noch Lipschitz-stetig, d.h. es gibt eine Konstante L > 0 mit: Dann ist die Konvergenzrate quadratisch. Beweis:
|
||
21.08.2007, 15:01 | tigerbine | Auf diesen Beitrag antworten » |
7. Newton für p-fache Nullstellen einer C²-Funktion Nun soll sich mit der Frage beschäftigt werden, ob das Newton-Verfahren auch zur Bestimmung mehrfacher Nullstellen einer Funktion f anwendbar ist. Zunächst einmal formuliert man einfach einmal das Verfahren. Newton-Iteration zugehörige Fixpunktfunktion Da die Funktion h auf dem Intervall [a,b] zweimal stetig differenzierbar ist, betrachtet man zunächst einmal die Ableitungen der Funktion f: Es ist nun die stetige Funktion g an der Stelle x* nicht definiert. Welche Art von Unstetigkeitsstelle liegt vor? Eine hebbare (Funktionsgraph hat ein Loch) und g besitzt eine stetige Fortsetzung (SF). Somit gilt für sie folgenden Grenzwerte: Welche Art von Fixpunkt liegt mit x* bei der Funktion g nun vor? Wobei man auch hier die Definitionslücke bei x^* stetig fortsetzen kann. Es gilt also: Somit ist der Fixpunkt x* anziehend und aus der stetigen Fortsetzbarkeit der Ableitung g' folgt, dass es eine Umgebung von x* gibt, in der die Fixpunktiteration konvergiert. Bleibt als letztes noch die Frage nach der Konvergenzgeschwindigkeit. Die Antwort darauf haben wir mit Gliederungspunktt (3) schon geleistet. Die lineare Konvergenzrate ist also asymptotisch gleich . Somit liegt keine superlineare Konvergenz vor, und damit auch keine der Ordnung 2 oder höher. Fazit Das Newton-Verfahren kann auch bei mehrfachen Nullstellen anwendbar sein, je größer die Vielfachheit der Nullstelle ist, umso langsamer konvergiert es jedoch. |
||
21.08.2007, 19:43 | tigerbine | Auf diesen Beitrag antworten » |
8. Modifiziertes Newton-Verfahren bei p-fachen Nullstellen Vorarbeit Sei x* eine 2-fache Nullstelle einer 3-fach stetig differenzierbaren Funktion f. Hierfür formuliert man die Newton-Iteration: Mit dem Verallgemeinerten Mittelwertsatz der Differentialrechnung folgt: Nun sei x* eine p-fache Nullstelle einer (p+1)-fach stetig differenzierbaren Funktion f. Es gilt dann also: Taylor-Polynom um x* mit Restglied Ableitung der Taylordarstellung Damit ergibt sich für f'(x) ungleich 0: Nun macht man den modifizierten Ansatz Daraus ergibt sich dann: Nun benutzt man obige Umrechung, so ergibt sich: Zur Interpretation stellt man noch ein wenig um: Nun versucht man I, II abzuschätzen. Wählt man nun so folgt: Aufgrund der stetigen Differenzierbarkeit der Funktion f sind sowohl ihre Ableitungen sowie die daraus resultierenden Betragsfunktionen stetig. Sie nehmen daher auf einer kompakten Umgebung von x* ein Minimum und ein Maximum an. Man definiert: Und man erhält ein "Quadratisches" Konvergenzverhalten wie im Fall der einfachen Nullstelle: |
||
22.08.2007, 02:18 | tigerbine | Auf diesen Beitrag antworten » |
9. Vereinfachtes Newton-Verfahren Ist x* die Nullstelle einer stetig differenzierbaren Funktion f, so haben wir gesehen, dass die Newton-Iteration gegen x* konvergiert, wenn der Startwert nur nahe genug bei x* gewählt wird. Jeder Iterationsschritt erfordert die Auswertung der Funktion f und die der Ableitung f', was bei komplizierten Funktionen unter Umständen zuviel Aufwand bedeutet. In solchen Fällen geht man zum sogenannten "Vereinfachten Newton-Verfahren" über: mit einen geeignet gewählten Punkt c. Diese Iteration ist Spezialfall der allgemeineren Fixpunktiteration: mit einer geeigneten Zahl . Für hatten wir diese Iterationsvorschrift schon hier gesehen. Die Wahl war jedoch ungeeignet. |
||
22.08.2007, 03:52 | tigerbine | Auf diesen Beitrag antworten » |
10a. Höhere Konvergenzordnungen Sei x* eine einfache Nullstelle der Funktion f, so ist sie ein Fixpunkt der folgenden folgenden Funktion: Dies ist i.A. von Null verschieden. Somit folgt die quadratische Ordnung der Fixpunktiteration. Vergleiche hierzu [Workshop - Fixpunktiterationen] |
||
22.08.2007, 03:57 | tigerbine | Auf diesen Beitrag antworten » |
10b. Verfahren 3ter Ordnung für einfache Nullstelle Nun sucht man in Anwendung von [9] ein Verfahren, so dass man zu einer einfachen Nullstelle der Funktion f eine Fixpunktiteration der Ordnung 3 erhält. Es muss also gelten: Man macht den Ansatz: x* soll einfache Nullstelle von f sein Damit gilt: Und somit: Wähle: Dann gilt: Somit hat das Verfahren mind. die Ordnung 3, vergleiche [9] |
||
23.08.2007, 00:31 | tigerbine | Auf diesen Beitrag antworten » |
11. Newton Verfahren zur Berechnung von Nullstellen von Polynomen Ziel ist die Berechnung einer Nullstelle eines Polynoms
|
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |
|