Verfahren der Intervallrechnung zum Nachweis der Existenz und Eindeutigkeit bzw. der Nichtexistenz einer Nullstelle x* in einem reellen kompakten Intervall \({\bf x}^{(0)}=[{\mathop{x}\limits_{-}}^{(0)},{\bar{x}}^{(0)}]\subseteq D\) einer stetig differenzierbaren Funktion f : D ⊆ ℝ → ℝ. Ist f′(x) die Intervallauswertung von f′ über x ⊆ x⁽⁰⁾, und gilt \begin{eqnarray}0\notin {\bf f}^{^{\prime} }({\bf x}^{(0)}),\end{eqnarray} so heißt \begin{eqnarray}{\bf N}(\tilde{x},{\bf x})=\tilde{x}-\frac{f(\tilde{x})}{{\bf f}^{^{\prime}}(\bf x)},\tilde{x}\in {\bf x},\end{eqnarray}

Intervall-Newton-Operator und die Iteration \begin{eqnarray}{\bf x}^{(k+1)}={\bf N}({\tilde{x}}^{(k)},{\bf x}^{(k)})\cap {\bf x}^{(k)},k=0,1,\ldots,\end{eqnarray} Intervall-Newton-Verfahren. Dabei ist das Verfahren abzubrechen, wenn der Durchschnitt leer ist. Als \(\tilde{x}\) wählt man häufig den Mittelpunkt von x.

Unter den genannten Voraussetzungen gilt der folgende Satz:

1. Gilt \({\bf N}(\overline {x},\bf x)\subseteq x\)für ein \(\bf x\subseteq {x}^{(0)}\), so besitzt f inxeine Nullstelle, die inx⁽⁰⁾eindeutig ist.
2. f besitzt inx⁽⁰⁾genau dann keine Nullstelle, wenn der Durchschnitt in (1) nach endlich vielen Schritten leer wird.
3. Besitzt f inx⁽⁰⁾eine Nullstelle x^*, so ist diese dort eindeutig, der Durchschnitt in (1) wird nie leer, die Iteriertenx^(k)sind für jedes k ∈ ℕ₀definiert und konvergieren im Sinn der Hausdorff-Metrik q gegen x*. Genügtf′ aufx⁽⁰⁾einer Intervall-Lipschitz-Bedingung, so erfolgt die Konvergenz quadratisch, d. h. \begin{eqnarray}q({\bf x}^{(k+1)},{x}^{* })\le \gamma q{({\bf x}^{(k)},{x}^{* })}^{2},\quad k=0,1,\ldots,\end{eqnarray}mit einer Konstanten γ > 0.

