Newton-Verfahren

23.06.2010, 16:16

Anna90

Newton-Verfahren

Meine Frage:
Hallo!!

Ich muss eine Aufgabe zu dem Newton-Verfahren lösen,habe aber leider keine Ahnung,was genau ich da machen soll...
Die Aufgabe lautet:
Die Funktion ln(x) soll an der Stelle x = a > 0 näherungsweise berechnet werden. Dies kann beispielsweise
mit dem Newton-Verfahren zur Bestimmung einer Nullstelle der Funktion f(x)=e^x -a geschehen.
a)Geben Sie die zugehörige Iterationsvorschrift an.
b)Weisen Sie explizit die quadratische Konvergenz nach,indem Sie in der Iterationsvorschrift a=e^(lna)=e^(x_k+(lna-x_k)) durch eine abgebrochene Taylorreihe um x_k ersetzen.

Meine Ideen:
Also,bei der a) hab ich x_n+1=x_n-1+(a/e^x)
stimmt das?oder muss da noch was hin?

bei der b)muss ich ehrlich sagen,hab ich keine ahnung,was ich da machen soll und wäre echt froh,wenn mir da jemand helfen könnte...
danke!!

23.06.2010, 17:55

tigerbine

Auf diesen Beitrag antworten »

RE: Newton-Verfahren
$\begin{eqnarray*} f(x)=e^x -a \end{eqnarray*}$

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

Newton [WS] Eindimensionale Nullstellenprobleme 1 - versch. Verfahren

(a) $\begin{eqnarray*} x_{k+1} = x_k - \frac{e^{x_k} -a}{e^{x_k}} \end{eqnarray*}$

(b) $\begin{eqnarray*} x_{k+1} = x_k - \frac{e^{x_k} -e^{x_k+(\ln(a)-x_k)}}{e^{x_k}} =x_k - \frac{e^{x_k}(1 -e^{(\ln(a)-x_k)})}{e^{x_k}}=x_k-1+e^{(\ln(a)-x_k)} \end{eqnarray*}$

Da die Nullstelle einfach ist und die e-Funktion so schön oft diff'bar... [WS] Eindimensionale Nullstellenprobleme 2 - Das Newton Verfahren

24.06.2010, 10:41

Anna90

Auf diesen Beitrag antworten »

ok,danke erstmal...
also,die a) hab ich dann verstanden.is ja eigentlich nur einsetzen..
nur bei der b)bin ich immernoch verwirrt...ich hab mir deinen link mal durchgelesen,allerdings hatten wir diesen satz noch nicht..also,voraussetzungen prüfen und satz anwenden geht leider nicht.
Ich weiß nicht so recht,wie ich da anfangen soll...die Taylorreihe irritiert mich

24.06.2010, 13:22

tigerbine

Auf diesen Beitrag antworten »

In meinem Link steht die Taylorentwicklung allgemein, du musst doch nur deine konkrete Funktion einsetzen und die Rechnung machen. Idee!

24.06.2010, 13:53

Anna90

Auf diesen Beitrag antworten »

ja,das hab ich verstanden,aber wie muss ich das denn machen?ich verstehs ned...wie schreib ich denn e^(lna-x_k) als taylorreihe und wie mache ich dann weiter..?

24.06.2010, 14:15

tigerbine

Auf diesen Beitrag antworten »

$\begin{eqnarray*} f(x)=e^x -a \end{eqnarray*}$

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

$\begin{eqnarray*} f^{(n)}(x)=e^x, ~n \geq 1 \end{eqnarray*}$

Zitat:

Damit wäre der erste Schritt getan. Obiger Satz enthält ja noch eine Behauptung über die Konvergenzgeschwindigkeit. Die Funktion f ist 2mal stetig differenzierbar, daher lautet ihr 2-tes Taylorpolynom mit dem Restglied von Lagrange wie folgt (Entwicklungspunkt $\begin{eqnarray*} x_k \end{eqnarray*}$ )

$\begin{eqnarray*} f(x) = f(x_k) + \frac{f'(x_k)}{1!}(x-x_k) + \frac{f''(\xi_x)}{2!}\cdot (x-x_k)^2 \end{eqnarray*}$

Der Index bei $\begin{eqnarray*} \xi_x \end{eqnarray*}$ soll nur verdeutlichen, dass diese Variable von x abhängt.

Das können wir uns dann auch umstellen (wichtig!)

$\begin{eqnarray*} f(x^*) -f(x_k) - f'(x_k)(x^*-x_k) = \frac{1}{2} \cdot f''(\xi_{x^*})\cdot (x^*-x_k)^2 \end{eqnarray*}$

Also, muss doch nur eingesetzt werden.

$\begin{eqnarray*} f(x) = e^{_k} -a + \frac{e^{x_k}}{1!}(x-x_k) + \frac{e^{\xi_x}}{2!}\cdot (x-x_k)^2 \end{eqnarray*}$

Im gesuchten Punkt x* also

$\begin{eqnarray*} f(x^*) = e^{_k} -a + \frac{e^{x_k}}{1!}(x^*-x_k) + \frac{e^{\xi_{x^*}}}{2!}\cdot (x^*-x_k)^2 \end{eqnarray*}$

Zitat:

$\begin{eqnarray*} \text{Da f' stetig ist, existiert auf dem Kompaktum } [a,b] \text{ ein } m \in \mathbb R \text{ mit: } \end{eqnarray*}$

$\begin{eqnarray*} m:=\min_{x \in [a,b]}~|f'(x)|>0 \end{eqnarray*}$

$\begin{eqnarray*} \text{Da f'' stetig ist, existiert ein M auf dem Kompaktum } [a,b] \text{ mit: } \end{eqnarray*}$

$\begin{eqnarray*} M:=\max_{x \in [a,b]}~|f''(x)|< \infty \end{eqnarray*}$

Wir sollten zumindest ein grobes Intervall, in dem sich die Nullstelle befindet angeben können. Nun müssen wir zeigen, dass gilt

Zitat:

$\begin{eqnarray*} |x_{k+1}-x^*| && =.... \leq \frac{M}{2m} \cdot |x^*-x_k|^2 \end{eqnarray*}$

Das machen wir durch einsetzen. Schritt 1 sollte klar sein. Siehe a.

$\begin{eqnarray*} |x_{k+1}-x^*| && = |x_k-\frac{f(x_k)}{f'(x_k)}-x^*| = ... \end{eqnarray*}$

Dann alles auf einen Bruch bringen und ausklammern und eine Null addieren

$\begin{eqnarray*} ... = |\frac{0 + f'(x_k) \cdot x_k -f(x_k) - f'(x_k)\cdot x^* }{f'(x_k)}| = |\frac{f(x^*)-f(x_k) - f'(x_k)\cdot (x^*-x_k) }{f'(x_k)}| \end{eqnarray*}$

Nun benutzen wir die Umstellung von oben

$\begin{eqnarray*} ...= |\frac{\frac{1}{2} \cdot f''(\xi) \cdot (x^*-x_k)^2}{f'(x_k)}| \leq .... \end{eqnarray*}$

und schätzen im letzten Schritt ab.

$\begin{eqnarray*} ... \leq \frac{M}{2m} \cdot |x^*-x_k|^2 \end{eqnarray*}$

Das ist die Idee dahinter. f ist egal, so lange genügend oft differenzierbar und einfache Nullstelle.

Zitat:

b)Weisen Sie explizit die quadratische Konvergenz nach,indem Sie in der Iterationsvorschrift a=e^(lna)=e^(x_k+(lna-x_k)) durch eine abgebrochene Taylorreihe um x_k ersetzen.

Ich habe mit Restglieddarstellung gearbeitet, du kannst dir das entsprechend anpassen. Ideen solltest du nun genug haben. Du solltest also Taylor mit f' und f'' mindestens entwickeln.

24.06.2010, 18:41

Anna90

Auf diesen Beitrag antworten »

ok,vielen dank für deine hilfe..werd mich nachher mal dransetzen und versuchen das hinzubekommen!

24.06.2010, 18:48

tigerbine

Auf diesen Beitrag antworten »

Neue Frage »

Antworten »

Newton-Verfahren

Verwandte Themen