Konvergenz des Newtonverfahrens

19.01.2008, 15:45

Tschulee

Konvergenz des Newtonverfahrens

hey Leute!
Eine Frage:

Konvergiert das Newtonverfahren, also wenn es konvergiert, immer quadratisch???

Danke!

Mfg Tschulee

19.01.2008, 16:20

20_Cent

Auf diesen Beitrag antworten »

Soweit ich weiß ja.
mfG 20

19.01.2008, 17:40

Chris2005

Auf diesen Beitrag antworten »

und ist das "einzige" konvergenzkriterium wirklich nur

$\begin{eqnarray*} \left|\frac{f(x_0)\cdot f''(x_0)}{f'(x_0)^2}\right|<1 \end{eqnarray*}$

oder gibt es allgemeinere kriterien welche mir die konvergenz etwa für alle positiven startwerte liefert?

mfg Chris

20.01.2008, 14:28

tigerbine

Auf diesen Beitrag antworten »

Immer quadratisch?
Imho stimmt das nicht.

Zitat:

tigerbine

Zitat:

Original von tigerbine
Sei f einmal stetig differenzierbar (auf [a, b]) und x* eine einfache Nullstelle in diesem Intervall, d.h. es gilt:

$\begin{eqnarray*} f(x^*)=0 \end{eqnarray*}$
$\begin{eqnarray*} f'(x^*) \neq 0 \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow \end{eqnarray*}$

Dann gibt es eine Umgebung $\begin{eqnarray*} K_r(x^*) \end{eqnarray*}$ derart, dass das Newtonverfahren für jeden Startwert $\begin{eqnarray*} x_0 \in K_r(x^*) \end{eqnarray*}$ superlinear gegen x* konverviert.

Beweis:

Da $\begin{eqnarray*} f'(x^*) \neq 0 \end{eqnarray*}$ und $\begin{eqnarray*} f' \end{eqnarray*}$ stetig ist, gibt es eine Umgebung $\begin{eqnarray*} K_r(x^*) \end{eqnarray*}$ , so dass $\begin{eqnarray*} |f'(x)|>0 \end{eqnarray*}$ ist $\begin{eqnarray*} \forall~x \in K_r(x^*) \end{eqnarray*}$
In dieser Umgebung ist dann $\begin{eqnarray*} \frac{1}{|f'(x)|} \end{eqnarray*}$ wohl definiert.
Da f stetig differenzierbar ist, kann man den Mittelwertsatz der Differenzialrechnung anwenden. Dies führt für $\begin{eqnarray*} x_k \in K_r(x^*) \end{eqnarray*}$ zu:

$\begin{eqnarray*} |x_{k+1}-x^*| && = |x_k - \frac{f(x_k)}{f'(x_k)} - x^*| \\&& = |x_k - x^*- \frac{f(x_k)}{f'(x_k)} | \\&& = |(x_k-x^*)-(x_k-x^*) \cdot \frac{f(x_k)-f(x^*)}{(x_k-x^*)f'(x_k)} | \\&& \stackrel{\text{MWS}}\leq |x_k-x^*| \cdot |1-\frac{f'(\zeta)}{f'(x_k)}| \end{eqnarray*}$
Da f' stetig ist und $\begin{eqnarray*} \zeta \end{eqnarray*}$ zwischen $\begin{eqnarray*} x_k \end{eqnarray*}$ und $\begin{eqnarray*} x^* \end{eqnarray*}$ liegt, kann man den Radius r ggf. soweit verkleinern, dass gilt:

$\begin{eqnarray*} |1-\frac{f'(\zeta)}{f'(x_k)}| \leq q < 1 \end{eqnarray*}$
Mit Induktion folgt dann, dass für $\begin{eqnarray*} x_0 \in K_r(x^*) \end{eqnarray*}$ alle Iterierten in $\begin{eqnarray*} K_r(x^*) \end{eqnarray*}$ . Somit ist das Newton Verfahren wohl definiert.
Damit folgt aus $\begin{eqnarray*} |x_{k+1}-x^*| \leq q \cdot |x_k-x^*| \end{eqnarray*}$ die "lineare Konvergenz" (und damit die Konvergenz!) der Folge gegen x*.
Da nun die Folge gegen x* konvergiert, folgt aus

$\begin{eqnarray*} \lim_{k \to \infty}~|1-\frac{f(x_k)-f(x^*)}{(x_k-x^*)\cdot f'(x_k)}| = |1-\frac{f'(x^*)}{f'(x^*)}|=0 \end{eqnarray*}$ , die superlineare Konvergenz des Newtonverfahrens.

Sei nun f' zusätzlich noch Lipschitz-stetig, d.h. es gibt eine Konstante L > 0 mit:

$\begin{eqnarray*} |f'(x) - f'(y)| \leq L \cdot |x-y|,~\quad \forall ~x ,y\in K_r(x^*) \subseteq [a,b] \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow \end{eqnarray*}$

Dann ist die Konvergenzrate quadratisch.

Beweis:

Da f' stetig auf dem Kompaktum $\begin{eqnarray*} K_r(x^*) \end{eqnarray*}$ ist, nimmt die Funktion dort ein Minimum m > 0 an, d.h.

$\begin{eqnarray*} |\frac{1}{f'(x)}| \leq \frac{1}{m} \end{eqnarray*}$
Mit obigen Überlegungen folgt nun:

$\begin{eqnarray*} |x_{k+1} - x^*| && \leq |x_k-x^*| \cdot |1-\frac{f'(\zeta)}{f'(x_k)}| \\&&= |x_k-x^*|\cdot |\frac{f'(x_k)-f'(\zeta)}{f'(x_k)}|\\&& \leq |x_k-x^*| \cdot \frac{L\cdot |x_k-\zeta|}{m} \\&& \leq |x_k-x^*| \cdot \frac{L\cdot |x_k-x^*|}{m} \\ &&= \frac{L}{m} \cdot |x_k-x^*|^2 \end{eqnarray*}$

und somit die quadratische Konvergenz.

20.01.2008, 17:32

Mathespezialschüler

Auf diesen Beitrag antworten »

Zitat:

Original von tigerbine
Imho stimmt das nicht.

Hast du auch ein Gegenbeispiel? Ich hab selbst auch keine Ahnung, ob es tatsächlich immer quadratisch konvergiert.
Aber dein Beweis für die superlineare Konvergenz unter bestimmten Voraussetzungen ist ja noch kein Beweis dafür, dass die Konvergenz dann nicht auch quadratisch ist, sie kann es ja trotzdem immer sein.

20.01.2008, 17:36

20_Cent

Auf diesen Beitrag antworten »

Wenn f zweimal stetig diffbar ist, dann ist das Newtonverfahren lokal quadratisch konvergent, steht so in meinem Buch (Dahmen/Reusken).
mfG 20

edit: stetig ergänzt

20.01.2008, 17:40

Mathespezialschüler

Auf diesen Beitrag antworten »

Zitat:

Original von 20_Cent
Wenn f zweimal stetig diffbar ist, dann ist das Newtonverfahren lokal quadratisch konvergent, steht so in meinem Buch (Dahmen/Reusken).
mfG 20

Mag ja sein. Und was machst du, wenn $\begin{eqnarray*} f \end{eqnarray*}$ nicht zweimal stetig differenzierbar ist? Kann ja sein, dass die Newtonfolge dann trotzdem noch konvergiert, allerdings nicht mehr quadratisch.

20.01.2008, 17:59

20_Cent

Auf diesen Beitrag antworten »

Ich wollte nur meine obige Antwort rechtfertigen Augenzwinkern

Ich war mir über die Voraussetzungen nicht im klaren, jetzt siehts anders aus.
Ich würde aber auch gerne ein Gegenbeispiel sehen.
mfG 20

20.01.2008, 18:26

tigerbine

Auf diesen Beitrag antworten »

Konstruiert doch mal eine Funktion, die nur der ersten Bedingung genügt. Dann könnten wir weiter untersuchen (Ball zurück schieß Augenzwinkern

) Heute wird mir die Zeit dafür fehlen, also erinnert mich sonst im Laufe der Woche nochmal.

Gruß,
tigerbine

edit: Hier mal ein Funktionsansatz mit dem ich damals ein Beispiel konstruieren wollte. Richtig ist, dass der nachweis der supl. Konvergenz erstmal die Möglichkeit der quadratischen nicht ausschließt. Aber so wie ich es verstanden hatte, muss man quasi das Extra L-Stetig haben, um diese nachweisen zu können.

Das Beispiel würde dann ja, bei Betrachtung auf geeignetem Intervall wieder quad. Konvergenz liefern. Mit der aussage von WebFritzi könnte müßte das dann ja für jede stetig diffbare Funktion klappen. Also doch wieder quadratisch? Augenzwinkern

20.01.2008, 18:51

Mathespezialschüler

Auf diesen Beitrag antworten »

Sei $\begin{eqnarray*} x_0=1 \end{eqnarray*}$ bei

$\begin{eqnarray*} f(x)=x^2 \end{eqnarray*}$ .

Für die Folge $\begin{eqnarray*} (x_n)_{n\in\mathbb N_0} \end{eqnarray*}$ mit $\begin{eqnarray*} x_0=1 \end{eqnarray*}$ und

$\begin{eqnarray*} x_{n+1}=\frac{x_n}{2} \end{eqnarray*}$

sieht man induktiv, dass jedes $\begin{eqnarray*} x_n\neq 0 \end{eqnarray*}$ ist. (Diese "Hilfsfolge" habe ich nur eingeführt, damit man sieht, dass die Newtonfolge auch definiert ist.) Diese Folge ist eine geometrische Folge:

$\begin{eqnarray*} x_n=\frac{1}{2^n} \end{eqnarray*}$

und somit konvergent. Außerdem gilt:

$\begin{eqnarray*} x_{n+1}=\frac{x_n}{2}=x_n\cdot\left(1-\frac{1}{2}\right) =x_n-\frac{x_n^2}{2x_n}=x_n-\frac{f(x_n)}{f'(x_n)} \end{eqnarray*}$ .

Es ist also die Newtonfolge von $\begin{eqnarray*} f \end{eqnarray*}$ mit Startwert $\begin{eqnarray*} 1 \end{eqnarray*}$ . Wegen

$\begin{eqnarray*} \frac{x_{n+1}}{x_n}=\frac{1}{2} \end{eqnarray*}$

ist die Konvergenz dieser Folge aber sogar nur linear, also nicht einmal superlinear!

edit: Deinen Edit, tigerbine, habe ich jetzt erst gesehen. Sieht aber sehr unsortiert aus das Ganze dort, deswegen wurschtel' ich mich da mal nich durch. Hab ja jetzt schon ein Gegenbeispiel gefunden. Augenzwinkern

20.01.2008, 19:01

tigerbine

Auf diesen Beitrag antworten »

Unsortiertes Gewurschtel .rofl: Naja, ob das hier besser ist. Aber ich muss Hammer

machen. An mehrfache Nullstellen hatte ich gerade gar nicht gedacht. (*Gedanken wo anders sind *)

Kannst Dich ja da mal durchwuseln... Big Laugh

Aber ein Beispiel für den Fragesteller haben wir (Du)^^) nun ja angegeben.

Interessant fände ich jetzt dennoch die Betrachtung für einfache Nullstellen, also bei meinem ersten Ansatz. Kann man da durch die Wahl eines kompakten Intervalls alles immer noch in Wohlgefallen (quadr. Konverganz) auflösen?

LG Wink

Zitat:

Original von tigerbine
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*}$

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.

20.01.2008, 19:57

Mathespezialschüler

Auf diesen Beitrag antworten »

Zitat:

Original von tigerbine
Interessant fände ich jetzt dennoch die Betrachtung für einfache Nullstellen, also bei meinem ersten Ansatz. Kann man da durch die Wahl eines kompakten Intervalls alles immer noch in Wohlgefallen (quadr. Konverganz) auflösen?

Nein. Du hast ja oben gezeigt, dass das jedenfalls dann gilt, wenn $\begin{eqnarray*} f' \end{eqnarray*}$ Lipschitz-stetig ist.
Allerdings muss $\begin{eqnarray*} f' \end{eqnarray*}$ nicht Lipschitz-stetig sein, wie das Beispiel $\begin{eqnarray*} f:[0,1]\to\mathbb R \end{eqnarray*}$ ,

$\begin{eqnarray*} f(x)=\frac{2}{3}x\sqrt{x}+x \end{eqnarray*}$

zeigt. Hier ist $\begin{eqnarray*} x^{*}=0 \end{eqnarray*}$ mit $\begin{eqnarray*} f(0)=0 \end{eqnarray*}$ und $\begin{eqnarray*} f'(0)=\sqrt{0}+1=1\neq 0 \end{eqnarray*}$ .
Nun könnte man ja einfach mal die Newton-Folge für diese Funktion betrachten und gucken, was passiert.
Also los: Sei $\begin{eqnarray*} x_0=1 \end{eqnarray*}$ .

$\begin{eqnarray*} x_{n+1}=x_n-\frac{\frac{2}{3}x_n\sqrt{x_n}+x_n}{\sqrt{x_n}+1} =x_n\cdot\left(1-\frac{\frac{2}{3}\sqrt{x_n}+1}{\sqrt{x_n}+1}\right) =\frac{x_n}{3}\cdot \frac{\sqrt{x_n}}{\sqrt{x_n}+1} \end{eqnarray*}$ .

Induktiv sieht man jetzt schnell, dass jedes $\begin{eqnarray*} x_n \end{eqnarray*}$ im Intervall $\begin{eqnarray*} [0,1] \end{eqnarray*}$ liegt. Z.B. durch folgende Abschätzung:

$\begin{eqnarray*} x_{n+1}=\frac{x_n\sqrt{x_n}}{3}\cdot \frac{1}{\sqrt{x_n}+1}\leq \frac{x_n\sqrt{x_n}}{3}\leq \frac{x_n}{3}\leq \ldots\leq \frac{x_0}{3^{n+1}}=\frac{1}{3^{n+1}} \end{eqnarray*}$ .

Diese bringt auch die Konvergenz der Folge gegen $\begin{eqnarray*} 0 \end{eqnarray*}$ und wegen

$\begin{eqnarray*} \lim_{n\to\infty}\frac{x_{n+1}}{x_n\sqrt{x_n}}=\lim_{n\to\infty}\frac{1}{3(\sqrt{x_n}+1)}=\frac{1}{3} \end{eqnarray*}$

beträgt die Konvergenzordnung $\begin{eqnarray*} 1,5 \end{eqnarray*}$ .

21.01.2008, 00:49

tigerbine

Auf diesen Beitrag antworten »

Ohne Dein Beispiel schon gelesen zu haben, habe ich in dem anderen Thread einen Fehler gemacht. Ich fragte, ob f L-stetig ist, hätte aber nach f' fragen müssen. Wenn wir nun eine nur 1x stetig diffbare Funktion f nehmen, so ist f' ja nicht mehr stetig diffbar. also kann man den Satz von WebFritzi auch nicht anwenden.

21.01.2008, 19:25

Mathespezialschüler

Auf diesen Beitrag antworten »

Richtig, das ist mir auch schon etwas früher aufgefallen, dachte aber, es wäre dir klar bzw. hab deswegen durch den anderen Thread auch nicht wirklich durchgeblickt. Deswegen hab ichs auch nicht erwähnt.

Neue Frage »

Antworten »

Konvergenz des Newtonverfahrens

Verwandte Themen