MN04

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania


Własności zadania obliczeniowego i algorytmu numerycznego

<<< Powrót do strony głównej przedmiotu Metody numeryczne

Uwarunkowanie zadania obliczeniowego

Jak zobaczyliśmy w poprzednich przykładach, dane, jakimi dysponujemy wykonując zadanie obliczeniowe, są z natury rzeczy wartościami zaburzonymi. Źródłem tych zaburzeń są:

  • błąd reprezentacji danych w arytmetyce zmiennoprzecinkowej (np. 0.1 nie jest równe dokładnie )
  • błędy w parametrach będących rezultatem poprzednich obliczeń (np. chcemy rozwiązać równanie , ale jest rezultatem innej symulacji), a także
  • błędy pomiarowe w zadaniach praktycznych (np. chcemy policzyć numeryczną prognozę pogody, ale temperaturę wyjściową znamy tylko z dokładnością do 0.1 stopnia, co gorsza --- z niektórych stacji w ogóle nie mamy danych)

Okazuje się, że powszechna intuicja, że małe zaburzenia danych powinny dawać małe zaburzenia wyniku, nie znajduje potwierdzenia nawet w bardzo prostych przypadkach. Z drugiej strony, umiejętność oceny jakościowego wpływu zaburzenia danych na wynik jest kapitalna w świecie obliczeń numerycznych w ogólności, a w szególności --- inżynierskich.

Wprowadza się pojęcie uwarunkowania zadania, to znaczy jego podatności na zaburzenia danych. Dla przejrzystości przypuśćmy, że nasze zadanie obliczeniowe polega na wyznaczeniu dla danego .


Jak bardzo będzie odległe , gdy ? Rozważa się dwa przypadki:

  • uwarunkowanie względne: jak względne zaburzenie danych wpływa na błąd względny wyniku:

Najmniejszy mnożnik spełniający powyższą nierówność nazywamy współczynnikiem uwarunkowania (względnego) zadania obliczenia dla danego .

  • uwarunkowanie bezwzględne: jak bezwzględne zaburzenie danych wpływa na błąd bezwzględny wyniku:

Najmniejszy mnożnik spełniający powyższą nierówność nazywamy współczynnikiem uwarunkowania (bezwzględnego) zadania obliczenia dla danego .

Powiemy, że zadanie jest

  • dobrze uwarunkowane w punkcie , gdy ,
  • źle uwarunkowane w punkcie , gdy ,
  • źle postawione w punkcie , gdy .

Teraz już rozumiemy, że redukcja cyfr przy odejmowaniu jest tylko odzwierciedleniem faktu, że zadanie odejmowania dwóch bliskich liczb jest po prostu zadaniem źle uwarunkowanym!

Przykład: Uwarunkowanie zadania obliczenia sumy

Właściwie już wcześniej sprawdziliśmy, że zadanie obliczenia ma

Tak więc, gdy , to i zadanie jest bardzo źle uwarunkowane. Nawet małe zaburzenie względne danych może skutkować bardzo dużym zaburzeniem wyniku. Zgodnie z prawem Murphy'ego, najczęściej rzeczywiście tak będzie...

Przykład

Dla różniczkowalnej funkcji skalarnej mamy

i w konsekwencji dla zadania obliczenia dla danego mamy, przy założeniu małych zaburzeń,

Jest zrozumiałe, że złe uwarunkowanie jest szkodliwe w praktyce numerycznej: zaburzenia danych są nieuniknione, a źle uwarunkowane zadanie tylko je wzmocni na wyjściu. Jednak za jakiś czas zobaczysz wyjątkową sytuację, gdy złe uwarunkowanie pewnego podzadania nie tylko nie przeszkadza, ale wręcz pomaga szybciej rozwiązać zadanie główne!

Rozkład algorytmu względem informacji

Algorytm to dokładnie określona i dozwolona w danym modelu obliczeniowym sekwencja akcji, pozwalająca na rozwiązanie danego zadania (w sposób dokładny lub przybliżony).

Z każdym algorytmem związany jest operator

taki że jest wynikiem działania algorytmu w arytmetyce idealnej dla danej .

Zauważmy, że wynik działania algorytmu nie zależy bezpośrednio od , ale raczej od informacji o (uzyskanej dzięki poleceniu ). Informacja ta może być pełna albo tylko częściowa. Informacja jest pełna gdy, np. i wczytamy wszystkie współrzędne . Informacja może być częściowa, gdy jest funkcją. Wtedy wiele danych może posiadać tę samą informację, co łatwo zaobserwować na przykładzie zadania całkowania.

Niech będzie operatorem informacji, tzn.

jest informacją o zebraną przy idealnej realizacji algorytmu. Zauważmy, że informacja jest pełna, gdy jest przekształceniem różnowartościowym, tzn. jeśli implikuje . W przeciwnym przypadku mamy do czynienia z informacją częściową.

