Intervallarithmetik

Intervallarithmetik bezeichnet in der Mathematik eine Methodik zur automatisierten Fehlerabschätzung auf Basis abgeschlossener Intervalle. Einfache Rechenoperationen, wie die Grundrechenarten oder Sinus und Kosinus, werden hierbei durch intervallwertige Varianten ersetzt, die äußere Grenzen des gesuchten Wertebereiches erzeugen. Dieses Konzept bildet einen einheitlichen Rahmen zu Behandlung von Ungenauigkeiten durch Rundungsfehler, ungenaue Modellierung und Linearisierung sowie Unsicherheiten bei physikalischen und technischen Parametern.

Einführung

Das Hauptaugenmerk bei der Intervallarithmetik liegt darauf auf möglichst einfache Art und Weise obere und untere Schranken für den Wertebereich einer Funktion in einer oder mehreren Veränderlichen zu bestimmen, wenn jede Variable innerhalb eines gegebenen Intervalls variiert. Dabei müssen die Grenzen nicht unbedingt den genauen Supremum und Infimum entsprechen, da die genaue Berechnung diese Werte oft zu schwierig ist. (Es lässt sich sogar zeigen, dass diese Aufgabenstellung im allgemeinen NP-schwer wäre.)

Üblicherweise beschränkt man sich auf die Behandlung abgeschlossener reeller Intervalle, also Mengen der Form

$[a,b]=\{x\in \mathbb {R} \,|\,a\leq x\leq b\}$,

wobei auch $a={-\infty }$ und $b={\infty }$ zulässig sind. Dabei entsprechen $[{-\infty },b]$ und $[a,{\infty }]$ den entsprechenden halboffenen Intervallen, die alle reellen Zahlen kleiner oder gleich $b$ bzw. größer oder gleich $a$ umfassen. Entsprechend bezeichnet das Intervall $[{-\infty },{\infty }]$ die gesamte reelle Achse.

Wie beim klassischen Rechnen mit Zahlen muss zunächst einmal definiert werden, wie die arithmetischen Operationen und elementaren Funktionen auf Intervalle anzuwenden sind. Komplexere Funktionen können dann aus diesen Grundelementen zusammengesetzt werden.

Grundrechenarten

Eine Operationen $\circ$ zwischen zwei Intervallen muss die Bedingung

$[x_{1},x_{2}]\circ [y_{1},y_{2}]=\{x\circ y|\,$für alle$\,x\in [x_{1},x_{2}],y\in [y_{1},y_{2}]\}$

erfüllen. Für die vier Grundrechenarten folgt daraus, dass

$[x_{1},x_{2}]\circ [y_{1},y_{2}]=[\min(x_{1}\circ y_{1},x_{1}\circ y_{2},x_{2}\circ y_{1},x_{2}\circ y_{2}),\max(x_{1}\circ y_{1},x_{1}\circ y_{2},x_{2}\circ y_{1},x_{2}\circ y_{2})]$,

falls $x\circ y$ zulässig ist für alle $x\in [x_{1},x_{2}]$ und $y\in [y_{1},y_{2}]$.

Für praktische Anwendungen lässt sich dies noch weiter vereinfachen:

• Addition: $[x_{1},x_{2}]+[y_{1},y_{2}]=[x_{1}+y_{1},x_{2}+y_{2}]$
• Subtraktion: $[x_{1},x_{2}]-[y_{1},y_{2}]=[x_{1}-y_{2},x_{2}-y_{1}]$
• Multiplikation: $[x_{1},x_{2}]\cdot [y_{1},y_{2}]=[\min(x_{1}y_{1},x_{1}y_{2},x_{2}y_{1},x_{2}y_{2}),\max(x_{1}y_{1},x_{1}y_{2},x_{2}y_{1},x_{2}y_{2})]$
• Division: $[x_{1},x_{2}]/[y_{1},y_{2}]=[x_{1},x_{2}]\cdot (1/[y_{1},y_{2}])$,

