04.1 – Newton-Verfahren für nichtlineare Gleichungen

 

Wir betrachten für eine Funktion f \in {C^{m+1}}\left( \mathbb{R} \right) die Newton-Iteration

{x_{k+1}} = \Phi \left( {{x_k}} \right) = {x_k}-\frac{{f\left( {{x_k}} \right)}}{{{f^\prime }\left( {{x_k}} \right)}},\quad k \in \mathbb{N}

a) veranschaulichen Sie das Newton-Verfahren graphisch.

b) Es sei nun \tilde x eine m-fache Nullstelle von f. Bestimmen Sie die Konvergenzordnung p in Abhängigkeit von m und machen Sie eine lokale Aussage über den dominierenden Konvergenzfaktor (d.h. den Faktor vor {\left| {{x_k}-\tilde x} \right|^p}) des Newton-Verfahrens.

c) In einer Modifikation des Newton-Verfahrens

{x_{k+1}} = \tilde \Phi \left( {{x_k}} \right) = {x_k}-\gamma \frac{{f\left( {{x_k}} \right)}}{{{f^\prime }\left( {{x_k}} \right)}},\quad k \in \mathbb{N}

ersetzt man die Newton-Korrektur durch ihr \gamma-faches (\gamma  \geq 1). Bestimmen Sie die Konvergenzordnung und den dominierenden Konvergenzfaktor in Abhängigkeit von m und \gamma.

Lösung

a )

Herleitung des Newton-Verfahrens

Das Newtonverfahren dient dazu, Nullstellen einer Funktion zu finden.

Bei einer Nullstelle gilt:

f\left( x \right) = 0

Iteratives Verfahren nach Newton:

{x_{x+1}} = \Phi \left( {{x_k}} \right) = {x_k}-\frac{{f\left( {{x_k}} \right)}}{{{f^\prime }\left( {{x_k}} \right)}}

Wie kommt man auf diese Vorschrift?

Wir starten bei einer beliebigen Stelle {x_0} 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 f in \left( {{x_k},f\left( {{x_k}} \right)} \right) lautet:

t\left( x \right) = {f^\prime }\left( {{x_k}} \right)\left( {x-{x_k}} \right)+f\left( {{x_k}} \right)

Die Nullstelle dieser Geraden finden wir wie folgt:

t\left( x \right) = 0\quad  \Rightarrow \quad {f^\prime }\left( {{x_k}} \right)\left( {x-{x_k}} \right)+f\left( {{x_k}} \right) = 0\quad  \Rightarrow \quad x = {x_k}-\frac{{f\left( {{x_k}} \right)}}{{{f^\prime }\left( {{x_k}} \right)}}

Die k+1-te Iterierte ist die Nullstelle der Tangente von f im Punkt \left( {{x_k},f\left( {{x_k}} \right)} \right).

Man kann zeigen, dass das Verfahren lokal mit der Konvergenzordnung 2 konvergiert.

b )

Konvergenzordnung p:

\left| {{x_{k+1}}-\tilde x} \right| \leq C{\left| {{x_k}-\tilde x} \right|^p},\quad \quad \left| C \right| < 1\quad wenn\quad p = 1

Taylorentwicklung von \Phi um \tilde x:

{x_{k+1}} = \Phi \left( {{x_k}} \right) = \Phi \left( {\tilde x} \right)+{\Phi ^\prime }\left( {\tilde x} \right)\left( {{x_k}-\tilde x} \right)+\frac{1}{2}{\Phi ^{\prime \prime }}\left( {\tilde x} \right){\left( {{x_k}-\tilde x} \right)^2}+O\left( {{{\left( {{x_k}-\tilde x} \right)}^3}} \right)

= \tilde x+{\Phi ^\prime }\left( {\tilde x} \right)\left( {{x_k}-\tilde x} \right)+O\left( {{{\left( {{x_k}-\tilde x} \right)}^2}} \right) \\

\quad  \Rightarrow \quad \left| {{x_{k+1}}-\tilde x} \right| = \left| {{\Phi ^\prime }\left( {\tilde x} \right)} \right|\left| {{x_k}-\tilde x} \right|+O\left( {{{\left( {{x_k}-\tilde x} \right)}^2}} \right)

Hier:

{\Phi ^\prime }\left( x \right) = {\left( {x-\frac{{f\left( x \right)}}{{{f^\prime }\left( x \right)}}} \right)^\prime } = 1-\frac{{{f^\prime }\left( x \right){f^\prime }\left( x \right)-f\left( x \right){f^{\prime \prime }}\left( x \right)}}{{{f^\prime }\left( x \right){f^\prime }\left( x \right)}}

