Welche Anwendungen erfordern Intervallarithmetik?

15

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 .

Faleichik
quelle

Antworten:

11

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.

Geoff Oxberry
quelle
Vielen Dank! Irgendeine Idee, wie gut Intervall-Arithmetik-Messen für EVD- und / oder SVD-Berechnung sind? Oder Krylov-Algorithmen?
Jack Poulson
1
Soweit ich weiß, kann man sich auf Eigenwerte oder Singularwerte beschränken. Ich bin nicht sicher, was Intervalleigenvektoren oder singuläre Vektoren bedeuten würden. Die letzte Veröffentlichung, die ich in einer renommierten Zeitschrift kenne, ist "Bounds on Real Eigenvalues ​​und Singular Values ​​of Interval Matrices" von Hladík, Daney und Tsigaridas in SIAM J. Matrix. Anal. Appl. (2010). Für die Lösung linearer Systeme ist dieses Buch die beste Referenz.
Geoff Oxberry
7

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 .

Ali
quelle
3
Ehrliche Frage: Inwiefern ist es strenger als die Art der Grenzen, die sich aus der klassischen Fehleranalyse ergeben, z. B. in Bezug auf die Genauigkeit und Stabilität numerischer Algorithmen von Higham ?
Jack Poulson
1
@JackPoulson: Ich habe versucht, Ihren Kommentar in meiner Antwort zu beantworten, zusammen mit einigen Referenzen.
Geoff Oxberry
1
Siehe auch Beweis von Vermutungen mit Intervallarithmetik von Andreas Frommer.
LHF
5

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 .

lhf
quelle
1
Das ist richtig; Die Unterteilung von Intervallen liefert genauere Ergebnisse, und diese Eigenschaft hilft bei der adaptiven Untersuchung des Bereichs einer Funktion.
Geoff Oxberry
@lhf Upvoted! Es ist eine Schande, dass ich die Theorembeweise und die Website von Prof. Kearfott vergessen habe. Danke für den Hinweis!
Ali
2

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.

BrunoLevy
quelle