Direkt zum Inhalt

Lexikon der Mathematik: Intervall-Newton-Verfahren

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 xx(0), 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 in x eine Nullstelle, die in x(0)eindeutig ist.
  2. f besitzt in x(0)genau dann keine Nullstelle, wenn der Durchschnitt in (1) nach endlich vielen Schritten leer wird.
  3. Besitzt f in x(0)eine Nullstelle x*, so ist diese dort eindeutig, der Durchschnitt in (1) wird nie leer, die Iterierten x(k)sind für jedes k ∈ ℕ0definiert und konvergieren im Sinn der Hausdorff-Metrik q gegen x*. Genügt fauf x(0)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(0) in y(1)z(1) liegen muß, kann man das Intervall-Newton-Verfahren auf beide Intervalle getrennt anwenden. Besitzt f in x(0) 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(0), so ist die Voraussetzung \(0\notin {\bf f}^{^{\prime}}({\bf y}^{(1)})\) bzw. \(0\notin {\bf f}^{^{\prime} }({\bf z}^{(1)})\) wegen y(1)x(0) und z(1)x(0) 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(0) eine mehrfache Nullstelle x**, so liefert das Verfahren nicht unbedingt eine enge Einschließung von x**. Man betrachte z. B. f(x) = x2, x(0) = [−1, 1], \({\mathop{x}\limits^{\sim}}^{(k)}={\bar{x}}^{(k)}\) im Gegensatz zu f(x) = x2, x(0) = [0, 1], \({\mathop{x}\limits^{\sim}}^{(k)}={\bar{x}}^{(k)}\). Hier kann eine Aufteilung von x(0) 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 ⊆ ℝn → ℝn übertragen. Dazu braucht man die Intervallauswertung f′(x) über xx(0)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(0))) 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(0))) die Intervallmatrix, deren i-te Spalte mit IGA(f′(x(0)), e(i)) übereinstimmt (e(i) 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}\).

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.