Lineare Konvergenzordnung beim Newton-Verfahren für mehrfache Nullstellen

24.06.2010, 19:09

schiepie

Lineare Konvergenzordnung beim Newton-Verfahren für mehrfache Nullstellen

Meine Frage:
Bin gerade dabei, meine heutige Numerik-Vorlesung nachzuarbeiten und habe da ein Problem bei dem Beweis von Satz 3.11.
Hier mal das Skript:
http://wwwmath.uni-muenster.de/num/Vorlesungen/Numerik1_SS10/Script/skriptum.pdf
Der Satz, um den es geht steht auf Seite 73f. (Bei der direkten Eingabe im AdobeReader ist das die 78).
Dass $\begin{eqnarray*} \lim_{x \to x^{*}} Phi(x) = x^{*} \end{eqnarray*}$ gilt, ist mir klar und ich habe hier auch die Anwendung von L'Hospital verstanden.
Aber warum folgt dann mit L'Hospital:
$\begin{eqnarray*} \lim_{x \to x^{*}} Phi'(x) = 1 - 1/n \end{eqnarray*}$ ?

Meine Ideen:
Wenn man $\begin{eqnarray*} \lim_{x \to x^{*}} 1 - (f'(x)^{2}-f(x)f''(x))/(f'(x))^{2} \end{eqnarray*}$ bildet, kommt man doch mit L'Hospital dann irgendwann auf
$\begin{eqnarray*} 1 - \lim_{x \to x^{*}} (f^{(n)}(x)^{2}-f^{(n-1)}(x)f^{(n+1)}(x))/(f^{(n)}(x))^{2} \end{eqnarray*}$ .
Wodurch ja dann im Zähler (wenn man für x also $\begin{eqnarray*} x^{*} \end{eqnarray*}$ "einsetzt") des Grenzwertausdruckes $\begin{eqnarray*} f^{(n)}(x^{*})^{2}-0 \end{eqnarray*}$ steht und dann wäre ja
$\begin{eqnarray*} \lim_{x \to x^{*}} Phi'(x) = 1 - 1 = 0 \end{eqnarray*}$ ...also doch quadratische Konvergenzordnung.
Kann mir jemand sagen, wo da mein Denkfehler ist?

24.06.2010, 19:15

tigerbine

Auf diesen Beitrag antworten »

RE: Lineare Konvergenzordnung beim Newton-Verfahren für mehrfache Nullstellen
Mein Senf dazu: [WS] Eindimensionale Nullstellenprobleme 2 - Das Newton Verfahren Vielleicht findest du da schon die Antwort. Augenzwinkern

(für mehr habe ich gerade keine Zeit)

24.06.2010, 19:24

schiepie

Auf diesen Beitrag antworten »

Mh,nee danke, hilft mir nicht wirklich weiter.

25.06.2010, 00:45

tigerbine

Auf diesen Beitrag antworten »

Vielleicht kopierst du deinen Beitrag und machst das mit latex einmal ordentlich. Siehe meine Signatur. So mag man sich da nicht durchlesen. Augenzwinkern

Und warum das so ist, steht doch in meinem Link. Es ist halt viel Rechenarbeit nötig.

Zitat:

Nun soll sich mit der Frage beschäftigt werden, ob das Newton-Verfahren auch zur Bestimmung mehrfacher Nullstellen einer Funktion f anwendbar ist.

$\begin{eqnarray*} \text{Die Funktion } f: \mathbb R \to \mathbb R \text{ besitze in x* eine p-fache Nullstelle }p\geq 2 \text{ d.h. } \end{eqnarray*}$

$\begin{eqnarray*} f(x) = (x-x^*)^p \cdot h(x),\qquad h(x^*) \neq 0,~x^* \in [a,b] \end{eqnarray*}$

Zunächst einmal formuliert man einfach einmal das Verfahren.

Newton-Iteration