Ist \begin{eqnarray}0\in {\bf f}^{\prime}({\bf x}^{(0)})=[{\underline{s}}^{(0)},{\bar{s}}^{(0)}],{\underline{s}}^{(0)}\ne {\bar{s}}^{(0)}\end{eqnarray} und \(f({\mathop{x}\limits^{}}^{(0)})\gt 0\), so bildet man, sofern existent, die Intervalle \begin{eqnarray}{\bf y}^{(1)}=[{\underline{x}}^{(0)},{\mathop{x}\limits^{}}^{(0)}-f({\mathop{\bar x}\limits^{}}^{(0)})/{\bar{s}}^{(0)}]\end{eqnarray} und \begin{eqnarray}{\bf z}^{(1)}=[{\bar{x}}^{(0)}-f({\bar{x}}^{(0)})/{\underline{s}}^{(0)},{\bar{x}}^{(0)}].\end{eqnarray} (Im Fall \(f({\bar{x}}^{(0)})\lt 0\) vertausche man die Rollen von \({\mathop{s}\limits_{-}}^{(0)}\) und \({\bar{s}}^{(0)}\). Existiert eines der beiden Intervalle nicht, führe man die folgenden Betrachtungen nur für das andere durch.) Da jede Nullstelle von f aus x⁽⁰⁾ in y⁽¹⁾ ∪ z⁽¹⁾ liegen muß, kann man das Intervall-Newton-Verfahren auf beide Intervalle getrennt anwenden. Besitzt f in x⁽⁰⁾ nur endlich viele Nullstellen \({x}_{i}^{* },i=1,\mathrm{...},n\), für die überdies \({f}^{^{\prime} }({x}_{i}^{* })\ne 0\) gilt, und besitzt auch f′ höchstens endlich viele Nullstellen in x⁽⁰⁾, so ist die Voraussetzung \(0\notin {\bf f}^{^{\prime}}({\bf y}^{(1)})\) bzw. \(0\notin {\bf f}^{^{\prime} }({\bf z}^{(1)})\) wegen y⁽¹⁾ ⊆ x⁽⁰⁾ und z⁽¹⁾ ⊆ x⁽⁰⁾ möglicherweise für eines oder gar beide Teilintervalle erfüllt und die Aussagen des Satzes für das entsprechende Teilintervall gültig. Gegebenenfalls zerlege man weiter. Besitzt f in x⁽⁰⁾ eine mehrfache Nullstelle x**, so liefert das Verfahren nicht unbedingt eine enge Einschließung von x**. Man betrachte z. B. f(x) = x², x⁽⁰⁾ = [−1, 1], \({\mathop{x}\limits^{\sim}}^{(k)}={\bar{x}}^{(k)}\) im Gegensatz zu f(x) = x², x⁽⁰⁾ = [0, 1], \({\mathop{x}\limits^{\sim}}^{(k)}={\bar{x}}^{(k)}\). Hier kann eine Aufteilung von x⁽⁰⁾ in mehrere Teilintervalle \({\bf x}_{i}^{(0)},i=1,\mathrm{...},m,\), weiterhelfen, über denen man die Intervallauswertung von f bildet. Gilt \(0\notin {\bf f}({\bf x}_{k}^{(0)})\) für ein Teilintervall \({\bf x}_{k}^{(0)}\), so enthält es wegen der Einschließungseigenschaft der Intervallrechnung sicher keine Nullstelle von f und braucht fortan nicht weiter betrachtet zu werden.

Das Intervall-Newton-Verfahren läßt sich auch auf stetig differenzierbare Funktionen f : D ⊆ ℝⁿ → ℝⁿ übertragen. Dazu braucht man die Intervallauswertung f′(x) über x ⊆ x⁽⁰⁾ ⊆ D der Funktionalmatrix f′ und den Intervallvektor IGA(f′(x), \(f(\mathop{x}\limits^{\sim})\)) aus dem Intervall-Gauß-Algorithmus. Der Interval-Newton-Operator lautet dann \begin{eqnarray}{\bf N}(\tilde{x},{\bf x})=\tilde{x}-{\bf IGA({f}^{^{\prime} }(x)},f(\tilde{x})),\quad \tilde{x}\in \bf x\end{eqnarray} das Intervall-Newton-Verfahren ist durch (1) definiert. Der Satz oben gilt analog, wenn man die Existenz von IGA(f′(x⁽⁰⁾)) voraussetzt und bei b), c) zusätzlich \(\varrho (|I-{\bf IGA({f}^{^{\prime} }({x}^{(0)}))\cdot {f}^{^{\prime} }({x}^{(0)})|)}\lt 1\) fordert. Außerdem ist in (2) auf beiden Seiten q(·, ·) durch ||q(·, ·)||_∞ zu ersetzen. Dabei bezeichnet || · ||_∞ die Maximumsnorm, ϱ(·) den Spektralradius, | · | den Betrag einer Intervallgröße und IGA(f′(x⁽⁰⁾)) die Intervallmatrix, deren i-te Spalte mit IGA(f′(x⁽⁰⁾), e⁽ⁱ⁾) übereinstimmt (e⁽ⁱ⁾i-te Spalte der Einheitsmatrix I ∈ ℝ^n×n). Ohne die zusätzliche Voraussetzung folgt bei c) im allgemeinen nur noch \({x}^{* }\in \mathop{\mathrm{lim}}\limits_{k\to \infty }{\bf x}^{k}\).