Welche Anwendungen erfordern Intervallarithmetik?

Ich habe eine sehr grundlegende Vorstellung von Intervallarithmetik (IA), aber es scheint sowohl theoretisch als auch praktisch ein sehr interessanter Zweig der Computerwissenschaft zu sein. Es ist klar, dass es sich bei den offensichtlichen Anwendungen um verifizierte Computer- und unsachgemäße Probleme handelt, aber dies ist zu abstrakt. Da hier viele Menschen mit angewandten Berechnungen befasst sind, bin ich neugierig auf reale Probleme, die ohne IA nur schwer oder gar nicht zu lösen sind .

Diese Antwort antwortet teilweise auf JackPoulsons Kommentar (weil er lang ist) und teilweise auf die Frage.

Die Intervallarithmetik ist ein Berechnungsverfahren, mit dem die berechneten Größen streng begrenzt werden, und zwar nur in dem Sinne, dass die Intervallverlängerung einer reellen Funktion über ein Intervall das Bild dieser Funktion über dasselbe Intervall einschließt. Ohne Berechnung kann die Intervallarithmetik keine Einsicht darüber geben, welche Faktoren den numerischen Fehler in einer Berechnung beeinflussen, wohingegen die Sätze in Highams Buch und anderen auf Kosten potenziell schwacher Grenzen Einsicht in die Faktoren geben, die den numerischen Fehler beeinflussen. Zugegeben, die mit der Intervallarithmetik ermittelten Grenzen können aufgrund des sogenannten Abhängigkeitsproblems ebenfalls schwach sein , aber manchmal sind sie viel stärker. Zum Beispiel die Intervallgrenzen, die mit dem Integrationspaket COSY Infinity ermittelt wurdensind viel enger als die Arten von Fehlergrenzen, die Sie bei der numerischen Integration aus den Ergebnissen von Dahlquist erhalten würden (siehe Hairer, Wanner und Nørsett für Details); Diese Ergebnisse (ich beziehe mich insbesondere auf Theoreme 10.2 und 10.6 in Teil I) geben mehr Einblick in Fehlerquellen, aber die Grenzen sind schwach, wohingegen die Grenzen, die COSY verwenden, eng sein können. (Sie verwenden mehrere Tricks, um Abhängigkeitsprobleme zu mindern.)

Ich zögere, das Wort "Beweis" zu verwenden, wenn ich beschreibe, was Intervallarithmetik tut. Es gibt Beweise mit Intervallarithmetik, aber die Berechnung von Ergebnissen mit Intervallarithmetik und Rundung nach außen ist eigentlich nur ein Mittel der Buchhaltung, um den Bereich einer Funktion konservativ zu begrenzen. Intervallberechnungen sind keine Beweise; Sie sind ein Weg, um Unsicherheit zu verbreiten.

Soweit es um Anwendungen geht, wurden neben Stadtherrs Arbeiten in der chemischen Verfahrenstechnik auch Intervallarithmetiken verwendet, um Grenzen für Teilchenstrahlexperimente zu berechnen (siehe die Arbeiten von Makino und Berz, die mit der COSY Infinity-Website verknüpft sind) verwendet in globalen Optimierungs- und chemischen Konstruktionsanwendungen (unter anderem) von Barton (der Link führt zu einer Liste von Veröffentlichungen), im Raumfahrzeugdesign und in globalen Optimierungsanwendungen (unter anderem) von Neumaier (der Link führt wiederum zu einer Liste von Veröffentlichungen) ), globale Optimierungs- und nichtlineare Gleichungslöser von Kearfott (eine weitere Liste von Veröffentlichungen) und zur Quantifizierung der Unsicherheit (verschiedene Quellen; Barton ist eine davon).

Zum Schluss noch ein Disclaimer: Barton ist einer meiner Diplomarbeitsberater.

Die Intervallarithmetik liefert Ihnen einen Beweis mit mathematischer Genauigkeit.

Gute Beispiele für konkrete Anwendungen sind die Arbeiten von Mark Stadtherr und seiner Forschungsgruppe. Insbesondere werden Phasengleichgewichts- und Stabilitätsberechnungen mit Intervallmethoden erfolgreich gelöst.

Eine schöne Sammlung von Benchmarks mit Bezug auf ihren physischen Hintergrund finden Sie auf der ALIAS-Website .

Ein weiteres Merkmal der Intervallarithmetik und ihrer Verallgemeinerungen besteht darin, dass sie eine adaptive Untersuchung des Bereichs einer Funktion ermöglicht. Es kann somit zur adaptiven geometrischen Modellierung, Verarbeitung und Wiedergabe verwendet werden, um nur Beispiele aus der Computergrafik zu entnehmen.

Intervallmethoden wurden in jüngster Zeit in einigen Beweisen für schwierige mathematische Theoreme verwendet, beispielsweise für die Existenz von Chaos im Lorenz-Attraktor und in der Kepler-Vermutung. Informationen zu diesen und anderen Anwendungen finden Sie unter http://www.cs.utep.edu/interval-comp/kearfottPopular.pdf .

Intervallarithmetik ist sehr nützlich für geometrische Algorithmen. Solche geometrischen Algorithmen nehmen eine Menge von geometrischen Objekten (z. B. eine Menge von Punkten) als Eingabe und konstruieren eine kombinatorische Datenstruktur (z. B. eine Triangulation) basierend auf räumlichen Beziehungen zwischen den Punkten. Diese Algorithmen hängen von einer kleinen Anzahl von Funktionen ab, die als "Prädikate" bezeichnet werden, die eine feste Anzahl von geometrischen Objekten als Eingabe verwenden und einen diskreten Wert zurückgeben (normalerweise einer von "oben, ausgerichtet, unten"). Solche Prädikate entsprechen typischerweise dem Vorzeichen einer Determinante der Punktkoordinaten.

Die Verwendung von Standard-Gleitkommazahlen ist nicht ausreichend, da sie möglicherweise das Vorzeichen der Determinante nicht genau berechnen und noch schlimmer inkohärente Ergebnisse zurückgeben (dh, dass A über B und B über A liegt, sodass der Algorithmus a erstellt Chaos statt Masche!). Die systematische Verwendung von Multipräzision (wie in der Gnu Multipräzisionsbibliothek und ihrer MPFR-Erweiterung auf Multipräzisions-Gleitkommazahlen) funktioniert, verursacht jedoch erhebliche Leistungseinbußen. Wenn das geometrische Prädikat das Vorzeichen von etwas ist (wie in den meisten Fällen), können Sie mit Intervallarithmetik eine schnellere Berechnung durchführen und dann nur dann die umfangreichere Berechnung mit mehreren Genauigkeiten starten, wenn sich Null im Intervall befindet.

Ein solcher Ansatz wird in mehreren großen Berechnungsgeometriecodes (z. B. CGAL) verwendet.