MN04

From Studia Informatyczne


Spis treści

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 \displaystyle 1/10)
  • błędy w parametrach będących rezultatem poprzednich obliczeń (np. chcemy rozwiązać równanie \displaystyle f(x) = a, ale \displaystyle a 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 \displaystyle f(x) dla danego \displaystyle x.


Jak bardzo będzie odległe \displaystyle f(\widetilde{x}), gdy \displaystyle \widetilde{x}\approx x? Rozważa się dwa przypadki:

  • uwarunkowanie względne: jak względne zaburzenie danych wpływa na błąd względny wyniku:
    \displaystyle  \frac{||f(x) - f(\widetilde{x})||}{||f(x)||} \leq  \mbox{cond} _{rel}(f,x) \cdot \frac{||x - \widetilde{x}||}{||x||}.

Najmniejszy mnożnik \displaystyle  \mbox{cond} _{rel}(f,x) spełniający powyższą nierówność nazywamy współczynnikiem uwarunkowania (względnego) zadania obliczenia \displaystyle f(x) dla danego \displaystyle x.

  • uwarunkowanie bezwzględne: jak bezwzględne zaburzenie danych wpływa na błąd bezwzględny wyniku:
    \displaystyle  ||f(x) - f(\widetilde{x})|| \leq  \mbox{cond} _{abs}(f,x) \cdot ||x - \widetilde{x}||.

Najmniejszy mnożnik \displaystyle  \mbox{cond} _{abs}(f,x) spełniający powyższą nierówność nazywamy współczynnikiem uwarunkowania (bezwzględnego) zadania obliczenia \displaystyle f(x) dla danego \displaystyle x.

Powiemy, że zadanie \displaystyle f(x) jest

  • dobrze uwarunkowane w punkcie \displaystyle x, gdy \displaystyle  \mbox{cond} (f,x) \approx 1,
  • źle uwarunkowane w punkcie \displaystyle x, gdy \displaystyle  \mbox{cond} (f,x) \gg 1,
  • źle postawione w punkcie \displaystyle x, gdy \displaystyle  \mbox{cond} (f,x) = +\infty.

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 \displaystyle s(x,y) = x + y ma

\displaystyle   \mbox{cond} _{abs}(s, (a,b)) = 1, \qquad  \mbox{cond} _{rel}(s, (a,b)) = \frac{|a|+|b|}{|a+b|}

Tak więc, gdy \displaystyle a\approx -b, to \displaystyle  \mbox{cond} _{rel}(s, (a,b)) \approx +\infty 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 \displaystyle f : R \rightarrow R mamy

\displaystyle  |f(x) - f(\widetilde{x})| \approx |f'(x) | | x - \widetilde{x} |

i w konsekwencji dla zadania obliczenia \displaystyle f(x) dla danego \displaystyle x mamy, przy założeniu małych zaburzeń,

\displaystyle   \mbox{cond} _{abs}( f, x) = |f'(x)|, \qquad  \mbox{cond} _{rel}( f, x) = \frac{|f'(x)|\cdot|x|}{|f(x)|}.

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

\displaystyle {\bf ALG}:\,F\longrightarrowG,

taki że \displaystyle {\bf ALG}(f) jest wynikiem działania algorytmu w arytmetyce idealnej dla danej \displaystyle f.

Zauważmy, że wynik \displaystyle {\bf ALG}(f) działania algorytmu nie zależy bezpośrednio od \displaystyle f, ale raczej od informacji o \displaystyle f (uzyskanej dzięki poleceniu \displaystyle {\cal IN}). Informacja ta może być pełna albo tylko częściowa. Informacja jest pełna gdy, np. \displaystyle f=(f_1,\ldots,f_n)\inR^n i wczytamy wszystkie współrzędne \displaystyle f_i. Informacja może być częściowa, gdy \displaystyle f jest funkcją. Wtedy wiele danych może posiadać tę samą informację, co łatwo zaobserwować na przykładzie zadania całkowania.

Niech \displaystyle N:F\to\cup_{n=0}^\inftyR^n będzie operatorem informacji, tzn.

\displaystyle N(f)\,=\,(y_1,y_2,\ldots,y_n)

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

Każdy algorytm \displaystyle {\bf ALG} może być przedstawiony jako złożenie operatora informacji i pewnego operatora \displaystyle \varphi:N(F)\toG zdefiniowanego równością

\displaystyle \varphi\left(N(f)\right)\,=\,{\bf ALG}(f).

