Jak rozpoznać niestabilne obliczenia zmiennoprzecinkowe?

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?

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)

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.

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.

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.