3te Wurzel Konvergenz,Newton Verfahren

18.01.2015, 20:09

StrunzMagi

Auf diesen Beitrag antworten »

3te Wurzel Konvergenz,Newton Verfahren

Nach den Beispiel in der Vorlesung wird das Newtonsche Verfahren zur Berechnung der 3.ten Wurzel von $\begin{eqnarray*} a\in\mathbb{R}_{+} \end{eqnarray*}$ (ohne 0) durch die Iterationsvorschrift $\begin{eqnarray*} x_{n+1}=\frac{1}{3}(2x_n+\frac{a}{x_n^2}) \end{eqnarray*}$ mit beliebigen Anfangswert $\begin{eqnarray*} x_0>0 \end{eqnarray*}$ gegeben.
Man zeige, dass auch die durch
$\begin{eqnarray*} x_{n+1}=\frac{1}{2}(x_n+\frac{a}{x_n^2}) \end{eqnarray*}$
rekursiv definierte Folge gegen $\begin{eqnarray*} \sqrt[3]{a} \end{eqnarray*}$ konvergiert und vergleiche die Konvergenzgeschwindigkeiten beider Verfahren.

Hallo,
Wenn die rekursiv definierte Folge konvergiert, dann
$\begin{eqnarray*} x_{n+1}=\frac{1}{2}(x_n+\frac{a}{x_n^2}) \rightarrow g=\frac{1}{2}g+\frac{a}{2g^2} \iff \frac{1}{2}g=\frac{a}{2g^2}\iff g=\sqrt[3]{a} \end{eqnarray*}$

Um die Konvergenz fetszustellen hab ich versucht das Newtonverfahren auf die Funktion $\begin{eqnarray*} f(x)=(x^3-a)^{\frac{2}{3}} \end{eqnarray*}$ anzuwenden.
$\begin{eqnarray*} f'(x)=\frac{2}{3}(x^3-a)^{\frac{-1}{3}}*3x^2=\frac{2x^2}{\sqrt[3]{x^3-a}} \end{eqnarray*}$
$\begin{eqnarray*} x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}=x_n-\frac{(\sqrt[3]{x_n^3-a})^2}{\frac{2x_n^2}{\sqrt[3]{x_n^3-a}}} \end{eqnarray*}$
$\begin{eqnarray*} =x_n-\frac{x_n^3-a}{2x_n^2}=\frac{2x_n^3-x_n^3-a}{2x_n^2}=\frac{x_n^3-a}{2x_n^2}=\frac{1}{2}(x_n-\frac{a}{x_n^2}) \end{eqnarray*}$

Hier hab ich aber das problem,dass ich für die Konvergenz des Newton-Verfahrens brauche, dass die Funktion in dem angeschauten Intervall konkav oder konvex ist.
Ja ich muss mir ein Intervall um die dritte Wurzel von a anschauen aber wie genau ich das machen soll da bin ich überfragt!

$\begin{eqnarray*} f''(x)=2*(-\frac{1}{3}(x^3-a)^{\frac{-4}{3}}*3x^2*x^2+(x^3-a)^{\frac{-1}{3}}*2x)=2*(\frac{-x^4}{(\sqrt[3]{x^3-a})^4}+\frac{2x}{\sqrt[3]{x^3-a}}) \end{eqnarray*}$
Wenn ich $\begin{eqnarray*} \frac{x}{(\sqrt[3]{x^3-a})}=\epsilon \end{eqnarray*}$ schreibe dann ist $\begin{eqnarray*} f''(x)=0 \iff 2(-\epsilon^4+2\epsilon)=0\iff -\epsilon^4+2\epsilon=0\iff \epsilon^4=2\epsilon \iff \frac{\epsilon^3}{2}=1 \end{eqnarray*}$

19.01.2015, 10:49

HAL 9000

Auf diesen Beitrag antworten »

Eine Frage: Warum machst du es dir so furchtbar kompliziert und betrachtest $\begin{align*} f(x)=(x^3-a)^{\frac{2}{3}} \end{align*}$ statt des einfacher strukturierten $\begin{align*} f(x)=x^3-a \end{align*}$ ?

EDIT: Ok, ich verstehe - du hast eine Funktion gesucht, so dass das Newton-Verfahren angewandt auf diese Funktion deine zweite Iteration ergibt.

19.01.2015, 11:07

StrunzMagi

Auf diesen Beitrag antworten »

Achso ich hab meinen Post die ganze Zeit gesucht und deshalb neu geschrieben, kannst du ihn in den Uni-Bereich verschieben?