Zauważmy, że w przypadku informacji częściowej zwykle nie istnieje algorytm dający dokładne rozwiązanie zadania dla każdej danej \displaystyle f\inF, 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 \displaystyle S(f) a rozwiązaniem \displaystyle {\bf ALG}(f) dawanym przez algorytm w arytmetyce idealnej. Jeśli \displaystyle {\bf ALG}(f) = S(f), \displaystyle  \forall f \in F, 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 \displaystyle f składa się koszt uzyskania infomacji \displaystyle y=N(f) (zwykle jest on proporcjonalny do liczby wywołań polecenia \displaystyle {\cal IN}), oraz koszt kombinatoryczny przetworzenia tej informacji, aż do uzyskania wyniku \displaystyle \varphi(y). 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 \displaystyle fl_\nu. 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 \displaystyle fl_\nu. Niestety, jak zobaczymy, nie zawsze jest to możliwe. Nawet jeśli algorytm jest dokładny, to w wyniku jego realizacji w \displaystyle fl_\nu możemy otrzymać wynik \displaystyle fl_\nu({\bf ALG}(f)) daleko odbiegający od \displaystyle S(f). W szczególności, prawie zawsze mamy

\displaystyle S(f)\,\ne\,fl_\nu\left({\bf ALG}(f)\right).

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 \displaystyle fl_\nu. 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 \displaystyle y=N(f) o danej \displaystyle f 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 \displaystyle y_\nu, 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 \displaystyle fl_\nu będzie \displaystyle (\varphi(y_\nu))_\nu zamiast \displaystyle \varphi(y). Algorytmy dające tego rodzaju wyniki uznamy za posiadające najlepsze własności numeryczne w arytmetyce \displaystyle fl_\nu i nazwiemy numerycznie poprawnymi.

Powiemy, że ciąg rzeczywisty \displaystyle a_\nu=(a_{\nu,1},\ldots,a_{\nu,n}) (a właściwie rodzina ciągów \displaystyle \{a_\nu\}_\nu) jest nieco zaburzonym ciągiem \displaystyle a=(a_1,\ldots,a_n), jeśli istnieje stała \displaystyle K taka, że dla wszystkich dostatecznie małych \displaystyle \nu zachodzi

\displaystyle    |a_{\nu,j} - a_j|\,\le\,K\,\nu\,|a_j|,\qquad 1\le j\le n,

albo ogólniej

\displaystyle    \|a_\nu - a\|\,\le\,K\,\nu\,\|a\|,

gdzie \displaystyle \|\cdot\| jest pewną normą w \displaystyle R^n. W pierwszym przypadku mówimy o zaburzeniu "po współrzędnych", a w drugim o zaburzeniu w normie \displaystyle \|\cdot\|.

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

\displaystyle \|a_\nu - a\|_\infty \,=\, \max_{1\le j\le n} |a_{\nu,j} - a_j|   \,\le\,K\,\nu\,\max_{1\le j\le n} |a_j|\,=\,K\,\nu\,\|a\|_\infty,

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

\displaystyle \|a_\nu - a\|\,\le\,K_1\|a_\nu-a\|_\infty\,\le\,     K_1 K\,\nu\,\|a\|_\infty\,\le\,K_2 K_1 K\,\nu\,\|a\|,

czyli nierówność dla zaburzenia w normie, ze stałą \displaystyle K = K_2 K_1 K.

Definicja Algorytm numerycznie poprawny

Algorytm \displaystyle {\bf ALG} rozwiązywania zadania nazywamy numerycznie poprawnym w zbiorze danych \displaystyle F_0\subsetF, jeśli dla każdej danej \displaystyle f\inF_0 wynik \displaystyle fl_\nu({\bf ALG}(f)) działania algorytmu w arytmetyce \displaystyle fl_\nu można zinterpretować jako nieco zaburzony wynik algorytmu w arytmetyce idealnej dla nieco zaburzonej informacji \displaystyle y_\nu=(N(f))_\nu\inN(F) o \displaystyle f, przy czym poziom zaburzeń nie zależy od \displaystyle f.

Formalnie znaczy to, że istnieją stałe \displaystyle K_1, \displaystyle K_2 oraz \displaystyle \nu_0>0 takie, że spełniony jest następujący warunek. Dla dowolnej \displaystyle \nu\le\nu_0 oraz informacji \displaystyle y\inN(F_0) można dobrać \displaystyle y_\nu\inN(F) oraz \displaystyle \left(\varphi(y_\nu)\right)_\nu takie, że

