Wir betrachten für eine Funktion die Newton-Iteration
a) veranschaulichen Sie das Newton-Verfahren graphisch.
b) Es sei nun eine
-fache Nullstelle von
. Bestimmen Sie die Konvergenzordnung
in Abhängigkeit von
und machen Sie eine lokale Aussage über den dominierenden Konvergenzfaktor (d.h. den Faktor vor
) des Newton-Verfahrens.
c) In einer Modifikation des Newton-Verfahrens
ersetzt man die Newton-Korrektur durch ihr -faches (
). Bestimmen Sie die Konvergenzordnung und den dominierenden Konvergenzfaktor in Abhängigkeit von
und
.
Lösung
a )
Herleitung des Newton-Verfahrens
Das Newtonverfahren dient dazu, Nullstellen einer Funktion zu finden.
Bei einer Nullstelle gilt:
Iteratives Verfahren nach Newton:
Wie kommt man auf diese Vorschrift?
Wir starten bei einer beliebigen Stelle und legen dort die Tangente an die Funktion an. Nun bestimmen wir die Nullstelle dieser Tangente. An dieser Nullstelle legen wir nun erneut eine Tangente an die Funktion an und bestimmen die Nullstelle dieser neuen Tangente. Dieses Verfahren setzen wir fort und nähren uns der echten Nullstelle. Ein Problem ergibt sich, wenn der Startwert zu weit von der echten Nullstelle entfernt ist, da die Steigung der Funktion zu flach sein kann.
Die Funktionsgleichung für eine Tangente an in
lautet:
Die Nullstelle dieser Geraden finden wir wie folgt:
Die -te Iterierte ist die Nullstelle der Tangente von
im Punkt
.
Man kann zeigen, dass das Verfahren lokal mit der Konvergenzordnung 2 konvergiert.
b )
Konvergenzordnung p:
Taylorentwicklung von um
:
Hier:
Dies funktioniert allerdings nur, wenn eine einfache Nullstelle ist, also
. Es folgt die Konvergenzordnung 2.
Nun betrachten wir eine mehrfache Nullstelle der Funktion. Es ist also:
mit .
Ableitung:
Es folgt:
Wir haben also immer noch Konvergenz, da immer kleiner ist als 1. Für
ist die Konvergenz linear mit Konvergenzfaktor
.
Bei einer Funktion mit m-facher Nullstelle stimmt die Ableitung nicht ganz: Es fehlt das ^(m-1) im Exponenten.
Danke für den Hinweis wurde korrigiert.