P4180004

2.3.2. NUMERYCZNA POPRAWNOŚĆ ALGORYTMU

Za numerycznie poprawne uważa się algorytmy, które spełniają pewne realistyczne wymagania co do wartości wnoszonych przez nie błędów. Nie chodzi na ogół o to, aby utrzymać te błędy na poziomie eps czy jakiejś niewielkiej krotności eps , ale o to, aby te błędy pozostawały w praktycznie akceptowalnym stosunku do błędów wnoszonych przez dane. Dla użytkownika wyników obliczeń na ogół obojętne jest bowiem źródło ich błędów, liczy się tylko ich sumaryczna wartość. Za realistyczne należy zatem uznać wymaganie, aby błędy wnoszone przez algorytm były małe dla tych danych, dla których małe są błędy wnoszone przez dane. Wymaganie to leży u podstaw następującego określenia numerycznej poprawności: algorytm jest numerycznie poprawny, jeżeli dla dokładnych danych dostarcza rozwiązań będących dokładnymi rozwiązaniami zadania dla „nieco” zaburzonych danych [J1 ].

Przykład 2.8. Algorytm obliczania wartości wyrażenia y - x+ x\ jest numerycznie poprawny, ponieważ:

y - [*? 0+rii)+*2 (i⁺ ^2)] 0+n.) a zgodnie z regułą (2. lOa):

+^t1i+tU + *2²(^{1 + t}1i^+tO] zaś zgodnie z regułą (2. lOb):

	/ i | v	2	/ i j y^2
y ~	.T^+2^n' ^+ 2^,1*J.	+	H^1 + 2^Th + 2^T,*J.

Z tego ostatniego wyrażenia wynika, że skutek błędów zaokrągleń wyników podnoszenia do kwadratu i sumowania jest taki sam jak skutek zaburzenia danych na poziomie eps.

Metoda badania numerycznej poprawności algorytmu, zastosowana w przykładzie 2.8, nie zawsze prowadzi do rozstrzygnięcia. Jeżeli nie udaje się wyznaczyć zastępczych zaburzeń danych, których skutek byłby równoważny wpływowi na wynik błędów zaokrągleń, to nie można stąd wyciągać wniosku, że algorytm jest numerycznie niepoprawny. Można jedynie domniemywać, że tak jest i podjąć próbę potwierdzenia tej hipotezy na drodze poszukiwania takiego przykładu danych w zbiorze D, dla którego błąd spowodowany zaokrągleniami rośnie nie-ograniczenie, chociaż błąd pochodzący od danych jest ograniczony.