wobei $1/[y_{1},y_{2}]=[1/y_{2},1/y_{1}]$ falls $0\notin [y_{1},y_{2}]$, $1/[y_{1},0]=[{-\infty },1/y_{1}]$ und $1/[0,y_{2}]=[1/y_{2},{\infty }]$. Ansonsten setzt man $1/[y_{1},y_{2}]=[{-\infty },{\infty }]$.

Da man eine Zahl $r\in \mathbb {R}$ als das Intervall $[r,r]$ interpretieren kann, erhält man sofort eine Vorschrift zur Kombination von intervall- und reellwertigen Größen.

Mit Hilfe diese Definitionen lässt sich bereits der Wertebereich einfacher Funktionen, wie $f(a,b,x)=a\cdot x+b$ bestimmen. Setze man beispielsweise $a=[1,2]$, $b=[5,7]$ und $x=[2,3]$, so rechnet man

$f(a,b,x)=([1,2]\cdot [2,3])+[5,7]=[1\cdot 2,2\cdot 3]+[5,7]=[7,13]$.

Interpretiert man nun $f(a,b,x)$ als Funktion in einer Variablen $x$ mit intervallwertigen Parametern $a$ und $b$, dann lässt sich die Menge aller Nullstellen diese Funktionenschar leicht bestimmen. Es gilt dann

$f([1,2],[5,7],x)=([1,2]\cdot x)+[5,7]=0\Leftrightarrow [1,2]\cdot x=[-7,-5]\Leftrightarrow x=[-7,-5]/[1,2]$,

Die möglichen Nullstellen liegen also im Intervall $[-7,{-2.5}]$

Wie im obigen Beispiel, kann die Multiplikation von Intervallen oft auf die Multiplikation nur zweier Zahlen zurückgeführt werden kann. Es gilt nämlich

$[x_{1},x_{2}]\cdot [y_{1},y_{2}]=[x_{1}\cdot y_{1},x_{2}\cdot y_{2}]$, falls $x_{1},y_{1}\geq 0$.

Entsprechendes gilt wenn eines der beiden Intervalle ganz im nicht-positiven und das andere ganz im nicht-negativen Bereich der reellen Achse liegt. Generell muss bei der Multiplikation noch beachtet werden, dass das Ergebnis sofort auf $[{-\infty },{\infty }]$ gesetzt werden muss, falls unbestimmte Werte wie $0\cdot \infty$ auftreten. Dies tritt z. B. bei einer Division auf, bei der Zähler und Nenner beide Null enthalten.

Notation

Um intervallwertige Größen leichter in Formeln zu erkennen, zweckentfremdet man die eckigen Klammern zur „Markierung“.

Dementsprechend bezeichnet $[x]\equiv [x_{1},x_{2}]$ ein Intervall und die Menge aller reellen Intervalle werden als $[\mathbb {R} ]:=\{[x_{1},x_{2}]|x_{1}\leq x_{2},x_{1},x_{2}\in \mathbb {R} \cup \{-\infty ,\infty \}\}$ abgekürzt. Für eine Box oder Vektor von Intervallen $([x]_{1},\cdots ,[x]_{n})\in [\mathbb {R} ]^{n}$ verwendet man zusätzlich fetten Schriftschnitt: $[\mathbf {x} ]$.

Bei einer derart kompakten Notation ist zu beachten, dass $[x]$ nicht mit einem sogenannten uneigentlichen Intervall $[x_{1},x_{1}]$ verwechselt wird, bei dem obere und untere Grenze übereinstimmen.

Monotone und stückweise monotone Funktionen

Wertebereich einer monotonen Funktion

Für monotone Funktionen in einer Variablen lässt sich der Wertebereich ebenfalls leicht bestimmen. Ist $f:\mathbb {R} \rightarrow \mathbb {R}$ monoton steigend oder fallend in einem Intervall $[x_{1},x_{2}]$, dann gilt für alle Werte $y_{1},y_{2}\in [x_{1},x_{2}]$ mit $y_{1}\leq y_{2}$ die Ungleichung

$f(y_{1})\leq f(y_{2})$, bzw. $f(y_{1})\geq f(y_{2})$.

