Newton-Verfahren

06.02.2011, 19:08

Gast11022013

Newton-Verfahren

Meine Frage:

Das Konvergenzverhalten des Newton-Verfahrens soll am Beispiel der Nullstellenbestimmung der Funktion

$\begin{eqnarray*} f(x)=x^3-2x, x\in [-2,2] \end{eqnarray*}$ untersucht werden.

(a) Konvergiert das Newton-Verfahren mit dem Startwert 2?
(b) Bestimmen Sie ein (möglichst großes) Intervall I, sodass für alle Startwerte aus I das Newton-Verfahren gegen 0 konvergiert.

Es wäre nett, wenn jemand drüber guckt.
[Insbesondere bei Teil b.]

Meine Ideen:
Zu (a):

Ich verwende den Fixpunktsatz von Banach:
"Sei D abgeschlossen und $\begin{eqnarray*} g: D\to \mathbb R^n \end{eqnarray*}$ kontrahierend in D mit $\begin{eqnarray*} g(D)\subseteq D \end{eqnarray*}$ . Dann konvergiert die Folge $\begin{eqnarray*} x_{k+1}=g(x_k), k=0,1,2,... \end{eqnarray*}$ , wobei $\begin{eqnarray*} x_0\in D \end{eqnarray*}$ beliebig, gegen den eindeutig bestimmten Fixpunkt $\begin{eqnarray*} \overline{x} \end{eqnarray*}$ in D und es gilt:

(i) $\begin{eqnarray*} ||\overline{x}-x_k||\leq\frac{q}{1-q}||x_k-x_{k-1}||\leq \frac{q^k}{1-q}||x_1-x_0|| \end{eqnarray*}$

(ii) $\begin{eqnarray*} ||\overline{x}-x_k||\leq q||\overline{x}-x_{k-1}|| \end{eqnarray*}$ ."

(a)

$\begin{eqnarray*} f(x)=x^3-2x, f'(x)=3x-2 \end{eqnarray*}$
$\begin{eqnarray*} x_{k+1}=x_k-\frac{f(x)}{f'(x)}=:g(x_k) \end{eqnarray*}$
$\begin{eqnarray*} g(x)=\frac{2x^3}{3x^2-2}, g'(x)=\frac{6x^2(x^2-2)}{(3x^2-2)^2} \end{eqnarray*}$
$\begin{eqnarray*} g''(x)=\frac{24x(x^2+2)}{(3x^2-2)^3} \end{eqnarray*}$

Betrachte $\begin{eqnarray*} D=[1.2,2] \end{eqnarray*}$ .

Auf diesem Intervall ist g kontrahierend, also $\begin{eqnarray*} |g'(x)|<1 \end{eqnarray*}$ :
$\begin{eqnarray*} g'(1.2)=-0.89..., g'(2)=0.48... \end{eqnarray*}$
Da nun $\begin{eqnarray*} \forall x\in D: g''(x)>0 \end{eqnarray*}$ , ist $\begin{eqnarray*} g'(x) \end{eqnarray*}$ monoton wachsend in D. Und aus alledem folgt die behauptete Kontraktion auf D.

Es gilt $\begin{eqnarray*} g(D)\subseteq D \end{eqnarray*}$ :
$\begin{eqnarray*} g(1.2)=1.489..., g(2)=1.6 \end{eqnarray*}$

Weiter gilt:
$\begin{eqnarray*} \forall x\in [1.2,\sqrt{2}]: g'(x)\leq 0 \end{eqnarray*}$
$\begin{eqnarray*} \forall x\in [\sqrt{2},2]: g'(x)> 0 \end{eqnarray*}$ .

D.h. man kennt den Verlauf des Graphen von g auf D, nämlich monoton fallend in $\begin{eqnarray*} 1.2,\sqrt{2}] \end{eqnarray*}$ und monoton wachsend in $\begin{eqnarray*} [\sqrt{2},2] \end{eqnarray*}$ und mit den Werten an den Eckpunkte (s.o.) folgt: $\begin{eqnarray*} g(x)\subseteq D \forall x\in D \end{eqnarray*}$ .

Also ist der Banach´sche Fixpunktsatz anwendbar, denn alle Kriterien sind erfüllt: Das Newtonverfahren mit Startwert 2.