Każdy algorytm może być przedstawiony jako złożenie operatora informacji i pewnego operatora zdefiniowanego równością

Zauważmy, że w przypadku informacji częściowej zwykle nie istnieje algorytm dający dokładne rozwiązanie zadania dla każdej danej , ponieważ dla danych o tej samej informacji mogą istnieć różne rozwiązania.

Problem wyboru algorytmu

Wybór algorytmu jest najistotniejszą częścią całego procesu numerycznego rozwiązywania zadania. Kierujemy się przy tym przede wszystkim następującymi kryteriami:

  • dokładnością algorytmu,
  • złożonością algorytmu,
  • własnościami numerycznymi algorytmu.

Przez dokładność algorytmu rozumiemy różnicę między rozwiązaniem dokładnym a rozwiązaniem dawanym przez algorytm w arytmetyce idealnej. Jeśli , , to algorytm nazywamy dokładnym.

Mówiąc o złożoności, mamy na myśli złożoność pamięciową (zwykle jest to liczba stałych i zmiennych używanych przez algorytm), jak również złożoność obliczeniową. Na złożoność obliczeniową algorytmu dla danej składa się koszt uzyskania infomacji (zwykle jest on proporcjonalny do liczby wywołań polecenia ), oraz koszt kombinatoryczny przetworzenia tej informacji, aż do uzyskania wyniku . Koszt kombinatoryczny zwykle mierzymy liczbą operacji arytmetycznych wykonywanych przez algorytm.

Przez własności numeryczne algorytmu rozumiemy jego własności przy realizacji w arytmetyce . Temu ważnemu tematowi poświęcimy teraz osobny paragraf.

Numeryczna poprawność algorytmu

Pożądane jest, aby algorytm dawał "dobry" wynik zarówno w arytmetyce idealnej, jak i w arytmetyce . Niestety, jak zobaczymy, nie zawsze jest to możliwe. Nawet jeśli algorytm jest dokładny, to w wyniku jego realizacji w możemy otrzymać wynik daleko odbiegający od . W szczególności, prawie zawsze mamy

Zauważmy również, że o ile z reguły znamy dokładne zachowanie się algorytmu w arytmetyce idealnej dla danej informacji, to nie można tego samego powiedzieć o jego zachowaniu się w arytmetyce . W związku z tym powstaje pytanie, jak kontrolować błąd algorytmów wynikający z błędów zaokrągleń i jakie algorytmy uznamy za te o najwyższej jakości numerycznej.

Istnienie błędów reprezentacji liczb rzeczywistych powoduje, że informacja o danej nie jest w ogólności reprezentowana dokładnie. Znaczy to, że zamiast na informacji dokładnej, dowolny algorytm będzie operować na informacji nieco zaburzonej , tzn. zaburzonej na poziomie błędu reprezentacji. Tak samo wynik dawany przez algorytm będzie w ogólności zaburzony na poziomie błędu reprezentacji. W najlepszym więc wypadku wynikiem działania algorytmu w będzie zamiast . Algorytmy dające tego rodzaju wyniki uznamy za posiadające najlepsze własności numeryczne w arytmetyce i nazwiemy numerycznie poprawnymi.

Powiemy, że ciąg rzeczywisty (a właściwie rodzina ciągów ) jest nieco zaburzonym ciągiem , jeśli istnieje stała taka, że dla wszystkich dostatecznie małych zachodzi

albo ogólniej

gdzie jest pewną normą w . W pierwszym przypadku mówimy o zaburzeniu "po współrzędnych", a w drugim o zaburzeniu w normie .

Zauważmy, że niewielkie zaburzenia po współrzędnych pociągają za sobą niewielkie zaburzenia w normie. Rzeczywiście, zachodzi wówczas

i korzystając z faktu, że w przestrzeni skończenie wymiarowej wszystkie normy są równoważne, otrzymujemy dla pewnych stałych i

czyli nierówność dla zaburzenia w normie, ze stałą .

Definicja Algorytm numerycznie poprawny

Algorytm rozwiązywania zadania nazywamy numerycznie poprawnym w zbiorze danych , jeśli dla każdej danej wynik działania algorytmu w arytmetyce można zinterpretować jako nieco zaburzony wynik algorytmu w arytmetyce idealnej dla nieco zaburzonej informacji o , przy czym poziom zaburzeń nie zależy od .

Formalnie znaczy to, że istnieją stałe , oraz takie, że spełniony jest następujący warunek. Dla dowolnej oraz informacji można dobrać oraz takie, że

oraz

Numerycznie poprawny algorytm daje w arytmetyce wynik , który daje się zinterpretować jako mało zaburzony wynik zadania na mało zaburzonych danych .

Zauważmy,że jeśli , , oraz algorytm jest dokładny, , to numeryczną poprawność algorytmu można równoważnie zapisać jako

Numeryczna poprawność algorytmu jest wielce pożądaną cechą.