Den Wertebereiches des Intervalles $[y_{1},y_{2}]\subseteq [x_{1},x_{2}]$ erhält man durch auswerten der Funktion an den Endpunkten $y_{1}$ und $y_{2}$:

$f([y_{1},y_{2}])=[\min(f(y_{1}),f(y_{2})),\max(f(y_{1}),f(y_{2}))]$.

Daher lassen sich folgende Intervallisierungen elementarer Funktionen leicht definieren:

• Exponentialfunktion: $e^{[x_{1},x_{2}]}=[e^{x_{1}},e^{x_{2}}]$,
• Logarithmus: $\log({[x_{1},x_{2}]})=[\log {x_{1}},\log {x_{2}}]$, bzw. $\ln({[x_{1},x_{2}]})=[\ln {x_{1}},\ln {x_{2}}]$, für positive Intervalle $[x_{1},x_{2}]$
• Ungerade Potenzen: ${[x_{1},x_{2}]}^{n}=[{x_{1}}^{n},{x_{2}}^{n}]$, für ungerade $n\in \mathbb {N}$.

Es ist außerdem noch wichtig den Wertebereich für gerade Potenzen bestimmen zu können. Im Gegensatz zur üblichen Numerik, ist es hier nicht sinnvoll, die Berechnung auf die Multiplikation zurückzuführen. Beispielsweise bewegt sich $x^{n}$ für $x\in [-1,1]$ innerhalb des Intervalles $[0,1]$ wenn $n=2,4,6,\ldots$. Versucht man $[-1,1]^{n}$ aber durch Multiplikationen der Form $[-1,1]\cdot \ldots \cdot [-1,1]$ zu bestimmen, so erhält man in jedem Fall als Ergebnis $[-1,1]$.

Sinnvoller ist es hier die Parabel $x^{n}$ als Zusammensetzung einer monoton fallenden (für $x<0$) und einer monoton steigenden Funktion (für $x>0$) zu betrachten. Es gilt also für gerade $n\in \mathbb {N}$:

• ${[x_{1},x_{2}]}^{n}=[x_{1}^{n},x_{2}^{n}]$, falls $x_{1}\leq 0$,
• ${[x_{1},x_{2}]}^{n}=[x_{2}^{n},x_{1}^{n}]$, falls $x_{2}<0$,
• ${[x_{1},x_{2}]}^{n}=[0,\max(x_{1}^{n},x_{2}^{n})]$, sonst.

Allgemeiner kann man sagen, dass es für stückweise monotone Funktionen ausreicht, diese an den Endpunkten $x_{1},x_{2}$eines Intervalles $[x_{1},x_{2}]$ sowie an den in $[x_{1},x_{2}]$ enthaltenen sogenannten kritischen Punkten ausgerechnet werden müssen. Die kritischen Punkte entsprechen hierbei den Stellen, an denen sich die Monotonieeigenschaften ändern.

Dies lässt sich z. B. auf Sinus und Kosinus anwenden, die zusätzlich an Stellen $({1}/{2}+{n})\,\pi$ bzw. ${n}\,\pi$ für alle $n\in \mathbb {Z}$ ausgewertet werden müssen. Hierbei spielen höchstens fünf Punkte eine Rolle, da man als Ergebnis sofort $[-1,1]$ festlegen kann, wenn das Eingangintervall mindestens eine ganze Periode enthält. Außerdem müssen Sinus und Kosinus lediglich an den Randpunken neu evaluiert werden, da die entsprechenden Werte an den kritischen Stellen – nämlich -1, 0 , +1 – vorab abgespeichert werden können.

Intervallerweiterungen allgemeiner Funktionen

Im allgemeinen findet man für beliebige Funktionen keine derart einfache Beschreibung des Wertebereiches. Man kann aber diese aber oft auf Intervalle ausdehnen. Wenn $f:\mathbb {R} ^{n}\rightarrow \mathbb {R}$ eine Funktion ist, die einen reellwertigen Vektor auf eine reelle Zahl abbildet, dann nennt man $[f]:[\mathbb {R} ]^{n}\rightarrow [\mathbb {R} ]$ eine Intervallerweiterung von $f$, wenn gilt