{\Phi ^\prime }\left( {\tilde x} \right) = 1-\frac{{{{\left( {{f^\prime }\left( {\tilde x} \right)} \right)}^2}-\overbrace {f\left( {\tilde x} \right)}^{ = 0}{f^{\prime \prime }}\left( {\tilde x} \right)}}{{{{\left( {{f^\prime }\left( {\tilde x} \right)} \right)}^2}}} = 1-1 = 0

Dies funktioniert allerdings nur, wenn \tilde x eine einfache Nullstelle ist, also {f^\prime }\left( {\tilde x} \right) \ne 0. Es folgt die Konvergenzordnung 2.

Nun betrachten wir eine mehrfache Nullstelle der Funktion. Es ist also:

f\left( x \right) = {\left( {x-\tilde x} \right)^m}g\left( x \right)

mit g\left( x \right) \ne 0,\quad g\left( x \right) \in {C^1}\left( \mathbb{R} \right).

Ableitung:

{f^\prime }\left( x \right) = m\left( {x-\tilde x} \right)^{m-1}g\left( x \right)+{\left( {x-\tilde x} \right)^m}{g^\prime }\left( x \right)

Es folgt:

\Phi \left( x \right) = x-\frac{{\left( {x-\tilde x} \right)g\left( x \right)}}{{mg\left( x \right)+\left( {x-\tilde x} \right){g^\prime }\left( x \right)}}

{\Phi ^\prime }\left( {\tilde x} \right) = 1-\frac{1}{m}

Wir haben also immer noch Konvergenz, da {\Phi ^\prime }\left( {\tilde x} \right) immer kleiner ist als 1. Für m \geq 2 ist die Konvergenz linear mit Konvergenzfaktor 1-\frac{1}{m}.

c )

\tilde \Phi \left( x \right) = x-\gamma \frac{{\left( {x-\tilde x} \right)g\left( x \right)}}{{mg\left( x \right)+\left( {x-\tilde x} \right){g^\prime }\left( x \right)}}

Substitution:\quad u = \left( {x-\tilde x} \right),\quad v = g\left( x \right),\quad w = mg\left( x \right),\quad z = {g^\prime }\left( x \right)

{{\tilde \Phi }^\prime }\left( x \right) = {\left( {x-\gamma \frac{{u \cdot  v}}{{w+u \cdot  z}}} \right)^\prime } = 1-\gamma \frac{{{{\left( {u \cdot  v} \right)}^\prime }\left( {w+u \cdot  z} \right)-\left( {u \cdot  v} \right){{\left( {w+u \cdot  z} \right)}^\prime }}}{{{{\left( {w+u \cdot  z} \right)}^2}}}

{{\tilde \Phi }^\prime }\left( x \right) = 1+\frac{{\gamma g\left( x \right){g^{\prime \prime }}\left( x \right)\left( {x-\tilde x} \right)+m{g^\prime }\left( x \right)+{g^\prime }\left( x \right)\left( {x-\tilde x} \right)}}{{{{\left( {{g^\prime }\left( x \right)\left( {x-\tilde x} \right)+mg\left( x \right)} \right)}^2}}}

-\frac{{\gamma {g^\prime }\left( x \right)\left( {x-\tilde x} \right)}}{{{g^\prime }\left( x \right)\left( {x-\tilde x} \right)+mg\left( x \right)}}-\frac{{\gamma g\left( x \right)}}{{{g^\prime }\left( x \right)\left( {x-\tilde x} \right)+mg\left( x \right)}}

{{\tilde \Phi }^\prime }\left( {\tilde x} \right) = 1+\frac{{\gamma g\left( {\tilde x} \right)\left[ {{g^{\prime \prime }}\left( {\tilde x} \right)\left( {\tilde x-\tilde x} \right)+m{g^\prime }\left( {\tilde x} \right)+{g^\prime }\left( {\tilde x} \right)} \right]\left( {\tilde x-\tilde x} \right)}}{{{{\left( {{g^\prime }\left( {\tilde x} \right)\left( {\tilde x-\tilde x} \right)+mg\left( {\tilde x} \right)} \right)}^2}}}

-\frac{{\gamma {g^\prime }\left( {\tilde x} \right)\left( {\tilde x-\tilde x} \right)}}{{{g^\prime }\left( {\tilde x} \right)\left( {\tilde x-\tilde x} \right)+mg\left( {\tilde x} \right)}}-\frac{{\gamma g\left( {\tilde x} \right)}}{{{g^\prime }\left( {\tilde x} \right)\left( {\tilde x-\tilde x} \right)+mg\left( {\tilde x} \right)}}

{{\tilde \Phi }^\prime }\left( {\tilde x} \right) = 1-\frac{{\gamma g\left( {\tilde x} \right)}}{{mg\left( {\tilde x} \right)}} = 1-\frac{\gamma }{m}

Ähnliche Artikel

2 Kommentare zu “04.1 – Newton-Verfahren für nichtlineare Gleichungen”

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.

Kommentar verfassen