Intervallarithmetik

Grundidee und Zweck

Intervallarithmetik ist eine mathematische Methode zur automatisierten Fehlerabschätzung mit abgeschlossenen Intervallen. Statt mit einem nicht genau bekannten reellen Wert x zu rechnen, beschreibt man ihn durch ein Intervall [a,b]. Das bedeutet: x kann jeden Wert zwischen a und b annehmen, einschließlich der Grenzen. Für eine Funktion f sucht man dann ein möglichst kleines Intervall [c,d], das alle möglichen Werte f(x) für x in [a,b] enthält.

Die Methode ist wichtig, weil sie Unsicherheiten während einer Rechnung ausdrücklich mitführt. Sie wird verwendet, um Rundungsfehler, Messfehler, Bauteil-Toleranzen und ungenau bekannte physikalische oder technische Parameter zu behandeln. Außerdem hilft sie dabei, verlässliche Lösungen von Gleichungen und Optimierungsproblemen zu erhalten.

Ein einfaches Beispiel ist der Körpermasseindex BMI. Wenn eine Waage 80 kg anzeigt und auf ganze Kilogramm rundet, kann die tatsächliche Masse bei üblicher Rundung zwischen 79,5 kg und 80,5 kg liegen, also im Intervall [79.5;80.5]. Bei einer Körpergröße von 1,80 m ergibt sich für diesen Gewichtsbereich ungefähr der BMI-Bereich [24,5;24,9]. Wenn zusätzlich die Körpergröße nur auf ganze Zentimeter bekannt ist, also 1,80 m eigentlich [1.795;1.805] m bedeutet, erhält man mit Intervallrechnung [79.5;80.5]/([1.795;1.805])² = [24.4;25.0].

Intervalle, Rechenregeln und Notation

Meist betrachtet die Intervallarithmetik abgeschlossene reelle Intervalle der Form [a,b] = {x in R | a <= x <= b}. Auch a = -unendlich und b = unendlich sind zugelassen; [-unendlich,unendlich] beschreibt die gesamte reelle Achse. Ziel ist es, obere und untere Schranken für Wertebereiche von Funktionen zu finden. Diese Schranken müssen nicht immer das exakte Infimum oder Supremum sein, weil deren genaue Berechnung im Allgemeinen NP-schwer sein kann.

Für die Grundrechenarten werden Operationen so definiert, dass alle möglichen Ergebnisse eingeschlossen sind. Für Intervalle [x1,x2] und [y1,y2] gilt:

• Addition: [x1,x2] + [y1,y2] = [x1+y1, x2+y2]
• Subtraktion: [x1,x2] - [y1,y2] = [x1-y2, x2-y1]
• Multiplikation: [min(x1y1,x1y2,x2y1,x2y2), max(x1y1,x1y2,x2y1,x2y2)]
• Division: [x1,x2]/[y1,y2] = [x1,x2] * (1/[y1,y2]), wobei 1/[y1,y2] = [1/y2,1/y1] gilt, falls 0 nicht in [y1,y2] liegt.

Wenn ein Nennerintervall die Null enthält, entstehen besondere Fälle. Für y1 < 0 < y2 gilt 1/[y1,y2] = [-unendlich,1/y1] vereinigt mit [1/y2,unendlich]. Würde man dies zu [-unendlich,unendlich] zusammenfassen, ginge die Lücke (1/y1,1/y2) verloren. Deshalb rechnet man oft mit mehreren Teilintervallen weiter. Eine systematische Form davon ist die Multi-Intervall-Arithmetik mit Vereinigungen von Intervallen.

In Formeln schreibt man ein Intervall häufig als [x] = [x1,x2]. Die Menge aller reellen Intervalle wird als [R] bezeichnet. Ein Vektor aus Intervallen heißt Box oder Intervallvektor und wird zum Beispiel als [x] in fetter Schreibweise notiert.

Funktionen und Intervallerweiterungen

Damit Intervallarithmetik nicht nur für Grundrechenarten funktioniert, werden auch elementare Funktionen auf Intervalle erweitert. Bei monotonen Funktionen ist das besonders einfach: Ist f in einem Intervall steigend oder fallend, genügt es, f an den beiden Endpunkten auszuwerten. Dann ist f([y1,y2]) = [min{f(y1),f(y2)}, max{f(y1),f(y2)}].