Algorytm numerycznie poprawny działa w arytmetyce zmiennoprzecinkowej (niemal) tak, jakby wszystkie obliczenia były wykonywane w arytmetyce dokładnej, a tylko dane i wyniki podlegały reprezentacji w skończonej precyzji.

Rola uwarunkowania zadania

Niech będzie algorytmem numerycznie poprawnym dla danych . Wtedy jego błąd w można oszacować następująco:

przy czym . Stąd w szczególności wynika, że jeśli algorytm jest numerycznie poprawny i ciągły ze względu na informację , to

To znaczy, że dla dostatecznie silnej arytmetyki algorytm będzie się zachowywał w prawie tak, jak w arytmetyce idealnej.

Z powyższych wzorów wynika, że błąd w algorytmu numerycznie poprawnego zależy w dużym stopniu od:

  • dokładności algorytmu w arytmetyce idealnej,
  • dokładności arytmetyki ,
  • wrażliwości algorytmu na małe względne zaburzenia informacji .

Ponieważ dwa pierwsze punkty są raczej oczywiste, poświęcimy trochę więcej uwagi jedynie trzeciemu.

Jeśli spełnia warunek Lipschitza ze stałą , a dokładniej

to

W tym przypadku błędy zaokrągleń zwiększają błąd bezwzględny algorytmu proporcjonalnie do .

Bardziej jednak interesuje nas błąd względny. Wybierzmy "małe" i przypuśćmy, że

dla pewnej niezależnej od , tzn. błąd względny informacji, , przenosi się na błąd względny wyniku (w arytmetyce idealnej) ze "współczynnikiem wzmocnienia" , albo na błąd bezwzględny ze współczynnikiem . (Zauważmy, że gdybyśmy wzięli , to dla takiej, że , musiałoby być --- co zwykle, choć nie zawsze, nie jest prawdą.) Wtedy

W szczególności, gdy algorytm jest dokładny i korzysta z pełnej informacji o , tzn. , to błąd

Stąd wynika, że jeśli , to błąd względny algorytmu w jest mały, o ile . Błąd względny jest proporcjonalny do dokładności , arytmetyki , współczynników proporcjonalności algorytmu numerycznie poprawnego, oraz do wrażliwości zadania na małe względne zaburzenia danych.

Zwróćmy uwagę na istotny fakt, że interesują nas właściwie tylko te zaburzenia danych (informacji), które powstają przy analizie algorytmu numerycznie poprawnego. I tak, jeśli algorytm jest numerycznie poprawny z pozornymi zaburzeniami danych w normie, to trzeba zbadać wrażliwość zadania ze względu na zaburzenia danych w normie. Jeśli zaś mamy pozorne zaburzenia "po współrzędnych" (co oczywiście implikuje pozorne zaburzenia w normie) to wystarczy zbadać uwarunkowanie zadania ze względu na zaburzenia "po współrzędnych", itd.

Przykład: Iloczyn skalarny

Załóżmy, że dla danych ciągów rzeczywistych o ustalonej długości , , , , chcemy obliczyć

Rozpatrzymy algorytm dokładny zdefiniowany powyższym wzorem i korzystający z pełnej informacji o kolejnych współrzednych.

Oznaczmy przez i reprezentacje liczb i w , , , oraz przez i błędy względne powstałe przy kolejnych mnożeniach i dodawaniach. Oczywiście . Otrzymujemy

gdzie w przybliżeniu (tzn. gdy ) mamy i , . Algorytm naturalny jest więc numerycznie poprawny w całym zbiorze danych, gdyż wynik otrzymany w można zinterpretować jako dokładny wynik dla danych i , przy czym .

Zobaczmy teraz, jak błąd we współrzędnych wpływa na błąd wyniku. Mamy

Stąd dla

gdzie

Zauważmy, że jeśli iloczyny są wszystkie dodatnie albo wszystkie ujemne, to , tzn. zadanie jest dobrze uwarunkowane, a błąd względny jest zawsze na poziomie co najwyżej . W tym przypadku algorytm zachowuje się bardzo dobrze, o ile liczba składników nie jest horrendalnie duża. W ogólności jednak może być liczbą dowolnie dużą i wtedy nie możemy być pewni uzyskania dobrego wyniku w .


Literatura

W celu dogłębnego zapoznania się z omawianym na wykładzie materiałem, przeczytaj rozdział 2.3 w

  • D. Kincaid, W. Cheney Analiza numeryczna, Wydawnictwa Naukowo-Techniczne, Warszawa 2006, ISBN 83-204-3078-X.

Warto także przejrzeć rozdział 2 w

  • P. Deulfhard, A. Hohmann, Numerical Analysis in Modern Scientific Computing, Springer, 2003,

omawiający zagadnienia uwarunkowania i numerycznej poprawności algorytmów. Nieocenioną monografią na ten temat jest

  • N. Higham, Accuracy and Stability of Numerical Algorithms, SIAM, 2002.