\displaystyle \|y_\nu-y\|\,\le\,K_1\,\nu\,\|y\|,
\displaystyle \|\left(\varphi(y_\nu)\right)_\nu - \varphi(y_\nu)\|\,\le\,      K_2\,\nu\,\|\varphi(y_\nu)\|,

oraz

\displaystyle fl_\nu\left({\bf ALG}(f)\right)\,=\,       fl_\nu\left(\varphi(N(f))\right)\,=\,        \left(\varphi(y_\nu)\right)_\nu.
Numerycznie poprawny algorytm daje w arytmetyce  wynik , który daje się zinterpretować jako mało zaburzony wynik  zadania na mało zaburzonych danych .
Enlarge
Numerycznie poprawny algorytm daje w arytmetyce \displaystyle fl_\nu wynik \displaystyle ALG(N(x)), który daje się zinterpretować jako mało zaburzony wynik \displaystyle f(y) zadania na mało zaburzonych danych \displaystyle x.

Zauważmy,że jeśli \displaystyle f\inR^n, \displaystyle N(f)=(f_1,\ldots,f_n), oraz algorytm jest dokładny, \displaystyle {\bf ALG}\equiv\varphi\equivS, to numeryczną poprawność algorytmu można równoważnie zapisać jako

\displaystyle fl_\nu\left({\bf ALG}(f)\right)\,=\,   \left(S(f_\nu)\right)_\nu.

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 \displaystyle {\bf ALG}(\cdot)=\varphi(N(\cdot)) będzie algorytmem numerycznie poprawnym dla danych \displaystyle F_0\subsetF. Wtedy jego błąd w \displaystyle fl_\nu można oszacować następująco:

\displaystyle \aligned \lefteqn{ \|S(f)-fl_\nu({\bf ALG}(f))\| \;=\;      \|S(f)-\left(\varphi(y_\nu)\right)_\nu\| } \\    &\le \|S(f)-\varphi(y)\|\,+\,           \|\varphi(y)-\varphi(y_\nu)\|\,+\,           \|\varphi(y_\nu)-\left(\varphi(y_\nu)\right)_\nu\| \\    &\le \|S(f)-{\bf ALG}(f)\|\,+\,           \|\varphi(y)-\varphi(y_\nu)\|\,+\,           K_2\,\nu\,\|\varphi(y_\nu)\| \\    &\le \|S(f)-{\bf ALG}(f)\|\,+\,           (1 + K_2 \nu) \|\varphi(y)-\varphi(y_\nu)\|\,+\,           K_2\,\nu\,\|\varphi(y)\|, \endaligned

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

\displaystyle \lim_{\nu\to 0}\,\|S(f)-fl_\nu({\bf ALG}(f))\|\,=\,       \|S(f)-{\bf ALG}(f)\|.

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

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

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

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

Jeśli \displaystyle \varphi spełnia warunek Lipschitza ze stałą \displaystyle L, a dokładniej

\displaystyle \|\varphi(y_\nu)-\varphi(y)\|\,\le\,L\,\|y_\nu-y\|,

to

\displaystyle \aligned \lefteqn{ \|S(f)-fl_\nu({\bf ALG}(f))\|} \\       &\le \|S(f)-{\bf ALG}(f)\|\,+\,        (1+K_2\nu)L\|y_\nu-y\|\,+\,K_2\nu\|\varphi(y)\|  \\      &\le \|S(f)-{\bf ALG}(f)\|\,+\,         (1+K_2\nu)LK_1\nu\|y\|\,+\,K_2\nu\|\varphi(y)\|. \endaligned

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

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

\displaystyle \|\varphi(y_\nu)-\varphi(y)\|\;\le\;     M\,K_1\,\nu\,\max(\eta,\|\varphi(y)\|),

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

\displaystyle \aligned \|S(f)-fl_\nu({\bf ALG}(f))\|    & \le \|S(f)-{\bf ALG}(f)\|+      (1 + K_2 \nu) M K_1 \nu \max (\eta, \|\varphi(y)\|)+        K_2 \nu \|\varphi(y)\| \\     &= \|S(f)-{\bf ALG}(f)\|\,+\,\nu\,         \Big(\,MK_1(1+K_2\nu)+K_2\Big)\max(\eta,\|\varphi(y)\|). \endaligned

W szczególności, gdy algorytm jest dokładny i korzysta z pełnej informacji o \displaystyle f, tzn. \displaystyle S\equiv{\bf ALG}\equiv\varphi, to błąd

