MN04

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

Naszym zadaniem jest wyznaczenie, dla $x\in X$, wartości $f(x)\in Y$.

Jaki będzie rozrzut wyników, gdy lekko zaburzymy dane?

Jeśli równie mały, co zaburzenie, powiemy, że zadanie jest dobrze uwarunkowane (jego wynik jest mało podatny na zaburzenia danych).

Może jednak zdarzyć się, że zadanie jest źle uwarunkowane i małe zaburzenie danych skutkuje dużym rozrzutem wyników.

Wtedy nawet bliskie sobie punkty w X, przekształcenie $f$ może odwzorowywać w punkty bardzo od siebie odległe. Jest to sytuacja skrajnie niekorzystna w zastosowaniach, a zwłaszcza --- w obliczeniach numerycznych.

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

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

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

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

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

Powiemy, że zadanie $f(x)$ jest

• dobrze uwarunkowane w punkcie $x$, gdy $\text{cond}(f,x)\approx 1$,
• źle uwarunkowane w punkcie $x$, gdy $\text{cond}(f,x)\gg 1$,
• źle postawione w punkcie $x$, gdy $\text{cond}(f,x)=+\mathrm{\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 $s(x,y)=x+y$ ma

${\text{cond}}_{abs}(s,(a,b))=1,{\text{cond}}_{rel}(s,(a,b))=\frac{|a|+|b|}{|a+b|}$

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

$|f(x)-f(\tilde{x}|\approx |f^{\prime }(x)||x-\tilde{x}|$

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

${\text{cond}}_{abs}(f,x)=|f^{\prime }(x)|,{\text{cond}}_{rel}(f,x)=\frac{|f^{\prime }(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

Parser nie mógł rozpoznać (nieznana funkcja „\longrightarrowG”): {\displaystyle \displaystyle {\bf ALG}:\,F\longrightarrowG, }

taki że $\mathbf{𝐀}\mathbf{𝐋}\mathbf{𝐆}(f)$ jest wynikiem działania algorytmu w arytmetyce idealnej dla danej $f$.

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

Niech Parser nie mógł rozpoznać (nieznana funkcja „\inftyR”): {\displaystyle \displaystyle N:F\to\cup_{n=0}^\inftyR^n} będzie operatorem informacji, tzn.

$N(f)=(y_1,y_2,\dots ,y_n)$

jest informacją o $f$ zebraną przy idealnej realizacji algorytmu. Zauważmy, że informacja jest pełna, gdy $N$ jest przekształceniem różnowartościowym, tzn. jeśli Parser nie mógł rozpoznać (nieznana funkcja „\nef”): {\displaystyle \displaystyle f_1\nef_2} implikuje Parser nie mógł rozpoznać (nieznana funkcja „\neN”): {\displaystyle \displaystyle N(f_1)\neN(f_2)} . W przeciwnym przypadku mamy do czynienia z informacją częściową.

Każdy algorytm $\mathbf{𝐀}\mathbf{𝐋}\mathbf{𝐆}$ może być przedstawiony jako złożenie operatora informacji i pewnego operatora Parser nie mógł rozpoznać (nieznana funkcja „\toG”): {\displaystyle \displaystyle \varphi:N(F)\toG} zdefiniowanego równością

$\phi (N(f))=\mathbf{𝐀}\mathbf{𝐋}\mathbf{𝐆}(f).$

Zauważmy, że w przypadku informacji częściowej zwykle nie istnieje algorytm dający dokładne rozwiązanie zadania dla każdej danej Parser nie mógł rozpoznać (nieznana funkcja „\inF”): {\displaystyle \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 $S(f)$ a rozwiązaniem $\mathbf{𝐀}\mathbf{𝐋}\mathbf{𝐆}(f)$ dawanym przez algorytm w arytmetyce idealnej. Jeśli $\mathbf{𝐀}\mathbf{𝐋}\mathbf{𝐆}(f)=S(f)$, $\mathrm{\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 $f$ składa się koszt uzyskania infomacji $y=N(f)$ (zwykle jest on proporcjonalny do liczby wywołań polecenia ${ℐ}{𝒩}$), oraz koszt kombinatoryczny przetworzenia tej informacji, aż do uzyskania wyniku $\phi (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 $f{l}_{\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 $f{l}_{\nu }$. Niestety, jak zobaczymy, nie zawsze jest to możliwe. Nawet jeśli algorytm jest dokładny, to w wyniku jego realizacji w $f{l}_{\nu }$ możemy otrzymać wynik $f{l}_{\nu }(\mathbf{𝐀}\mathbf{𝐋}\mathbf{𝐆}(f))$ daleko odbiegający od $S(f)$. W szczególności, prawie zawsze mamy

$S(f)\ne f{l}_{\nu }(\mathbf{𝐀}\mathbf{𝐋}\mathbf{𝐆}(f)).$

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

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

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

albo ogólniej

$\Vert a_{\nu }-a\Vert \le K\nu \Vert a\Vert ,$

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

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

$\Vert a_{\nu }-a{\Vert }_{\mathrm{\infty }}=\underset{1\le j\le n}{\max }|a_{\nu ,j}-a_j|\le K\nu \underset{1\le j\le n}{\max }|a_j|=K\nu \Vert a{\Vert }_{\mathrm{\infty }},$

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

$\Vert a_{\nu }-a\Vert \le K_1\Vert a_{\nu }-a{\Vert }_{\mathrm{\infty }}\le K_{1}K\nu \Vert a{\Vert }_{\mathrm{\infty }}\le K_2{K}_{1}K\nu \Vert a\Vert ,$

czyli nierówność dla zaburzenia w normie, ze stałą $K=K_2{K}_{1}K$.

Definicja Algorytm numerycznie poprawny

Algorytm $\mathbf{𝐀}\mathbf{𝐋}\mathbf{𝐆}$ rozwiązywania zadania nazywamy numerycznie poprawnym w zbiorze danych Parser nie mógł rozpoznać (nieznana funkcja „\subsetF”): {\displaystyle \displaystyle F_0\subsetF} , jeśli dla każdej danej Parser nie mógł rozpoznać (nieznana funkcja „\inF”): {\displaystyle \displaystyle f\inF_0} wynik $f{l}_{\nu }(\mathbf{𝐀}\mathbf{𝐋}\mathbf{𝐆}(f))$ działania algorytmu w arytmetyce $f{l}_{\nu }$ można zinterpretować jako nieco zaburzony wynik algorytmu w arytmetyce idealnej dla nieco zaburzonej informacji Parser nie mógł rozpoznać (nieznana funkcja „\inN”): {\displaystyle \displaystyle y_\nu=(N(f))_\nu\inN(F)} o $f$, przy czym poziom zaburzeń nie zależy od $f$.

Formalnie znaczy to, że istnieją stałe $K_1$, $K_2$ oraz ${\nu }_0>0$ takie, że spełniony jest następujący warunek. Dla dowolnej $\nu \le {\nu }_0$ oraz informacji Parser nie mógł rozpoznać (nieznana funkcja „\inN”): {\displaystyle \displaystyle y\inN(F_0)} można dobrać Parser nie mógł rozpoznać (nieznana funkcja „\inN”): {\displaystyle \displaystyle y_\nu\inN(F)} oraz ${(\phi (y_{\nu }))}_{\nu }$ takie, że

$\Vert y_{\nu }-y\Vert \le K_1\nu \Vert y\Vert ,$ $\Vert {(\phi (y_{\nu }))}_{\nu }-\phi (y_{\nu })\Vert \le K_2\nu \Vert \phi (y_{\nu })\Vert ,$

oraz

$f{l}_{\nu }(\mathbf{𝐀}\mathbf{𝐋}\mathbf{𝐆}(f))=f{l}_{\nu }(\phi (N(f)))={(\phi (y_{\nu }))}_{\nu }.$

Numerycznie poprawny algorytm daje w arytmetyce $f{l}_{\nu }$ wynik $ALG(N(x))$, który daje się zinterpretować jako mało zaburzony wynik $f(y)$ zadania na mało zaburzonych danych $x$.

Zauważmy,że jeśli Parser nie mógł rozpoznać (nieznana funkcja „\inR”): {\displaystyle \displaystyle f\inR^n} , $N(f)=(f_1,\dots ,f_n)$, oraz algorytm jest dokładny, Parser nie mógł rozpoznać (nieznana funkcja „\equivS”): {\displaystyle \displaystyle {\bf ALG}\equiv\varphi\equivS} , to numeryczną poprawność algorytmu można równoważnie zapisać jako

$f{l}_{\nu }(\mathbf{𝐀}\mathbf{𝐋}\mathbf{𝐆}(f))={(S(f_{\nu }))}_{\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 $\mathbf{𝐀}\mathbf{𝐋}\mathbf{𝐆}(\cdot )=\phi (N(\cdot ))$ będzie algorytmem numerycznie poprawnym dla danych Parser nie mógł rozpoznać (nieznana funkcja „\subsetF”): {\displaystyle \displaystyle F_0\subsetF} . Wtedy jego błąd w $f{l}_{\nu }$ można oszacować następująco:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 $\Vert y_{\nu }-y\Vert \le K_1\nu \Vert y\Vert$. Stąd w szczególności wynika, że jeśli algorytm jest numerycznie poprawny i ciągły ze względu na informację $y$, to

$\underset{\nu \to 0}{\lim }\Vert S(f)-f{l}_{\nu }(\mathbf{𝐀}\mathbf{𝐋}\mathbf{𝐆}(f))\Vert =\Vert S(f)-\mathbf{𝐀}\mathbf{𝐋}\mathbf{𝐆}(f)\Vert .$

To znaczy, że dla dostatecznie silnej arytmetyki algorytm będzie się zachowywał w $f{l}_{\nu }$ prawie tak, jak w arytmetyce idealnej.

Z powyższych wzorów wynika, że błąd w $f{l}_{\nu }$ algorytmu numerycznie poprawnego zależy w dużym stopniu od:

• dokładności algorytmu w arytmetyce idealnej,
• dokładności $\nu$ arytmetyki $f{l}_{\nu }$,
• wrażliwości algorytmu na małe względne zaburzenia informacji $y$.

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

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

$\Vert \phi (y_{\nu })-\phi (y)\Vert \le L\Vert y_{\nu }-y\Vert ,$

to

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 $\nu$.

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

$\Vert \phi (y_{\nu })-\phi (y)\Vert \le M{K}_1\nu \max (\eta ,\Vert \phi (y)\Vert ),$

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 $f$, tzn. $S\equiv \mathbf{𝐀}\mathbf{𝐋}\mathbf{𝐆}\equiv \phi$, to błąd

$\frac{\Vert S(f)-f{l}_{\nu }(\mathbf{𝐀}\mathbf{𝐋}\mathbf{𝐆}(f))\Vert }{\max (\eta ,\Vert S(f)\Vert )}\le (M{K}_1(1+K_2\nu )+K_2)\nu \approx (M{K}_1+K_2)\nu .$

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

$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 ${\tilde{a}}_j$ i ${\tilde{b}}_j$ reprezentacje liczb $a_j$ i $b_j$ w $f{l}_{\nu }$, ${\tilde{a}}_j=a_j(1+{\alpha }_j)$, ${\tilde{b}}_j=b_j(1+{\beta }_j)$, oraz przez ${\gamma }_j$ i ${\delta }_j$ błędy względne powstałe przy kolejnych mnożeniach i dodawaniach. Oczywiście $|{\alpha }_j|,|{\beta }_j|,|{\gamma }_j|,|{\delta }_j|\le \nu$. Otrzymujemy

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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) \\ & & \qquad\qquad\qquad\qquad +\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)\\ & & \qquad\qquad\qquad\qquad +\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 $\nu \to 0$) mamy $|e_1|\le (n+2)\nu$ i $|e_j|\le (n-j+4)\nu$, $2\le j\le n$. Algorytm naturalny jest więc numerycznie poprawny w całym zbiorze danych, gdyż wynik otrzymany w $f{l}_{\nu }$ można zinterpretować jako dokładny wynik dla danych $a_{\nu ,j}=a_j$ i $b_{\nu ,j}=b_j(1+e_j)$, przy czym $\Vert b_{\nu }-b{\Vert }_p\le (n+2)\nu \Vert b{\Vert }_p$.

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 $\eta \ge 0$

$\frac{|\sum _{j=1}^n{a}_j{b}_j-f{l}_{\nu }(\sum _{j=1}^n{a}_j{b}_j)|}{\max (\eta ,|\sum _{j=1}^n{a}_j{b}_j|)}\le K_{\eta }(n+2)\nu ,$

gdzie

$K_{\eta }=K_{\eta }(a,b)=\frac{\sum _{j=1}^n|a_j{b}_j|}{\max (\eta ,|\sum _{j=1}^n{a}_j{b}_j|)}.$

Zauważmy, że jeśli iloczyny $a_j{b}_j$ są wszystkie dodatnie albo wszystkie ujemne, to $K_{\eta }=1$, tzn. zadanie jest dobrze uwarunkowane, a błąd względny jest zawsze na poziomie co najwyżej $n\nu$. W tym przypadku algorytm zachowuje się bardzo dobrze, o ile liczba $n$ składników nie jest horrendalnie duża. W ogólności jednak $K_{\eta }$ może być liczbą dowolnie dużą i wtedy nie możemy być pewni uzyskania dobrego wyniku w $f{l}_{\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.