Aktualna wersja na dzień 21:50, 11 wrz 2023

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: ${𝐀 𝐋 𝐆}_{1} (a, b) = a * a - b * b$ oraz ${𝐀 𝐋 𝐆}_{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_{ν} (a) = a$ i $r d_{ν} (b) = b$ .

Rozwiązanie

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

\tilde{s} = f l_{ν} (f l_{ν} (a \cdot a) - f l_{ν} (b \cdot b)) = (a^{2} (1 + ϵ_{a}) - b^{2} (1 + ϵ_{b})) (1 + ϵ_{-})

,

gdzie $| ϵ_{a} |, | ϵ_{b} |, | ϵ_{-} | \leq ν$ . 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_{ν} (f l_{ν} (a - b) \times f l_{ν} (a + b)) = ((a - b) (1 + ϵ_{-}) \cdot (a + b) (1 + ϵ_{+})) (1 + ϵ_{\times})

,

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

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

,

gdzie $| E | \leq 3 ν$ , 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_{ν}$ . 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{(\sum_{j = 1}^{n} a_{j}^{2}) (\sum_{j = 1}^{n} b_{j}^{2})}}

,

jest numerycznie poprawny. Oszacować błąd względny wyniku w $f l_{ν}$ .

Ć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

{cond}_{a b s} (f^{- 1}, 0) = \frac{1}{f^{'} (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, ${cond}_{a b s} (f^{- 1}, 0) = \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...

@@ Linia 19: / Linia 19: @@
 <div class="exercise">
-Aby obliczyć <math>\displaystyle S(a,b)=a^2-b^2</math> można zastosować
+Aby obliczyć <math>S(a,b)=a^2-b^2</math> można zastosować
-dwa algorytmy: <math>\displaystyle {\bf ALG}_1(a,b)=a*a-b*b</math> oraz <math>\displaystyle {\bf ALG}_2(a,b)=(a+b)*(a-b)</math>.
+dwa algorytmy: <math>{\bf ALG}_1(a,b)=a*a-b*b</math> oraz <math>{\bf ALG}_2(a,b)=(a+b)*(a-b)</math>.
 Pokazać, że oba algorytmy są numerycznie poprawne, ale drugi
 z nich wywołuje mniejszy błąd względny wyniku w przypadku, gdy
-<math>\displaystyle rd_\nu(a)=a</math> i <math>\displaystyle rd_\nu(b)=b</math>.
+<math>rd_\nu(a)=a</math> i <math>rd_\nu(b)=b</math>.
 </div></div>
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"><div style="margin-left:1em">
-Rzeczywiście, dla pierwszego algorytmu obliczony w <math>\displaystyle fl_\nu</math> wynik <math>\displaystyle \tilde{s}</math> spełnia
+Rzeczywiście, dla pierwszego algorytmu obliczony w <math>fl_\nu</math> wynik <math>\tilde{s}</math> spełnia
-<center><math>\displaystyle
+<center><math>
-\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_{-}),
+\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_{-})</math>,</center>
-</math></center>
-gdzie <math>\displaystyle |\epsilon_{a}|, |\epsilon_{b}|, |\epsilon_{-}| \leq \nu</math>. A więc jesteśmy w sytuacji, gdy --- jeśli tylko <math>\displaystyle |a|\approx |b|</math> --- może nastąpić redukcja cyfr przy odejmowaniu...
+gdzie <math>|\epsilon_{a}|, |\epsilon_{b}|, |\epsilon_{-}| \leq \nu</math>. A więc jesteśmy w sytuacji, gdy --- jeśli tylko <math>|a|\approx |b|</math> --- może nastąpić redukcja cyfr przy odejmowaniu...
 Natomiast drugi algorytm w ogóle nie jest na to czuły,
-<center><math>\displaystyle
+<center><math>
-\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}),
+\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})</math>,</center>
-</math></center>
-gdzie znów <math>\displaystyle |\epsilon_{+}|, |\epsilon_{-}|, |\epsilon_{\times}| \leq \nu</math>.
+gdzie znów <math>|\epsilon_{+}|, |\epsilon_{-}|, |\epsilon_{\times}| \leq \nu</math>.
 Ponieważ ostatecznie
