Beispiel zum Newton-Verfahren gesucht

Neue Frage »

tigerbine Auf diesen Beitrag antworten »
Beispiel zum Newton-Verfahren gesucht
Servus,

ich zerpflücke gerade meine Numerik Vorlesung und anstatt endlich den großen Durchblick zu bekommen, stellen sich immer mehr Fragen. Meine Internet-Recherche hat mich auch nicht viel "schlauer gemacht.

Also, die "Million-Dollar-Question" ist, wann und wie schnell konvergiert das Newton-Verfahren.

Dabei will ich mich zunächst euf den eindimensionalen Fall beschränken. Gerne wird einem hier ja einfach die quadratische Konvergenz vor die Füße geworfen, die man ja mit dem Beispiel widerlegen kann.

Nagut, dann eben nur für "einfache Nullstellen". Und genau an dieser Stelle komme ich nicht weiter. Da stehen im Satz nämlich noch mehr Forderungen drin.

Sei z eine einfache Nullstelle von der Funktion auf dem Intervall [a,b]. Des weiteren

(1) soll z die einzige Nullstelle von f auf [a,b] sein
(2) f soll auf [a,b] zweimal stetig differenzierbar sein

Dann gibt eine eine Umgebung K von z derat, das das Newton Verfahren für alle STartwerte aus K quadratisch gegen z konvergiert.

So, die Sache scheint also doch nicht so einfach zu sein, wie sie gerne hingestellt wird. "...f muss diffbar sein..." als einzige weitere Anfordung im Vergleich z.B. zu Bisektion (Stetigkeit von f gefordert).

Um nun obigen Satz zu verifizieren bin ich auf deer Suche nach einer Funktion, mit einfacher Nullstelle in einem Intervall [a, b], die nicht zweimal stetig diffbar ist. (Konvergiert Newton für diese Funktion? Wenn ja, wie schnell?) Das Beispiel sollte gerade die Notwendigkeit von (2mal stetig diffbar verdeutlichen)

Wäre schön wenn mir da jemand unter die Arme greifen könnte. Bin da gerade etwas entnervt. Die klassischen Klausuraufgaben zu dem Thema sind ja auch eher für den "A...". Der Nachweis der Konvergenz über den Nachweis der linearen Konvergenzrate klappt da ja auch nur, weil man die Nullstelle schon kennt. Sehr witzig, dann brauch man Newton ja auch oft nicht mehr!

Gruß in die Nacht von der Tigerbine unglücklich
mathemaduenn Auf diesen Beitrag antworten »
RE: Beispiel zum Newton-Verfahren gesucht
Hallo tigerbine
Zitat:
Original von tigerbine
So, die Sache scheint also doch nicht so einfach zu sein, wie sie gerne hingestellt wird. "...f muss diffbar sein..." als einzige weitere Anfordung im Vergleich z.B. zu Bisektion (Stetigkeit von f gefordert).

Um nun obigen Satz zu verifizieren bin ich auf deer Suche nach einer Funktion, mit einfacher Nullstelle in einem Intervall [a, b], die nicht zweimal stetig diffbar ist. (Konvergiert Newton für diese Funktion? Wenn ja, wie schnell?) Das Beispiel sollte gerade die Notwendigkeit von (2mal stetig diffbar verdeutlichen)

Das f 2mal stetig diffbar ist braucht man glaub ich gar nicht für die quadratische Konvergenz.Es reicht imho und f Lipschitz stetig. DAS Newtonverfahren ist schon sinnvoll wenn man weiß( oder glaubt :-) ) das man sich nahe an der Nullstelle befindet. Wenn man vom Startwert unabhängig sein will kann man z.B. Intervall Arithmetik benutzen oder Armijo Schrittweitensteuerung( Abstieg sichern)
viele Grüße
mathemaduenn
tigerbine Auf diesen Beitrag antworten »
RE: Beispiel zum Newton-Verfahren gesucht
Das ist dann aber wieder ein anderer Satz! Wenn man den mehrdimensionalen Fall betrachtet lautert dieser:

Sei stetig differenzierbar, x* eine Nullstelle von F und F'(x*) regulär. Dann existiert eine epsilon-Kugel um x*, derart, dass für jeden Startwert gilt:

(a) Das lokale Newton-Verfahren ist wohldefiniert und erzeugt eine gegen x* konvergente Folge

(b) Die Konvergenzrate ist superlinear

(c) Die Konvergenzrate ist quadratisch, fofern F' zusätzlich lokal Lipschitz-stetig ist


Ich habe versucht, den Beweis hiezu zu verstehen und ihn auch für den eindimensionalen Fall zu verifizieren. Aber dabei wird ein Lemma verwendet, dass ich nicht verstehe. Da wird die Konvergenz der erzeugten Folge schon vorausgesetzt, aber gerade die soll ja gezeigt werden.

