Direkt zum Inhalt

Lexikon der Mathematik: Intervallrechnung

Die Intervallrechnung stellt ein Teilgebiet der numerischen Mathematik dar, das sich mit dem Nachweis von Lösungen eines mathematischen Problems beschäftigt und gleichzeitig Unter- und Oberschranken für diese Lösungen liefert. Man spricht in diesem Zusammenhang von Lösungsverifikation, Verifikationsnumerik, validiertem Rechnen, selbst validierenden Verfahren, Lösungsnachweis mit Schrankengarantie, Einschließungsverfahren, E-Methoden.

Eine Grundphilosophie der Intervallrechnung besteht darin, alle möglichen Fehler in die Betrachtung mit einzubeziehen. Hierzu gehören Modellierungsfehler (etwa durch Meß- oder Einstellungsungenauigkeiten), Verfahrensfehler (wie Dis- kretisierungsfehler oder Fehler durch die Approximation von Funktionen durch einfachere Funktionen, etwa durch Polynome), Darstellungsfehler (bei der Umwandlung eines Dezimalbruchs in einen Dualbruch), Rundungsfehler (beim Rechnen mit endlicher Genauigkeit auf einem Computer), Abbruchfehler (beim Ersetzen eines Folgengrenzwerts durch das k-te Folgenglied, etwa bei einem Iterationsverfahren). Dies führt zu einer Klassifikation der Einschließungsverfahren

  1. nach der Art der Ausgangsdaten (Punktgrößen / toleranzbehaftete Größen),
  2. nach der Anzahl der Rechenschritte (unendlich viele / nur endlich viele erlaubt),
  3. nach der Art der Darstellung und Rechnung (exakt / gerundet).

Dabei versteht man unter toleranzbehafteten Ausgangsdaten solche, die innerhalb gewisser Grenzen (= Toleranzen) von einem mittleren Wert abweichen dürfen, also Intervalle sind im Gegensatz zu Punktgrößen (Punktintervall). In der Intervallrechnung geht man davon aus, daß sich alle Fehler letzten Endes mit Hilfe kompakter Intervalle (auch Funktionsintervalle; Funktionenschlauch) einschließen lassen. Für reelle kompakte Intervalle werden eine Intervallarithmetik und IntervallStandardfunktionen bereitgestellt, die grundlegend für die Inklusionsmonotonie und die Einschließungseigenschaft der Intervallrechnung sind. Dabei definiert man die Verknüpfungen und Funktionen so, daß sie in die entsprechenden Verknüpfungen und Standardfunktionen der Analysis übergehen, wenn man sie auf Punktintervalle [a, a] anwendet und diese mit den zugehörigen Zahlen a identifiziert.

Arithmetik und Standardfunktionen lassen sich unter Erhalt der Inklusionsmonotonie und der Einschließungseigenschaft sowie unter Berücksichtigung von Darstellungs- und Rundungsfehlern auf einem Rechner implementieren (Maschinen- intervallarithmetik) und bilden dann die Voraussetzung dafür, daß der Computer mit geeigneten Verfahren der Verifikationsnumerik (meist in Zusammenspiel mit Fixpunktsätzen) den gewünschten Lösungsnachweis alleine durchführen kann („Beweisen mit dem Computer”). Die Aussagen, die der Rechner am Ende eines Verifikationsalgorithmus über die Existenz, die Eindeutigkeit und die Einschließung einer Lösung macht, sind dabei mathematisch korrekt.

Die meisten Verfahren der Intervallrechnung zielen darauf ab, neben dem Lösungsnachweis eine möglichst enge Einschließung dieser Lösung zu liefern. Als Hilfsmittel für die Beurteilung der Einschließungsgüte können bei toleranzbehafteten Problemen sogenannte Inneneinschließungen dienen. Liegen die Ausgangsdaten dagegen als Punktgrößen vor, ist der Durchmesser der einschließenden Intervalle ein Gradmesser. Ist er sehr klein, stimmen (außer in Sonderfällen) die führenden Ziffern von Unter- und Oberschranke überein. Diese Ziffern sind dann dieselben für den eingeschlossenen Lösungswert („Zifferngarantie”).

Zur Konstruktion effizienter Verifikationsverfahren genügt es in der Regel nicht, die herkömmlichen Verfahren der numerischen Mathematik zu kopieren und alle Zahlen durch Intervalle zu ersetzen. Es sind vielmehr Anpassungen vorzunehmen oder vollständig neue Algorithmen zu entwickeln. Zwar stellen der Intervall-Gauß-Algorithmus und das Intervall-Cholesky-Verfahren Übertragungen der bekannten direkten Verfahren zur Lösung linearer Gleichungssysteme dar, bei Iterationsverfahren wie dem Intervall-Newton-Verfahren kommt jedoch mit der Durchschnittsbildung noch eine Operation hinzu, die in den traditionellen numerischen Verfahren im allgemeinen nicht verwendet wird. Hierdurch lassen sich ineinandergeschachtelte Einschließungen der Lösung berechnen oder Aussagen über die Nichtexistenz einer Nullstelle in einem vorgegebenen Bereich machen. Die Einschließung des Wertebereichs einer hinreichend glatten reellwertigen Funktion über einem reellen kompakten Intervall etwa mit Hilfe einer Intervallauswertung oder einer zentrierten Form spielt in den Verifikationsalgorithmen eine wesentlich größere Rolle als bei den übrigen Verfahren der Numerik. Dahinter steckt die bereits erwähnte Einschließungseigenschaft der Intervallrechnung, die in vielen Algorithmen im Verbund mit einer guten Lösungsnäherung und der sogenannten ε-Inflation u. a. dafür sorgt, daß die Selbstabbildungseigenschaft in Fixpunktsätzen rechnerisch nachgewiesen werden kann. Algorithmen zur Lösungsverifikation bei linearen bzw. nichtlinearen Gleichungssystemen, beim Eigenwertproblem, beim Singulärwertproblem, bei gewöhnlichen und bei partiellen Differentialgleichungen basieren auf dieser Strategie (Krawczyk- Verfahren, Lösungsverifikation bei linearen Gleichungssystemen, Lösungsverifikation bei nichtlinearen Gleichungssystemen, Lösungsverifikation bei quadratischen Gleichungssystemen, Lösungsverifikation beim algebraischen Eigenwertproblem, Lösungsverifikation beim inversen Eigenwertproblem, Lösungsverifikation beim Singulärwertproblem, Lösungsverifikation bei Anfangswertproblemen mit gewöhnlichen Differentialgleichungen, Lösungsverifikation bei Randwertproblemen mit gewöhnlichen Differentialgleichungen, Lösungsverifikation bei partiellen Differentialgleichungen).

Mehr auf einem Gebietszerlegungs- und Ausschlußprinzip beruhen die Verfahren zur Lösungsverifikation in der globalen Optimierung, wenngleich auch hier die Wertebereichseinschließung eine zentrale Rolle einnimmt.

Literatur

[1] Alefeld, G.; Herzberger, J.: Einführung in die Intervallrechnung. BI Wissenschaftsverlag Mannheim, 1974.

[2] Kearfott, R.B.: Rigorous Global Search: Continuous problems. Kluwer Dordrecht, 1996.

[3] Moore, R.E.: Interval Analysis. Prentice Hall Englewood Cliffs, 1966.

[4] Neumaier, A.: Interval Methods for Systems of Equations. Cambridge University Press, 1990.

Lesermeinung

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

Partnervideos