$\begin{eqnarray*} x_{k+1}:= x_k - \frac{f(x_k)}{f'(x_k)} \end{eqnarray*}$

zugehörige Fixpunktfunktion

$\begin{eqnarray*} g(x):=x - \frac{f(x)}{f'(x)} \end{eqnarray*}$

Da die Funktion h auf dem Intervall [a,b] zweimal stetig differenzierbar ist, betrachtet man zunächst einmal die Ableitungen der Funktion f:

$\begin{eqnarray*} f(x)&&:=(x-x^*)^p \cdot h(x) \end{eqnarray*}$

$\begin{eqnarray*} f'(x) &&= p \cdot (x-x^*)^{p-1}\cdot h(x) + (x-x^*)^{p}\cdot h'(x) \\&& = (x-x^*)^{p-1} \cdot [p \cdot h(x) + (x-x^*) \cdot h'(x)] \end{eqnarray*}$

$\begin{eqnarray*} f''(x) &&= p \cdot (p-1) \cdot (x-x^*)^{p-2} \cdot h(x) + p \cdot (x-x^*)^{p-1}\cdot h' (x) + p \cdot (x-x^*)^{p-1} \cdot h'(x) + (x-x^*)^{p}\cdot h''(x) \\&& = (x-x^*)^{p-2}\cdot [p\cdot (p-1) \cdot h(x) + p \cdot (x-x^*) \cdot h'(x) + p \cdot (x-x^*) \cdot h'(x) + (x-x^*)^2 \cdot h''(x)] \end{eqnarray*}$

Es ist nun die stetige Funktion g an der Stelle x* nicht definiert. Welche Art von Unstetigkeitsstelle liegt vor? Eine hebbare (Funktionsgraph hat ein Loch) und g besitzt eine stetige Fortsetzung (SF).

$\begin{eqnarray*} \frac{f(x)}{f'(x)} = \frac{(x-x^*)^p \cdot h(x)}{p \cdot (x-x^*)^{p-1}\cdot h(x) + (x-x^*)^{p}\cdot h'(x)} \stackrel{SF}=\frac{(x-x^*)\cdot h(x)}{p \cdot h(x) + (x-x^*) \cdot p'(x)} \end{eqnarray*}$

Somit gilt für sie folgenden Grenzwerte:

$\begin{eqnarray*} \lim_{x \to x^*} ~\frac{f(x)}{f'(x)} = 0 \end{eqnarray*}$

$\begin{eqnarray*} \lim_{x \to x^*}~g(x) =x^* \end{eqnarray*}$

Welche Art von Fixpunkt liegt mit x* bei der Funktion g nun vor?

$\begin{eqnarray*} g'(x) && = 1 - \frac{f'(x)f'(x) - f(x)f''(x)}{[f'(x)]^2} \\&&= \frac{f(x)f''(x)}{[f'(x)]^2} \\\\ && = \frac{\Bigl((x-x^*)^p \cdot h(x) \Bigr) \cdot \Bigl( (x-x^*)^{p-2}\cdot [p\cdot (p-1) \cdot h(x) + p \cdot (x-x^*) \cdot h'(x) + p \cdot (x-x^*) \cdot h'(x) + (x-x^*)^2 \cdot h''(x)]\Bigr)}{\Bigl( (x-x^*)^{p-1} \cdot [p \cdot h(x) + (x-x^*) \cdot h'(x)]\Bigr)^2} \\&& = \frac{\Bigl((x-x^*)^p \cdot h(x) \Bigr) \cdot \Bigl( (x-x^*)^{p-2}\cdot [p\cdot (p-1) \cdot h(x) + p \cdot (x-x^*) \cdot h'(x) + p \cdot (x-x^*) \cdot h'(x) + (x-x^*)^2 \cdot h''(x)]\Bigr)}{ (x-x^*)^{2p-2} \Bigl([p \cdot h(x) + (x-x^*) \cdot h'(x)]\Bigr)^2}\\&& = \frac{h(x) \cdot \Bigl( (x-x^*)^{p-2}\cdot [p\cdot (p-1) \cdot h(x) + p \cdot (x-x^*) \cdot h'(x) + p \cdot (x-x^*) \cdot h'(x) + (x-x^*)^2 \cdot h''(x)]\Bigr)}{ (x-x^*)^{p-2} \Bigl([p \cdot h(x) + (x-x^*) \cdot h'(x)]\Bigr)^2} \\&& \stackrel{SF}= \frac{h(x) \cdot [p\cdot (p-1) \cdot h(x) + p \cdot (x-x^*) \cdot h'(x) + p \cdot (x-x^*) \cdot h'(x) + (x-x^*)^2 \cdot h''(x)]}{ [p \cdot h(x) + (x-x^*) \cdot h'(x)]^2} \\\\&& = \frac{p\cdot (p-1) \cdot [h(x)]^2 + p \cdot (x-x^*) \cdot h(x) \cdot h'(x) + p \cdot (x-x^*) \cdot h(x) \cdot h'(x) + (x-x^*)^2 \cdot h(x) \cdot h''(x)]}{ p^2 \cdot [h(x)]^2 +2 \cdot p \cdot h(x) \cdot (x-x^*) \cdot h'(x) + (x-x^*)^2 \cdot [h'(x)]^2} \\\\&& = \frac{(p-1) \cdot [h(x)]^2 + (x-x^*) \cdot h(x) \cdot h'(x) + (x-x^*) \cdot h(x) \cdot h'(x) + \frac{1}{p}\cdot(x-x^*)^2 \cdot h(x) \cdot h''(x)]}{ p \cdot [h(x)]^2 +2 \cdot h(x) \cdot (x-x^*) \cdot h'(x) + \frac{1}{p}\cdot (x-x^*)^2 \cdot [h'(x)]^2} \end{eqnarray*}$

Wobei man auch hier die Definitionslücke bei x^* stetig fortsetzen kann. Es gilt also:

$\begin{eqnarray*} \lim_{x \to x^*}~{g'(x)} = \frac{p-1}{p} < 1 \end{eqnarray*}$ <= hier steht es!

Somit ist der Fixpunkt x* anziehend und aus der stetigen Fortsetzbarkeit der Ableitung g' folgt, dass es eine Umgebung von x* gibt, in der die Fixpunktiteration konvergiert.

Bleibt als letztes noch die Frage nach der Konvergenzgeschwindigkeit.

Die Antwort darauf haben wir mit Gliederungspunktt (3) schon geleistet. Die lineare Konvergenzrate ist also asymptotisch gleich $\begin{eqnarray*} \frac{p-1}{p} >0 \end{eqnarray*}$ .

Somit liegt keine superlineare Konvergenz vor, und damit auch keine der Ordnung 2 oder höher.

Lehrer

Fazit
Das Newton-Verfahren kann auch bei mehrfachen Nullstellen anwendbar sein, je größer die Vielfachheit der Nullstelle ist, umso langsamer konvergiert es jedoch.

Neue Frage »

Antworten »

Lineare Konvergenzordnung beim Newton-Verfahren für mehrfache Nullstellen

Verwandte Themen