19.01.2015, 11:15

HAL 9000

Auf diesen Beitrag antworten »

Das mit der Konvexität/Konkavität wird schwierig - Beispielplot im Fall a=1:

19.01.2015, 11:32

StrunzMagi

Auf diesen Beitrag antworten »

Oder kann ich den Thread selbst in die Hoschulmathematik verschieben?

Ich hätte auch noch einen Beweis des Newtonschen-Verfahrens mithilfe des Fixpunktsatzes, da hab ich dann keine Konvexität/Konkavität in den Annahmen:
Sei $\begin{eqnarray*} D \subseteq \mathbb{R} \end{eqnarray*}$ ein abgeschlossenes Intervall mit $\begin{eqnarray*} f: D \rightarrow \mathbb{R} \end{eqnarray*}$ eine zweimal differenzierbare Funktion mit $\begin{eqnarray*} f(D)\subseteq D \wedge |f(x)f''(x)|<q|f'(x)|^2 \end{eqnarray*}$ mit $\begin{eqnarray*} q<1 \forall x \in D \end{eqnarray*}$
Dann konvergiert für ein $\begin{eqnarray*} x_0 \in D \end{eqnarray*}$ die durch $\begin{eqnarray*} x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)} \end{eqnarray*}$ rekursiv definierte Folge $\begin{eqnarray*} (x_n)_{n\in\mathbb{N}} \end{eqnarray*}$ gegen die Löung der Gleichung $\begin{eqnarray*} f(x)=0 \end{eqnarray*}$

Glaubst du damit hab ich mehr Chancen?
Das problem ist ohne Newton-Verfahren sondern mit Monotonie&Beschränktheit kann ich die Aufgabe auch nicht lösen. Denn die Folge wackelt um die 3.te wurzel herum.

19.01.2015, 11:57

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von StrunzMagi
Das problem ist ohne Newton-Verfahren sondern mit Monotonie&Beschränktheit kann ich die Aufgabe auch nicht lösen. Denn die Folge wackelt um die 3.te wurzel herum.

Allerdings - das sieht man ja bereits dem Plot oben an, wenn man sich das Newton-Verfahren grafisch vorstellt.

Warum aber trotzdem nicht direkt: Mit $\begin{align*} b=\sqrt[3]{a} \end{align*}$ ist

$\begin{align*} x_{n+1}-b &= \frac{1}{2}\left( x_n + \frac{b^3}{x_n^2} - 2b \right) = \frac{x_n^3-2bx_n^2+b^3}{2x_n^2} = \frac{x_n^2-bx_n-b^2}{2x_n^2} (x_n-b)\\ &= -\frac{1}{2} \left(1- \frac{(2x_n+b)}{x_n^2}(x_n-b) \right) (x_n-b) \end{align*}$

D.h., in der "Nähe" der Lösung $\begin{align*} b \end{align*}$ hat man in etwa den Kontraktionsfaktor $\begin{align*} \frac{1}{2} \end{align*}$ , bzw. mit ein wenig Rechnerei findet man für Kontraktionsfaktoren $\begin{align*} \frac{1}{2}<q<1 \end{align*}$ ein Intervall um $\begin{align*} b \end{align*}$ , wo diese Kontraktion dann greift. Auf alle Fälle ist die Konvergenzordnung linear, d.h. schlechter als die quadratische Konvergenz der anderen Iteration

$\begin{align*} x_{n+1} = \frac{1}{3}\left( 2x_n+\frac{a}{x_n^2} \right) \end{align*}$ .

Anzeige

19.01.2015, 15:43

StrunzMagi

Auf diesen Beitrag antworten »

Warum regierst du nicht auf meine Frage, ob ich das verschieben kann? Oder geht das grundsätzlich gar nicht - was schade ist, denn im Schulmathematikforum werden die wenigstens darauf aufmerksam werden.

Ich kann ehrlich gesagt mit deinen Post nicht soviel anfangen. Die Rechnung ist mir noch klar, aber das mit dem Kontraktionsfaktor verstehe ich nicht mehr, ich hab zwar im Internet nachgeschaut was ein Kontraktionsfaktor ist aber trotzdem ist mir, dass in dem Zusammenhang unklar. Denn du hast ja noch viel mehr als nur das 1/2 vor $\begin{eqnarray*} x_n -b \end{eqnarray*}$ stehen.
Zeigst du damit vlt. die Lipschitzstetigkeit?
Das Beispiel ist für das erste Semester Augenzwinkern

