Konvergenzgeschwindigkeit beim Newton-Verfahren

02.07.2006, 02:12

tigerbine

Konvergenzgeschwindigkeit beim Newton-Verfahren

Servus,

bin auf der suche nach dem Beweis folgender Aussage:

"Für mehrfach Nullstellen konvergiert das Newton-Verfahren Linear".

Bitte direkt link zu einem Beweis oder Beweis ausführen Freude

Danke.

Das Thema wurde bei uns so "schnell" abgehandelt, dass die Beweise der Aussagen fehlen. Dieses Beweis bekomme ich alleine nicht hin und die Recherche im Netz hat für mich auch noch nichts ergeben.

Und da sind noch mehr offene Punkte in diesem Kapitel unglücklich

Danke und Gruß
tigerbine

02.07.2006, 10:41

Abakus

Auf diesen Beitrag antworten »

RE: Konvergenzgeschwindigkeit beim Newton-Verfahren
Angenommen y ist eine k-fache Nullstelle von f und ist ferner lokal die einzige Nullstelle. Dann gilt:

$\begin{eqnarray*} f(y) = f'(y) =~...~=f^{k-1}(y) = 0 \end{eqnarray*}$

Damit sind in der Taylorentwicklung von f bzw f' die ersten k bzw (k-1) Summanden gleich 0. Die Taylorentwicklung setzen wir jetzt in die Interationsfunktion ein, es ist:

