MN04LAB

From Studia Informatyczne


Uwarunkowanie zadania i algorytmy numerycznie poprawne.

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

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

Ćwiczenie

Aby obliczyć \displaystyle S(a,b)=a^2-b^2 można zastosować dwa algorytmy: \displaystyle {\bf ALG}_1(a,b)=a*a-b*b oraz \displaystyle {\bf ALG}_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 \displaystyle rd_\nu(a)=a i \displaystyle rd_\nu(b)=b.

Rozwiązanie

Rzeczywiście, dla pierwszego algorytmu obliczony w \displaystyle fl_\nu wynik \displaystyle \tilde{s} spełnia

\displaystyle  \tilde{s} = fl_\nu(fl_\nu(a\cdot a)-fl_\nu(b\cdot b)) = (a^2(1+\epsilon_a) - b^2(1+\epsilon_b))(1+\epsilon_{-}),

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

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

\displaystyle  \tilde{s} = fl_\nu(fl_\nu(a - b) \times fl_\nu(a + b)) = ((a-b)(1+\epsilon_{-}) \cdot (a+b)(1+\epsilon_{+}))(1+\epsilon_{\times}),

gdzie znów \displaystyle |\epsilon_{+}|, |\epsilon_{-}|, |\epsilon_{\times}| \leq \nu. Ponieważ ostatecznie

\displaystyle  \tilde{s} = (a-b)(a+b)(1+\epsilon_{-})(1+\epsilon_{+})(1+\epsilon_{\times})= = (a^2 - b^2)(1+E),

gdzie \displaystyle |E| \leq 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 \displaystyle a i \displaystyle b są liczbami maszynowymi, reprezentowanymi dokładnie w \displaystyle fl_\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 \displaystyle  a, b\inR^n,

\displaystyle \cos(a,b)\,=\,\frac{\sum_{j=1}^n a_jb_j}       {\sqrt{\Big(\sum_{j=1}^n a_j^2\Big)              \Big(\sum_{j=1}^n b_j^2\Big)}},

jest numerycznie poprawny. Oszacować błąd względny wyniku w \displaystyle fl_\nu.


Ćwiczenie

Podaj przykład funkcji \displaystyle f, której miejsce zerowe \displaystyle x^* ma wspólczynnik uwarunkowania

  • mały
  • duży
Rozwiązanie

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

\displaystyle   \mbox{cond} _{abs} (f^{-1},0) = \frac{1}{f'(x^*)}.

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

Zauważ, iż dla wielokrotnych miejsc zerowych, \displaystyle  \mbox{cond} _{abs} (f^{-1},0) = \infty. Zgadza się to z intuicją, bo może się zdarzyć, że nawet minimalne zaburzenie \displaystyle 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.
Enlarge
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.
Enlarge
Gdy trochę zaburzymy wartości funkcji f, źle uwarunkowane miejsce zerowe może przemieścić się bardzo daleko od miejsca zerowego f.