$[f]([\mathbf {x} ])\supseteq \{f(\mathbf {y} )|\mathbf {y} \in [\mathbf {x} ]\}$.

Dies definiert die Intervallerweiterung nicht eindeutig. So sind beispielsweise sowohl $[f]([x_{1},x_{2}])=[e^{x_{1}},e^{x_{2}}]$ als auch $[g]([x_{1},x_{2}])=[{-\infty },{\infty }]$ zulässige Erweiterungen der Exponentialfunktion. Natürlich möglichst scharfe Erweiterungen gewünscht, also solche, die so genau wie möglich den gesuchten Wertebereich approximieren. Daher wird man in diesem Fall eher $[f]$ wählen, da sie sogar den exakten Bereich bestimmt, wie oben gesehen.

Die natürliche Intervallerweiterung erhält man, indem man in der Funktionsvorschrift $f(x_{1},\cdots ,x_{n})$ die Grundrechenarten und elementaren Funktionen durch ihre intervallwertigen Äquivalente ersetzt.

Die Taylor-Intervallerweiterung (vom Grad $k$ ) einer $k+1$ mal differenzierbaren Funktion $f$ ist definiert durch

$[f]([\mathbf {x} ]):=$$f(\mathbf {y} )+\sum _{i=1}^{k}{\frac {1}{i!}}\mathrm {D} ^{i}f(\mathbf {y} )\cdot ([\mathbf {x} ]-\mathbf {y} )^{i}+[r]([\mathbf {x} ],[\mathbf {x} ],\mathbf {y} )$, für ein $\mathbf {y} \in [\mathbf {x} ]$,

wobei $\mathrm {D} ^{i}f(\mathbf {y} )$ das Differential $i$-ter Ordnung am Punkt $\mathbf {y}$ und $[r]$ eine Intervallerweiterung des Taylorrestgliedes

$r(\mathbf {x} ,\xi ,\mathbf {y} )={\frac {1}{(k+1)!}}\mathrm {D} ^{k+1}f(\xi )\cdot (\mathbf {x} -\mathbf {y} )^{k+1}$

bezeichnet. Da der Vektor $\xi$ zwischen $\mathbf {x}$ und $\mathbf {y}$ mit $\mathbf {x} ,\mathbf {y} \in [\mathbf {x} ]$ liegt, lässt sich $\xi$ ebenfalls durch $[\mathbf {x} ]$ abschätzen. Üblicherweise wählt man für $\mathbf {y}$ den Mittelpunkt des Intervallvektors und die natürliche Intervallerweiterung zur Abschätzung des Restgliedes.

Den Spezialfall der Taylor-Intervallerweiterung vom Grad $k=0$ bezeichnet man auch als Mittelwert-Intervallerweiterung. Für eine Intervallerweiterung der Jacobi-Matrix $[J_{f}](\mathbf {[x]} )$ erhält man hier

$[f]([\mathbf {x} ]):=f(\mathbf {y} )+[J_{f}](\mathbf {[x]} )\cdot ([\mathbf {x} ]-\mathbf {y} )$.

Intervall-Verfahren

Die Methoden der klassischen Numerik können nicht 1:1 für die Intervallarithmetik umgesetzt werden.

Gerundete Intervallarithmetik

Um effizient mit Intervallen rechnen zu können, muss eine konkrete Implementierung kompatibel zum Rechnen mit Gleitkommazahlen sein. Die oben definierten Operationen basieren auf exakter Arithmetik, die bei schnellen numerischen Lösungsverfahren nicht zur Verfügung steht. Der Wertebereich der Funktion $f(x,y)=x+y$ für $x\in [0.1,0.8]$ und $y\in [0.06,0.08]$ wäre beispielsweise $[0.16,0.88]$. Führt man die gleiche Rechnung mit einstelliger Präzision durch, so würde das Ergebnis üblicherweise zu $[0.2,0.9]$ gerundet. Da aber $[0.2,0.9]\not \supseteq [0.16,0.88]$ würde dieser Ansatz den Grundprinzipen der Intervallarithmetik widersprechen, da ein Teil des Wertebereiches von $f([0.1,0.8],[0.06,0.08])$ verloren geht. Stattdessen ist hier die nach außen gerundete Lösung $[0.1,0.9]$ vorzuziehen.

