====== Analiza numeryczna (M) - Lista 2. ======
{{:analiza_numeryczna:09.listaM02.pdf|Lista 2}}.

===== Zadanie 1. =====

Definicja rd(x):

$rd(x) = s2^{c}(\sum_{k=1}^{t}e_{-k}2^{-k}+e_{-t-1}2^{-t})$

Chcemy znaleźć $c_t$ i e z gwiazdkami takie, że:

$rd(x)=s\left(\sum_{k=1}^{t}e_{-k}^{*}2^{k}\right)2^{c_{t}}$

Znaki wywalamy na starcie bo się one nie zmieniął i rozpatrujemy przypadki:

1. Gdy pierwszy odcięty bit jest zerowy:

$e_{-t-1}=0$

Wtedy oczywiście: $\forall_{1\leq k\leq t}e_{-k}^{*}=e_{-k};\, c_{t}=c$

2. Gdy wszystkie t+1 bitów było 1 i po zaokrągleniu m przekręca się na 1.0:

$\forall_{1\leq k\leq t+1}e_{-k}=1$

Wtedy równie oczywiste:

$\forall_{2\leq k\leq t}e_{-k}^{*}=0;\, e_{-1}^{*}=1;\, c_{t}=c+1$

3. Ostatni przypadek odpowiada zwykłemu dodawaniu w którym m nie dojdzie do 1.0:

$\exists_{1\leq k\leq t}e_{-k}=0\wedge e_{-t-1}=1$

Niech:

$k_{0}=max\{k:e_{-k}=0\}$

Wtedy już mniej oczywiste, ale też za trudno nie jest:

$\forall_{1\leq k<k_{0}}e_{-k}^{*}=e_{-k};\, e_{-k_{0}}^{*}=1;\,\forall_{k_{0}<k\leq t}e_{-k}^{*}=0;\, c_{t}=c$

===== Zadanie 2. =====
wzory:
$rd(x)=sgn(x) \cdot \overline{m} \cdot 2^{c}$ \\
$x=sgn(x) \cdot m \cdot 2^{c}$

Jadymy:
$ |rd(x)-x|=|sgn(x) \cdot 2^{c} | \cdot |\overline{m} - m| $

Rozpatrzmy samą różnicę mantys by stworzyc ograniczenie z góry. 

**a)**

Przypadek gdy  $ e_{t+1}=0 $ czyli mantysa sie nie zaokrągli tylko skróci:

$m - \overline{m} = \sum_{i=t+1}e_{i}2^{-i} \ = \ e_{t+1}2^{-(t+1)} + \sum_{i=t+2}e_{i}2^{-i} \ = \\
= \ (2 \cdot \frac{1}{2} - 1)2^{-(t+1)} + \sum_{i=t+2}e_{i}2^{-i} \ = \ \frac{1}{2}2^{-t} - 2^{-(t+1)} + \sum_{i=t+2}e_{i}2^{-i} $

liczba ta jest na pewno mniejsza równa od liczby która ma od t+2 miejsca włącznie samiutkie jedynki:

$ m - \overline{m} \leq \frac{1}{2}2^{-t} - 2^{-(t+1)} + (2-1)(\sum_{i=t+2}2^{-i}) \ = \\
= \frac{1}{2}2^{-t} - 2^{-(t+1)} + 2 \sum_{i=t+2}2^{-i} - \sum_{i=t+2}2^{-i} \ = $

2*suma zmienia jedynie potęgi o 1 w górę czyli:
$ = \  \frac{1}{2}2^{-t} - 2^{-(t+1)} + \sum_{i=t+1}2^{-i} - \sum_{i=t+2}2^{-i} \ = \ \frac{1}{2}2^{-t} - 2^{-(t+1)} + 2^{-(t+1)} \ = \ \frac{1}{2}2^{-t} $

zatem:
$ m - \overline{m} \leq \frac{1}{2}2^{-t} $

**b)**

mantysa znormalizowana ulegnie zmianie ( $ e_{t+1} = 1 $ ) , czyli skorzystamy z drugiego wzoru:

$m - \overline{m} \ = \ \sum_{i=t+1}e_{i}2^{-i} - 2^{-t} \ =$

wyciągamy pierwszy składnik sumy:
$= \ 2^{-t-1} - 2^{-t} + \sum_{i=t+2}e_{i}2^{-i}  \ = \\
= \ \frac{1}{2}2^{-t} - 2^{-t} + \sum_{i=t+2}e_{i}2^{-i} \ = \\
= \ -\frac{1}{2}2^{-t} + \sum_{i=t+2}e_{i}2^{-i}$

ta liczba jest na pewno większa lub równa liczbie która po t+1 miejscu miała same zera:

$m - \overline{m} \geq - \frac{1}{2}2^{-t} \Rightarrow \overline{m} - m \leq \frac{1}{2}2^{-t}$



**podsumowanie a i b**: $|\overline{m} - m| \leq \frac{1}{2}2^{-t}$

kontynuacja rozważań: \\
$|rd(x)-x|=|sgn(x) \cdot 2^{c} | \cdot |\overline{m} - m| \Rightarrow |rd(x)-x| \leq 2^{c} \cdot \frac{1}{2}2^{-t}$

:3

===== Zadanie 2, alternatywne rozwiązanie =====
$rd(x)=sgn(x) \cdot \overline{m} \cdot 2^{c}$ \\
$x=sgn(x) \cdot m \cdot 2^{c}$

$ |rd(x)-x|= $\\
$|sgn(x) \cdot 2^{c} | \cdot |\overline{m} - m| =$ \\
$2^{c} \cdot |\overline{m} - m| =$ \\
$2^{c} \cdot |\sum_{i=1}^{t}e_i2^{-i} + e_{-t-1} \cdot 2^{-t} - (\sum_{i=1}^{t}e_i2^{-i} + \sum_{i=t+1}e_i2^{-i})| =$ \\
$2^{c} \cdot |e_{-t-1} \cdot 2^{-t} - \sum_{i=t+1}e_i2^{-i}| \le 2^{c} \cdot 2^{-t-1}$ \\
bo np. 0.01 - (0.001xxxx...) = 0.00yyyyyy...

===== Zadanie 3. =====
znając nierówność z zadania 2:
dodajemy mianownik który rozpiszemy jedynie z definicji, pamiętając że najmniejsza mantysa to $\frac{1}{2}$
$\frac{|rd(x)-x|}{|x|} \leq \frac{2^{c} \cdot \frac{1}{2} \cdot 2^{-t}}{2^{c} \cdot m} \leq \frac{\frac{1}{2} \cdot 2^{-t}}{\frac{1}{2}} \leq 2^{-t}$

===== Zadanie 4. =====

[[http://www.im.pwr.wroc.pl/~pziel/lectures/nm/mnw2.pdf]] (pierwszy slajd)

//coś podobnego mam w notatkach z wykładu, co prawda ani z jednego ani z drugiego nie rozumiem skąd pojawia się pochodna, ale mniejsza o to...//
  * skąd pochodna: http://pl.wikipedia.org/wiki/Pochodna_funkcji#Definicja

a) $f(x) = \frac{1}{x^2+c}$ \\ $f'(x) = \frac{-2x}{(x^2+c)^2}$

liczymy wskaźnik uwarunkowania

$\displaystyle C_f = \frac{|x\cdot\frac{-2x}{(x^2+c)^2}|}{|\frac{1}{x^2+c}|} = | \frac{-2x^2}{x^2+c}|$

No i teraz w zależności od stałej możemy mieć problem jeśli stała jest ujemna to dla x ~ $\pm\sqrt{|c|} $ ten ułamek dąży do nieskończoności przez co w wynikach pojawi się epic fail z tym związany. Dla stałych dodatnich chyba nie ma problemu, ew. ja go nie dostrzegam.

b) $f(x) = \frac{(1-cosx)}{x}$ \\ $f'(x) = \frac{x\cdot sinx - 1\cdot(1-cosx)}{x^2} = \frac{x \cdot sinx + cosx -1}{x^2}$

ponownie liczymy wskaźnik

$C_f = \frac {x\cdot sinx + cosx -1}{1 - cosx}$

o ile się gdzieś nie pomyliłem licząc f' to tutaj jest przejebane na całej linii, mianownik co chwila zbliża się do 0 i cały wskaźnik rośnie w kosmos.

Odp: Zadanie jest źle uwarunkowane dla $x = 2k\pi + k/2$.