Augenzwinkern

Das Newton-Verfahren greift hier also sicher nicht?

19.01.2015, 15:45

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von StrunzMagi
Warum regierst du nicht auf meine Frage, ob ich das verschieben kann?

Das können nur Moderatoren - also weder du noch ich. Irgendein Moderator wird es schon noch verschieben. Also lass das Generve, und vor allem diesen unangebracht vorwurfsvollen Ton: Schließlich reagierst du auch nicht auf meine Ausführungen so, wie ich mir das vielleicht wünsche.

Zitat:

Original von StrunzMagi
Die Rechnung ist mir noch klar, aber das mit dem Kontraktionsfaktor verstehe ich nicht mehr, ich hab zwar im Internet nachgeschaut was ein Kontraktionsfaktor ist aber trotzdem ist mir, dass in dem Zusammenhang unklar. Denn du hast ja noch viel mehr als nur das 1/2 vor $\begin{eqnarray*} x_n -b \end{eqnarray*}$ stehen.

Du hast ja selbst mit so einem $\begin{align*} q \end{align*}$ operiert, also dachte ich du wüsstest, was du da tust.

Ich rede von einem $\begin{align*} q<1 \end{align*}$ mit der Eígenschaft

$\begin{align*} \left| x_{n+1}-b \right| \leq q\cdot \left| x_{n}-b \right| \end{align*}$

für alle $\begin{align*} n \end{align*}$ , oder zumindest alle $\begin{align*} n\geq n_0 \end{align*}$ - denn dann ist die Konvergenz der Folge gegen $\begin{align*} b \end{align*}$ gesichert (Majorisierung dieser Differenzenfolge durch eine geometrische Folge).

19.01.2015, 16:12

StrunzMagi

Auf diesen Beitrag antworten »

"Das können nur die Moderatoren" hätte gereicht, danke.

Wir hatten nur einmal, dass wenn für $\begin{eqnarray*} (a_n) \end{eqnarray*}$ ein festes $\begin{eqnarray*} q\in \mathbb{R} \end{eqnarray*}$ mit 0<q<1 gibt sodass:
$\begin{eqnarray*} |a_{n+1}-a_n|\le q||a_n-a_{n-1}| (n\ge1) \end{eqnarray*}$
gilt, dann konvergiert $\begin{eqnarray*} (a_n) \end{eqnarray*}$ .
In der Form wie du das machst kam es bei uns noch nicht dran .Es steht doch aber noch ein anderer Faktor als nur $\begin{eqnarray*} 1/2 \end{eqnarray*}$ vor dem $\begin{eqnarray*} |x_n-b| \end{eqnarray*}$ . Wie weißt du denn in welcher Größenordnung $\begin{eqnarray*} 1-\frac{2x_n+b}{x_n^2} (x_n-b) \end{eqnarray*}$ ist?

19.01.2015, 16:47

HAL 9000

Auf diesen Beitrag antworten »

Alles mache ich nun nicht für dich, ich habe doch erwähnt, wo anzusetzen ist:

Zitat:

Original von HAL 9000
mit ein wenig Rechnerei findet man für Kontraktionsfaktoren $\begin{align*} \frac{1}{2}<q<1 \end{align*}$ ein Intervall um $\begin{align*} b \end{align*}$ , wo diese Kontraktion dann greift

19.01.2015, 17:11

StrunzMagi

Auf diesen Beitrag antworten »

Ich glaub nicht, dass ich mit meinen Anfagspost und meinen anderen Themen, den Eindruck mache, dass ich nur auf schnelle Lösungen ohne Eigeninitiative aus bin.
Am falschen Fuß aufgestanden? Oder wir sprechen einfach aneinander vorbei, kann auch sein.

Ich verstehe nur nicht was ich genau machen muss und frage deshalb nach.
Ist das Ziel $\begin{eqnarray*} |1-\frac{2x_n+b}{x_n^2} (x_n-b)| \end{eqnarray*}$ gegen 1 abzuschätzen? Ich bin da überfragt, wie du den teil abschätzen möchtest.

19.01.2015, 19:12

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von StrunzMagi
Am falschen Fuß aufgestanden?

Vielleicht ist mir dein Ton (oben schon) einfach zu vorlaut, so dass ich ebenso ungehalten antworte. Wie man in den Wald hineinruft, so schallt es heraus.

19.01.2015, 20:09

StrunzMagi

Auf diesen Beitrag antworten »

