MN04

Własności zadania obliczeniowego i algorytmu numerycznego

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 (0.1 nie jest

równe dokładnie $1/10$)

• błędy w parametrach będących rezultatem poprzednich obliczeń (chcemy

rozwiązać równanie $f(x)=a$, ale $a$ jest rezultatem innej symulacji), a także

• błędy pomiarowe w zadaniach praktycznych (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$.

<flash>file=XXX.swf</flash><div.thumbcaption>Zadanie obliczeniowe i jego odporność na zaburzenia

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 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)|}.$

Możnaby myśleć, że złe uwarunkowanie zawsze jest szkodliwe w praktyce numerycznej. Najczęściej właśnie tak jest istotnie. Jednak w praktyce numerycznej sporadycznie zdarza się, że Dodaj link: złe uwarunkowanie pewnego podzadania nie tylko nie pogarsza sytuacji, 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 nformacja 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.

Dokładniej, 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 }.$

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 horendalnie 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 }$.