0 Daumen
1k Aufrufe

Ich habe gelernt, wie man die Newtonsche Methode zur immer genaueren Bestimmung von Wurzeln anwendet. Der Algorithmus ist mir klar:

x2 = x1 – f(x)/f'(x)

Doch was ist der Grund, warum x2 näher am gesuchten Wurzelwert ist als der willkürlich gewählte Punkt x1 und warum rückt x3 noch näher an jenen heran?

Avatar von

2 Antworten

0 Daumen

Doch was ist der Grund, warum x2 näher am gesuchten Wurzelwert ist als der willkürlich gewählte Punkt x1

Es gibt keinen. Das Newtonverfahren kann auch divergieren, vor allem, wenn Du x1 willkuerlich waehlst. Es gibt aber einen Satz, nachdem die Newtonfolge immer gegen die Nullstelle ξ (die muss existieren!) einer "anstaendigen" Funktion konvergiert, wenn man den Anfangswert x1 nahe genug an ξ waehlt.

Geometrische Veranschaulichungen zum Newtonverfahren findest Du zuhauf im Netz.

Avatar von
0 Daumen

§1: Newton-V. funktioniert (konvergiert) mit jeder Funktion, die die Konvergenzkriterien erfüllt.

§2: "Deine Wurzel" ist nichts weiter als eine primitive Potenzfunktion:

Wurzel(x)=sqrt(x)=x^{1/2}=e^{ln[x]/2}

ohne Ausbuchtungen, gleichmäßig ansteigend -> also nichts besonderes, sondern ideal für dieses Verfahren.

§3:Alles beschrieben unter

https://de.wikipedia.org/wiki/Newton-Verfahren

In der Animation mit der Tangente musst Du Dir dass so vorstellen:

Du gehst mit einer langen Stange (Tangente) einen Berg herab und suchst Meeresspiegelhöhe (Nullstelle)

Wenn der Berg flach ist (geringer Anstieg) musst Du bei gleicher Anfangshöhe weit laufen (Delta x; nicht verwechseln mit Wegstrecke entlang der Funktionskurve) um bis zum Meer zu kommen.

Wenn Abhang sehr steil (Klippe = sehr großer Anstiegsbetrag {denn beim Herunterlaufen ist das Vorzeichen negativ})

reichen wenige Delta x, um ins Meer zu fallen.

Man hat also über den Anstieg einer Funktion an einem Punkt das mathematische Hintergrundwissen, wie weit es noch sein wird.

Natürlich darf man bei Funktionen mit starken Ausbuchtungen (Bergsee), nicht "blind" ein lokales Extremum (wo auch Anstieg zu 0 werden kann) mit einsetzen. Aber so etwas gibt es ja bei der Wurzelfunktion nicht.

Das schöne am Newton-Verfahren ist die meist (bei einfachen Funktionen ohne viele Ausbuchtungen) vorhandene

quadratische Konvergenzgeschwindigkeit.

Im Gegensatz zur Bisektion ( https://de.wikipedia.org/wiki/Bisektion ),

wo nur 2 Bereiche verglichen werden und pro Iterationsschritt etwa 1 Nachkommastelle verbessert wird,

schafft die Newton-Iteration pro Iterationsschritt eine Verdopplung der Nachkommastellen, weil sie ja den Anstieg mit berücksichtigt (also Erweiterung der Information über eine Funktion)! Besonders ab 100 Nachkommastellen unschlagbar schnell.

Der Iterationsrechner unter http://www.gerdlamprecht.de/Roemisch_JAVA.htm

rechnet das in den Beispielen 2, 4, 118 online vor und gibt eine Wertetabelle aus (Pro Schritt, also pro Iteration).

Im Beispiel 2 kann man mit der Erweiterung aB[i]=c;

leicht die Wertetabelle füllen lassen: 49 Schritte für 15 Nachkommastellen bei Bisektion.

Beispiel 118 schafft gleiche Genauigkeit mit 4 Schritten!

Vorsicht mit der Abbruchbedingung: wenn die kleiner als die Rechengenauigkeit von double (15 Stellen) ist, wird diese Bedingung unter gewissen Umständen nie erreicht -> Endlosschleife!

Wenn man sich nicht sicher ist, besser i>9 als Abbruch angeben, denn nach spätestens 9 Schritten ist sicher, ob Konvergenz vorliegt & wie groß Zwischenergebnisse (Differenz zur wirklichen Nullstelle) sind.

Wurzel von 1 Mrd. (1e9 ) kann nie mit Datentyp Double auf 15 Nachkommastellen genau berechnet werden!

Am einfachsten lässt sich natürlich das "Ziel" bestimmen, wenn der Anstieg konstant ist -> dazu braucht man aber keine Iteration, sondern kann das durch Gleichung umstellen direkt berechnen.

Bei Funktionen mit irrationalem Ergebnissen (unendlich viele Nachkommastellen) ist es wie im Nebel: man hat zwar ein Gefühl, wie steil der Berg gerade ist, aber wenn man da angekommen ist (was man prognostiziert hat), stell man fest, dass es noch nicht genau genug war. Das kann man bis in alle Ewigkeit so machen.

Bei der Wurzelfunktion ergeben alle Argumente - bis auf wenige Quadratwerte - immer irrationale Ergebnisse!

Avatar von 5,7 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community