-<center><math>\displaystyle
+<center><math>
 \tilde{s} = (a-b)(a+b)(1+\epsilon_{-})(1+\epsilon_{+})(1+\epsilon_{\times})=
-= (a^2 - b^2)(1+E),
+= (a^2 - b^2)(1+E)</math>,</center>
-</math></center>
-gdzie <math>\displaystyle |E| \leq 3\nu</math>, algorytm drugi będzie <strong>zawsze</strong> dawał wynik obarczony małym błędem względnym.
+gdzie <math>|E| \leq 3\nu</math>, algorytm drugi będzie <strong>zawsze</strong> dawał wynik obarczony małym błędem względnym.
-Zwróć uwagę na istotną rolę przyjętego założenia, że <math>\displaystyle a</math> i <math>\displaystyle b</math> są liczbami maszynowymi, reprezentowanymi dokładnie w <math>\displaystyle fl_\nu</math>. W praktyce obliczeniowej,  najczęściej właśnie z takimi danymi będziemy się spotykać...
+Zwróć uwagę na istotną rolę przyjętego założenia, że <math>a</math> i <math>b</math> są liczbami maszynowymi, reprezentowanymi dokładnie w <math>fl_\nu</math>. W praktyce obliczeniowej,  najczęściej właśnie z takimi danymi będziemy się spotykać...
 </div></div></div>
@@ Linia 57: / Linia 54: @@
 Pokazać, że naturalny algorytm obliczania cosinusa
-kąta między dwoma wektorami <math>\displaystyle  a, b\inR^n</math>,
+kąta między dwoma wektorami <math>a, b\in R^n</math>,
-<center><math>\displaystyle \cos(a,b)\,=\,\frac{\sum_{j=1}^n a_jb_j}
+<center><math>\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)}},
+              \Big(\sum_{j=1}^n b_j^2\Big)}}</math>,</center>
-</math></center>
 jest numerycznie poprawny. Oszacować błąd względny wyniku
-w <math>\displaystyle fl_\nu</math>.
+w <math>fl_\nu</math>.
 </div></div>
@@ Linia 75: / Linia 71: @@
 Pokazać, że naturalny algorytm obliczania
-<math>\displaystyle \|A x\|_2</math> dla danej macierzy <math>\displaystyle A\inR^{n\times n}</math> i wektora
+<math>\|A x\|_2</math> dla danej macierzy <math>A\inR^{n\times n}</math> i wektora
-<math>\displaystyle  x\inR^n</math> jest numerycznie poprawny. Dokładniej,
+<math>x\inR^n</math> jest numerycznie poprawny. Dokładniej,
-<center><math>\displaystyle fl_\nu (\|A x\|_2)\,=\,(A+E) x,
+<center><math>fl_\nu (\|A x\|_2)\,=\,(A+E) x</math>,</center>
-</math></center>
-gdzie <math>\displaystyle \|E\|_2\leq 2(n+2)\sqrt n\nu\|A\|_2</math>. Ponadto, jeśli
+gdzie <math>\|E\|_2\leq 2(n+2)\sqrt n\nu\|A\|_2</math>. Ponadto, jeśli
-<math>\displaystyle A</math> jest nieosobliwa, to
+<math>A</math> jest nieosobliwa, to
-<center><math>\displaystyle |fl_\nu(\|A x\|_2)-\|A x\|_2|\,\leq\,2(n+2)\sqrt{n}\,\nu\,
+<center><math>|fl_\nu(\|A x\|_2)-\|A x\|_2|\,\leq\,2(n+2)\sqrt{n}\,\nu\,
-    \left(\|A\|_2\|A^{-1}\|_2\right)\,\|A x\|_2.
+    \left(\|A\|_2\|A^{-1}\|_2\right)\,\|A x\|_2</math></center>
-</math></center>
 </div></div>
@@ Linia 94: / Linia 88: @@
 <div class="exercise">
