Jakie aplikacje wymagają arytmetyki przedziałowej?

Mam bardzo podstawowe pojęcie na temat arytmetyki interwałowej (IA), ale wydaje się, że jest to bardzo interesująca gałąź nauki obliczeniowej zarówno teoretycznie, jak i praktycznie. Oczywiste jest, że oczywiste aplikacje to sprawdzone obliczenia i źle postawione problemy, ale jest to zbyt abstrakcyjne. Ponieważ w obliczeniach stosowanych jest wiele osób, jestem ciekawy problemów w świecie rzeczywistym, które są trudne lub niemożliwe do rozwiązania bez IA .

Ta odpowiedź częściowo odpowiada na komentarz JackPoulson (ponieważ jest długi), a częściowo odpowiada na pytanie.

Arytmetyka przedziałowa jest procedurą obliczeniową, która daje rygorystyczne granice wielkości obliczonych, tylko w tym sensie, że przedłużenie przedziału funkcji o wartościach rzeczywistych w przedziale otacza obraz tej funkcji w tym samym przedziale. Bez niczego obliczania arytmetyka przedziałowa nie może dać ci żadnego wglądu w to, jakie czynniki wpływają na błąd numeryczny w obliczeniach, podczas gdy twierdzenia w książce Highama i innych dają ci wgląd w czynniki wpływające na błąd numeryczny, kosztem potencjalnie słabych granic. To prawda, że ​​granice uzyskane za pomocą arytmetyki przedziałowej mogą być również słabe z powodu tak zwanego problemu zależności , ale czasami są znacznie silniejsze. Na przykład granice przedziałów uzyskane za pomocą pakietu integracyjnego COSY Infinitysą znacznie ściślejsze niż typy granic błędów, które można uzyskać przy integracji numerycznej z wyników Dahlquist (szczegółowe informacje można znaleźć w Hairer, Wanner i Nørsett ); wyniki te (szczególnie odnoszę się do Twierdzeń 10.2 i 10.6 w Części I) dają więcej wglądu w źródła błędów, ale granice są słabe, podczas gdy granice przy użyciu COSY mogą być ciasne. (Używają kilku sztuczek, aby złagodzić problemy z zależnościami).

Waham się przed użyciem słowa „dowód” przy opisywaniu działania arytmetyki przedziałowej. Istnieją dowody dotyczące arytmetyki przedziałowej, ale obliczanie wyników za pomocą arytmetyki przedziałowej z zaokrąglaniem na zewnątrz jest tak naprawdę tylko sposobem prowadzenia księgowości w celu konserwatywnego ograniczenia zakresu funkcji. Obliczenia arytmetyczne interwałowe nie są dowodami; są sposobem na propagowanie niepewności.

Jeśli chodzi o aplikacje, oprócz pracy Stadtherr w inżynierii chemicznej, arytmetyka interwałowa została również wykorzystana do obliczenia granic eksperymentów z wiązką cząstek (patrz praca Makino i Berza, połączona ze stroną internetową COSY Infinity), zostały one wykorzystywane w globalnej optymalizacji i aplikacjach do projektowania inżynierii chemicznej (między innymi) przez Bartona (link do listy publikacji), projektowanie statków kosmicznych i optymalizacji globalnej (między innymi) przez Neumaiera (ponownie link do listy publikacji ), optymalizacja globalna i rozwiązywanie równań nieliniowych Kearfott (inna lista publikacji) oraz kwantyfikacja niepewności (różne źródła; jednym z nich jest Barton).

Wreszcie zastrzeżenie: Barton jest jednym z moich doradców.

Arytmetyka interwałowa daje dowód z matematyczną dyscypliną.

Dobrym przykładem rzeczywistych zastosowań jest praca Marka Stadtherra i jego grupy badawczej. W szczególności z powodzeniem rozwiązuje się obliczenia równowagi faz i stabilności metodami interwałowymi.

Ładna kolekcja benchmarków, w odniesieniu do ich fizycznego pochodzenia, znajduje się na stronie ALIAS .

Inną cechą arytmetyki przedziałowej i jej uogólnień jest to, że umożliwia ona adaptacyjne badanie dziedziny funkcji. Można go zatem wykorzystać do adaptacyjnego modelowania geometrycznego, przetwarzania i renderowania, aby wziąć przykłady z grafiki komputerowej.

Metody interwałowe pojawiły się w niektórych najnowszych dowodach twardych twierdzeń matematycznych, takich jak istnienie chaosu w atraktorze Lorenza i hipotezie Keplera. Zobacz http://www.cs.utep.edu/interval-comp/kearfottPopular.pdf dla tych i innych aplikacji.

Arytmetyka interwałowa jest bardzo przydatna w przypadku algorytmów geometrycznych. Takie algorytmy geometryczne przyjmują jako dane wejściowe zestaw obiektów geometrycznych (np. Zbiór punktów) i konstruują kombinatoryczną strukturę danych (np. Triangulację) w oparciu o relacje przestrzenne między punktami. Algorytmy te zależą od niewielkiej liczby funkcji, zwanych „predykatami”, które przyjmują jako dane wejściowe stałą liczbę obiektów geometrycznych i zwracają wartość dyskretną (zazwyczaj jedną z „powyżej, wyrównane, poniżej”). Takie predykaty zazwyczaj odpowiadają znakowi wyznacznika współrzędnych punktu.

Użycie standardowych liczb zmiennoprzecinkowych nie jest wystarczające, ponieważ może nie być w stanie dokładnie obliczyć znaku wyznacznika, a co gorsza, zwrócić niespójne wyniki (tj. Powiedzieć, że A jest powyżej B, a B jest powyżej A, co powoduje, że algorytm tworzy bałagan zamiast siatki!). Systematyczne stosowanie wieloprecyzyjnego (takiego jak w bibliotece Gnu Multi-Precision i jego rozszerzenia MPFR do wieloprecyzyjnych liczb zmiennoprzecinkowych) działa, ale powoduje znaczny spadek wydajności. Gdy predykat geometryczny jest znakiem czegoś (jak w większości przypadków), użycie arytmetyki przedziałowej pozwala wykonać szybsze obliczenia, a następnie uruchomić bardziej ekspansywne obliczenia wieloprecyzyjne, jeśli zero jest w przedziale.

Takie podejście stosuje się w kilku dużych kodach geometrii obliczeniowej (np. CGAL).