===== Zadanie 5. =====
Niech $\delta_i$ oznacza błąd reprezentacji $w_i$ dla $0\leq i \leq 3$, a $\delta_x$ - ów błąd dla $x$. Wiemy, że $ \forall_i\delta_i \leq 2^{-t}$ (patrz poprzednie zadania, wykład, etc.).
Mamy więc kolejno:
  * $w_3=a_3(1+\delta_3)$
  * $p_2=a_3x(1+\delta_3)(1+\delta_x)$
  * $w_2=a_3x(1+\delta_3)(1+\delta_x)+a_2(1+\delta_2)$
  * $p_1=a_3x^2(1+\delta_3)(1+\delta_x)^2+a_2x(1+\delta_2)(1+\delta_x)$
  * $w_1=a_3x^2(1+\delta_3)(1+\delta_x)^2+a_2x(1+\delta_2)(1+\delta_x)+a_1(1+\delta_1)$
  * $p_0=a_3x^3(1+\delta_3)(1+\delta_x)^3+a_2x^2(1+\delta_2)(1+\delta_x)^2+a_1x(1+\delta_1)(1+\delta_x)$
  * $w_0=a_3x^3(1+\delta_3)(1+\delta_x)^3+a_2x^2(1+\delta_2)(1+\delta_x)^2+a_1x(1+\delta_1)(1+\delta_x)+a_0(1+\delta_0)$
Ponieważ iloczyn $\delta_3\delta_x$ jest mikroskopijnej wielkości, możemy zastosować następujące przybliżenie (wymnażając):
  * $w_0\approx a_3x^3(1+3\delta_3+3\delta_x)+a_2x^2(1+2\delta_2+2\delta_x)+a_1x(1+\delta_1+\delta_x)+a_0(1+\delta_0)$
Ponieważ $\delta_3,\delta_x \leq 2^{-t}$, mamy oszacowanie: $1+3\delta_3+3\delta_x \leq 1+6*2^{-t} \leq 1+2^{-t+3}$.
Zaburzenia pozostałych składników (sumy) również spełniają tę nierówność. Tak więc ostatecznie:
  * $\frac{|w-w_0|}{|w|} \leq 2^{-t+3}$
Jak łatwo zauważyć, błąd względny wyniku jest co najwyżej osiem razy większy od błędu reprezentacji, co dla np. $t=72$ daje pułap $10^{-21}$, a więc mało. Algorytm jest numerycznie poprawny.

===== Zadanie 6. =====

Niech $\varepsilon_i$ oznaczają błędy reprezentacji odpowiednio kolejnych operacji.

**a)**

  * $p = (a-b)(1+\varepsilon_1)$
  * $q = (a+b)(1+\varepsilon_2)$
  * $r = (a-b)(a+b)(1+\varepsilon_1)(1+\varepsilon_2)(1+\varepsilon_3)$
  * $w = c(a-b)(a+b)(1+\varepsilon_1)(1+\varepsilon_2)(1+\varepsilon_3)(1+\varepsilon_4) \approx c(a-b)(a+b)(1+\varepsilon_1+\varepsilon_2+\varepsilon_3+\varepsilon_4)$

Współczynnik zaburzający dokładną wartość można oszacować jako $1+4\varepsilon$, gdzie $\varepsilon$ to błąd reprezentacji. Algorytm jest więc numerycznie poprawny.

**b)**

  * $f = a^2(1+\varepsilon_1)$
  * $g = ca^2(1+\varepsilon_1)(1+\varepsilon_2)$
  * $h = b^2(1+\varepsilon_3)$
  * $j = cb^2(1+\varepsilon_3)(1+\varepsilon_4)$
  * $w = \displaystyle (ca^2(1+\varepsilon_1)(1+\varepsilon_2)-cb^2(1+\varepsilon_3)(1+\varepsilon_4))(1+\varepsilon_5) \approx (ca^2-cb^2)(1+3\varepsilon)$. Hmm, cos jest nie tak, ten algorytm nie mial byc gorszy?

===== Zadanie 7. =====

  * $\displaystyle p_k = \prod_{i=1}^k{x_i (1+\varepsilon)}$
  * $\displaystyle fl(w) = p_n = \prod_{i=1}^n{x_i} \cdot \prod_{i=1}^k{(1+\varepsilon)} \approx w \cdot (1 + n\varepsilon) $
  * $\displaystyle \frac{|w-fl(w)|}{|w|} = \frac{|w-w(1 + n\varepsilon)|}{|w|} = n\varepsilon$
{{tag>[listy_zadan]}}