$\begin{eqnarray*} |\frac{x_{n+1} - y}{x_n - y}| = |\frac{x_{n} - \frac{f(x_n)}{f'(x_n)} - y}{x_n - y}| = |1 - \frac{1}{x_n -y} \cdot \frac{f(x_n)}{f'(x_n)}| \end{eqnarray*}$

$\begin{eqnarray*} = |1 - \frac{1}{x_n -y} \cdot \frac{\frac{1}{k!} f^{(k)}(y) \cdot (x_n - y)^k + R_{k+1}(f) }{\frac{1}{(k-1)!} f^{(k)}(y) \cdot (x_n - y)^{k-1} + R_{k}(f') }| \end{eqnarray*}$

$\begin{eqnarray*} \longrightarrow 1 - \frac{1}{k} < 1 \end{eqnarray*}$

Letzteres dann für hinreichend große n (Grenzwertbetrachtung), was insgesamt (noch knapp) genau lineare Konvergenz ergibt.

Grüße Abakus smile

EDIT: Latex

02.07.2006, 14:49

tigerbine

Auf diesen Beitrag antworten »

RE: Konvergenzgeschwindigkeit beim Newton-Verfahren
Hallo Abakus,

Danke erstmal. Aber genau bei der Grenzwertbetrachtung hapert es bei mir. Kannst du mir den mal "im Detail" erklären.

Gruß,

tigerbine Wink

02.07.2006, 16:05

Abakus

Auf diesen Beitrag antworten »

RE: Konvergenzgeschwindigkeit beim Newton-Verfahren
Die hinteren Terme gehen aufgrund ihrer höheren Ordnung schneller gegen 0 als die vorne jeweils, das können wir durch Kürzen sehen:

$\begin{eqnarray*} ...~= |1 - \frac{1}{x_n -y} \cdot \frac{\frac{1}{k!} f^{(k)}(y) \cdot (x_n - y)^k + R_{k+1}(f) }{\frac{1}{(k-1)!} f^{(k)}(y) \cdot (x_n - y)^{k-1} + R_{k}(f') }| \end{eqnarray*}$

$\begin{eqnarray*} = |1 - \frac{1}{k} \cdot \frac{\frac{1}{(k-1)!} f^{(k)}(y) \cdot (x_n - y)^k + \frac{k}{(k+1)!} f^{(k+1)}(\xi) (x_n - y)^{k+1} }{\frac{1}{(k-1)!} f^{(k)}(y) \cdot (x_n - y)^k + \frac{1}{k!} f^{(k+1)}(\xi') (x_n - y)^{k+1} }| \end{eqnarray*}$

$\begin{eqnarray*} = |1 - \frac{1}{k} \cdot \frac{1 + \frac{1}{k+1} \frac{f^{(k+1)}(\xi)}{f^{(k)}(y)} (x_n - y) } {1 + \frac{1}{k} \frac{f^{(k+1)}(\xi')}{f^{(k)}(y)} (x_n - y) } |~\stackrel{n \rightarrow \infty}{\longrightarrow} 1 - \frac{1}{k} \end{eqnarray*}$

Dabei ist $\begin{eqnarray*} f^{(k)}(y) \ne 0 \end{eqnarray*}$ , sonst wäre y ja eine Nullstelle (k+1)-ster Ordnung oder mehr. Ferner wurde das Lagrangesche Restglied benutzt.

Wegen $\begin{eqnarray*} \lim_{n \rightarrow \infty} x_n = y \end{eqnarray*}$ folgt nun die Behauptung.

Grüße Abakus smile

EDIT: Latex

02.07.2006, 17:30

tigerbine

Auf diesen Beitrag antworten »

RE: Konvergenzgeschwindigkeit beim Newton-Verfahren
Und da liegt doch gerade der Hund begraben. Ich will ja zeigen, dass das Newton-Verfahren konvergiert.

Dies würde aus der Erfüllung der abschäztung der Linearen Konvergenzrate folgen. Also wenn gilt:

$\begin{eqnarray*} |x_{n+1} - y| \leq c|x_{n} - y| \end{eqnarray*}$ für 0 < c < 1

Deswegen wollte ich diese Abschätung zeigen, dann hätte ich die Konvergenz und die lineare Konvergenzgeschwindigkeit. Die Grenzwertbetrachtung (danach) würde mir dann wie schon von Dir angegeben die Konvergenzrate

$\begin{eqnarray*} a:=\lim_{n \to \infty} \frac{|x_{n+1}-y|}{|x_{n}-y|} = 1-\frac{1}{k} \end{eqnarray*}$

liefern.

Also, warum konvergiert die durch die Newton-Iterationsvorschrift erzeugte folge gegen y? unglücklich

02.07.2006, 18:38

Abakus

Auf diesen Beitrag antworten »

RE: Konvergenzgeschwindigkeit beim Newton-Verfahren
Die Frage nach der Konvergenzordnung setzt erstmal Konvergenz zwingend voraus.

Wenn du die Konvergenz zeigen möchtest, benötigst du dazu bestimmte Voraussetzungen. Die Iterationsfunktion hat etwa dann einen anziehenden Fixpunkt y, wenn ihre Ableitung in y betragsmäßig kleiner 1 ist. In diesem Fall existiert eine Umgebung U von y, in der das Newton-Verfahren (lokal) gegen y konvergiert.

Ansonsten können die Verhältnisse beliebig kompliziert sein. Insbesondere gibt es keine globale Konvergenz gegen irgendwelche Nullstellen von f.

Grüße Abakus smile

02.07.2006, 19:46

tigerbine

Auf diesen Beitrag antworten »

RE: Konvergenzgeschwindigkeit beim Newton-Verfahren

Zitat:

Original von Abakus
Die Frage nach der Konvergenzordnung setzt erstmal Konvergenz zwingend voraus.

Schön endlich jemand zu treffen der das auch so sieht Augenzwinkern

Die meisten Beweise zu dem Thema gehen nämlich immer nur auf die Konvergenzordnung ein. Daraus folgern sie dann die Konvergenz.

Für einfache Nullstellen denke ich habe ich genug Material für die Prüfung, welche Voraussetzungen die Funktion f erfüllt sein muss, damit Newoton gegen dieNnullstelle geht und mit welcher Geschwindigkeit.

Dabei soll immer lokale Konvergenz betrachtet werden. Also mich interessieren jetzt noch 2 Fragen:

Satz
Sei y eine einfache Nullstelle von f und f einmal stetig differenzierbar. Dann konvergiert das Newton verfahren lokal (super)linear gegen y.

Ich denke mal, in diesem Satz sind die Minimumvorrausstzungen an die Funktion f gestellt, damit wir z.b. überhaupt eine Kugel um y finden, so dass das Verfahren wohl definiert ist.

Erhöhen den Bedingungen führt dann zu quadratischer Konvergenzgeschwindigkeit, in ggf. kleinerer Kugel.

1) Wie sieht es nun bei Mehrfachen (k-fachen) Nullstellen aus? Wie würde dann die zusatzbedingungen (1Beispiel) lauten, damit die Folge konvergiert?

In einem Satz (ohne Beweis) stand, dass f dann2k-mal stetig diffbar sien müsste. Aber wie führe ich dann den Konvergenzbeweis?

2) Du hast ja schon die Betrachtung von Newton als Fixpunktiteration ins Spiel gebracht.Sei die Iterationsfunktin dann g(x):=x - f(x)/f'(x)

Wann kann man nun Banach auf g anwenden?

Es ist dann $\begin{eqnarray*} g'(x) = 1-\frac{f'(x)f'(x)-f(x)f''(x)}{[f'(x)]^{2}} =\frac{f(x)f''(x)}{[f'(x)]^{2}} \end{eqnarray*}$

Dann ist doch g(y) = 0 und es gibt eine Umgebung von y in der gilt |g'(x)| < 1. Durch entsprechende Fordungungen an f ist g' dann eine stetige Funktion und nimmt auf dem Kugel (Kompaktum) ein Minimum und Maximum an. Also |g'(x)| < |M| < 1.

Damit wäre die Bedingung der kontraktioseingenschaft erfüllt. Nur wie folgt dann die Selbstabbildung?

Schonmal herzlichen Dank,
tigerbine

02.07.2006, 21:32

Abakus

Auf diesen Beitrag antworten »

RE: Konvergenzgeschwindigkeit beim Newton-Verfahren

Zitat:

Original von tigerbine
1) Wie sieht es nun bei Mehrfachen (k-fachen) Nullstellen aus? Wie würde dann die zusatzbedingungen (1Beispiel) lauten, damit die Folge konvergiert?

In einem Satz (ohne Beweis) stand, dass f dann2k-mal stetig diffbar sien müsste. Aber wie führe ich dann den Konvergenzbeweis?

Zwischen ein- und mehrfachen Nullstellen sehe ich bei den Konvergenzbedingungen ad hoc keinen Unterschied. (Es braucht in beiden Fällen einen anziehenden Fixpunkt der Iterationsfunktion.)

Zitat:

2) Du hast ja schon die Betrachtung von Newton als Fixpunktiteration ins Spiel gebracht.Sei die Iterationsfunktin dann g(x):=x - f(x)/f'(x)

Wann kann man nun Banach auf g anwenden?

Es ist dann $\begin{eqnarray*} g'(x) = 1-\frac{f'(x)f'(x)-f(x)f''(x)}{[f'(x)]^{2}} =\frac{f(x)f''(x)}{[f'(x)]^{2}} \end{eqnarray*}$

Dann ist doch g(y) = 0 und es gibt eine Umgebung von y in der gilt |g'(x)| < 1. Durch entsprechende Fordungungen an f ist g' dann eine stetige Funktion und nimmt auf dem Kugel (Kompaktum) ein Minimum und Maximum an. Also |g'(x)| < |M| < 1.

Damit wäre die Bedingung der kontraktioseingenschaft erfüllt. Nur wie folgt dann die Selbstabbildung?

Für stetig differenzierbares g (definiert auf einem geeigneten, reellen Intervall I) hast du die Äquivalenz:

$\begin{eqnarray*} |g(x) - g(y)| \le k \cdot |x - y| \Leftrightarrow |g'(x)| \le k~(x, y \in I) \end{eqnarray*}$

Damit ergibt sich die Kontraktionseigenschaft des BFS aus einer Bedingung an die Ableitung. (hier geht beim Beweis u.a. der Mittelwertsatz ein)

Für die Selbstabbildungseigenschaft brauchst du eine lokale Variante des BFS, du musst zusätzlich eine "Kugelbedingung" dazunehmen:

Ist $\begin{eqnarray*} K_r(z) := \{x : ||x - z|| \le r\} \end{eqnarray*}$ , so müsstest du fordern:

$\begin{eqnarray*} ||z - g(z)|| \le r \cdot (1 - k) \end{eqnarray*}$

Genau ein Fixpunkt liegt dann innerhalb dieser Kugel, gegen die die Newton-Iterationsfolge bei beliebigem Startwert innerhalb dieser konvergiert.

Grüße Abakus smile

02.07.2006, 21:57

tigerbine

Auf diesen Beitrag antworten »

RE: Konvergenzgeschwindigkeit beim Newton-Verfahren
"Zwischen ein- und mehrfachen Nullstellen sehe ich bei den Konvergenzbedingungen ad hoc keinen Unterschied. (Es braucht in beiden Fällen einen anziehenden Fixpunkt der Iterationsfunktion.)"

naja, bei mehrfahcen Nullstellen ist zunächst mal die Iteration nicht wohl definiert, denn es ist ja f'(y) = 0. Es muss noch gezeigt werden, dass sich der Term "0"/"0" in wohlgefallen auflöst. Das könnte ja mit z.B. möglich L'Hospital sein.

Aber dann musste man erstmal zeigen, wie die "neue Vorschrift" aussieht" um dann ähnlich zur einfachen Nullstelle argumentieren zu können.

Zu 2)
Das mit der Kugelbedingung habe ich anders formuliert auch in meinem Buch stehen. Versuche diese Angebe jetzt mal zu verstehen. Denn aus der dortigen Formuliereng geht nicht eraus, dass es immer eine solche Kugel gibt.

Thanks so long,
tigerbine

02.07.2006, 22:10

Abakus

Auf diesen Beitrag antworten »

RE: Konvergenzgeschwindigkeit beim Newton-Verfahren

Zitat:

Original von tigerbine
naja, bei mehrfahcen Nullstellen ist zunächst mal die Iteration nicht wohl definiert, denn es ist ja f'(y) = 0. Es muss noch gezeigt werden, dass sich der Term "0"/"0" in wohlgefallen auflöst. Das könnte ja mit z.B. möglich L'Hospital sein.

f(y) = 0 prüfst du vorher ab (per Software-Programm stelle ich mir etwa eine Schritt für Schritt-Berechnung aller relevanten Werte vor). Wenn es gilt, hast du den Fixpunkt/die Nullstelle gefunden.

Grüße Abakus smile

02.07.2006, 22:13

tigerbine

Auf diesen Beitrag antworten »

RE: Konvergenzgeschwindigkeit beim Newton-Verfahren
Scusi,

aber das verstehe ich jetz nicht. Ich soll für einen allgemeinen Existenzbeweis mit dem Comupter eine nullstelle f(y)=0 ausrechnen?

unglücklich

02.07.2006, 22:53

Abakus

Auf diesen Beitrag antworten »

RE: Konvergenzgeschwindigkeit beim Newton-Verfahren

Zitat:

Original von tigerbine
aber das verstehe ich jetz nicht. Ich soll für einen allgemeinen Existenzbeweis mit dem Comupter eine nullstelle f(y)=0 ausrechnen? unglücklich

Nur wenn du das Verfahren programmierst bzw. schrittweise durchführst. Für den Existenzbeweis mag sein, dass du derartige Überlegungen brauchst; hier sollte dann $\begin{eqnarray*} \lim_{x \rightarrow y}\frac{f(x)}{f'(x)} = 0 \end{eqnarray*}$ sein.

Grüße Abakus smile

Neue Frage »

Antworten »

Konvergenzgeschwindigkeit beim Newton-Verfahren

Verwandte Themen