Die Norm IEEE 754 definiert hierfür neben Standarddarstellungen für binäre Gleitkommazahlen auch genaue Verfahren für das Durchführung von Rundungen. Demnach muss ein zu IEEE 754 konformes System dem Programmierer neben dem mathematischen Runden (zur nächsten Gleitkommazahl) noch weitere Rundungsmodi bereitstellen: immer aufrunden, immer abrunden und Rundung gegen 0 (Ergebnis betragsmäßig verkleinern).

Das benötigte nach außen Runden lässt sich also durch entsprechendes Umschalten der Rundungseinstellungen der CPU beim Berechnen von oberer und unterer Grenze bewerkstelligen. Alternativ kann dies durch Hinzuaddition eines geeigneten schmalen Intervalls $[\varepsilon _{1},\varepsilon _{2}]$ erreicht werden.

Das Abhängigkeitsproblem

Überschätzung des Wertebereiches

Das sogenannte Abhängigkeitsproblem ist ein Haupthindernis bei der Anwendung der Intervallarithmetik. Obwohl der Wertebereich der elementaren arithmetischen Operationen und Funktionen mit Intervallmethoden sehr genau bestimmt werden kann, gilt dies nicht mehr für zusammengesetzte Funktionen. Falls ein intervallwertiger Parameter mehrfach in einer Rechnung auftritt, wird jedes Auftreten unabhängig voneinander behandelt. Dies führt zu einer ungewollten Aufblähung der resultierenden Intervalle.

Unabhängige Betrachtuung jedes Auftretens einer Variablen

Zur Illustration sei eine Funktion $f$ durch den Ausdruck $f(x)=x^{2}+x$ gegeben. Der Wertebereich dieser Funktion über dem Intervall $[-1,1]$ beträgt eigentlich $[-1/4,2]$. Um die natürliche Intervallerweiterung zu erhalten, rechnet man aber $[-1,1]^{2}+[-1,1]=[0,1]+[-1,1]=[-1,2]$, was einen etwas größeren Bereich ergibt. In der Tat berechnet man eigentlich Infinum und Supremum der Funktion $h(x,y)=x^{2}+y$ über $x,y\in [-1,1]$. Hier würde man also besser eine alternative Formulierung für $f$ verwenden, die die Variable $x$ nur einmal verwendet. In diesem Fall kann man den Ausdruck $f(x)=x^{2}+x$ einfach durch quadratische Ergänzung zu $f(x)=\left(x+{\frac {1}{2}}\right)^{2}-{\frac {1}{4}}$ umformen. Dann liefert die entsprechende Intervall-Rechnung

$\left([-1,1]+{\frac {1}{2}}\right)^{2}-{\frac {1}{4}}=\left[-{\frac {1}{2}},{\frac {3}{2}}\right]^{2}-{\frac {1}{4}}=\left[0,{\frac {9}{4}}\right]-{\frac {1}{4}}=\left[-{\frac {1}{4}},2\right]$

auch den richtigen Wertebereich.

Im allgemeinen lässt sich zeigen, dass man tatsächlich den genauen Wertebereich erhält, wenn jede Variable nur einmal auftaucht. Allerdings lässt sich nicht jede Funktion geeignet auflösen.

Die durch das Abhängigkeitsproblem verursachte Überschätzung des Wertebereiches, kann soweit gehen, dass das Resultat einen derart großen Bereich umfasst, der keine sinnvollen Schlüsse mehr zulässt.

Lineare Intervall-Systeme

Ein lineares Intervall-System besteht aus einer intervallwertigen Matrix $[\mathbf {A} ]\in [\mathbb {R} ]^{n\times m}$ und einem Intervall-Vektor $[\mathbf {b} ]\in [\mathbb {R} ]^{n}$. Gesucht ist dann eine möglichst schnmale Box $[\mathbf {x} ]\in [\mathbb {R} ]^{m}$, die alle Vektoren $\mathbf {x} \in \mathbb {R} ^{m}$ enthält, für die es ein Paar $(\mathbf {A} ,\mathbf {b} )$ mit $\mathbf {A} \in [\mathbf {A} ]$, und $\mathbf {b} \in [\mathbf {b} ]$ gibt, die die Gleichung

$\mathbf {A} \cdot \mathbf {x} =\mathbf {b}$

erfüllen.

Für quadratische Systeme - also wenn gilt $n=m$ - lässt sich ein solcher Intervall-Vektor $[\mathbf {x} ]$, der alle möglichen Lösungen enthält sehr einfach mit dem Intervall-Gauß Verfahren bestimmen. Hierfür ersetzt man einfach die numerischen Operationen, die bei dem aus der linearen Algebra bekannten Gaußschen Eliminationsverfahren auftauchen, durch ihren Intervall-Versionen. Da allerdings während der Abarbeitung dieser Methode die intervallwertigen Einträge von $[\mathbf {A} ]$ und $[\mathbf {b} ]$ mehrfach in die Rechnung eingehen, leidet dieser Ansatz sehr stark an dem Abhängigkeitsproblem. Daher biete sich der Intervall-Gauß nur für grobe erste Abschätzungen an, die zwar die gesamten Lösungemenge enthält, aber auch einen sehr großen Bereich außerhalb davon.

Eine grobe Lösung $[\mathbf {x} ]$ kann aber oft durch eine Intervallisierung des Gauß-Seidel-Verfahrens verbessert werden. Diese ist folgendermaßen motiviert: Die $i$-te Zeile des der intervallwertigen linearen Gleichung

${\begin{pmatrix}{[a_{11}]}&\cdots &{[a_{1n}]}\\\vdots &\ddots &\vdots \\{[a_{n1}]}&\cdots &{[a_{nn}]}\end{pmatrix}}\cdot {\begin{pmatrix}{x_{1}}\\\vdots \\{x_{n}}\end{pmatrix}}={\begin{pmatrix}{[b_{1}]}\\\vdots \\{[b_{n}]}\end{pmatrix}}$

lässt sich nach der Variablen $x_{i}$ auflösen, falls die Division $1/[a_{ii}]$ erlaubt ist. Es gilt demnach gleichzeitig $x_{j}\in [x_{j}]$ und $x_{j}\in ([b_{i}]-\sum _{k\not =j}[a_{ik}]\cdot [x_{k}])/[a_{ij}]$. Man kann also nun $[x_{j}]$ durch $[x_{j}]\cap ([b_{i}]-\sum _{k\not =j}[a_{ik}]\cdot [x_{k}])/[a_{ij}]$ ersetzen, und so den Vektor $[\mathbf {x} ]$ elementweise verbessern. Da das Verfahren effizienter für diagonaldomante Matrizen ist, versucht man oft statt dem System $[\mathbf {A} ]\cdot \mathbf {x} =[\mathbf {b} ]$ dies durch Multiplikation mit einer geeigneten reellen Matrix $\mathbf {M}$ entstandene Matrixgleichung $(\mathbf {M} \cdot [\mathbf {A} ])\cdot \mathbf {x} =\mathbf {M} \cdot [\mathbf {b} ]$ . Wählt man beispielsweise $\mathbf {M} =\mathbf {A} ^{-1}$ für die Mittelpunktsmatrix $\mathbf {A} \in [\mathbf {A} ]$ so ist $\mathbf {M} \cdot [\mathbf {A} ]$ eine äußere Näherung der Einheitsmatrix.