So erhält man zum Beispiel für a > 1 die Exponentialfunktion a^[x1,x2] = [a^x1,a^x2] und für positive Intervalle den Logarithmus log_a([x1,x2]) = [log_a x1, log_a x2]. Ungerade Potenzen erfüllen [x1,x2]^n = [x1^n,x2^n]. Bei geraden Potenzen muss man gesondert beachten, ob das Intervall negative und positive Werte enthält: Für x in [-1,1] liegt x^n bei n = 2,4,6,... im Intervall [0,1], nicht in [-1,1].

Für stückweise monotone Funktionen wertet man zusätzlich kritische Punkte aus, also Stellen, an denen sich die Monotonie ändert. Bei Sinus und Kosinus sind das bestimmte Vielfache von pi; enthält das Eingangsintervall mindestens eine ganze Periode, kann man direkt [-1,1] als Wertebereich setzen.

Eine Intervallerweiterung einer Funktion f: R^n -> R ist eine Funktion [f]: [R]^n -> [R], deren Ergebnis alle Funktionswerte f(y) für y im Eingangsintervallvektor enthält. Die natürliche Intervallerweiterung entsteht, indem man in einer Formel alle normalen Rechenarten und elementaren Funktionen durch ihre Intervallversionen ersetzt. Daneben gibt es Taylor-Intervallerweiterungen. Der Spezialfall vom Grad k = 0 heißt Mittelwert-Intervallerweiterung und nutzt eine Intervallerweiterung der Jacobi-Matrix, um eine nichtlineare Funktion durch lineare Funktionen einzugrenzen.

Verfahren und typische Schwierigkeiten

Für praktische Berechnungen muss Intervallarithmetik mit Gleitkommazahlen umgehen. Da normale Rundung Wertebereiche verkleinern kann, verwendet man nach außen gerichtetes Runden. Ein Beispiel: Der exakte Wertebereich von x+y für x in [0,1;0,8] und y in [0,06;0,08] ist [0,16;0,88]. Bei einstelliger Präzision wäre [0,2;0,9] nicht zulässig, weil [0,16;0,88] darin nicht vollständig enthalten ist. Stattdessen ist [0,1;0,9] passend. IEEE 754 stellt dafür Rundungsmodi wie Aufrunden, Abrunden und Rundung gegen 0 bereit.

Ein zentrales Problem ist das Abhängigkeitsproblem. Wenn dieselbe Variable mehrfach in einer Rechnung vorkommt, behandelt die Intervallarithmetik die Vorkommen oft so, als wären sie unabhängig. Dadurch können Ergebnisintervalle zu groß werden. Für f(x)=x²+x über [-1,1] ist der echte Wertebereich [-1/4,2]. Die natürliche Intervallerweiterung liefert aber [-1,1]² + [-1,1] = [0,1] + [-1,1] = [-1,2]. Durch Umformung zu (x+1/2)² - 1/4 erhält man mit Intervallrechnung den exakten Bereich [-1/4,2].

Verwandt ist der Einhüllungs- oder Wrapping-Effekt: Wenn eine Lösungsmenge keine Box ist, wird sie durch eine Box eingeschlossen und dadurch vergrößert. Die Lösung des Systems x=y und x=p für p in [-1,1] ist genau die Strecke von (-1,-1) bis (1,1), Intervallmethoden liefern aber im besten Fall das Quadrat [-1,1] x [-1,1].

Für lineare Intervallsysteme sucht man eine möglichst schmale Box [x], die alle Lösungen von A*x=b für A in [A] und b in [b] enthält. Intervall-Gauß-Verfahren geben grobe Einschließungen, leiden aber stark unter dem Abhängigkeitsproblem. Intervallisierte Gauß-Seidel-Verfahren können solche Einschließungen verbessern, besonders bei diagonaldominanten Matrizen.

