Iterationsverfahren für Nullstellen

Auf dieser Seite werden einige Iterationsverfahren für Nullstellenapproximation interaktiv dargestellt.

Das Newtonverfahren gewinnt die Folge der Näherungen über die Nullstellen der jeweiligen Tangenten.
Für deren Steigungsdreieck mit der Spitze in deren Nullstelle und der oberen Ecke im Berührpunkt (x|f(x)) gilt: f'(x)=f(x)/Δx (m=Δy/Δx), d.h. Δx=f(x)/f'(x). Für positive Steigung liegt die Nullstelle links (und umgekehrt), d.h. x-f(x)/f'(x) ist die Nullstelle der Tangente bei x und die nächste Näherung im Newtonverfahren.
Mit der Funktion h(x):=f(x)/√(|f'(x)|) konvergiert das Newtonverfahren schneller, wenn die Steigungen von f ab dem Startwert zur Nullstelle hin betragsmäßig zunehmen, also insbesondere dann, wenn die Startstelle zwischen Nullstelle und einem Extremum liegt.
h hat die gleichen Nullstellen wie f (das ja im Zähler steht), dort jeweils Wendepunkte sowie einen wesentlich geraderen Verlauf, außerdem in der Regel Polstellen bei den Extrema von f.
Konstruiert man Parabeln p oder kubische Kurven k an f und die Stelle x mit p⁽ⁱ⁾(x)=f⁽ⁱ⁾(x) (i-Ableitung; i ∈ {0;1;2} ) bzw. mit k⁽ⁱ⁾(x)=f⁽ⁱ⁾(x) (i ∈ {0;1;2;3} ), so sind meist deren Nullstellen viel näher an der Nullstelle von f.
Hinweis: Berechnet man die Nullstelle der Parabel nicht komplett explizit, sondern ersetzt ein x im quadratischen Term durch die (lineare) Näherung aus dem Newtonverfahren, ergibt sich genau das zweite Verfahren. Siehe die Ausführungen im →Anhang.

Die Anzahl der Iterationen ist auf 20 beschränkt. (Klicken Sie auf die Zahl zum Ändern.) Die Iteration bricht ab, wenn sich die Näherungen im Rahmen der Rechengenauigkeit (ca. 10^-15) nicht mehr ändern oder f(x_n)≈0 ist.

Der Funktionsterm kann mit den üblichen Schreibkonventionen frei eingegeben werden, der Plotausschnitt ist — wie auf diesen Seiten üblich — mit der Maus verschieb- und zoombar. Der Startwert x₀ läßt sich im entsprechenden Feld eingeben, im Graph per Doppelklick festlegen oder mit gedrückter Maustaste verschieben.

Die Näherungsstellen sind sowohl in der Graphik als auch der Liste maussensibel: beim Draufzeigen werden die Stelle(n) im Graph und der Liste sowie der zugehörige Weg zur jeweils besseren Näherung im Graph markiert. Beim Draufklicken wird die Stelle zentriert, optional auch die Folgestelle mit der Tangente (oder entprechend der Parabel). Einstellmöglichkeiten dazu unter der Graphik. Klick auf die Listenüberschriften stellt auf Startwert, ein Doppelklick dort startet eine Komplettanimation der jeweiligen Nullstelleniteration. Falls es mit Doppelklick nicht funktionieren sollte, steht die Alternative mit Shift+Mausklick (einfacher Klick) zur Verfügung. Die Animation kann mit [Esc] gestoppt werden.

Zufallsbeispiel

Anhang

Für die die Funktion f bei x=a berührende Parabel gilt die Potenzreihenentwicklung

	p(x)	= f(a) + f'(a)·(x-a) + 0,5·f"(a)·(x-a)²
		= f(a) + (x-a)·(f'(a) + 0,5·f"(a)·(x-a))

Setzt man für das hintere x die Newton-Näherung x ← a-f(a)/f'(a) ein, so ergibt sich

	p(x)	= f(a) + (x-a)·(f'(a) + 0,5·f"(a)·(a-f(a)/f'(a)-a))
		= f(a) + (x-a)·(f'(a) - 0,5·f"(a)·(f(a)/f'(a))

Das ist in x linear. Für p(x)=0 (Nullstelle):

f(a) + (x-a)·(f'(a) - 0,5·f"(a)·(f(a)/f'(a)) = 0

f(a) + (x-a)·

f'(a)² - 0,5·f"(a)·f(a)

f'(a)

= 0

(x-a)·

f'(a)² - 0,5·f(a)·f"(a)

f'(a)

= -f(a)

x = a -

f(a)·f'(a)

f'(a)² - 0,5·f(a)·f"(a)

Der Newton-Schritt x = a - h(a)/h'(a) für h(x)=f(x)/|f'(x)|^1/2 (s.o.) ergibt interessanterweise das gleiche:

Für f'(a)>0 ist h'(a) =

2·f'(a)² - f(a)·f"(a)

2·f'(a)^3/2

und es ergibt sich: x = a -

h(a)

h'(a)

= a -

2·f(a)·f'(a)^3/2

f'(a)^1/2·(2·f'(a)² - f(a)·f"(a))

= a -

2·f(a)·f'(a)

2·f'(a)² - f(a)·f"(a)

Für f'(a)<0 kann man alle f'(a)^1/2 und f'(a)^3/2 jeweils mit -1 multiplizieren, das sich dann wieder herauskürzt.

	f(x) = Newton Halley: - Newton mit h(x):=f(x)/√\|f'(x)\| - mit Berührparabeln - ... kubisch Tangente an f bei Maus-x zeichnen h(x) immer zeichnen Tangente an h Berührparabel bei Maus-x zeichnen ... kubisch x₀ =
beim Klicken in die Liste diese Stelle zentrieren Stelle und Folgestelle sowie f(x) einblenden animieren Liste nicht anpassen (alles zeigen) Animationsdauern: zur nächste Stelle ms, warten: ms