-Niech <math>\displaystyle {\bf ALG}</math> będzie algorytmem numerycznie
+Niech <math>{\bf ALG}</math> będzie algorytmem numerycznie
-poprawnym w zbiorze danych <math>\displaystyle f\in F_0</math>, przy czym dla małych <math>\displaystyle \nu</math>,
+poprawnym w zbiorze danych <math>f\in F_0</math>, przy czym dla małych <math>\nu</math>,
-<math>\displaystyle fl_\nu({\bf ALG}(f))=\varphi(y_\nu)</math>, gdzie <math>\displaystyle \|y_\nu-y\|\le K\nu\|y\|</math>
+<math>fl_\nu({\bf ALG}(f))=\varphi(y_\nu)</math>, gdzie <math>\|y_\nu-y\|\le K\nu\|y\|</math>
-i <math>\displaystyle K</math> nie zależy od <math>\displaystyle \nu</math> i <math>\displaystyle f</math> (<math>\displaystyle y=N(f)</math>). Pokazać, że
+i <math>K</math> nie zależy od <math>\nu</math> i <math>f</math> (<math>y=N(f)</math>). Pokazać, że
-w ogólności <math>\displaystyle {\bf ALG}</math> nie musi być "numerycznie poprawny po
+w ogólności <math>{\bf ALG}</math> nie musi być "numerycznie poprawny po
 współrzędnych", tzn. w ogólności nie istnieje bezwzględna
-stała <math>\displaystyle K_1</math> taka, że dla małych <math>\displaystyle \nu</math> i dla dowolnej
+stała <math>K_1</math> taka, że dla małych <math>\nu</math> i dla dowolnej
-<math>\displaystyle f\in F_0</math>
+<math>f\in F_0</math>
-<center><math>\displaystyle |y_{\nu,j}-y_j|\,\le\,K_1\,\nu\,|y_j|, \qquad 1\le j\le n,
+<center><math>|y_{\nu,j}-y_j|\,\le\,K_1\,\nu\,|y_j|, \qquad 1\le j\le n</math>,</center>
-</math></center>
-gdzie <math>\displaystyle y=(y_1,\ldots,y_n)</math>.
+gdzie <math>y=(y_1,\ldots,y_n)</math>.
 </div></div>
@@ Linia 115: / Linia 108: @@
 <div class="exercise">
-Podaj przykład funkcji <math>\displaystyle f</math>, której miejsce zerowe <math>\displaystyle x^*</math> ma wspólczynnik
+Podaj przykład funkcji <math>f</math>, której miejsce zerowe <math>x^*</math> ma wspólczynnik
 uwarunkowania
 * mały
@@ Linia 123: / Linia 116: @@
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"><div style="margin-left:1em">
-Ponieważ nasze zadanie to wyznaczenie <math>\displaystyle x^* = f^{-1}(0)</math>, to
+Ponieważ nasze zadanie to wyznaczenie <math>x^* = f^{-1}(0)</math>, to
-<center><math>\displaystyle
+<center><math>
-  \mbox{cond} _{abs} (f^{-1},0) = \frac{1}{f'(x^*)}.
+  \mbox{cond} _{abs} (f^{-1},0) = \frac{1}{f'(x^*)}</math></center>
-</math></center>
-Znaczy to, że im bardziej płaska jest <math>\displaystyle f</math> w otoczeniu pierwiastka <math>\displaystyle x^*</math>, tym
+Znaczy to, że im bardziej płaska jest <math>f</math> w otoczeniu pierwiastka <math>x^*</math>, tym
-bardziej nawet małe zaburzenia <math>\displaystyle f</math> mogą spowodować duże przemieszczenie jej
+bardziej nawet małe zaburzenia <math>f</math> mogą spowodować duże przemieszczenie jej
 miejsca zerowego.
-Zauważ, iż dla wielokrotnych miejsc zerowych, <math>\displaystyle  \mbox{cond} _{abs} (f^{-1},0) = \infty</math>. Zgadza się to z intuicją, bo może się zdarzyć, że nawet minimalne zaburzenie <math>\displaystyle f</math>
+Zauważ, iż dla wielokrotnych miejsc zerowych, <math>\mbox{cond} _{abs} (f^{-1},0) = \infty</math>. Zgadza się to z intuicją, bo może się zdarzyć, że nawet minimalne zaburzenie <math>f</math>
 spowoduje, iż miejsc zerowych po prostu nie będzie...

MN04LAB: Różnice pomiędzy wersjami

Aktualna wersja na dzień 21:50, 11 wrz 2023

Uwarunkowanie zadania i algorytmy numerycznie poprawne.

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia