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 .

c )