Das Newton-Verfahren

Wir stellen ein klassisches Verfahren zur Bestimmung von Nullstellen für konvexe oder konkave Funktionen vor (Newton-Verfahren). Durch Übergang zu −f können wir uns auf konvexe Funktionen beschränken. Vorab beobachten wir:

Satz (Nullstellensatz für konvexe Funktionen)

Sei f : [ a, b ] → ℝ stetig und konvex mit f (a) < 0 < f (b). Dann besitzt f eine eindeutige Nullstelle p, und es gilt

f < 0 in [ a, p [, f > 0 in ] p, b ].

Ist f differenzierbar, so gilt f ′ > 0 in [ p, b ].

Eine analoge Aussage gilt, falls f (a) > 0 > f (b).

Beweis

Die Existenz einer Nullstelle folgt aus f (a) < 0 < f (b) und der Stetigkeit von f aus dem Zwischenwertsatz.

Zum Beweis der Eindeutigkeit sei p eine Nullstelle von f. Da f konvex ist, gilt f ≤ f_{a, p} auf [ a, p ]. Wegen f (a) < 0 und f (p) = 0 gilt also

f ≤ f_{a, p} < 0 auf [ a, p [.

Dies zeigt, dass links einer Nullstelle keine weitere Nullstelle liegen kann, woraus die Eindeutigkeit folgt.

Sei also p die eindeutige Nullstelle von f. Wegen f (b) > 0 ist f > 0 in ] p, b ], da sonst f eine weitere Nullstelle in ] p, b ] hätte. Analog ist f < 0 in [ a, p [.

Sei nun f differenzierbar. Da f konvex ist, gilt f ″ ≥ 0 und damit ist f ′ monoton steigend. Es genügt also, f ′(p) > 0 zu zeigen. Wäre aber

f ′(p) ≤ 0,

so wäre f ′ ≤ 0 auf [ a, p ] nach Monotonie von f ′. Dann wäre aber f monoton fallend auf [ a, p ], im Widerspruch zu f (a) < 0 und f (p) = 0.

Das Diagramm suggeriert im Fall der Differenzierbarkeit von f ein approximatives Verfahren zum Auffinden der eindeutigen Nullstelle p von f:

Wir beginnen mit einem beliebigen Startpunkt x₀ mit f (x₀) ≥ 0, etwa dem rechten Randpunkt x₀ = b. Nun legen wir die Tangente g₀ an f im Punkt (x₀, f (x₀)) an, und berechnen ihren Schnittpunkt x₁ mit der x-Achse. Ist f identisch mit g₀ auf [ x₁, x₀ ], so haben wir die Nullstelle p bereits gefunden. Andernfalls führt die Konvexität von f dazu, dass

p < x₁ < x₀,

und damit ist f (x₁) ≥ 0. Nun wiederholen wir das Verfahren mit der Bildung der Tangente g₁ an f im Punkt (x₁, f (x₁)) und erhalten so ein x₂ mit x₂ = p oder

p < x₂ < x₁ < x₀

usw. Die Schnittpunkte der Tangenten mit der x-Achse sind dabei leicht zu berechnen. Es gilt

g₀(x) = f (x₀) + f ′(x₀) (x − x₀) für alle x,

und damit ist

x₁ = „die eindeutige Nullstelle von g₀“ = x₀ − ^f (x₀)_{f ′(x₀)}.

Analog erhalten wir:

x₂ = „die eindeutige Nullstelle von g₁“ = x₁ − ^f (x₁)_{f ′(x₁)}.

Diese Überlegungen motivieren die folgende Definition:

Definition (Newton-Iteration)

Sei f : [ a, b ] → ℝ differenzierbar, und sei x₀  ∈  [ a, b ]. Wir definieren rekursiv

x_n + 1 = x_n − ^f (x_n)_{f ′(x_n)} für alle n, solange möglich.

Im Fall der Existenz heißt die Folge (x_n)_{n  ∈  ℕ} die Newton-Iteration von f für den Startpunkt x₀.

Der Ausdruck „solange möglich“ beinhaltet zweierlei: Es muss f ′(x_n) ≠ 0 gelten und x_n muss im Definitionsbereich von f liegen. Unter diesen Voraussetzungen ist x_n + 1 definiert. Andernfalls bricht die Rekursion ab.

Wir zeigen nun:

Satz (Konvergenzsatz für die Newton-Iteration für konvexe Funktionen)

Sei f : [ a, b ] → ℝ stetig differenzierbar und konvex mit f (a) < 0 < f (b).

Sei p die eindeutige Nullstelle von f, und sei x₀ ein Punkt in [ a, b ] mit

(i)	f (x₀) ≥ 0 oder

(ii)	f (x₀) < 0, f ′(x₀) > 0, x₁ = x₀ − f (x₀)/f ′(x₀) ≤ b.

Dann existiert die Newton-Iteration (x_n)_{n  ∈  ℕ} von f für den Startpunkt x₀ und es gilt lim_n x_n = p. Ist x₀ ≥ p, so ist (x_n)_{n  ∈  ℕ} monoton fallend. Andernfalls ist x₁ ≥ p und (x_n)_n ≥ 1 monoton fallend.

Eine analoge Aussage gilt, falls f (a) > 0 > f (b).

Beweis

Wir nehmen zunächst (i) an, sodass x₀ ≥ p. Die Aussage ist klar für x₀ = p, denn dann gilt x_n = x₀ = p für alle n.

Sei also x₀ > p. Sei g₀ die Tangente an f im Punkt (x₀, f (x₀)). Nach dem Tangentenkriterium gilt g ≤ f, und damit gilt p ≤ x₁ ≤ x₀ für die eindeutige Nullstelle x₁ der Geraden g₀. Induktiv zeigt diese Überlegung, dass die Newton-Iteration (x_n)_{n  ∈  ℕ} existiert und dass

p ≤ … ≤ x_n ≤ … ≤ x₁ ≤ x₀.

Sei p* = lim_n x_n = inf_n x_n. Da f und f ′ stetig sind, gilt

p* = lim_n x_n + 1 = lim_n (x_n − ^f (x_n)_{f ′(x_n)}) = p* − ^f (p*)_f ′(p*).

Folglich ist f (p*) = 0. Da f nur eine Nullstelle besitzt, ist p = p*.

Gilt (ii), so gilt g₀ ≤ f für die Tangente g₀ an f im Punkt (x₀, f (x₀)). Also gilt x₁ ≥ p für den Schnittpunkt x₁ < b von g₀ mit der x-Achse. Damit verläuft die Newton-Iteration ab x₁ wie für (i).

Der Leser beachte, dass die Konvergenz im Fall (i) streng monoton ist, solange x_n ≠ p gilt. Dies ist immer der Fall, wenn für alle ε > 0 gilt, dass f auf dem Intervall [ p, p + ε ] keine Gerade ist.

Die Newton-Iteration konvergiert im Allgemeinen sehr schnell. Mit Hilfe des Satzes von Taylor werden wir eine Abschätzung für den Fehler x_n − p nachreichen können.

Das Verfahren lässt sich insbesondere zur effektiven Berechnung von Wurzeln einsetzen:

Korollar (Wurzelberechnung mit dem Newton-Verfahren)

Seien k  ∈  ℕ*, a > 0, und sei f : [ 0, ∞ [ → ℝ die Funktion mit

f (x) = x^k − a für alle x  ∈  [ 0, ∞ [.

Dann konvergiert die Newton-Iteration von f für jedes x₀ > 0 gegen ^k $\sqrt{a}$ .

Beweis

Für b hinreichend groß erfüllt f | [ 0, b ] die Voraussetzungen des Konvergenzsatzes.

Es gilt also ^k $\sqrt{a}$ = lim_n x_n mit einem beliebigen x₀ > 0 und der Rekursion

x_n + 1 = x_n − $\frac{x_{n}^{k} - a}{k x_{n}^{k - 1}}$ für alle n.

Für den Fall k = 2 der Berechnung von Quadratwurzeln erhalten wir

x_n + 1 = x_n − $\frac{x_{n}^{2} - a}{2 x_{n}}$ = ^{x_n + a/x_n}₂ für alle n.

Damit stimmt die Newton-Iteration für k = 2 und x₀ = 0 mit der Heron-Folge für a überein (vgl. 2.1). Eine geometrische Interpretation diskutieren wir in den Ergänzungen E11.

Beispiel

Sei f : [ 0, ∞ [ → ℝ mit f (x) = x² − x − 1. Für die Newton-Iteration gilt

x_n + 1 = x_n − ^{x_n² − x_n − 1}_{2x_n − 1} = ^x_n² + 1_{2x_n − 1}.

Für den Startwert x₀ = 2 erhalten wir

x₁ = ⁵₃, x₂ = ³⁴₂₁, x₃ = ¹⁵⁹⁷₉₈₇ = 1,6180344…

Es gilt f (x) = 0 genau dann, wenn x = 1 + 1/x. Die Werte x_n approximieren

Φ = ( $\sqrt{5}$ + 1)/2 = 1,6180339887…(Goldener Schnitt)