Heurystyczna kontrola stabilności numerycznej

12

Załóżmy, że mam funkcję o wartościach rzeczywistych niektórych zmiennych które chcę ocenić liczbowo. Zasadniczo wzór na może zawierać produkty, racjonalności, funkcje transcendentalne itp. I będzie musiał długo badać analityczną stabilność numeryczną. Albo będzie to przynajmniej czasochłonne, aby zrobić to w praktyce. Załóżmy, że nie mam krótszego odpowiednika ze stabilnością gwarantowaną. Czy istnieje metodyczna procedura analizy stabilności numerycznejf(x1,,xN)xiff. Myślę o porównaniu go z wynikami arbitralnej precesji uzyskanymi za pomocą komputerowego systemu algebry. Powiedzmy, że funkcja zostanie zaimplementowana w języku C przy użyciu funkcji stdlib i pojedynczej lub podwójnej precyzji. Jakie ilości powinienem porównać, aby oszacować jakość aproksymacji przy skończonej prewencji? Jak określić wartości krytyczne zmiennych? Jak mogę wybrać kompilator i optymalizacje kompilatora, aby inne osoby mogły łatwo odtworzyć wyniki? ... Wiem, że ustawienie problemu jest prawdopodobnie ogólne, aby dać dobre odpowiedzi. Ale nadal uważam, że jest to powszechny problem w informatyce i zastanawiam się, czy istnieją odniesienia, które proponują standardy przeprowadzenia takiej analizy.

wysoki
źródło

Odpowiedzi:

7

To, czego szukasz, nazywa się „automatyczną analizą błędów” i jest przedmiotem rozdziału 26 książki Highama „Dokładność i stabilność algorytmów numerycznych”, wyd. 2, Wydawnictwo SIAM.

Jedną z technik, które opisuje, jest bezpośrednia optymalizacja wyszukiwania: spróbuj sformułować swój problem jako problem optymalizacji i użyj algorytmu optymalizacji, aby znaleźć współczynniki lub wartości parametrów, które maksymalizują lub minimalizują wielkość związaną z dokładnością twojego algorytmu / formuły. Używa przykładu czynnika wzrostu w eliminacji Gaussa (jaka matryca maksymalizuje ten czynnik wzrostu) lub pierwiastków sześciennych (jak odpowiedziałem w jednym z poprzednich pytań).

Sugerowałbym, abyście otrzymali kopię tej książki, przeczytali rozdziały wprowadzające i ten rozdział 26 oraz odnośniki do niego.

GertVdE
źródło
3

Oceń swoją funkcję kilka razy (zwykle wystarcza 3), a wszystkie dane wejściowe są nieco przypadkowo zaburzone o ulp. Odchylenie standardowe trzech wyników da przybliżoną (ale zwykle wystarczającą) miarę wrażliwości numerycznej. Możesz to porównać do oczekiwanej czułości z linearyzacji i utworzyć iloraz, aby uzyskać oszacowanie stabilności.±1

Zauważ, że stabilność numeryczna pyta, o ile gorszy jest rzeczywisty błąd przy ocenie konkretnego porównaniu do błędu oczekiwanego na podstawie analizy wrażliwości przy zmianie danych wejściowych o pm1 ulp; drugi błąd wyrażony w ulps określa stan problemu. Warunek może być bardzo słaby dla stabilnego algorytmu (przykład: blisko ), a stabilność może być słaba dla bardzo dobrze uwarunkowanej funkcji (przykład: blisko ).± 1 1 / x x = 0 1 / ( 1 - x ) - 1 / ( 1 + x ) x = 0x±11/xx=01/(1x)1/(1+x)x=0

Arnold Neumaier
źródło
0

To, co opisuje GertVdE, to błąd numeryczny. To może być to, czego szukasz, ale to nie to samo, co stabilność liczbowa, jak wskazano w tytule pytania. Stabilność numeryczna zasadniczo pyta, czy pobliskie wartości zmiennych wejściowych dają pobliskie wartości danych wyjściowych. Innymi słowy, czy formuła taka jakzachodzi dla pewnego umiarkowanego stałej . W tym celu możesz przeanalizować pochodną lub, jeśli twoja funkcja nie różni się gwałtownie pod względem właściwości w swojej domenie, po prostu wypróbuj to dla kilku par .C f x , ϵ

|f(x+ε)f(x)|C|ε|
Cfx,ϵ
Wolfgang Bangerth
źródło
Co można zrobić, jeśli funkcje różnią się znacznie w swojej domenie lub jeśli nie ma dostępnej możliwej pochodnej? Czy są jakieś inne techniki, czy też skończilibyśmy podejście Monte Carlo?
André
1
-1: Wyjaśniasz pojęcie warunku, a nie stabilności numerycznej.
Arnold Neumaier,