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