\displaystyle \frac{\|S(f)-fl_\nu({\bf ALG}(f))\|}        {\max (\eta, \|S(f)\|)} \;\le\;         \Big( M K_1 (1+K_2\nu) + K_2\Big)\,\nu         \,\approx\,(M\,K_1\,+\,K_2)\,\nu.

Stąd wynika, że jeśli \displaystyle (MK_1+K_2)\nu\ll 1, to błąd względny algorytmu w \displaystyle fl_\nu jest mały, o ile \displaystyle \|S(f)\|\ge\eta. Błąd względny jest proporcjonalny do dokładności \displaystyle \nu, arytmetyki \displaystyle fl_\nu, współczynników proporcjonalności \displaystyle K_i algorytmu numerycznie poprawnego, oraz do wrażliwości \displaystyle M zadania \displaystyle S 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 \displaystyle n, \displaystyle a_j, \displaystyle b_j, \displaystyle 1\le j\le n, chcemy obliczyć

\displaystyle S(a,b)\,=\,\sum_{j=1}^n a_j b_j.

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

Oznaczmy przez \displaystyle \tilde a_j i \displaystyle \tilde b_j reprezentacje liczb \displaystyle a_j i \displaystyle b_j w \displaystyle fl_\nu, \displaystyle \tilde a_j=a_j(1+\alpha_j), \displaystyle \tilde b_j=b_j(1+\beta_j), oraz przez \displaystyle \gamma_j i \displaystyle \delta_j błędy względne powstałe przy kolejnych mnożeniach i dodawaniach. Oczywiście \displaystyle |\alpha_j|,|\beta_j|, |\gamma_j|, |\delta_j|\le\nu. Otrzymujemy

\displaystyle \aligned fl_\nu\left(\sum_{j=1}^n a_jb_j\right) &=      \Big(\,(fl_\nu(\sum_{j=1}^{n-1}a_jb_j)\,+\,\tilde a_n\tilde b_n        (1+\gamma_n)\,\Big)(1+\delta_n)\,=\,\ldots \\    &= \bigg(\cdots\Big(        \tilde a_1\tilde b_1(1+\gamma_1)+\tilde a_2\tilde b_2         (1+\gamma_2)\Big)(1+\delta_2) +\cdots+         \tilde a_n\tilde b_n(1+\gamma_n)\bigg)(1+\delta_n) \\    &= \tilde a_1\tilde b_1(1+\gamma_1)(1+\delta_2)                  \cdots(1+\delta_n) +\cdots+\tilde a_j        \tilde b_j(1+\gamma_j)(1+\delta_j)\cdots(1+\delta_n) \\    &= \sum_{j=1}^n a_jb_j(1+e_j),  \endaligned

gdzie w przybliżeniu (tzn. gdy \displaystyle \nu\to 0) mamy \displaystyle |e_1|\leq (n+2)\nu i \displaystyle |e_j|\leq (n-j+4)\nu, \displaystyle 2\le j\le n. Algorytm naturalny jest więc numerycznie poprawny w całym zbiorze danych, gdyż wynik otrzymany w \displaystyle fl_\nu można zinterpretować jako dokładny wynik dla danych \displaystyle a_{\nu,j}=a_j i \displaystyle b_{\nu,j}=b_j(1+e_j), przy czym \displaystyle \|b_\nu-b\|_p\leq (n+2)\nu\|b\|_p.

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

\displaystyle \aligned \Big|\sum_{j=1}^n a_jb_j-fl_\nu\Big(\sum_{j=1}^n a_jb_j\Big)\Big|      &= \Big|\sum_{j=1}^n a_jb_j-\sum_{j=1}^n a_jb_j(1+e_j)\Big| \\     &= \Big|\sum_{j=1}^n e_ja_jb_j\Big|        \,\le\, \sum_{j=1}^n |e_j||a_jb_j| \\     &\leq  (n+2)\nu\sum_{j=1}^n |a_jb_j|.  \endaligned

Stąd dla \displaystyle \eta\ge 0

\displaystyle \frac{|\sum_{j=1}^n a_jb_j-fl_\nu(\sum_{j=1}^n a_jb_j)|}        {\max(\eta,|\sum_{j=1}^n a_jb_j|)} \,\leq\,          K_{\eta}\,(n+2)\,\nu,

gdzie

\displaystyle K_\eta\,=\,K_\eta(a,b)\,=\,\frac{\sum_{j=1}^n |a_jb_j|}              {\max(\eta,|\sum_{j=1}^n a_jb_j|) }.

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


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.