[WS] Eindimensionale Nullstellenprobleme 2 - Das Newton Verfahren

Neue Frage »

tigerbine Auf diesen Beitrag antworten »
[WS] Eindimensionale Nullstellenprobleme 2 - Das Newton Verfahren
Gliederung


  1. Konvergente Folge

  2. Konvergenzgeschwindigkeiten und Konvergenz

  3. Lineare Konvergenzrate bei Fixpunktiterationen stetig differenzierbarer Funktionenn

  4. Richtige Dezimalstellen


  5. Newton für C²-Funktionen und einfache Nullstelle

  6. Newton für C-Funktionen und einfache Nullstelle

  7. Newton für C²-Funktionen und p-fache Nullstelle

  8. Modifiziertes Newton-Verfahren bei mehrfachen Nullstellen


  9. Konvergenzordnung von Fixpunktiterationen


  10. Bezug Newton-Verfahren und Fixpunktiterationen

    10a. einfache Nullstelle einer C²-Funktion

    10b. Verfahren 3ter Ordnung für einfache Nullstelle


  11. Newton Verfahren zur Berechnung von Nullstellen von Polynomen
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.


  1. Das Verfahren trifft auf einen lokalen Extremwert. In diesem Fall ist die Ableitung gleich Null. Division nicht möglich.




  2. Das Verfahren nähert sich nicht der Nullstelle, sondern entfernt sich



  3. Das Verfahren oszilliert


 
 
tigerbine Auf diesen Beitrag antworten »
1. Konvergente Folge


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:


  1. Lineare Konvergenz, q=1




    Folgerung:




    Es folgt




  2. Konvergenz der Ordnung q > 1




    Folgerung:



    Gilt dann , so konvergiert die Folge gegen x*. D.h. der Startwert muss nahe genug bei x* liegen.



Im Fall (a), also der linearen Konvergenz sollte noch folgendes bemerkt werden:

  • Lineare Konvergenzrate

    Darunter versteht man die "beste Konstante" c für die Abschätzung in (a). also den Grenzwert



  • Superlineare Konvergenz

    Gilt die Abschätzung für eine Nullfolge



    so spricht man von superlinearer Konvergenz.

    Folgerung:

    Ist nun von einer Folge diese Eigenschaft bekannt, so kann man folgende Aussage über ihre Konvergenz treffen.

    Es gibt ein K, ab dem für alle gilt . Es folgt dann:



    Somit folgt ab diesem K aus der linearen Konvergenz, die Konvergenz der Folge (siehe a).


    Liegt superlineare Konvergenz vor, so gilt:



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.
tigerbine Auf diesen Beitrag antworten »
4. Richtige Dezimalstellen
Welche Bedeutung haben die Konvergenzordnung und die Konvergenzrate?

  • Die Lineare Konvergenzrate bedeutet, dass sich in jedem Iterationsschritt (für große k) die Anzahl der richtigen Mantissendezimalen um



    erhöht.

  • Die Konvergenzrate q bedeutet, dass sich (für große k) die Anzahl der richtigen Mantissenstellen ver -q - facht.
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.
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
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:

  1. Da und stetig ist, gibt es eine Umgebung , so dass ist

  2. In dieser Umgebung ist dann wohl definiert.

  3. Da f stetig differenzierbar ist, kann man den Mittelwertsatz der Differenzialrechnung anwenden. Dies führt für zu:



  4. Da f' stetig ist und zwischen und liegt, kann man den Radius r ggf. soweit verkleinern, dass gilt:



  5. Mit Induktion folgt dann, dass für alle Iterierten in . Somit ist das Newton Verfahren wohl definiert.

  6. Damit folgt aus die "lineare Konvergenz" (und damit die Konvergenz!) der Folge gegen x*.

  7. Da nun die Folge gegen x* konvergiert, folgt aus

    , die superlineare Konvergenz des Newtonverfahrens.




Sei nun f' zusätzlich noch Lipschitz-stetig, d.h. es gibt eine Konstante L > 0 mit:





Dann ist die Konvergenzrate quadratisch.



Beweis:

  1. Da f' stetig auf dem Kompaktum ist, nimmt die Funktion dort ein Minimum m > 0 an, d.h.



  2. Mit obigen Überlegungen folgt nun:



    und somit die quadratische Konvergenz.
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.



Lehrer Fazit
Das Newton-Verfahren kann auch bei mehrfachen Nullstellen anwendbar sein, je größer die Vielfachheit der Nullstelle ist, umso langsamer konvergiert es jedoch.
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:

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 .


Lehrer
Für hatten wir diese Iterationsvorschrift schon hier gesehen. Die Wahl war jedoch ungeeignet.
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]
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]
tigerbine Auf diesen Beitrag antworten »
11. Newton Verfahren zur Berechnung von Nullstellen von Polynomen
Ziel ist die Berechnung einer Nullstelle eines Polynoms



  1. Wahl eines Startwertes


  2. Auswertung von p und p' mit dem Horner-Schema

    Für => Startwert ändern (Extremstelle der Ableitung)


  3. Newton-Korrektur:





  4. Iterationsschritt:



Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »