5.3.6.1 Newton-Intervallverfahren

Das Newtonsche (Näherungs-)Verfahren aus der Numerik dient zur numerischen Bestimmung von Nullstellen nichtlinearer Gleichungen. Die Aufgabe, eine reelle Gleichung mit einer Unbekannten zu lösen, ist äquivalent mit dem Problem, die Nullstellen einer Funktion zu berechnen. Solch eine Gleichung kann deshalb immer in der Form $f(x)=0$ geschrieben werden. Wenn die Funktion $f$ differenzierbar ist, gestattet es das Newton-Verfahren in vielen Fällen, die Nullstellen sehr schnell und mit hoher Präzision zu ermitteln (vgl. Embacher und Oberhuemer, 2003).

Angefangen mit einem Schätzwert $x_0$ für die zu berechnende Nullstelle, werden iterativ weitere Näherungswerte $x_1,x_2,\ldots$ durch Einsetzen in die folgende, rekursive Formel berechnet (vgl. Bronstein et al., 1996, S. 1137):

$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$

Die grafische Interpretation des Verfahrens ist in Abbildung 5.24 zu sehen. Beginnend mit dem ersten Schätzwert $x_0$ wird eine Tangente durch den Punkt P an den Graphen von f gelegt. Die Tangente schneidet die x-Achse in $x_1$, was in diesem Fall bereits eine deutliche Verbesserung darstellt. Für $x_2$ wird dasselbe Verfahren auf $x_1$ angewendet usw. Bereits nach wenigen Iterationen liegen häufig sehr genaue Näherungswerte vor.

Abbildung 5.24: Newton-Näherungsverfahren zur Nullstellenberechnung (vgl. Embacher und Oberhuemer, 2003)

Dieses Verfahren kann für die Intervallrechnung erweitert werden, wie von Krawczyk (1969, S. 192 ff.) bzw. Moore (1969, S. 84 ff.) dargelegt wird. Stark vereinfacht geschieht dies, indem für ein Intervall $X=[a,b]$ und $m(X)=$ der Mittelpunkt von X, die Intervallfunktion N (für ,,Newton``) definiert wird:

$$N(X)=m(X)-\frac{F(m(X))}{F'(X)}$$

Beginnend mit einem Ausgangsintervall $X_0$ wird durch

$$X_{n+1}=N(X_n) \cap X_n$$

die konvergierende Intervallfolge $X_1,X_2,\ldots$ berechnet. Bei jedem Iterationsschritt verkleinert sich dieser Bereich, wodurch, wie bei der reellen Version des Newton-Verfahrens, eine Annäherung an eine Nullstelle berechnet wird. Benhamou et al. (1994a) nennen diese Approximation ,,Quasi-Nullstelle`` und bezeichnen damit, dass eine Quasi-Nullstelle aufgrund der begrenzten Fließkomma-Präzision nicht von einer Nullstelle unterschieden werden kann (vgl. Benhamou et al., 1994a, S. 131).

Abbildung 5.25: Bestimmung der äußersten Quasi-Nullstellen (vgl. Benhamou et al., 1999b, S. 14)

Um Box-Konsistenz zu erreichen, muss jeweils die äußerste linke und rechte Quasi-Nullstelle berechnet werden (siehe Abbildung 5.25). Weil das Newton-Intervallverfahren allein dazu nicht ausreicht, wird ein internes Splitting vorgenommen, so dass die Suche nach Nullstellen auf unterschiedliche Bereiche fokussiert werden kann. Jedes Intervall wird dazu in zwei gleich große Subintervalle zerteilt. Wird in dem linken Teil keine Quasi-Null gefunden, wird dieser Teil ,,abgeschnitten`` (engl. pruned) und die Suche in dem verbleibenden rechten Teil fortgesetzt, wie in Abbildung 5.26 anhand der beispielhaft dargestellten Suchreihenfolge zu sehen ist.

Abbildung 5.26: Berechnung von Box-Konsistenz (vgl. Benhamou, 2002, S. 48)