Schade, dass man durch das Internet so aneinender vorbeiredet. Ich habe nur so reagiert, da ich mich von dir in mehreren Posts angegriffen sowie von oben betrachtet fühlte und ich das Gefühl hatte, dass du auf meine Fragen und Antworten gar nicht eingehst und nur deine Lösung gültig ist.

Ich hoffe wir können das nun ganz beiseite schieben. Morgen setz ich mich nochmal an das Beispiel.

19.01.2015, 20:23

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von StrunzMagi
dass du auf meine Fragen und Antworten gar nicht eingehst und nur deine Lösung gültig ist.

Die nächste unverschämte Unterstellung. unglücklich

unglücklich

Ich hab doch festgestellt, dass dieses dein f weder konvex noch konkav ist, und dass deswegen dieser Weg nicht sehr aussichtsreich ist. Dann habe ich meinen Vorschlag unterbreitet, du musst ihn ja nicht nehmen. Ich bin hier kein Helfersklave, der jeden noch so seltsamen Weg, den mir ein Threadersteller vorschlägt, mit Engagement unterstützt. Da such dir mal einen anderen, oder gleich lokale bezahlte Nachhilfe, mit der kannst du vielleicht so umspringen, wie du es hier mit mir versuchst. Wink

Wink

19.01.2015, 21:34

StrunzMagi

Auf diesen Beitrag antworten »

Ach, ich verstehe echt nicht wieso du immer so negativ reagierst, das ist schon nicht mehr schön. Bitte belassen wir es nun so dabei. Es war vlt. meine Schuld, da es schon damit begonnen hat, dass ich es ins falsche Forum gepostet habe. Dieses Gespräch führt zu absolut nichts, also bitte lass uns einen Schlussstrich darunterziehen.

22.01.2015, 12:11

StrunzMagi

Auf diesen Beitrag antworten »

Hallo,
So, ich hoffe wir können wieder zur Mathematik zurückkehren.
Ich hab versucht das ganze nachzuvollziehen und schreibe deine Idee/Ausführung deshalb nochmals nieder mit meinen Ergänzungen.

Sei $\begin{eqnarray*} \lim_{n\rightarrow\infty} x_{n}=x \end{eqnarray*}$ , falls er existiert.
$\begin{eqnarray*} |x_{n+1}-x|=|\frac{1}{2}(x_n+\frac{a}{x_n^2})-x|=|\frac{1}{2}(x_n+\frac{a}{x_n^2}-2x)|=\frac{1}{2}|\frac{x_n^3+a-2xx_n^2}{x_n^2}| \end{eqnarray*}$
Wenn die Folge $\begin{eqnarray*} (x_n) \end{eqnarray*}$ konvergiert, dann
$\begin{eqnarray*} x_{n+1}=\frac{1}{2}(x_n+\frac{a}{x_n^2}) \rightarrow x=\frac{1}{2}x+\frac{a}{2x^2} \end{eqnarray*}$
D.h. $\begin{eqnarray*} x=\sqrt[3]{a} \iff x^3=a \end{eqnarray*}$

Ich rechne also weiter:
$\begin{eqnarray*} \frac{1}{2}|\frac{x_n^3+a-2xx_n^2}{x_n^2}|= \frac{1}{2}|\frac{x_n^3+x^3-2xx_n^2}{x_n^2}|=\frac{1}{2}|\frac{(x_n-x)*(x_n^2-x^2-x_n*x)}{x_n^2}| \end{eqnarray*}$
$\begin{eqnarray*} =\frac{1}{2}|x_n-x||\frac{(x_n^2-x^2-x_n*x)}{x_n^2}|=\frac{1}{2}|x_n-x||(1-(\frac{x}{x_n})^2-\frac{x}{x_n})|\le \frac{1}{2}|x_n-x|*1 \end{eqnarray*}$
Der letzte Schritt, da das Quadrat ist sicher größer als 0 und die Folge $\begin{eqnarray*} (x_n) \end{eqnarray*}$ ist allgemein größer als 0 für positiven Anfangswert, also ist auch der Grenzwert größer als 0.
Daraus folgt induktiv: $\begin{eqnarray*} |x_{n+1}-x|\le (\frac{1}{2})^{n+1} |x_0-x| \end{eqnarray*}$
Nur Angst habe ich hier vor einen Zirkelschluß..

25.01.2015, 12:18

StrunzMagi

Auf diesen Beitrag antworten »

Ich bin noch an der Aufgabe interssiert und würde mich über Antworten freuen.
Ein kleiner Push für die Aufgabe Augenzwinkern

Augenzwinkern

LG

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »