Ordnung und Konvergenz eines Iterationsverfahren

29.12.2006, 15:10

Jessi85

Auf diesen Beitrag antworten »

Ordnung und Konvergenz eines Iterationsverfahren

Hi,

zunächst mal die Daten zur Aufgabe:

$\begin{eqnarray*} f:\mathbb{R} \to \mathbb{R} \end{eqnarray*}$ sei in der Umgebung einer einfachen Nullstelle $\begin{eqnarray*} \zeta \end{eqnarray*}$ zweimal stetig diffbar. Zeige, daß das Iterationsverfahren $\begin{eqnarray*} x_{k+1} = \Phi(x_k), (k=0,1,...) \end{eqnarray*}$ der Form

$\begin{eqnarray*} y_k = x_k - \frac{f(x_k)}{f'(x_k)} \end{eqnarray*}$
$\begin{eqnarray*} x_{k+1} = y_k - \frac{f(y_k)}{f'(x_k)} \end{eqnarray*}$

lokal gegen $\begin{eqnarray*} \zeta \end{eqnarray*}$ konvergiert und mindestens Ordnung 3 besitzt.

Zur Ordnung:
Es gilt der Satz, daß eine Funktion p-ter Ordnung ist, wenn die ersten (p-1) Ableitung 0 sind, und die p-te Ableitung ungleich 0. Hier ist schon mein erstes Problem: Um zu zeigen, daß die gefragte Funktion (mind.) 3. Ordnung ist, müßte f ja dreimal stetig diffbar sein. verwirrt

verwirrt

Ich habe es trotzdem mal versucht (zweimal stetig diffbar heißt ja insbes. dreimal diffbar - vielleicht hätten sich die dritten Ableitungen weggekürzt): Die erste Ableitung ist ja noch human und an der Stelle $\begin{eqnarray*} \zeta \end{eqnarray*}$ auch 0 - aber die zweite Ableitung wird ja grauenhaft lang.

Kann man vielleicht geschickter ausnutzen, daß dieses $\begin{eqnarray*} y_k = x_k - .... \end{eqnarray*}$ die Newtoniteration ist oder gibts da sonst einen Trick?

Vielen Dank schonmal!

29.12.2006, 15:18

Jessie85

Auf diesen Beitrag antworten »

Mir fällt gerade auf, daß ich ja nur zeigen muß, daß auch die zweite Ableitung der Funktion 0 ist - die dreimalige stetige Diffbarkeit ist also gar nicht notwendig.
Soll man hier dann tatsächlich stur rechnen? Das kommt mir irgendwie spanisch vor weil die zweite Ableitung wirklich scheußlich ist.

29.12.2006, 15:24

tigerbine

Auf diesen Beitrag antworten »

RE: Ordnung und Konvergenz eines Iterationsverfahren
Bedenke, es steht da einfache Nullstelle, dann muss die erste Ableitung an dieser Stelle ungleich Null sein. Der Satz auf den Du anspielst bezieht auf Fixpunktiterationen. Mir ist bei einfachen Nullstellein einer C²-Funktion nur die quadratische Konvergenz bekannt.

29.12.2006, 15:40

tigerbine

Auf diesen Beitrag antworten »

RE: Ordnung und Konvergenz eines Iterationsverfahren
Zunächst solltest du einmal die Konvergenz zeigen. D.h. zunächst einmal die Existenz einer Umgebung in der das Verfahren linear konvergiert. Denn aus linearer Konvergenz(geschwindigkeit) folgt die Konvergenz an sich. Bei Quadratischer ist das nicht der Fall.

$\begin{eqnarray*} \text{ Zeige: Es exisistiert eine Umgebung } K_r(\zeta) \text{ mit: } |x_k - \zeta| \leq |x_{k-1} -\zeta| \text{ mit }\ c \in (0,1) \end{eqnarray*}$

$\begin{eqnarray*} \text{Daraus kann man zeigen, dass es zu jedem } \epsilon >0 \text{ ein K gibt, so dass für alle } k > K \text{ gilt: } \end{eqnarray*}$

$\begin{eqnarray*} |x_k - \zeta| < \epsilon \end{eqnarray*}$

$\begin{eqnarray*} \text{d.h. } \{x_k\} \rightarrow \zeta \end{eqnarray*}$

30.12.2006, 00:58

Jessi85

Auf diesen Beitrag antworten »

Hi,
kannst du mir nochmal einen Tipp geben - ich komme nämlich bei der Abschätzung nicht richtig weiter. Ich habe so begonnen:

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

Hier wollte ich den MWS anwenden:

$\begin{eqnarray*} (\nu \in ]x_k, \zeta[) \end{eqnarray*}$ $\begin{eqnarray*} ... = |x_k - \zeta| \cdot |1 - \frac{f'(\nu)}{f'(x_k)} - \frac{f(y_k)}{f'(x_k) |x_k - \zeta|}| = ? \end{eqnarray*}$

Oder soll ich den ganz rechten Summanden mit der Dreiecksungleichung "abspalten" und auch darauf den MWS anwenden? Ich habe es versucht, aber das bringt mich auch nicht allzuweit.

Hach - wenn ich nur nicht immer wieder diese Schwierigkeiten mit Abschätzungen hätte unglücklich

unglücklich

30.12.2006, 08:54

tigerbine

Auf diesen Beitrag antworten »

Ich geb Dir mal ne Gliederung:

1. Zeige es gibt eine Umgebung $\begin{eqnarray*} K_r \end{eqnarray*}$ (=kompakte Menge) von $\begin{eqnarray*} \zeta \end{eqnarray*}$ , in der das Newton Verfahren woh definiert ist. (Also kein teilen durch "0")

2./3. Benutze die Existenz von Min/Max von Stetigen Funktionen auf kompakten Mengen. (Sowohl f' als f'' sind stetig!) m:=min|f'(x)<, M:=mx|f''(x)| auf $\begin{eqnarray*} K_r \end{eqnarray*}$

4. Verkleinere r so dass gilt: $\begin{eqnarray*} \frac{M}{m}\cdot r<1 \end{eqnarray*}$

5. Wende 2mal den Mittelwertsatz der Differenzialrechnung auf $\begin{eqnarray*} |x_{k+1} - \zeta| \end{eqnarray*}$ an.

Aus 1-4 folgt die lineare Konvergenz. Mit 5 die quadratische.

Anzeige

30.12.2006, 12:11

Jessi85

Auf diesen Beitrag antworten »

Hi,
sorry - wahrscheinlich nerve ich schon - aber so ganz verstehe ich das nicht. Wo kommt z.B. bei 2./3. die zweite Ableitung von f vor ohne den MWS anzuwenden?

Ich habe das jetzt nochmal versucht:

Wegen $\begin{eqnarray*} f'(\zeta) \neq 0 \end{eqnarray*}$ gibt es eine Umgebung von $\begin{eqnarray*} \zeta \end{eqnarray*}$ sodaß für alle x aus der Umgebung gilt $\begin{eqnarray*} f'(x) \neq 0 \end{eqnarray*}$ .
Nun sei $\begin{eqnarray*} M:= \max_{x \in U(\zeta)} |f'(x)|, \quad m:= \min_{x \in U(\zeta)} |f'(x)| \end{eqnarray*}$

$\begin{eqnarray*} |x_{k+1} - \zeta| = |x_k - \zeta - \frac{f(x_k) - f(\zeta)}{f'(x_k)} - \frac{f(y_k) - f(\zeta)}{f'(x_k)}| \leq |x_k - \zeta| \left| 1 - \frac{f'(\eta)}{f'(x_k)} - \frac{f'(\mu)}{f'(x_k)} \right| \leq \frac{3|M|}{|m|} |x_k - \zeta| \end{eqnarray*}$

mit $\begin{eqnarray*} \eta \in ]x_k, \zeta[, \quad \mu \in ]y_k, \zeta[ \end{eqnarray*}$ (und da $\begin{eqnarray*} |y_k - \zeta| \leq |x_k - \zeta| \end{eqnarray*}$ [wegen Newtoniteration] gilt das erste Ungleichheitszeichen)

Und jetzt müßte ich auch die Umgebung geeignet verkleinern, sodaß $\begin{eqnarray*} 3 \left| \frac{M}{m} \right| < 1 \end{eqnarray*}$ ist (für lineare Konvergenz).

Geht das auch so?

30.12.2006, 12:14

tigerbine

Auf diesen Beitrag antworten »

In der Angabe steht 2mal stetig diffbar. das reicht für m und M.

Den Rest lese ich später.

31.12.2006, 00:06

tigerbine

Auf diesen Beitrag antworten »

Also, dann wollen wir mal. Zunächst mal reines Umformulieren

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

Nun die erste Abschätzung und Anwendung des MWS der DiffR:

$\begin{eqnarray*} \leq |x_k-\zeta|\cdot|1-\frac{f'(y)}{f'(x_k)}|=|x_k-\zeta|\cdot |\frac{f'(x_k)-f'(y)}{f'(x_k)}|=|x_k-\zeta|\cdot|(x_k-y)\cdot\frac{f'(x_k)-f'(y)}{(x_k-y)\cdot f'(x_k)}| \end{eqnarray*}$

erneute Anwendung des MWS:

$\begin{eqnarray*} =|x_k-\zeta|\cdot|x_k-y|\cdot|\frac{f''(z)}{ f'(x_k)}| \end{eqnarray*}$

nun benutzen wir die Abschätzungen aus 2,3 und bedenke, dass wegen $\begin{eqnarray*} y \in (x_k; \zeta) \Rightarrow |x_k-y|\leq |x_k-\zeta| \end{eqnarray*}$

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

Für die lineare konvengenz können wir das ebenfalls ausnutzen, in der Art denn $\begin{eqnarray*} |x_k-y| \leq r \end{eqnarray*}$

$\begin{eqnarray*} \leq \frac{M}{m}\cdot r |x_k-\zeta| \end{eqnarray*}$

d.h. r soweit verkleinern, dass gilt:

$\begin{eqnarray*} \frac{M}{m} \cdot r < 1 \end{eqnarray*}$

31.12.2006, 12:16

Jessi85

Auf diesen Beitrag antworten »

Hi,
erstmal vielen Dank für deine Mühe!

Aber du zeigst ja "nur" die Konvergenz und Ordnung der Newtoniteration? Also dein $\begin{eqnarray*} y \end{eqnarray*}$ aus dem ersten MWS ist schon einfach aus dem offenen Intervall $\begin{eqnarray*} \overline{x_k,\zeta} \end{eqnarray*}$ , nicht das iterierte $\begin{eqnarray*} y_k \end{eqnarray*}$ von oben. Es ist doch

$\begin{eqnarray*} x_{k+1} = y_k - \frac{f(y_k)}{f'(x_k)} \end{eqnarray*}$ wobei die $\begin{eqnarray*} y_k \end{eqnarray*}$ jeweils newtoniteriert sind.

31.12.2006, 12:55

tigerbine

Auf diesen Beitrag antworten »

Mmh. Da hast Du recht. Habe nur "Newton" gelesen. nicht deine xy-Notation. Sry.

I. Deine Notation

$\begin{eqnarray*} y_k = x_k - \frac{f(x_k)}{f'(x_k)} \end{eqnarray*}$
$\begin{eqnarray*} x_{k+1} = y_k - \frac{f(y_k)}{f'(x_k)} \end{eqnarray*}$

II. Schauen wir mal 2 Schritte des NewtonVF an

$\begin{eqnarray*} x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} \end{eqnarray*}$
$\begin{eqnarray*} x_{k+2} = x_{k+1} - \frac{f(x_{k+1})}{f'(x_{k+1})} \end{eqnarray*}$

Wie hängt das jetzt zusammen? der Unterschied ist im Nenner. Da wir gezeigt haben, das NVF quadratisch konvergiert, müsste, wenn wir 2 SChritte zu einen zusammen fassen es mit p=4 konvergieren. Also besteht jetzt gute Chance zu zeigen, dass deine Variante mit p=3 konvergiert.

$\begin{eqnarray*} \text{I. } f'(x_k) \end{eqnarray*}$
$\begin{eqnarray*} \text{II. } f'(x_{k+1}) \end{eqnarray*}$

Ziel:

$\begin{eqnarray*} |x_{k+1}-\zeta| \leq c\cdot|x_k - \zeta|^3 \end{eqnarray*}$

Ich versuche da noch was aufzuschreiben, aber du wirst verzeihen, dass ich nicht weiß wann, heute ist ja Silvester und da ist noch einiges vorzubereiten Wink

Wink

01.01.2007, 11:56

tigerbine

Auf diesen Beitrag antworten »

Ein frohes neues Jahr Prost

Prost

Also wenn wir dein Verfahren mal zusammenfassen. Dann besteht ein Iterationsschritt aus 2 Schritten. Wir bleiben mal bei der Bezeichnung mit x.

Schritt 1 - Newton VF

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

Für diesen Schritt haben wir die quadr. Konvergenz bewiesen.

Schritt 2 - vereinfachtes Newton Verfahren

$\begin{eqnarray*} x_{k+2} = x_{k+1} - \frac{f(x_{k+1})}{f'(x_{k})} \end{eqnarray*}$

Dieser Schritt konvergiert nur linear. Das ist nun noch zu zeigen.

02.01.2007, 16:40

Jessi85

Auf diesen Beitrag antworten »

Das wünsche ich dir auch Wink

Wink

Ich versuche es mal:

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

Also:

In einer Umgebung $\begin{eqnarray*} U_r(\zeta) = [\zeta - r, \zeta + r] \end{eqnarray*}$ gilt:

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

jetzt der MWS mit $\begin{eqnarray*} \eta \in ]x_{k+1}, \zeta[ \end{eqnarray*}$ :

$\begin{eqnarray*} ... = |x_{k+1} - \zeta| \cdot |1 - \frac{f'(\eta)}{f'(x_{k})}| = |x_{k+1} - \zeta| \cdot |\frac{f'(x_k) - f'(\eta)}{f'(x_{k})}| = ... \end{eqnarray*}$

nochmal der MWS mit $\begin{eqnarray*} \mu \in ]x_k, \eta[ \end{eqnarray*}$ und mit M,m wie von dir definiert:

$\begin{eqnarray*} ... = |x_{k+1} - \zeta| \cdot |x_k - \eta| \cdot |\frac{f''(\mu)}{f'(x_k)}| \leq |x_{k+1} - \zeta| \cdot |x_k - \eta| \cdot |\frac{M}{m}| = ... \end{eqnarray*}$

und jetzt ist $\begin{eqnarray*} |x_k - \eta| \leq 2r \end{eqnarray*}$ , also

$\begin{eqnarray*} ... \leq 2r \cdot |\frac{M}{m}| \cdot |x_{k+1} - \zeta| \end{eqnarray*}$

Mit geeignetem r folgt lineare Konvergenz. Zusammen mit dem Newtonverfahren aus dem ersten Schritt (das mind. quadratisch konvergiert) folgt die Behauptung.

Noch eine Frage hätte ich: Man könnte aber auch das vereinfachte Newtonverfahren als Fixpunktiterations betrachten, und zeigen, daß die erste Ableitung ungleich 0 ist, woraus Ordung 1 folgt. Dann müßte man eben noch zeigen, daß das vereinfachte Newtonverfahren stark kontrahierend ist. Oder?

02.01.2007, 22:42

tigerbine

Auf diesen Beitrag antworten »

Zitat:

Original von Jessi85

Noch eine Frage hätte ich: Man könnte aber auch das vereinfachte Newtonverfahren als Fixpunktiterations betrachten, und zeigen, daß die erste Ableitung ungleich 0 ist, woraus Ordung 1 folgt. Dann müßte man eben noch zeigen, daß das vereinfachte Newtonverfahren stark kontrahierend ist. Oder?

nur eine kurze Antowrt am Abend. Du musst mit den Formulierungen aufpassen. Mit dem newton Verfahren bestimmen wir eine Nullstelle der Funktion f. Man kann dieses Problem durch das verwandte Problem der Bestimmung Fixpunktes einer Funktion g lösen. Diese (g) muss dann eine kontrahierende Selbstabbildung sein.

Den Rest lese ich morgen. nicht das ich wieder Indizes durcheinander bringe.

Gruß Wink

Wink

02.01.2007, 23:14

tigerbine

Auf diesen Beitrag antworten »

Zitat:

Original von Jessi85

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

Müßte da nicht $\begin{eqnarray*} x_{k+2}=... \end{eqnarray*}$ stehen?

03.01.2007, 12:13

Jessi85

Auf diesen Beitrag antworten »

Zitat:

Original von tigerbine

Zitat:

Original von Jessi85

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

Müßte da nicht $\begin{eqnarray*} x_{k+2}=... \end{eqnarray*}$ stehen?

Oh, ja natürlich. Im Folgenden habe ich es aber richtig. Sorry.

Zur Fixpunktiteration: Dein g wäre dann die Iterationsfunktion. Also $\begin{eqnarray*} g(x_{k+1}) := x_{k+1} - \frac{f(x_{k+1})}{f'(x_k)} \end{eqnarray*}$ . Und der Fixpunkt von g ist Nullstelle von f. So meintest du das, oder? (So dachte ich mir das nämlich)

03.01.2007, 17:58

tigerbine

Auf diesen Beitrag antworten »

Newton-Verfahren

$\begin{eqnarray*} \text{Gesucht: Nullstelle der Funktion f, also: } f(x) = 0 \end{eqnarray*}$

$\begin{eqnarray*} \text{Annäherung durch Tangente: } t(x) = (x-x_{k})\cdot f'(x_k) +f(x_k) \end{eqnarray*}$

$\begin{eqnarray*} \text{Iterartionsvorschrift aus Nullstelle der Tangente: } 0 = (x-x_{k})\cdot f'(x_k) +f(x_k) \Leftrightarrow 0 = x\cdot f'(x_k) - x_k\cdot f'(x_k)+f(x_k) \Leftrightarrow x = x_k - \frac{f(x_k)}{f'(x_k)} \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} \end{eqnarray*}$

Fixpunktiteration

$\begin{eqnarray*} \text{Anstatt der Nullstelle von f, können wir auch den Fixpunkt von g suchen. } g(x):=\zeta + h(x)\cdot f(x) \Rightarrow g(\zeta) = \zeta + h(\zeta)\cdot \underbrace{f(\zeta)}_{=0}=\zeta \end{eqnarray*}$

Wie dann daraus die Iteratonsvorschrift kommt, steht hier:

Newton und Fixpunkt

Bitte beachte die anderen Bezeichnungen Wink

Wink

03.01.2007, 21:37

tigerbine

Auf diesen Beitrag antworten »

Zitat:

Original von Jessi85
Das wünsche ich dir auch Wink

Wink

Ich versuche es mal:

$\begin{eqnarray*} x_{k+2} = x_{k+1} - \frac{f(x_{k+1})}{f'(x_k)} \end{eqnarray*}$

Also:

In einer Umgebung $\begin{eqnarray*} U_r(\zeta) = [\zeta - r, \zeta + r] \end{eqnarray*}$ gilt:

$\begin{eqnarray*} |x_{k+2} - \zeta| = |x_{k+1} - \zeta - \frac{f(x_{k+1})}{f'(x_k)}| = ... \end{eqnarray*}$ Freude

Freude

jetzt der MWS mit $\begin{eqnarray*} \eta \in ]x_{k+1}, \zeta[ \end{eqnarray*}$ :

$\begin{eqnarray*} ... = |x_{k+1} - \zeta| \cdot |1 - \frac{f'(\eta)}{f'(x_{k})}| = |x_{k+1} - \zeta| \cdot |\frac{f'(x_k) - f'(\eta)}{f'(x_{k})}| = ... \end{eqnarray*}$ Freude

Freude

nochmal der MWS mit $\begin{eqnarray*} \mu \in ]x_k, \eta[ \end{eqnarray*}$ und mit M,m wie von dir definiert:

$\begin{eqnarray*} ... = |x_{k+1} - \zeta| \cdot |x_k - \eta| \cdot |\frac{f''(\mu)}{f'(x_k)}| \leq |x_{k+1} - \zeta| \cdot |x_k - \eta| \cdot |\frac{M}{m}| = ... \end{eqnarray*}$ Freude

Freude

und jetzt ist $\begin{eqnarray*} |x_k - \eta| \leq 2r \end{eqnarray*}$ , also

$\begin{eqnarray*} ... \leq 2r \cdot |\frac{M}{m}| \cdot |x_{k+1} - \zeta| \end{eqnarray*}$ Freude

Freude

Mit geeignetem r folgt lineare Konvergenz.

Die Gesamtkonvergenzrate muss jetzt noch sauber aufgeschrieben werden.

17.01.2010, 13:25

Andy_

Auf diesen Beitrag antworten »

Hi,

ich bin durch eine Internet-Suche auf diesen alten Thread gestoßen. In einer aktuellen Übungsaufgabe muss ich die selbe Aufgabe beweisen. Leider verstehe ich aber diesen Beweis nicht - vor allem sehe ich nicht, wo hier der Mittelwert-Satz der Differentialrechnung angewendet wurde...
Und warum reicht es zu zeigen, dass der letzte Schritt nur linear konvergiert??

Danke für eure Antworten,
Andy

17.01.2010, 13:37

Andy_

Auf diesen Beitrag antworten »

Wie kommt man z. B. auf diese Gleihheit :

$\begin{eqnarray*} <br /> |x_{k+1} - \zeta - \frac{f(x_{k+1})}{f'(x_k)}| = |x_{k+1} - \zeta| \cdot |1 - \frac{f'(\eta)}{f'(x_{k})}| \end{eqnarray*}$

Erstens ist mir die multiplikative Schreibweise bei Beträgen noch nie begegnet - bei Beträgen muss man ungeheuer aufpassen, dass man nichts falsches macht. Und zweitens sehe ich ehrlich gesagt nicht, wie das, was rechts vom Gleichheitszeichen steht, durch Anweden des Mittelwertsatzes aus dem folgt, was links vom Gleihheitszeichen steht.

Es wäre sehr nett, wenn mir das jemand erklären würde.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »