Konvergenz des Newton-Verfahrens

04.11.2023, 19:26

HiBee123

Konvergenz des Newton-Verfahrens

Hallo liebe Leute Wink

Wir haben eine Funktion $\begin{eqnarray*} f \in C^2[a,b] \end{eqnarray*}$ gegeben für die gilt: $\begin{eqnarray*} f(\xi)=0 \end{eqnarray*}$ und $\begin{eqnarray*} f'(\xi)=0 \end{eqnarray*}$ aber $\begin{eqnarray*} f''(\xi)\neq 0 \end{eqnarray*}$ zu zeigen ist , dass das Newtonverfahren dann lokal gegen $\begin{eqnarray*} \xi \end{eqnarray*}$ konvergiert.

Als Tipp haben wir gegeben, dass wir eine Taylorentwicklung machen und den Mittelwertsatz verwenden sollen.

Ich habe also erstmal Taylorentwicklung angesetzt im Punkt $\begin{eqnarray*} x_n \end{eqnarray*}$
also $\begin{eqnarray*} Tf(x,x_n)=f(x_n)+f'(x_n)(x-x_n)+\frac{f''(x_n)}{2}(x-x_n)^2+\cdots \end{eqnarray*}$ Dann habe ich die zweite Ableitung mithilfe des MWS durch einen Term in Abhängigkeit der 2. Ableitung ersetzt, aber bin daraus nicht schlauer geworden...

Würde mich über Hilfe freuen.
Grüße,
eure HiBee

04.11.2023, 21:57

HAL 9000

Auf diesen Beitrag antworten »

$\begin{eqnarray*} C^2[a,b] \end{eqnarray*}$ bedeutet zweimal stetig (!) differenzierbar, d.h., die zweite Ableitung kann als stetig vorausgesetzt werden. Für $\begin{eqnarray*} a:=f''(\xi) \end{eqnarray*}$ ist vorausgesetzt $\begin{eqnarray*} a\neq 0 \end{eqnarray*}$ , sagen wir o.B.d.A. $\begin{eqnarray*} a>0 \end{eqnarray*}$ . Dann findet man ein $\begin{eqnarray*} \varepsilon>0 \end{eqnarray*}$ mit $\begin{eqnarray*} \frac{a}{2} < f''(x) < \frac{3a}{2} \end{eqnarray*}$ für alle $\begin{eqnarray*} x\in (\xi-\varepsilon,\xi+\varepsilon) \end{eqnarray*}$ . Könnte beim Beweis helfen...

EDIT: Die Annahme $\begin{eqnarray*} a>0 \end{eqnarray*}$ kann man unter o.B.d.A. verbuchen, denn im Fall $\begin{eqnarray*} a<0 \end{eqnarray*}$ betrachte man Funktion $\begin{eqnarray*} -f \end{eqnarray*}$ statt $\begin{eqnarray*} f \end{eqnarray*}$ mit haargenau derselben Näherungsfolge im Verlauf des Newton-Verfahrens.

05.11.2023, 11:53

HiBee123

Auf diesen Beitrag antworten »

Danke für die Antwort smile

Leider werd ich daraus immer noch nicht schlau. Ich hab das jetzt mal eingesetzt und komme auf die Ungleichung $\begin{eqnarray*} \frac{3a}{4}(x-\xi)^2\leq T_f(x,\xi)\leq \frac{9a}{4}(x-\xi)^2 \end{eqnarray*}$ aber ich bin mir nichtmal sicher ob ich die Taylorentwicklung so anwenden darf, ich meine, was passiert denn mit Termen höherer Ordnung?
Und inwiefern hilft mir diese Ungleichung jetzt weiter? Sofern sie überhaupt weiterhilft..

05.11.2023, 13:25

HAL 9000

Auf diesen Beitrag antworten »

Ok, ich muss das oben etwas verschärfen, sonst klappt meine Idee nicht: Man findet ein $\begin{eqnarray*} \varepsilon > 0 \end{eqnarray*}$ mit

$\begin{eqnarray*} a - \frac{a}{4} < f''(x) < a + \frac{a}{4} \end{eqnarray*}$ für alle $\begin{eqnarray*} x\in (\xi-\varepsilon,\xi+\varepsilon) \end{eqnarray*}$ , umgestellt

$\begin{eqnarray*} \frac{3a}{4} < f''(x) < \frac{5a}{4}\qquad (*) \end{eqnarray*}$ .

Gemäß Taylorformel gibt es nämlich (von $\begin{eqnarray*} x \end{eqnarray*}$ abhängige) $\begin{eqnarray*} \theta_1,\theta_2\in (0,1) \end{eqnarray*}$ mit