Zu (b):

Hier wende ich auch den Banach´schen Fixpunktsatz an.
Bestimme x so, dass $\begin{eqnarray*} |g'(x)|\leq 1 \end{eqnarray*}$ .
$\begin{eqnarray*} g'(x)=\frac{6x^2(x^2-2)}{(3x^2-2)^2}=-1 \end{eqnarray*}$ [-1 ergibt sich, da Werte ganz nah an 0 betrachtet werden.].

$\begin{eqnarray*} \Leftrightarrow 6x^4-12x^2=-9x^4+12x^2-4 \end{eqnarray*}$
$\begin{eqnarray*} \Leftrightarrow -15x^4+24x^2-4=0 \end{eqnarray*}$

Es ergibt sich: $\begin{eqnarray*} x_1=\pm 0.4347, x_2=\pm 1.18786 \end{eqnarray*}$ .

Für alle $\begin{eqnarray*} x\in [-0.4347,0.4347] \end{eqnarray*}$ gilt $\begin{eqnarray*} |g'(x)|\leq 1 \end{eqnarray*}$ .
$\begin{eqnarray*} g(0.4347)=-0.1146, g(-0.4347)=0.1146 \end{eqnarray*}$

Außerdem ist $\begin{eqnarray*} |g'(x)|\leq 1 \end{eqnarray*}$ für $\begin{eqnarray*} x\in [-\infty,-1.18786], [1.18786,\infty] \end{eqnarray*}$ , aber 0 liegt ja nicht in diesen Intervallen, also kommen sie nicht in Frage.

[Liege ich richtig?]

07.02.2011, 15:02

Gast11022013

Auf diesen Beitrag antworten »

Hat wohl keiner Lust, das alles zu kontrollieren...
Kann ich irgendwie verstehen...

08.02.2011, 00:10

tigerbine

Auf diesen Beitrag antworten »

RE: Newton-Verfahren
$\begin{eqnarray*} f(x)=x^3-2x, x\in [-2,2] \end{eqnarray*}$

$\begin{eqnarray*} f'(x)=3x^2-2, x\in [-2,2] \end{eqnarray*}$

$\begin{eqnarray*} f''(x)=6x^2, x\in [-2,2] \end{eqnarray*}$

Die $\begin{eqnarray*} C^{\infty} \end{eqnarray*}$ Funktion f hat 3 einfache Nullstellen. Das Newton-Verfahren ist daher in einer "kleinen"-Umgebung jeder dieser Nullstellen quadratisch konvergent gegen diese. (Beweis). Somit kann deine Aussage zu (b) schon nicht stimmen. Also: Fehlersuche.

$\begin{eqnarray*} g(x)=x-\frac{f(x)}{f'(x)} = x - \frac{x^3-2x}{3x^2-2}, x\in [-2,2] \end{eqnarray*}$

$\begin{eqnarray*} g'(x) = \frac{f(x)\cdot f''(x)}{[f'(x)]^2} = \frac{(x^3-2x)(6x)}{(3x^2-2)^2}, x\in [-2,2] \end{eqnarray*}$

Bei (a) fällt der Wert 1.2 für mich vom Himmel. Die Nullstellen der Funktion sind offensichtlich. Es geht imho darum, den Einzugsbereich zu untersuchen. Dazu musst du die erste Ableitung von g untersuchen und zwar in einer Umgebung von $\begin{eqnarray*} \sqrt{2} \end{eqnarray*}$ .

(b) Die Grafik zeigt ja schon das Ergebnis. Im Grunde rechnet man hier das aus, was man in der Theorie in dem Stetigkeitsargument verwendet:

g' ist stetig und g'(x^*))=0 => Es gibt eine Umgebung von x* mit |g'(x*)| <1

08.02.2011, 18:20

Gast11022013

Auf diesen Beitrag antworten »

RE: Newton-Verfahren
Bei a) willst du mir mitteilen, dass ich das Ganze besser betrachten sollte im Intervall $\begin{eqnarray*} [\sqrt{2},2] \end{eqnarray*}$ , damit besser nachzuvollziehen ist, was man macht?

