Jak rozpoznać niestabilne obliczenia zmiennoprzecinkowe?

15

W numeryce bardzo ważna jest umiejętność identyfikowania niestabilnych schematów i poprawy ich stabilności. Jak rozpoznać niestabilne obliczenia zmiennoprzecinkowe?

Pracuję nad bardzo złożoną symulacją, w której współdziała wiele schematów numerycznych i szukam metody pozwalającej zidentyfikować jej słabe części. Pracuję nad modelem fizycznym obejmującym równania różniczkowe. Ogólny proces z lotu ptaka przedstawia:

  1. (Etap wstępny) gromadzenia obserwacje fizycznej P .

  2. Określ początkowe parametry symulacji. Wykorzystuje to algorytm optymalizacyjny, w którym chodzimy w przestrzeni parametrów i szukamy parametrów C, tak że niektóre funkcje błędu E (F (C), P) są zminimalizowane, gdzie F jest pewną pochodną ilością parametrów.

  3. Podłącz C do silnika symulacyjnego. Jest to schemat Eulera EDP, dlatego na każdym etapie obliczamy warunki napędzające dynamikę (każda z nich jest złożoną funkcją, potencjalnie podlegającą niestabilności) i karmimy schemat Eulera tymi dynamicznymi terminami, aby obliczyć następny stan. Trwa to przez tysiące punktów czasowych.

  4. Pod koniec symulacji obliczamy pewną funkcję Dowód (S) stanu końcowego S i porównujemy z pewnymi wielkościami Wymagaj (P) wyprowadzonymi z obserwowanych wielkości. To nie jest formalny dowód wyniku, a bardziej kontrola wiarygodności.

Widzę też wieżę złożonych operacji (obliczanie dynamicznych terminów, w ramach schematu Eulera, w Dowodzie ). I chciałby rozpoznać „złe części” i naprawić je.

Spekuluję, że zastosowanie implementacji liczb zmiennoprzecinkowych ze zmniejszoną precyzją zwiększyłoby niestabilność schematów numerycznych, ułatwiając w ten sposób porównanie różnych implementacji. Czy jest to powszechna technika badania tego pytania? Czy można użyć maszyny wirtualnej, takiej jak Bochs, aby to osiągnąć bez zmiany programu?

Aby odpowiednio poradzić sobie z pytaniem o stabilność, czasami dopuszczalne jest ukierunkowanie na typowe dane wejściowe procedury numerycznej, aby można było dostroić się do tego wejścia, a może gorzej przy innych prawidłowych, ale mało prawdopodobnych danych wejściowych. Biorąc pod uwagę próbę typowych danych wejściowych, można schwytać niektóre wyniki pośrednie i przygotować dla nich profil statystyczny. Ponownie, czy jest to powszechna technika badania problemów ze stabilnością? Czy maszyna wirtualna jest do tego przydatna?

użytkownik40989
źródło
być może będziesz miał więcej ciekawych odpowiedzi na math.stackexchange.com
Simon Bergot
@ Simon Być może masz rację, ale z pewnością jest to pytanie między domenami. Sądzę, że osoby, które potrafią odpowiedzieć, są zarejestrowane zarówno dla matematyki, jak i dla programistów lub dla nikogo… Poczekajmy trochę, czy to pytanie znajdzie odpowiedź tutaj!
user40989,
1
Arytmetyka interwałowa?
SK-logic,
2
Używanie Eulera do propagowania stanu niekoniecznie jest złem; nie jest też optymalizacja, ale naprawdę musisz podzielić problem na podzadania. Niestabilność numeryczna może być najmniejszą z twoich nieszczęść - konwergencja do fałszywego maksimum i problemy związane ze sztywnością ODE / PDE są większe. I tak, nigdy nie używaj pojedynczej precyzji :)
Deer Hunter,

Odpowiedzi:

6

Badanie stabilności obliczeń zmiennoprzecinkowych jest częścią analizy numerycznej i jeśli naprawdę chcesz uzyskać dobry wynik, naprawdę chcesz, aby ktoś posiadający wiedzę w tej dziedzinie przeprowadził analizę zastosowanych algorytmów.

Istnieje kilka rzeczy, które mogą pomóc w eksperymentalnej identyfikacji niestabilnych algorytmów. Uruchamianie z zaokrąglaniem ustawionym na różne tryby (w górę / w dół / losowo) lub z różną precyzją i sprawdzanie, czy wynik nie różni się zbytnio. Odpowiedź to za dużo? wcale nie jest proste, a nawet jeśli odpowiedź brzmi „ nie” , nie oznacza to, że algorytm jest stabilny, tylko że nie został wykryty jako niestabilny na użytym zestawie danych.