$\begin{eqnarray*} f(x) = f(\xi) + f'(\xi)\cdot \left(x-\xi\right) + \frac{f''\left(\xi + \theta_1(x-\xi)\right)}{2}\cdot \left(x-\xi\right)^2 = \frac{f''\left(\xi + \theta_1(x-\xi)\right)}{2}\cdot \left(x-\xi\right)^2 \end{eqnarray*}$

$\begin{eqnarray*} f'(x) = f'(\xi) + f''\left(\xi + \theta_2(x-\xi)\right)\cdot \left(x-\xi\right) = f''\left(\xi + \theta_2(x-\xi)\right)\cdot \left(x-\xi\right) \end{eqnarray*}$ .

Mit der Abschätzung (*) bekommen wir also $\begin{eqnarray*} \frac{3a}{8}\left(x-\xi\right)^2\leq f(x)\leq \frac{5a}{8}\left(x-\xi\right)^2 \end{eqnarray*}$ sowie $\begin{eqnarray*} \frac{3a}{4}\left(x-\xi\right)\leq f'(x)\leq \frac{5a}{4}\left(x-\xi\right) \end{eqnarray*}$ für $\begin{eqnarray*} \xi < x < \xi+\varepsilon \end{eqnarray*}$ .

Gemäß $\begin{eqnarray*} x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} \end{eqnarray*}$ im Newtonverfahren bedeutet das die Abschätzungen

$\begin{eqnarray*} x_{n+1} < x_n - \frac{\frac{3a}{8}\left(x_n-\xi\right)^2}{\frac{5a}{4}\left(x_n-\xi\right)} = x_n - \frac{3}{10}\left(x_n-\xi\right) = \xi + \frac{7}{10}\left(x_n-\xi\right) \end{eqnarray*}$

sowie

$\begin{eqnarray*} x_{n+1} > x_n - \frac{\frac{5a}{8}\left(x_n-\xi\right)^2}{\frac{3a}{4}\left(x_n-\xi\right)} = x_n - \frac{5}{6}\left(x_n-\xi\right) = \xi + \frac{1}{6}\left(x_n-\xi\right) > \xi \end{eqnarray*}$ ,

beide (wie gesagt) gültig für $\begin{eqnarray*} \xi < x_n < \xi+\varepsilon \end{eqnarray*}$ und $\begin{eqnarray*} a>0 \end{eqnarray*}$ .

Ähnlich kannst du nun auch "von unten" $\begin{eqnarray*} \xi-\varepsilon < x_n < \xi \end{eqnarray*}$ diskutieren mit ähnlichem Ergebnis, insgesamt dann:

Die Newton-Iterationsfolge $\begin{eqnarray*} (x_n) \end{eqnarray*}$ konvergiert monoton gegen $\begin{eqnarray*} \xi \end{eqnarray*}$ , zumindest wenn der Startpunkt im Intervall $\begin{eqnarray*} (\xi-\varepsilon,\xi+\varepsilon) \end{eqnarray*}$ liegt.

07.11.2023, 18:55

HiBee123

Auf diesen Beitrag antworten »

Hallo Hal9000
aber steht der Beweis nicht schon da?
Wofür unterscheidest du in $\begin{eqnarray*} \xi < x <\xi+\epsilon \end{eqnarray*}$ und in
$\begin{eqnarray*} \xi- \epsilon<x<\xi \end{eqnarray*}$ ?
Grüße,
HiBee

07.11.2023, 23:41

HAL 9000

Auf diesen Beitrag antworten »

Fall $\begin{eqnarray*} \xi- \epsilon<x<\xi \end{eqnarray*}$ ist nicht substanziell anders, im Detail aber schon:

Z.B. gilt dort NICHT Ungleichung $\begin{eqnarray*} \frac{3a}{4}\left(x-\xi\right)\leq f'(x)\leq \frac{5a}{4}\left(x-\xi\right) \end{eqnarray*}$ , sondern stattdessen...

09.11.2023, 18:07

HiBee123

Auf diesen Beitrag antworten »

Da $\begin{eqnarray*} x-\xi \end{eqnarray*}$ negativ ist, würde ich behaupten, die Ungleichung dreht sich um
also $\begin{eqnarray*} \frac{5a}{4}(x-\xi)\leq f'( x) \leq \frac{3a}{4}(x-\xi) \end{eqnarray*}$

09.11.2023, 18:11

HAL 9000

Auf diesen Beitrag antworten »

