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
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
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…
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}
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…
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.
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:
Ponieważ iloczyn \delta_3\delta_x jest mikroskopijnej wielkości, możemy zastosować następujące przybliżenie (wymnażając):
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:
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.
Niech \varepsilon_i oznaczają błędy reprezentacji odpowiednio kolejnych operacji.
a)
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)