[Dass man also von der Nullstelle ausgeht usw.]

Bei (b) verstehe ich nicht, was Du meinst.

08.02.2011, 18:29

tigerbine

Auf diesen Beitrag antworten »

RE: Newton-Verfahren
(b)

Hast du meinen Link angeschaut und wie also die Konvergneztheorie für einfache Nullstellen (bei ausreichender Glattheit) aussieht? Damit macht deine Lösung (konvergiert nicht gegen x=0) ja keinen Sinn,

(a) Bei ist dann doch nur die Frage, ob x=2 nahe genug an der Nullstelle $\begin{eqnarray*} x=\sqrt{2} \end{eqnarray*}$ liegt. Da verstehe ich nicht, woher du die 1.2 hast und was du damit aussagen willst.

08.02.2011, 18:32

Gast11022013

Auf diesen Beitrag antworten »

RE: Newton-Verfahren
Okay, also bei a) - meinst Du - sollte ich besser das Intervall $\begin{eqnarray*} [\sqrt{2}, 2] \end{eqnarray*}$ betrachten?

Bei b) grüble ich noch.

Bei (b) habe ich doch nur festgestellt, dass für mich das größtmögliche Intervall [-0.4347,0.4347] ist.

[Du meinst ich hätte gesagt, das würde nicht gegen 0 konvergeiren? Nein, aber vielleicht habe ich mich falsch ausgedrückt.]

08.02.2011, 18:39

tigerbine

Auf diesen Beitrag antworten »

RE: Newton-Verfahren
Bei (a) solltest du mitteilen, warum du welches Intervall wählst. Des weiteren solltest du mal deine Funktionen, Ableitungen checken,. Irgendwo muss ein Rechenfehler sein. Siehe meine Bilder.

08.02.2011, 19:02

Gast11022013

Auf diesen Beitrag antworten »

RE: Newton-Verfahren
Einige Deiner Bilder werden nicht dargestellt.

Also:

Bei (a) würde ich jetzt sagen: Man untersucht, so wie ichs getan habe... nur eben das Intervall $\begin{eqnarray*} [\sqrt{2},2] \end{eqnarray*}$ .

Im Grunde sind die Voraussetzungen aber eben auch schon für den linken Wert 1.2 erfüllt nur man kann schlecht nachvollziehen, warum ich den gewählt habe. Wenn man den Fixpunkt nimmt bzw. die Nullstelle von f, so ists einsichtiger.

Begründung: Banach´scher Fixpunktsatz: Stimmen die Voraussetzungen, so konvergiert alles gegen den eindeutig bestimmten Fixpunkt in dem Intervall und das ist eben Wurzel 2.

Bei (b) schaut man halt, wo der Betrag der erste Ableitung kleiner 1 ist (und wo Kontraktion vorliegt) und in welchem Intervall 0 enthalten ist. Das ist der Fall für [-0.4347, 0.4347].

Daher bleib ich dabei, dass dies das gesuchte Intervall ist.

08.02.2011, 19:09

tigerbine

Auf diesen Beitrag antworten »

RE: Newton-Verfahren
Ich sehe alle Bilder.

(a) Ja.

(b) So ging das aus deinem ersten Post nicht hervor. Augenzwinkern

08.02.2011, 19:11

Gast11022013

Auf diesen Beitrag antworten »

RE: Newton-Verfahren
Ja, das war wirklich unglücklich formuliert.

Entschuldige.

Ich danke Dir für den Hinweis zu (a), denn so ist es für mich auch viel einsichtiger, wie man die Untersuchung startet!.. Ich hatte selbst ein ungutes Gefühl dabei und war nur durch Austesten auf mein Resultat gestoßen. So macht die Anwendung des Banach´schen Fixpunktsatzes auch viel mehr Sinn.

Freude

08.02.2011, 19:13

tigerbine

Auf diesen Beitrag antworten »

RE: Newton-Verfahren

Zitat:

Original von Dennis2010
Ja, das war wirklich unglücklich formuliert.

Entschuldige.

Kein Problem. Wenn du es schon perfekt könntest, würdest du ja nicht fragen. Viel Glück. Wink

Neue Frage »

Antworten »

Newton-Verfahren

Verwandte Themen