Approximation von Nullstellen:Newtonverfahren

Inhalt:

Das Problem Allgemeine Iterationsverfahren

Anschauliche Deutung Konvergenz Kontraktionssatz Konvergenzgüte Quadratische Konvergenz Startwert x(0)

Newton-Verfahren Newtonsche Iterationsverfahren Geometrische Deutung Mehrfache Nullstellen

Das Problem

in einem normiertem Vektorraum (X,║∙║) eine Lösung der Operatorgleichung F(x)=0 zu finden.F Abbildung F: D →X, D X;Nullstelle ξ von F

Nur in seltensten Fällen lässt sich Lösung in endlich vielen Schritten bestimmen.

Allgemeine Iterationsverfahren

Sei x R. Für die Abbildung F: D→R betrachten wir

x = F(x)zu deren Lösung der Iterationssatz

x(k+1) = F(x(k)), k N,

mit vorgegebenem Anfangselement x(0) gebildet

wird.

Allgemeine Iterationsverfahren

Zur Betrachtung des Iterationssatzes nehmen wir die Existenz einer Lösung ξ der Gleichung x = F(x) an.

Später:

Frage der Existenz wird gleichzeitig mit der Frage der Konvergenz des Iterationsverfahrens beantwortet.

Allgemeine Iterationsverfahren

Anschauliche Deutung

F C[a,b]

a ξ b

Beispiel1:

Alternierend konvergent

x(0) x(2) x(3) x(1)

Allgemeine Iterationsverfahren

Anschauliche Deutung

F C[a,b]

a ξ b

Beispiel2:

Divergent

x(0)x(2) x(1)

Allgemeine Iterationsverfahren

Konvergenz

Iteration konvergiert gegen Lösung ξ,

falls

limk→∞ x(k) = ξ

gilt.

Allgemeine Iterationsverfahren

Hinreichende Konvergenzaussage

nehmen an, dass (X,║∙║) ein Banachraum und F: X→X,und Operator F ist kontrahierend d.h.

║F(x) – F(z)║≤α║x - z║

mit α<1 für alle Elemente x,z X.

Allgemeine Iterationsverfahren

Kontraktionssatz

Ist F: X→X eine kontrahierende Abbildung, so besitzt sie genau einen Fixpunkt

ξ = F ξ.

Die Iteration konvergiert bei beliebigem x(0) gegen diesen Fixpunkt.

Allgemeine Iterationsverfahren

Lokale und globale KonvergenzKonvergiert Folge für Anfangselemente x(0)

aus Umgebung U D des Fixpunktes ξ, nennen wir die Iteration lokal konvergent. (Abbildung F nur auf U kontrahierend)

Kann x(0) in gesamt D beliebig gewählt werden, heißt sie global konvergent.

Allgemeine Iterationsverfahren

KonvergenzgüteBetrachten Folge (δ(k))kN der Abweichung

δ(k) := x(k) – ξMittelwertsatz liefert

δ(k+1) = F(x(k)) – ξ = F‘(ξ + θδ(k)) δ(k) : 0 < θ < 1Wenn δ(k) 0, dann

limk→∞ δ(k+1)/δ(k) = F‘(ξ)Wenn F‘(x) 0, dann lineare Konvergenz

Allgemeine Iterationsverfahren

Quadratische Konvergenz jedoch wenn F‘(x) = 0, dann Konvergenz

superlinear

mindestens quadratische Konvergenzδ(k+1) = F(x(k)) – ξ = F‘‘(ξ + θδ(k))/2 * (δ(k))2

mit 0 < θ < 1 limk→∞ δ(k+1)/(δ(k))2 = F‘‘(ξ)/2

Allgemeine Iterationsverfahren

Startwert x(0)

F muss kontrahierend sein, um gegen Fixpunkt zu konvergieren.

Also muss ||F‘‘(ξ)/2|| < 1 sein. Intervall [a,b] wird so lange verkleinert bis

maxx[a,b] {||F‘‘(x)/2||} < 1Dann kann x(0) beliebig in Intervall gewählt

werden.

Newton-Verfahren

Newtonsche IterationsverfahrenAufgabe:

Lösung der Gleichung

f(x) = 0 für f C1[a,b]

berechnen.

Newton-Verfahren

Newtonsche IterationsverfahrenBetrachten g(x)f(x) = 0 mit g C1[a,b]

Annahme g(x) ≠ 0 für x [a,b], dann gilt,

dass g(x)f(x) gleiche Nullstelle hat wie f(x)Entsprechende Fixpunktgleichung

x = x + g(x)f(x) =: F(x)müssen g so bestimmen, dass F‘(ξ)=0

Newton-Verfahren

Newtonsche IterationsverfahrenF‘(x) = 1 + g‘(x)f(x) + g(x)f‘(x)Da f‘(ξ) ≠ 0 und f(ξ) = 0 muss

g(ξ) = -(f‘(ξ))-1,

also wählen wir

g(x) = -(f‘(x))-1.

Newton-Verfahren

Newtonsche Iterationsverfahren

x(k+1) = x(k) – (f‘(x(k))) -1f(x(k))

für f C1[a,b] superlinear konvergent in Umgebung von ξ

Newton-Verfahren

Geometrische Deutung f C1[a,b], x(k) Nährungswert für Lösung ξ der

Gleichung f(x) = 0

ξ X(k)X(k+1)X(k+2)

Newton-Verfahren

Geometrische DeutungTangente an f im Punkt (x(k),f(x(k)))

y = f(x(k))+f‘(x(k))(x-x(k))

Schnittstelle x(k+1) der Tangente mit Y-Achse

x(k+1) := x(k) – f(x(k))/ f‘(x(k))

Newton-Verfahren

Startwert x(0)

ξ X(0) X(2)X(1)

Newton-Verfahren

Mehrfache Nullstellen f Ci[a,b], i>1, ξ [a,b] ist i-fache Nullstelle f(ξ)=f‘(ξ)=f‘‘(ξ)=…=f(i-1)(ξ)=0 und f(i)(ξ)≠0 F ist in Umgebung um ξ stetig und diffbar mit

F‘(ξ) = 1-1/iDa i>1 gilt 0<F‘(ξ)<1 also

lokale lineare Konvergenz