Konvergenz Newton-Verfahren

30.06.2014, 16:06

AntonDieAmeise

Konvergenz Newton-Verfahren

Meine Frage:
Konvergiert das Newton Verfahren mit dem Startwert $\begin{eqnarray*} x_0 = 1 \end{eqnarray*}$
für folgende drei Funktionen? Wenn ja wie schnell?

$\begin{eqnarray*} f(x) = x^2 , g(x)=5-4x, h(x) =(5-4x)x^4 \end{eqnarray*}$

Wie können Sie für die Funktion f(x) die quadratische Konvergenz des Newton-Verfahrens sicherstellen?

Meine Ideen:
bei f(x) habe ich eine doppelte Nullstelle also lineare Konvergenz (oder Superlinear?). Bei g(x) habe ich eine einfache Nullstelle, also habe ich quadratische Konvergenz (da die Funktion linear, bin ich sogar in einem Iterationsschritt fertig). Bei h(x) habe ich sowohl eine einfache Nullstelle als auch eine mehrfache, Konvergenz ist also einmal quadratisch und einmal linear.
Wie zeige ich am besten, dass die Verfahren bei dem gegebenen Startwert auch tatsächlich konvergieren? Newton garantiert ja nur lokale, aber keine globale Konvergenz.
Zur zweiten Aufgabe: wenn ich bei Aufgabe f(x) quadratische Konvergenz will, wie stelle ich das an? Das einzige was mir einfällt ist, die Funktion zu zerlegen in $\begin{eqnarray*} x*x \end{eqnarray*}$ und dann nur die Nullstelle für $\begin{eqnarray*} f_2(x)=x \end{eqnarray*}$ zu bestimmen. Gibt es noch eine andere Möglichkeit das zu lösen?

01.07.2014, 08:44

Ändru

Auf diesen Beitrag antworten »

RE: Konvergenz Newton-Verfahren
Hi,

zu a.)

Hast du denn schonmal ein oder zwei Stellen gerechnet? Wenn nein, dann mach das mal und du wirst die Frage ganz schnell beantworten koennen.
Hast du denn schonmal was vom gedaempften Newton-Verfahren gehoert? Damit laesst sich die Konvergenz "retten"

zu b.)

Deine Antwort ist richtig aber deine Begruendung nicht ganz... Was ist denn das Kriterium dass das NV quadratisch konv.?

zu c.)
Die Richtung ist schonmal richtig aber deine Begruendung nicht.... rechne doch einfach mal ein paar Stellen zum Startwert aus bzw. zu den Nullstellen.

Allg. Konvergenz)
Was ist denn das allgmeine Kriterium damit eine Fixpunktiteration ueberhaupt konvergiert?

Gruesse

01.07.2014, 18:39

AntonDieAmeise

Auf diesen Beitrag antworten »

RE: Konvergenz Newton-Verfahren

Zitat:

Original von Ändru
Hi,

zu a.)

Hast du denn schonmal ein oder zwei Stellen gerechnet? Wenn nein, dann mach das mal und du wirst die Frage ganz schnell beantworten koennen.
Hier habe ich also lineare Konvergenz. Kann ich das auch ohne Nachrechnen erkennen?

Hast du denn schonmal was vom gedaempften Newton-Verfahren gehoert? Damit laesst sich die Konvergenz "retten"
Das haben wir mal kurz erwähnt, werde es mir noch mal genauer anschauen, aber danke für den Tipp.

zu b.)

Deine Antwort ist richtig aber deine Begruendung nicht ganz... Was ist denn das Kriterium dass das NV quadratisch konv.?
Wir haben nur gelernt, dass das Newtonverfahren für einfache Nullstellen (für geeignete Startwerte) quadratisch konvergiert. Muss ich hier noch nachweisen, dass der Startwert geeignet ist? Wenn ja wie mache ich das? )

zu c.)
Die Richtung ist schonmal richtig aber deine Begruendung nicht.... rechne doch einfach mal ein paar Stellen zum Startwert aus bzw. zu den Nullstellen.
Hier komme ich immer näher an die vier-fache Nullstelle .Die Konvergenz ist aber ziemlich schlecht, nichtmal linear. Kann das sein?Wie nennt man dann die Art der Konvergenz

Allg. Konvergenz)
Was ist denn das allgmeine Kriterium damit eine Fixpunktiteration ueberhaupt konvergiert?
Die Ableitung der Fixpunktfunktion muss am Fixpunkt betraglich kleiner eins sein?

Gruesse

Wäre euch für weitere Tipps echt dankbar verwirrt

03.07.2014, 08:25

Ändru

Auf diesen Beitrag antworten »

Hi,

zu a.) Ja das kannst du ist aber im allgemeinen sehr schwer es gilt doch:

$\begin{eqnarray*} \|x_{k+1} - x^*\| \leq c \| x_k - x^*\|^p \end{eqnarray*}$

wobei $\begin{eqnarray*} x^* \end{eqnarray*}$ der Fikpunkt ist. Nun stellt sich ja die Frage was $\begin{eqnarray*} c \end{eqnarray*}$ ist welche werte die Konstante annehmen kann. $\begin{eqnarray*} p \end{eqnarray*}$ beschreibt die Konvergenzordnung. Hast du denn eine Idee was $\begin{eqnarray*} c \end{eqnarray*}$ sein koennte? Denk mal an an die Stetigkeit!
Ang. wir kennen $\begin{eqnarray*} c \end{eqnarray*}$ und kennen auch $\begin{eqnarray*} x^* \end{eqnarray*}$ , dann brauchst ja nur noch die $\begin{eqnarray*} x_k \end{eqnarray*}$ und schon bist du fertig. Du kennst ja (zum Glueck!) den Fixpunkt, also kannst du und solltest auch die information verwenden.

zu b.) Dein NV konvergiert genau dann quadratisch wenn gilt, dass

$\begin{eqnarray*} \| \phi'(x^*) \| = 0 \end{eqnarray*}$

ist. Nun kannst du dir ueberlegen was das denn heisst.

zu c.) du hast immer lineare Konvergenz, das nennt man halt so, auch wenn sie etwas schlechter ist in dem Sinn, dass du nicht nach jedem Schritt eine Stelle bzgl. der Genauigkeit dazugewinnst.

allg. )
Richtig! es musst gelten:

$\begin{eqnarray*} \| \phi'(x) \| < 1 \end{eqnarray*}$

Nun denk mal nach, was passiert wenn du zeigen kannst, dass die Eigenschaft immer gilt. Wie nennt man diese Eigenschaft (ist die gleiche Frage wie bei a.) )?

Gruesse

03.07.2014, 08:43

Ändru

Auf diesen Beitrag antworten »

Nachtrag:

Es gibt noch ein Lemma das besagt wenn,

$\begin{eqnarray*} \lim_{k \to \infty} \frac{x_{k+1} - x_k}{x^* - x_k} = 1 \end{eqnarray*}$

ist, dann ist die Konvergenzordnung $\begin{eqnarray*} p > 1 \end{eqnarray*}$ .

Wenn

$\begin{eqnarray*} \lim_{k \to \infty} \frac{x^* - x_{k+1}}{x^* - x_k} = c \in (-1,1), c \neq 0 \end{eqnarray*}$

ist, dann ist $\begin{eqnarray*} p = 1 \end{eqnarray*}$ .

Hinweis: mit $\begin{eqnarray*} x_k \end{eqnarray*}$ ist die Folge gemeint!

Neue Frage »

Antworten »

Konvergenz Newton-Verfahren

Verwandte Themen