Nullstellensuche

 Wir haben gesehen, dass viele Anwendungen der Differentialrechnung die Bestimmung von Nullstellen erfordern. In expliziter Form ist dies nur für sehr einfache Funktionen möglich. Bereits für Polynome fünften Grades existiert keine allgemeine Lösungsformel. Wir müssen uns also in vielen Fällen mit Näherungsverfahren begnügen. Ist f : P → ℝ eine Funktion mit mindestens einer Nullstelle, so produziert ein derartiges Verfahren ausgehend von einem Startwert x₀  ∈  P eine Folge x₀, x₁, x₂, …, x_n, … von Elementen von P, die gegen eine Nullstelle der Funktion konvergiert, d. h. es gilt f (x*) = 0 für x* = lim_n x_n. Gute Verfahren konvergieren zudem schnell, d. h. die Abstände |x* − x_n| zwischen der Nullstelle und den Approximationen x_n konvergieren schnell gegen 0.

 Ein Verfahren, das ganz ohne Methoden der Differentialrechnung auskommt, beruht auf dem Zwischenwertsatz:

 Ist f : [ a, b ] → ℝ mit sgn(f (a)) ≠ sgn(f (b)), so liefert das folgende Verfahren eine Nullstelle von f. Zudem lässt es sich als konstruktiver Beweis des Zwischenwertsatzes lesen.

 In jedem Schritt halbieren wir also das betrachtete Intervall unter Wahrung der „guten Voraussetzung“ der unterschiedlichen Vorzeichen. Das Verfahren stoppt mit einer Nullstelle c_n = (x_n + y_n)/2 von f oder es produziert eine Folge (x_n, y_n) mit

lim_n x_n  =  lim_n y_n  =  lim_n c_n  =  x*  und  f (x*)  =  0.

Der Beweis von f (x*) = 0 benutzt die Stetigkeit von f: Die Funktionswerte f (x_n) haben alle das gleiche Vorzeichen s₁, die Funktionswerte f (y_n) alle das gleiche Vorzeichen s₂. Nach Konstruktion gilt s₁ ≠ s₂. Sei s₁ = −1 und s₂ = 1. Aus Stetigkeitsgründen gilt f (x*) = lim_n f (x_n) ≤ 0 und f (x*) = lim_n f (y_n) ≥ 0, sodass f (x*) = 0. Analoges gilt, wenn s₁ = 1 und s₂ = −1.

 Ein ganz anderes Verfahren − das berühmte Newton-Verfahren − der Nullstellensuche ergibt sich aus dem folgenden anschaulichen Satz:

 Das Newton-Verfahren findet die Nullstelle x* durch wiederholtes Anlegen von Tangenten. Ist x₀ > x*, so liegt die Tangente

g(x)  =  f (x₀)  +  f ′(x₀) (x − x₀)

von f an der Stelle x₀ aufgrund der Konvexität von f unterhalb von f. Sie schneidet die x-Achse an der Stelle

x₁  =  x₀  −  ^{f (x₀)}_{f ′(x1)}.

Es gilt x* < x₁ < x₀, sodass x₁ näher an x* liegt als x₀. Diese Beobachtung motiviert:

 Die Folge x₀, x₁, x₂, … wird auch als Newton-Iteration von f (zum Startwert x₀) bezeichnet. Man kann wie erwartet zeigen, dass sie im Fall x₀ = b streng monoton fallend und im Fall x₀ = a streng monoton steigend gegen die eindeutige Nullstelle x* von f konvergiert.

 Analoge Ergebnisse gelten für streng konkave Funktionen. Durch Übergang von f zu −f können wir aber immer Konvexität erreichen, ohne die Nullstelle zu verändern.

 Das Newton-Verfahren eignet sich insbesondere zur Berechnung von Wurzeln. Seien also k ≥ 1 und c > 0. Wir berechnen x*  =  ^k$\sqrt{\mathrm{c}}$. Hierzu wählen wir ein beliebiges b mit b > x*, etwa b = max(2, c). Dann ist x* die eindeutige Nullstelle der streng konvexen Funktion f : [ 0, b ] → ℝ mit

f (x)  =  x^k − c  für alle x  ∈  [ 0, b ].

Die Newton-Iteration von f zum Startwert x₀ = b ist gegeben durch

x_n + 1  =  x_n  −  $\frac{{\mathrm{x}}_{\mathrm{n}}^{\mathrm{k}}-\mathrm{c}}{\mathrm{k}{\mathrm{x}}_{\mathrm{n}}^{\mathrm{k}-1}}$  für alle n ≥ 0.

Es gilt x* = lim_n x_n. Speziell können wir eine Quadratwurzel x* = $\sqrt{\mathrm{c}}$ mit einem beliebigen Startwert x₀ > x* approximativ durch

xn + 1  =  xn  −  $\frac{{\mathrm{x}}_{\mathrm{n}}^2-\mathrm{c}}{2{\mathrm{x}}_{\mathrm{n}}}$  =  xn  +  c/xn2  für alle n ≥ 0

berechnen. Diese lange vor Newton bekannte Rekursion ist auch als Heron-Verfahren bekannt.

Ein Vergleich der beiden Verfahren

 Wir berechnen

$\sqrt{2}$  =  1, 41421 35623 73095 04880 16887 24209 …

mit Hilfe des Bisektions- und des Newton-Verfahrens. Wir verwenden wieder die Funktion f : [ 0, 2 ] → ℝ mit

f (x)  =  x² − 2.

Die beiden folgenden Tabellen zeigen die ersten Approximationen. Auf einen Kommentar dürfen wir verzichten…