Für die oben genannten Methoden gilt allerdings, dass sie nur dann gut funktionieren, wenn die Breite der vorkommenden Intervalle hinreichend klein ist. Für breitere Intervalle kann es sinnvoll sein, das Intervall-lineare System auf mehrere reellwertige lineare Systeme zurückzuführen. Sind nämlich alle Matrizen $\mathbf {A} \in [\mathbf {A} ]$ invertierbar, dann ist es vollkommen ausreichend alle möglichen Kombinationen der (oberen und unteren) Endpunkte vorkommenden Intervalle zu betrachten. Dieser Ansatz ist allerdings nur für Systeme kleinerer Dimension möglich, da bei einer vollbesetzen $n\times n$ Matrix schon $2^{n^{2}}$ reelle Matrizen invertiert werden müssen, mit jeweils $2^{n}$ Vektoren für die rechte Seite.

Intervall-Newton Verfahren

Ein Intervall-Variante des Newton-Verfahrens zu Bestimmung der Nullstellen in einem Intervall-Vektor$[\mathbf {x} ]$ lässt sich einfach aus der Mittelwert-Erweiterung ableiten. Für einen unbekannten Vektor $\mathbf {z} \in [\mathbf {x} ]$ gilt für ein festes $\mathbf {y} \in [\mathbf {x} ]$, dass $f(\mathbf {z} )\in f(\mathbf {y} )+[J_{f}](\mathbf {[x]} )\cdot (\mathbf {z} -\mathbf {y} )$. Für eine Nullstelle $\mathbf {z}$ ist $f(z)=0$ und es muss gelten, dass $f(\mathbf {y} )+[J_{f}](\mathbf {[x]} )\cdot (\mathbf {z} -\mathbf {y} )=0$. Man erhält also $\mathbf {z} \in \mathbf {y} -[J_{f}](\mathbf {[x]} )^{-1}\cdot f(\mathbf {y} )$. Wobei die $[J_{f}](\mathbf {[x]} )^{-1}\cdot f(\mathbf {y} ))$ durch die linearen Verfahren bestimmt werden kann.

In jedem Newton-Schritt wird nun ein grober Startwert $[\mathbf {x} ]\in [\mathbb {R} ]^{n}$ durch $[\mathbf {x} ]\cap \left(\mathbf {y} -[J_{f}](\mathbf {[x]} )^{-1}\cdot f(\mathbf {y} )\right)$ ersetzt und so iterativ verbessert. Im Gegensatz zum klassischen Verfahren nähert sich diese Methode von außen den Nullstellen. Daher ist immer garantiert, dass das Ergebnis immer alle Nullstellen im Startwert enthält. Umgekehrt hat man bewiesen, dass $f$ keine Nullstelle in $[\mathbf {x} ]$ hat, wenn der Newton-Schritt die leere Menge zurückliefert.

Bisektion und Überdeckungen

Die verschiedenen Intervall-Methoden liefern nur äußerst konservative Abschätzungen eines jeweils gesuchten Bereiches, da Abhängigkeiten zwischen den intervallwertigen Größen nicht ausreichend berücksichtigt werden. Das Abhängigkeitsproblem spielt aber eine desto geringere Rolle je dünner die Intervalle sind.

Überdeckt man einen Intervallvektor $[\mathbf {x} ]$ durch kleinere Boxes $[\mathbf {x} _{1}],\cdots ,[\mathbf {x} _{k}]$, so dass $[\mathbf {x} ]=\bigcup _{i=1}^{k}[\mathbf {x} _{i}]$, dann gilt für den Wertebereich $f([\mathbf {x} ])=\bigcup _{i=1}^{k}f([\mathbf {x} _{i}])$. Für die oben genannten Intervallerweiterungen gilt dann $[f]([\mathbf {x} ])\supseteq \bigcup _{i=1}^{k}[f]([\mathbf {x} _{i}])$. Da $[f]([\mathbf {x} ])$ oft eine echte Obermenge der rechten Seite ist, erhält man somit meist eine verbesserte Abschätzung.