Genau, und zwar bewegen wir uns da ja auch in den negativen Zahlen. Diese und andere Dinge sind also ein wenig anders, und müssen beachtet werden bis man in diesem Fall dann zu der Aussage kommt, dass die $\begin{eqnarray*} x_n \end{eqnarray*}$ von unten kommend monoton wachsend gegen $\begin{eqnarray*} \xi \end{eqnarray*}$ konvergieren, während im obigen ersten Fall von oben kommend eine monoton fallende Konvergenz gegen $\begin{eqnarray*} \xi \end{eqnarray*}$ vorliegt.

Kann sein, dass das oben alles überumständlich ist, und es einen viel eleganteren Kurzaufschrieb gibt, aber der ist mir eben nicht eingefallen.

09.11.2023, 20:38

HiBee123

Auf diesen Beitrag antworten »

Also im Tutorium haben wir es anders gemacht. Nämlich mit dem Mittelwertsatz.

Wir wissen wieder, wegen der Stetigkeit, dass die zweite Ableitung auf einem Bereich ungleich 0 sein muss.

Es existiert ein z in unserem Bereich, so dass $\begin{eqnarray*} f'(x_n)=f'(x_n)-f(\xi)=f''(z)(x_n-\xi) \end{eqnarray*}$ ungleich null ist

Dann wenden wir Taylor auf $\begin{eqnarray*} f(\xi) \end{eqnarray*}$ an
$\begin{eqnarray*} f(\xi)= f(x_n)+f'(x_n)(\xi-x_n)+\frac{1}{2}f''(y)(\xi-x_n)^2 \end{eqnarray*}$ für ein y in unserem Bereich

Dann setzt man das ganze in das Newtonverfahren ein und kommt schließlich auf
$\begin{eqnarray*} \mid x_{n+1}-\xi\mid =\frac{1}{2} \mid \frac{f''(y)}{f''(z)}\mid\mid x_n-\xi\mid \end{eqnarray*}$

und es findet sich ein entsprechender Bereich wo dieser Bruch der zweiten Ableitung hinreichend klein ist und dann hat man ein q<1 gefunden und somit folgt die Konvergenz.

09.11.2023, 22:20

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von HiBee123
$\begin{eqnarray*} f'(x_n)=f'(x_n)-{\color{red}f(\xi)}=f''(z)(x_n-\xi) \end{eqnarray*}$

Hier muss es $\begin{eqnarray*} {\color{red}f'(\xi)} \end{eqnarray*}$ lauten. Macht aber in der Rechnung keinen Unterschied, da beide gleich Null sind.

Ganz zum Schluss hier

Zitat:

Original von HiBee123
und es findet sich ein entsprechender Bereich wo dieser Bruch der zweiten Ableitung hinreichend klein ist und dann hat man ein q<1 gefunden und somit folgt die Konvergenz.

wird es sehr schnell, und verliert sich mehr in Andeutungen denn in exakten Ausführungen. Augenzwinkern

Abgesehen davon ist es wohl in Ordnung.

10.11.2023, 14:25

HiBee123

Auf diesen Beitrag antworten »

Also wir hatten ja oben eine Umgebung definiert, sagen wir eine $\begin{eqnarray*} \epsilon \end{eqnarray*}$ -Umgebung
um $\begin{eqnarray*} \xi \end{eqnarray*}$ Wir definieren jetzt eine $\begin{eqnarray*} \delta \end{eqnarray*}$ -Umgebung um $\begin{eqnarray*} \xi \end{eqnarray*}$ ,
so dass $\begin{eqnarray*} \delta\leq \epsilon \end{eqnarray*}$ mit
$\begin{eqnarray*} sup_{x,y}\frac{f''(y)}{f''(z)}<2 \forall y,z \in I_{\delta} \end{eqnarray*}$ ,
dann ist unser q:= $\begin{eqnarray*} \frac{1}{2}\mid\frac{f''(y)}{f''(z)}\mid \end{eqnarray*}$ kleiner als 1 und so folgt die Konvergenz.

10.11.2023, 14:56

HAL 9000

Auf diesen Beitrag antworten »

Ja, lass es gut sein. Sofern dir klar ist, wie und warum die Existenz einer solchen $\begin{eqnarray*} \delta \end{eqnarray*}$ -Umgebung von $\begin{eqnarray*} \xi \end{eqnarray*}$ aus den Voraussetzungen folgt, dann ist der Zweck erfüllt.

11.11.2023, 13:03

HiBee123

Auf diesen Beitrag antworten »

Okay

Lieben Dank für die Antwort smile

Neue Frage »

Antworten »

Konvergenz des Newton-Verfahrens

Verwandte Themen