Das Intervall-Newton-Verfahren nähert sich Nullstellen von außen. In jedem Schritt wird ein Startintervall [x] durch den Schnitt mit einem Newton-Ausdruck ersetzt. Liefert ein Schritt die leere Menge, hat f in diesem Intervall keine Nullstelle. Beim Beispiel f(x)=x²-2 mit Startintervall [-2,2] trennt das Verfahren die Suche in [-2,-0,5] und [0,5,2] und konvergiert zu Intervallen um -sqrt(2) und +sqrt(2). Durch Bisektion oder Mincing kann man breite Intervalle in kleinere Boxen zerlegen; das verringert Überschätzung, erhöht aber den Rechenaufwand stark, etwa auf 2^r Boxen bei r Teilungen.

Anwendungen und Einordnung

In der Rundungsfehleranalyse liefert Intervallarithmetik nach jeder Operation ein Intervall, das das Ergebnis sicher einschließt. Aus dem Abstand der Intervallgrenzen kann man den aktuellen Berechnungsfehler ablesen: Fehler = abs(a-b) für ein Intervall [a,b]. Sie ersetzt klassische Methoden zur Fehlerreduktion wie Pivotisierung nicht, sondern ergänzt sie.

In der Toleranzanalyse beschreibt man technische oder physikalische Parameter durch Intervalle. Für ein System f(x,p)=0 mit p in [p] kann man die Menge aller möglichen Lösungen {x | es gibt p in [p] mit f(x,p)=0} abschätzen. Gegenüber punktbasierten Verfahren wie der Monte-Carlo-Simulation soll dabei kein Teil des Lösungsgebiets übersehen werden. Das Ergebnis ist aber eine Worst-Case-Analyse für gleichverteilte Fehler; andere Wahrscheinlichkeitsverteilungen sind nicht möglich.

In der Fuzzy-Arithmetik werden unscharfe Werte durch mehrere geschachtelte Intervalle angenähert. Zugehörigkeitsgrade mu liegen in [0,1], wobei mu=1 sichere Zugehörigkeit und mu=0 Nichtzugehörigkeit bedeutet. Für endlich viele Stufen mu_i nutzt man eine Folge [x^(1)] superset [x^(2)] superset ... superset [x^(k)]. Funktionswerte werden dann stufenweise mit Intervallverfahren abgeschätzt.

Geschichte, Software und Standards

Intervallideen tauchten schon früh auf: Archimedes berechnete im 3. Jahrhundert v. Chr. obere und untere Schranken für pi. Regeln für das Rechnen mit Intervallen und Teilmengen reeller Zahlen erschienen 1931 bei Rosalind Tanner. Paul S. Dwyer nutzte 1951 in einem Lehrbuch zur linearen Algebra sogenannte range numbers zur Abschätzung von Rundungsfehlern.

Als Beginn der modernen Intervallarithmetik gilt Ramon E. Moores Buch Interval Analysis von 1966. Moore hatte die Idee im Frühjahr 1958 und veröffentlichte kurz darauf Arbeiten zur computerunterstützten Intervallarithmetik. Mieczyslaw Warmus hatte bereits 1956 Formeln vorgeschlagen. In Deutschland arbeiteten in den 1960er Jahren Gruppen um Karl Nickel, Ulrich Kulisch und Fritz Krückeberg an intervallarithmetischen Themen. 1974 veröffentlichten Götz Alefeld und Jürgen Herzberger das erste deutschsprachige Lehrbuch.

Es gibt viele Implementierungen, meist als Programmbibliotheken. Seit 1967 entstanden an der Universität Karlsruhe XSC-Erweiterungen für wissenschaftliches Rechnen, später unter anderem Pascal-SC, ACRITH-XSC, Pascal-XSC und C-XSC. Weitere Beispiele sind Profil/BIAS, eine C++-Bibliothek von 1993, Boost-Intervalle, Mathematica, Maple, MuPAD, INTLAB für Matlab und b4m.

Ein IEEE-Standard für Intervallarithmetik wurde im Juni 2015 veröffentlicht. Dazu gibt es freie Referenzimplementierungen: libieeep1788 für C++ und ein Intervall-Paket für GNU Octave. Eine vereinfachte Variante des Standards wurde 2017 verabschiedet. Patente von G. William Walster aus den Jahren 2001 bis 2004, teilweise mit Ramon E. Moore und Eldon R. Hansen, sind in der Forschungsgemeinde umstritten, weil sie möglicherweise nur den bisherigen Stand der Technik wiedergeben.