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 geschrieben werden. Wenn die Funktion
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 für die zu berechnende
Nullstelle, werden iterativ weitere Näherungswerte
durch Einsetzen in die folgende, rekursive Formel
berechnet (vgl. Bronstein et al., 1996, S. 1137):
Die grafische Interpretation des Verfahrens ist in
Abbildung 5.24 zu sehen. Beginnend mit dem
ersten Schätzwert wird eine Tangente durch den Punkt
P an den Graphen von f gelegt. Die Tangente
schneidet die x-Achse in
, was in diesem Fall bereits
eine deutliche Verbesserung darstellt. Für
wird dasselbe
Verfahren auf
angewendet usw. Bereits nach wenigen Iterationen
liegen häufig sehr genaue Näherungswerte vor.
![]() |
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 und
der Mittelpunkt von X, die Intervallfunktion
N (für ,,Newton``) definiert wird:
Beginnend mit einem Ausgangsintervall wird durch
die konvergierende Intervallfolge
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).
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.