Stabilność numeryczna
W matematycznej poddziedzinie analizy numerycznej stabilność numeryczna jest ogólnie pożądaną właściwością algorytmów numerycznych . Dokładna definicja stabilności zależy od kontekstu. Jednym z nich jest numeryczna algebra liniowa , a drugim algorytmy rozwiązywania równań różniczkowych zwyczajnych i cząstkowych za pomocą aproksymacji dyskretnej.
W numerycznej algebrze liniowej głównym problemem są niestabilności spowodowane bliskością różnego rodzaju osobliwości, takich jak bardzo małe lub prawie kolidujące wartości własne . Z drugiej strony w algorytmach numerycznych dla równań różniczkowych problemem jest wzrost błędów zaokrągleń i/lub niewielkie fluktuacje danych początkowych, które mogą powodować duże odchylenie ostatecznej odpowiedzi od dokładnego rozwiązania. [ potrzebne źródło ]
Niektóre algorytmy numeryczne mogą tłumić niewielkie fluktuacje (błędy) danych wejściowych; inni mogą powiększać takie błędy. Obliczenia, co do których można udowodnić, że nie powiększają błędów aproksymacji, nazywane są numerycznie stabilnymi . Jednym z typowych zadań analizy numerycznej jest próba wybrania algorytmów, które są solidne – to znaczy nie dają bardzo różnych wyników przy bardzo małej zmianie danych wejściowych.
Przeciwnym zjawiskiem jest niestabilność . Zazwyczaj algorytm obejmuje metodę przybliżoną, aw niektórych przypadkach można udowodnić, że algorytm zbliżyłby się do właściwego rozwiązania w pewnej granicy (przy użyciu rzeczywistych liczb rzeczywistych, a nie liczb zmiennoprzecinkowych). Nawet w tym przypadku nie ma gwarancji, że zbiegnie się do prawidłowego rozwiązania, ponieważ błędy zaokrągleń lub obcinania liczb zmiennoprzecinkowych można powiększyć zamiast tłumić, powodując wykładniczy wzrost odchylenia od dokładnego rozwiązania.
Stabilność w numerycznej algebrze liniowej
Istnieją różne sposoby sformalizowania pojęcia stabilności. Następujące definicje stabilności do przodu, do tyłu i stabilności mieszanej są często używane w numerycznej algebrze liniowej .
Rozważ problem, który ma zostać rozwiązany przez algorytm numeryczny, jako funkcję f odwzorowującą dane x na rozwiązanie y . Wynik algorytmu, powiedzmy y *, będzie zwykle odbiegał od „prawdziwego” rozwiązania y . Głównymi przyczynami błędów są błąd zaokrąglenia i błąd obcięcia . Błąd naprzód algorytmu to różnica między wynikiem a rozwiązaniem; w tym przypadku Δ y = y * - y . The błąd wsteczny jest najmniejszym Δ x takim, że f ( x + Δ x ) = y * ; innymi słowy, błąd wsteczny mówi nam, jaki problem faktycznie rozwiązał algorytm. Błąd do przodu i do tyłu są powiązane przez numer warunku : błąd do przodu jest co najwyżej tak duży, jak numer warunku pomnożony przez wielkość błędu wstecznego.
W wielu przypadkach bardziej naturalne jest rozważenie błędu względnego
Mówimy, że algorytm jest wstecznie stabilny , jeśli błąd wsteczny jest mały dla wszystkich danych wejściowych x . Oczywiście „mały” jest pojęciem względnym, a jego definicja będzie zależeć od kontekstu. Często chcemy, aby błąd był tego samego rzędu lub tylko o kilka rzędów wielkości większy niż zaokrąglenie jednostek .
Zwykła definicja stabilności liczbowej wykorzystuje bardziej ogólną koncepcję, zwaną stabilnością mieszaną , która łączy błąd w przód i błąd w tył. W tym sensie algorytm jest stabilny, jeśli w przybliżeniu rozwiązuje pobliski problem, tj. jeśli istnieje Δ x takie, że zarówno Δ x jest małe, jak i f ( x + Δ x ) − y * jest małe. Dlatego algorytm stabilny wstecz jest zawsze stabilny.
Algorytm jest stabilny w przód , jeśli jego błąd w przód podzielony przez numer warunku problemu jest mały. Oznacza to, że algorytm jest stabilny w przód, jeśli ma błąd w przód o wielkości podobnej do niektórych algorytmów stabilnych wstecz.
Stabilność w numerycznych równaniach różniczkowych
Powyższe definicje są szczególnie istotne w sytuacjach, w których błędy obcięcia nie są istotne. W innych kontekstach, na przykład przy rozwiązywaniu równań różniczkowych , stosuje się inną definicję stabilności numerycznej.
W numerycznych równaniach różniczkowych zwyczajnych istnieją różne koncepcje stabilności numerycznej, na przykład A-stabilność . Wiążą się one z pewną koncepcją stabilności w układów dynamicznych , często stabilnością Lapunowa . Ważne jest, aby przy rozwiązywaniu sztywnego równania używać stabilnej metody .
Jeszcze inna definicja jest używana w numerycznych równaniach różniczkowych cząstkowych . Algorytm rozwiązywania liniowego ewolucyjnego równania różniczkowego cząstkowego jest stabilny, jeśli całkowita zmienność rozwiązania numerycznego w ustalonym czasie pozostaje ograniczona, gdy wielkość kroku dąży do zera. Twierdzenie o równoważności Laxa stwierdza, że algorytm jest zbieżny , jeśli jest spójny i stabilny (w tym sensie). Stabilność jest czasami osiągana przez uwzględnienie dyfuzji numerycznej . Dyfuzja liczbowa to termin matematyczny, który zapewnia, że zaokrąglenia i inne błędy w obliczeniach zostaną rozłożone i nie sumują się, powodując „wybuch” obliczeń. Analiza stabilności von Neumanna jest powszechnie stosowaną procedurą analizy stabilności schematów różnic skończonych w zastosowaniu do liniowych równań różniczkowych cząstkowych. Wyniki te nie dotyczą nieliniowych PDE, gdzie ogólna, spójna definicja stabilności jest skomplikowana przez wiele właściwości nieobecnych w równaniach liniowych.
Zobacz też
- Mikołaj J. Higham (1996). Dokładność i stabilność algorytmów numerycznych . Filadelfia: Towarzystwo Matematyki Przemysłowej i Stosowanej. ISBN 0-89871-355-2 .
- Richarda L. Burdena; J. Douglas Faires (2005). Analiza numeryczna (wyd. 8). USA: Thomson Brooks/Cole. ISBN 0-534-39200-8 .
- Mesnard, Olivier; Barba, Lorena A. (2017). „Odtwarzalna i powtarzalna obliczeniowa dynamika płynów: to trudniejsze niż myślisz” . Informatyka w nauce i inżynierii . 19 (4): 44–55. ar Xiv : 1605.04339 . Bibcode : 2017CSE....19d..44M . doi : 10.1109/MCSE.2017.3151254 . S2CID 11288122 .
