MN04LAB

Uwarunkowanie zadania i algorytmy numerycznie poprawne.

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

Oglądaj wskazówki i rozwiązania __SHOWALL__
Ukryj wskazówki i rozwiązania __HIDEALL__

Ćwiczenie

Aby obliczyć $S(a,b)=a^2-b^2$ można zastosować dwa algorytmy: ${\mathbf{𝐀}\mathbf{𝐋}\mathbf{𝐆}}_1(a,b)=a*a-b*b$ oraz ${\mathbf{𝐀}\mathbf{𝐋}\mathbf{𝐆}}_2(a,b)=(a+b)*(a-b)$. Pokazać, że oba algorytmy są numerycznie poprawne, ale drugi z nich wywołuje mniejszy błąd względny wyniku w przypadku, gdy $r{d}_{\nu }(a)=a$ i $r{d}_{\nu }(b)=b$.

Rozwiązanie

Rzeczywiście, dla pierwszego algorytmu obliczony w $f{l}_{\nu }$ wynik $\tilde{s}$ spełnia

$\tilde{s}=f{l}_{\nu }(f{l}_{\nu }(a\cdot a)-f{l}_{\nu }(b\cdot b))=(a^2(1+{ϵ}_a)-b^2(1+{ϵ}_b))(1+{ϵ}_{-}),$

gdzie $|{ϵ}_a|,|{ϵ}_b|,|{ϵ}_{-}|\le \nu$. A więc jesteśmy w sytuacji, gdy --- jeśli tylko $|a|\approx |b|$ --- może nastąpić redukcja cyfr przy odejmowaniu...

Natomiast drugi algorytm w ogóle nie jest na to czuły,

$\tilde{s}=f{l}_{\nu }(f{l}_{\nu }(a-b)\times f{l}_{\nu }(a+b))=((a-b)(1+{ϵ}_{-})\cdot (a+b)(1+{ϵ}_{+}))(1+{ϵ}_{\times }),$

gdzie znów $|{ϵ}_{+}|,|{ϵ}_{-}|,|{ϵ}_{\times }|\le \nu$. Ponieważ ostatecznie

$\tilde{s}=(a-b)(a+b)(1+{ϵ}_{-})(1+{ϵ}_{+})(1+{ϵ}_{\times })==(a^2-b^2)(1+E),$

gdzie $|E|\le 3\nu$, algorytm drugi będzie zawsze dawał wynik obarczony małym błędem względnym.

Zwróć uwagę na istotną rolę przyjętego założenia, że $a$ i $b$ są liczbami maszynowymi, reprezentowanymi dokładnie w $f{l}_{\nu }$. W praktyce obliczeniowej, najczęściej właśnie z takimi danymi będziemy się spotykać...

Ćwiczenie

Pokazać, że naturalny algorytm obliczania cosinusa kąta między dwoma wektorami $a,b\in R^n$,

$\cos (a,b)=\frac{\sum _{j=1}^n{a}_j{b}_j}{\sqrt{\left(\sum _{j=1}^n{a}_j^2\right)\left(\sum _{j=1}^n{b}_j^2\right)}},$

jest numerycznie poprawny. Oszacować błąd względny wyniku w $f{l}_{\nu }$.

Ćwiczenie

Podaj przykład funkcji $f$, której miejsce zerowe $x^{*}$ ma wspólczynnik uwarunkowania

• mały
• duży

Rozwiązanie

Ponieważ nasze zadanie to wyznaczenie $x^{*}=f^{-1}(0)$, to

${\text{cond}}_{abs}(f^{-1},0)=\frac{1}{f^{\prime }(x^{*})}.$

Znaczy to, że im bardziej płaska jest $f$ w otoczeniu pierwiastka $x^{*}$, tym bardziej nawet małe zaburzenia $f$ mogą spowodować duże przemieszczenie jej miejsca zerowego.

Zauważ, iż dla wielokrotnych miejsc zerowych, ${\text{cond}}_{abs}(f^{-1},0)=\mathrm{\infty }$. Zgadza się to z intuicją, bo może się zdarzyć, że nawet minimalne zaburzenie $f$ spowoduje, iż miejsc zerowych po prostu nie będzie...

Gdy trochę zaburzymy wartości funkcji f, dobrze uwarunkowane miejsce zerowe nie przemieści się zbyt daleko od miejsca zerowego f.

Gdy trochę zaburzymy wartości funkcji f, źle uwarunkowane miejsce zerowe może przemieścić się bardzo daleko od miejsca zerowego f.