Arytmetyka przedziałowa została zaproponowana w komentarzach. Kiedy na to spojrzałem, nawet najbardziej wściekły zwolennik arytmetyki przedziałowej przyznał, że działał dobrze z algorytmami zaprojektowanymi dla arytmetyki przedziałowej, ale przejście do niej bez analizy algorytmu i upewnienia się, że nie ma wzorców, o których wiadomo, że nie działa dobrze być użytecznym (przeciwnicy wydawali się zdania, że ​​warunki wstępne dla arytmetyki przedziałowej są użyteczne tam, gdzie są zbyt restrykcyjne, aby były praktyczne)

AProgrammer
źródło
3

Projektowanie stabilnych algorytmów zmiennoprzecinkowych jest wysoce nietrywialne. Osoby bardziej wykwalifikowane matematycznie ode mnie sugerują, aby w miarę możliwości używać dobrze uznanych bibliotek, zamiast próbować tworzyć własne. Standardowe odniesienie w tym obszarze wydaje się:

NJ Higham. Dokładność i stabilność algorytmów numerycznych. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, drugie wydanie, 2002. ISBN 0-89871-521-0

Brak wiedzy na temat rodzajów obliczeń, języków itp. Utrudnia udzielenie konkretnej odpowiedzi. Jest tu dobry wykład: http://introcs.cs.princeton.edu/java/91float/. Może to być trochę podstawowe, ale jest to dobre wprowadzenie, jeśli używasz Java.

WPrecht
źródło
1

Jak rozpoznać niestabilne obliczenia zmiennoprzecinkowe? Czy jest to powszechna technika badania tego pytania?

Myślę, że chyba że musisz pokazać statystyki dotyczące błędów, tak naprawdę nie musisz zbierać próbek. Potrzebujesz analizy numerycznej , która również podlega Metodom numerycznym, Numerycznej algebrze liniowej itp. I są one częścią informatyki, więc możesz również uzyskać odpowiedzi w cs.stackexchange.

W każdym razie, w programowaniu ogólnym, większość problemów jest łatwa do zauważenia, biorąc pod uwagę podstawowe zrozumienie działania zmiennoprzecinkowego i podstawowych metod numerycznych. Ale nawet bardziej złożone problemy są „łatwiejsze” do rozwiązania dzisiaj dzięki dostępności 128-bitowych liczb zmiennoprzecinkowych, tym mniej powodów do tworzenia próbek błędów. Oto kilka przykładowych problemów, które pokazują mój punkt widzenia:

  1. przy użyciu zmiennoprzecinkowego do obliczania wartości pieniężnych
  2. używając zmiennoprzecinkowego dla dużych liczb.
  3. nie robienie podziałów przed innymi operacjami, jeśli jest to możliwe. (aby zbliżyć wartość do 0).
  4. długie obliczenia bez specjalnego traktowania w zakresie propagacji błędów.

Jest też przykład naiwnego algorytmu i algorytmu z kompensacją błędów algorytm obliczania wariancji . W tym przykładzie, patrząc na naiwną wersję, można poczuć, że wykonywanie obliczeń w pętlach niesie ze sobą pewne błędy i nie jest kompensowane.

imel96
źródło
Dziękuję za odpowiedź, szukam jednak bardziej szczegółowych informacji. Mam bardzo duże obliczenia i chcę zidentyfikować jego słabe części. Zredagowałem to pytanie odpowiednio.
user40989,
Nie jestem do końca pewien, jaka jest twoja sytuacja, kiedy mówisz, że masz duże obliczenia i chcesz zidentyfikować słabe części. Obliczenia numeryczne z natury zawierają błędy, nawet jedną prostą operację dodawania. Tak więc, chyba że twoje duże obliczenia są skompensowane błędem, to należy je naprawić jako całość. Poprawianie słabszych miejsc może nie być wystarczająco dobre. Jeśli teraz masz „epsilon” modelu zmiennoprzecinkowego, prosta analiza pokaże, jak duży może być błąd podczas rozprzestrzeniania się przez długie obliczenia.
imel96
0

Można uniknąć błędów numerycznych, stosując odpowiednie typy danych (np. Ciągłe ułamki). Jeśli potrzebujesz lub chcesz użyć arytmetyki zmiennoprzecinkowej, musisz zastosować wiedzę numeryczną, aby poznać błędy.

Ingo
źródło
Nie chcę unikać błędów numerycznych, chcę dowiedzieć się, które części obliczeń są niestabilne. Jest to podobne do lokalizowania wąskich gardeł prędkości podczas optymalizacji prędkości. Chcę więc zoptymalizować precyzję i dlatego chcę znaleźć wąskie gardła. (Dalsze ułamki nie są tu przydatne.)
user40989,
1
@ user40989, to zdecydowanie potrzebujesz arytmetyki interwałów.
SK-logic