Eine solche Überdeckung kann man zum einen durch Bisektion generiert werden, indem man besonders dicke Elemente $[x_{i1},x_{i2}]$ des Intervallvektors $[\mathbf {x} ]=([x_{11},x_{12}],\cdots ,[x_{n1},x_{n2}])$ beispielsweise in der Mitte teilt und durch zwei Intervalle $[x_{i1},(x_{i1}+x_{i2})/2]$ und $[(x_{i1}+x_{i2})/2,x_{i2}]$ ersetzt. Sollte das daraus folgende Resultat immer noch nicht geeignet sein, kann sukzessive weiterzerlegt werden. Hierbei gilt allerdings zu beachten, dass durch $r$ geteilte Vektorelemente eine Überdeckung aus $2^{r}$ Intervallvektoren entsteht, was den Rechenaufwand natürlich stark erhöht.

Bei sehr breiten Intervallen kann es sogar sinnvoll sein, alle Intervalle gleich in mehrere Teilintervalle mit (kleiner) konstanter Breite zu zerlegen („Mincing“). Damit spart man die Zwischenrechnung für die einzelnen Bisektionsschritte. Beide Herangehensweisen sind allerdings nur für Probleme niedriger Dimension geeignet.

Anwendung

Die Intervallarithmetik kommt auf verschiedenen Gebieten zum Einsatz, um Größen zu behandeln für die keine genauen Zahlenwerte festgelegt werden können.

Rundungsfehleranalyse

Die Intervallarithmetik wird in der Numerischen Mathematik angewendet, um Kontrolle über die bei jeder Berechnung auftretenden Rundungsfehler zu bekommen. Der Vorteil der Intervallarithmetik liegt darin, dass man nach jeder Operation ein Intervall erhält welches das Ergebnis sicher einschließt. Aus dem Abstand der Intervallgrenzen kann man den aktuellen Berechnungsfehler direkt ablesen:

Fehler = $\mathrm {abs} (a-b)$ für gegebenes Intervall $[a,b]$.

Intervallanalyse bietet hierbei keinen Ersatz für klassischen Methoden zu Fehlerreduktion wie Pivotisierung, sondern ergänzt diese lediglich.

Toleranzanalyse

Bei der Simulation technischer und physikalischer Prozesse treten oft Parameter auf, für die keine exakten Zahlenwerte zugeordnet werden können. So unterliegt der Produktionsprozess technischer Bauteile gewissen Toleranzen, so bestimmte Parameter innerhalb bestimmter Intervalle schwanken können. Außerdem können viele Naturkonstanten nicht mit beliebiger Genauigkeit gemessen werden.

Wird das Verhalten eines solchen toleranzbehafteten Systems beispielsweise durch eine Gleichung $f(\mathbf {x} ,\mathbf {p} )=0$, für $\mathbf {p} \in [\mathbf {p} ]$ und Unbekannten $\mathbf {x}$, beschrieben, dann kann die Menge aller möglichen Lösungen

$\{\mathbf {x} \,|\,\exists \mathbf {p} \in [\mathbf {p} ],f(\mathbf {x} ,\mathbf {p} )=0\}$,

die durch Intervallmethoden abgeschätzt werden kann. Diese stellen hier eine Alternative zur klassischen Fehlerrechnung dar. Im Gegensatz zu punktbasierten Methoden wie der Monte-Carlo-Simulation stellt die verwendete Methodik sicher, dass keine Teile der Lösungsgebietes übersehen werden. Allerdings entspricht das Ergebnis immer einer Worst Case-Analyse für gleichverteilte Fehler, andere Wahrscheinlichkeitsverteilungen sind nicht möglich.

Literatur

• Jürgen Herzberger. Basic definitions and properties of interval arithmetic. In Jürgen Herzberger (Hrsg.), Topics in validated computations, Seiten 1-6. Elsevier Science B.V., Amsterdam, 1993.

• Günter Mayer, Grundbegriffe der Intervallrechnung. In Ulrich Kulisch (Hrsg.): Wissenschaftliches Rechnen mit Ergebnisverifikation, S. 101-118, Akademie-Verlag, Berlin 1989; auch: Vieweg-Verlag, Wiesbaden 1989.

Weblinks

• Link-Seite über Interval Computations von Vladik Kreinovich, Univ. of Texas, El Paso
• Brian Hayes, 'A Lucid Interval', gute Einführung (pdf)
• Linkseite von R. Baker Kearfott
• Linkseite von Arnold Neumaier