Ich danke Dir erstmal für deine Antwort, aber sie hilft mir leider nicht weiter. Aus der Überprüfung, dass eine Folge der Definition der quadratischen konvergenz genügt, folgt nämlich leider nicht dass die Folge überhaupt konvergiert. Das wird sehr oft unter den Tisch fallen gelassen.

Wenn es wirklich so wäre, warum schreibt dann "keiner" den Beweis, sei x* eine einfache Nullstelle von f, d.h. und , dann gibt es eine epsilon Umgebung um x*, so dass das Newotn Verfahren für alle Startwerte innerhalb dieser Kugel konvergiert? Wie schnell ist dann eine andere Sache!

Mir ist aber bislang aber nur der Beweis für f zweimal stetig diffbar, etc... wie im ersten Post unter die Finger gekommen.

Augenzwinkern
papahuhn Auf diesen Beitrag antworten »
RE: Beispiel zum Newton-Verfahren gesucht
Beim Beweis entwickelt man die Funktion um bis zum quadratischen Teil auf. Ich vermute, man braucht hier die Stetigkeit, um das reinzubasteln (Mittelwertsatz oder so). Ein Beispiel habe ich dazu leider auch nicht.
tigerbine Auf diesen Beitrag antworten »
RE: Beispiel zum Newton-Verfahren gesucht
Danke. Den Beweis für den eindimensionalen Fall habe ich verstanden. Mir geht es um folgendes. Wenn das Newton-VErfahren eingeführt wird, kommt der Satz:

"Das Newton Verfahren ist ein lokal quadratisch konvergentes Verfahren zur Nullstellenbestimmung einer differenzierbaren Funktion."

Ich bin der Meinung, dass das falsch ist. Denn alle Beweise die ich bislang gefunden habe, stellen eben weitere Bedingungen. Zunächst mal stetig diffbar, gerne auch zweimal. Warum ist mir dann schon klar. Aber wie passt das mit obiger Aussage zusammen. Wenn das so einfach wäre, nach dann hätte man doch einfach folgende Aussage beweisen müssen:

"Sei f eine differenzierbare Funktion und x* eine Nullstelle von f. Dann gibt es eine Epsilon-Umgebung von x* derart, dass das Newton Verfahren für alle Startwerte der Umgebung gegen x* konvergiert."

Den Beweis habe ich aber noch nicht gefunden. Deswegen suche ich Gegenbeispiele, aus denen die weiteren Bedingungen ersichtlich werden.

Gruß Wink
mathemaduenn Auf diesen Beitrag antworten »

Hallo tigerbine,
Stetige Differenzierbarkeit brauchst Du auf jeden Fall sonst ist die Durchführbarkeit sprich nicht gesichert. Und die braucht man ja als allererstes.
viele Grüße
mathemaduenn
Edit: Ein Bsp. wäre eine Funktion bei der beliebig nahe an der Nst. x=0 Nullstellen der Ableitung liegen.
Edit2: Die Fkt. ist nat. nicht richtig definiert und soll für x=0 Null sein ;-)
 
 
tigerbine Auf diesen Beitrag antworten »

Zitat:
Original von mathemaduenn
Hallo tigerbine,
Stetige Differenzierbarkeit brauchst Du auf jeden Fall sonst ist die Durchführbarkeit sprich nicht gesichert. Und die braucht man ja als allererstes.


Das ist so nicht korrekt. Die Funktion f(x) = x² hat ihre Nullstelle bei x*=0 und es gilt f'(x*) = 2x* = 0. dennoch konvergiert das Newton-Verfahren linear.

Man muss auch immer noch untersuchen ob der´Grenzwert f(x*)/f'(x') in diesem Fall existiert. Newton muss also nicht scheitern! Augenzwinkern

Wofür war jetzt das Beispiel verwirrt Sorry
mathemaduenn Auf diesen Beitrag antworten »

Hallo Tigerbine
Zitat:
Original von tigerbine
Zitat:
Original von mathemaduenn
Hallo tigerbine,
Stetige Differenzierbarkeit brauchst Du auf jeden Fall sonst ist die Durchführbarkeit sprich nicht gesichert. Und die braucht man ja als allererstes.


Das ist so nicht korrekt. Die Funktion f(x) = x² hat ihre Nullstelle bei x*=0 und es gilt f'(x*) = 2x* = 0. dennoch konvergiert das Newton-Verfahren linear.

Man muss auch immer noch untersuchen ob der´Grenzwert f(x*)/f'(x') in diesem Fall existiert. Newton muss also nicht scheitern! Augenzwinkern

Dafür muß erstmal der Funktionswert an der Nullstelle der Ableitung 0 sein.
Zitat:
Original von tigerbine
Wofür war jetzt das Beispiel verwirrt Sorry

Damit Du nicht behaubten kannst das der Funktionswert an den ensprechenden Nst. von f' auch 0 ist und man somit eine Sonderbetrachtung machen muß *grins* oder zum ausprobieren wie Du willst. Du wolltest Doch ein Bsp. oder?
viele Grüße
mathemaduenn
Neue Frage »
Antworten »



Verwandte Themen

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