Konvergenzbetrachtungen zum Newton-Verfahren

Das Newton-Verfahren ist ein so genanntes lokal konvergentes Verfahren. Konvergenz der in der Newton-Iteration erzeugten Folge zu einer Nullstelle ist also nur garantiert, wenn der Startwert, d.h. das 00-te Glied der Folge, schon "ausreichend nahe" an der Nullstelle liegt. Ist der Startwert zu weit weg, kann alles passieren:
  • Die Folge divergiert, der Abstand zur Nullstelle wächst über alle Grenzen.
  • Die Folge divergiert, bleibt aber beschränkt. Sie kann z.B. periodisch werden, d.h. endlich viele Punkte wechseln sich in immer derselben Reihenfolge ab. Man sagt auch, dass die Folge oszilliert.
  • Die Folge konvergiert trotz der Distanz zur Nullstelle, kann jedoch, falls die Funktion mehrere Nullstellen hat, gegen eine andere als die gewünschte Nullstelle (falls man weiß, welche man will) konvergieren.
Newtroot_1_0_0_m1.png
Newton-Fraktal für p(z)=z3−1p(z)=z^3-1
Ist der Startwert x0 x_0\, so gewählt, dass das Newton-Verfahren konvergiert, so ist die Konvergenz allerdings quadratisch, also mit der Konvergenzordnung 2 (falls die Ableitung an der Nullstelle nicht verschwindet). Die Menge der Startpunkte, für die das Newton-Verfahren gegen eine bestimmte Nullstelle konvergiert, bildet den Einzugsbereich dieser Nullstelle. Färbt man für eine Polynomfunktion, mit reellen oder komplexen Koeffizienten, die Einzugsbereiche verschiedener Nullstellen in der komplexen Ebene verschieden ein, so ergibt sich ein Newton-Fraktal. In diesem ist zu erkennen, dass die Einzugsbereiche Bassins, d.h. Kreisscheiben um die Nullstellen enthalten, aus welchen heraus die Newton-Iteration stabil gegen die Nullstelle im Zentrum konvergiert. Aber es ist auch zu erkennen, dass die Ränder der Einzugsbereiche "ausgefranst" sind, sie haben sogar eine fraktale Struktur. Geringe Abweichungen im Startpunkt können also zu verschiedenen Nullstellen führen. Falls es jedoch im Intervall I=]a;b[ I=]a;b[\, genau eine Nullstelle gibt, in I I\, durchweg f ′>0f\, \prime>0 sowie f ′′<0f\, {\prime\prime}<0 gilt und der Startwert x0∈I=]a;b[x_0\in I=]a;b[ links von der Nullstelle ξ∈I \xi\in I\, gewählt wird, dann konvergiert das Newton-Verfahren stets, und zwar streng monoton wachsend (siehe [!Abbildung] unten bzw. die Tabelle oben ab n=1n=1).
 
 

Beispiele für Nicht-Konvergenz

Oszillierendes Verhalten

Oszillierendes Verhalten ergibt sich für das Polynom f(x):=x3−2x+2 f(x):=x^3-2x+2 mit f ′(x)=3x2−2 f\, \prime(x)=3x^2-2 . Der Punkt x=0 x=0 mit f(0)=2 f(0)=2 und f ′(0)=−2 f\, \prime(0)=-2 wird durch den Newton-Operator auf den Punkt N(0)=0−2/(−2)=1 N(0)=0-2/(-2)=1 abgebildet, der Punkt x=1 x=1 wiederum, mit f(1)=1 f(1)=1 und f ′(1)=1 f\, \prime(1)=1 , wird auf N(1)=1−1/1=0 N(1)=1-1/1=0 abgebildet, so dass die Newton-Iteration mit einem dieser Punkte als Startwert eine periodische Folge ergibt, diese beiden Punkte wechseln sich zyklisch ab. Des Weiteren ist dieser [!Zyklus] stabil, er bildet einen Attraktor der Newton-Iteration. Das bedeutet, es gibt eine kleine Umgebung beider Punkte, so dass Startpunkte in dieser Umgebung gegen den Zyklus konvergieren und somit je einen der Punkte 00 und 11 als Grenzwert der Teilfolge mit geradem Index und der mit ungeradem Index haben.

Divergenz

Divergenz bzw. beliebig weites Entfernen vom Startpunkt ergibt sich für f(x)=sin⁡(x) f(x)=\sin(x) mit f′(x)=cos⁡(x) f^\prime(x)=\cos(x) und N(x)=x−tan⁡(x) N(x)=x-\tan(x) . Es gibt eine Stelle x0∈[−π/2,0] x_0 \isin\lbrack -\pi /2,0 \rbrack mit tan⁡(x0)=−2π\tan(x_0)=-2\pi . Man überzeugt sich, dass dann xn=x0+2πn x_n =x_0+2\pi n gilt. Dieses Verhalten ist nicht stabil, denn bei leichter Variation des Anfangswertes, wie sie zum Beispiel durch die numerische Berechnung entsteht, entfernt sich die Newton-Iteration immer weiter von der idealen divergierenden Folge. Selbst bei schließlicher Konvergenz wird die gefundene Nullstelle sehr weit vom Startwert entfernt sein.

Lokale quadratische Konvergenz

Sei f f eine zweimal stetig differenzierbare reelle Funktion und a a eine Nullstelle von f f , in welcher die Ableitung keine Nullstelle hat. Das bedeutet, dass der Graph der Funktion transversal, d.h. nicht-berührend, die xx-Achse schneidet. Sei xx ein Punkt nahe bei aa. Dann kann die Taylor-Formel zweiten Grades (mit Restglied)
0=f(a)=f(x)+f′(x)(a−x)+12f′′(ξ)(a−x)20=f(a)=f(x)+f'(x)(a-x)+\dfrac12 f''(\xi)(a-x)^2 (ξ \xi liegt zwischen xx und aa),
nach der Differenz (x−a)(x-a) umgestellt werden,
x−a=f(x)f′(x)+f′′(ξ)2 f′(x)(x−a)2x-a=\dfrac{f(x)}{f'(x)}+\dfrac{f''(\xi)}{2\,f'(x)}(x-a)^2.
Es wird nun so umgestellt, dass der Newton-Operator auf der rechten Seite erscheint,
Nf(x)−a=x−f(x)f′(x)−a=f′′(ξ)2 f′(x)(x−a)2N_f(x)-a=x-\dfrac{f(x)}{f'(x)}-a=\dfrac{f''(\xi)}{2\,f'(x)}(x-a)^2.
Seien II ein Intervall um aa ohne Nullstelle der Ableitung f ′(x)f\, '(x) und m1=min⁡x∈I∣f´(x)∣m_1=\min_{x\in I}|f´(x)| sowie M2=max⁡x∈I∣f′′(x)∣M_2=\max_{x\in I}|f''(x)| Schranken der Ableitungen von ff. Dann folgt für alle x∈Ix\in I die Abschätzung
∣Nf(x)−a∣≤M22m1∣x−a∣2\left|N_f(x)-a\right|\le\dfrac{M_2}{2m_1}|x-a|^2.
Mit K=M22m1K=\dfrac{M_2}{2m_1} sei der konstante Faktor bezeichnet. In jedem Schritt nn der Newtoniteration wird die Größe K ∣xn−a∣K\,|x_n-a| kleiner sein als das Quadrat derselben Größe im vorhergehenden Schritt (n−1)(n-1). Nach vollständiger Induktion ergibt sich
K ∣xn−a∣≤(K ∣x0−a∣)2nK\,|x_n-a|\le (K\,|x_0-a|)^{2^n}.
Kann also für den Startpunkt der Iteration die Abschätzung K ∣x0−a∣<1 K\,|x_0-a |<1 garantiert werden, z.B. indem die Intervallänge von II kleiner als 1/K1/K ist, so konvergiert die Folge (xn)(x_n) der Newton-Iteration gegen die Nullstelle aa, denn die Folge (K ∣xn−a∣)(K\,|x_n-a|) ist nach der angegebenen Abschätzung eine Nullfolge. Die Verkürzung des Intervalls kann durch einige Iterationen eines langsameren Verfahrens zur Nullstelleneinschränkung erreicht werden, z.B. des Bisektionsverfahrens oder der Regula falsi.
Die aus dieser Abschätzungen folgende Konvergenzgeschwindigkeit wird als quadratisch bezeichnet, die (logarithmische) Genauigkeit bzw. Anzahl gültiger Stellen verdoppelt sich in jedem Schritt. Die Abschätzung des Abstands ∣xn−a∣ |x_n -a| zur Nullstelle wird oft linear in ∣x0−a∣ | x_0- a| angegeben, so gilt z.B.
  • ∣xn−a∣≤(12)2n−1⋅∣x0−a∣|x_n-a|\le \left(\dfrac12\right)^{2^n-1}\cdot |x_0-a|, falls die Länge des Intervalls II kleiner als 12K\dfrac{1}{2K} ist. Dies ergibt eine Abschätzung der gültigen Stellen im Binärsystem.
  • ∣xn−a∣≤(110)2n−1⋅∣x0−a∣|x_n-a|\le \left(\dfrac1{10}\right)^{2^n-1}\cdot |x_0-a|, falls die Länge des Intervalls II kleiner als 110K\dfrac{1}{10K} ist, d.h. nahe genug an der Nullstelle ergibt sich eine Verdopplung der Dezimalstellen in jedem Schritt.

Bemerkungen

  • Der lokale Konvergenzbeweis kann auch auf gleiche Weise im mehrdimensionalen Fall geführt werden, allerdings ist er dann technisch etwas schwieriger, da mit zwei- und dreistufigen Tensoren für die erste bzw. zweite Ableitung gearbeitet wird. Im wesentlichen ist die Konstante KK durch K=12 sup⁡x∈U∥f′(x)−1∥(1,1) sup⁡x∈U∥f´´(x)∥(1,2)K=\dfrac12\,\sup_{x\in U}\|f'(x)^{-1}\|_{(1,1)}\,\sup_{x\in U}\|f´´(x)\|_{(1,2)} zu ersetzen, mit geeigneten induzierten Operatornormen.
  • Der lokale Konvergenzbeweis setzt voraus, dass ein eine Nullstelle enthaltendes Intervall bekannt ist. Aus seinem Beweis ergibt sich aber keine Möglichkeit, dies schnell zu testen. Ein Konvergenzbeweis, auch hierfür ein Kriterium liefert, wurde zuerst von Leonid Kantorowitsch geführt und ist als Satz von Kantorowitsch bekannt.
  • Um einen geeigneten Startpunkt zu finden, verwendet man gelegentlich andere ("gröbere") Verfahren. Beispielsweise kann man mit dem Gradientenverfahren eine ungefähre Lösung ermitteln und diese dann mit dem Newton-Verfahren verfeinern.
  • Bei unbekanntem Startpunkt kann man mittels einer Homotopie die Funktion f f , von der man eine Nullstelle sucht, zu einer einfacheren Funktion g g deformieren, von der (mindestens) eine Nullstelle bekannt ist. Man durchläuft dann die Deformation rückwärts in Form einer endlichen Folge sich nur "wenig" unterscheidender Funktionen. Von der ersten Funktion g g kennt man eine Nullstelle. Als Startwert der Newton-Iteration zur gerade aktuellen Funktion der Folge verwendet man die Näherung einer Nullstelle der in der Folge vorhergehenden Funktion.
Als Beispiel mag die "Flutungshomotopie" dienen: mit einem willkürlichen z z bilden wir die Ausgangsfunktion g(x)=f0(x):=f(x)−f(z) g(x)= f_0(x):= f(x)-f(z) mit bekannter Nullstelle z z . Wir haben den "Wasserspiegel" vom "Nullpegel" auf die Höhe f(z) f(z) geflutet. Nun senken wir schrittweise den Wasserstand, fn(x):=f(x)−(f(z)−n⋅h⋅f(z)), h=1/N, n=1…N f_n(x):= f(x)-(f(z)-n\cdot h\cdot f(z)),\, h=1/N ,\, n=1\dots N . In jedem Schritt wird eine Näherung ξ(n) \xi^{(n)} einer Nullstelle bestimmt, wobei x0:=ξ(n−1) x_0 := \xi^{(n-1)} gesetzt wird. Es ist fN=f f_N=f und somit ξ(N) \xi ^{(N)} eine der gesuchten Näherungslösungen.

Nicht etwa, daß bei größerer Verbreitung des Einblickes in die Methode der Mathematik notwendigerweise viel mehr Kluges gesagt würde als heute, aber es würde sicher viel weniger Unkluges gesagt.

Karl Menger

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Newton-Verfahren aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Nichtlineare Gleichungssysteme