Čtení: 45 minHodnotí se: volitelný úkol, písemka, ústní

4 Strojová čísla a chyby výpočtu

Po přečtení umíš

převést číslo do formátu IEEE 754 ručně
spočítat strojovou přesnost a zaokrouhlovací jednotku
najít ztrátu platných cifer a vyhnout se jí
rozlišit dopřednou a zpětnou chybu a podmíněnost úlohy

Z numerické matematiky je volitelný úkol za 10 bodů a nejspíš i další minikvízy, přesná témata v materiálech nejsou. Úkol se vyplatí, je to nejlevnější rezerva k ústní zkoušce.

4.1 Ukázka: počítač neumí 0,1

V dvojkové soustavě má $1/10$ nekonečný periodický rozvoj, podobně jako $1/3$ v desítkové. Počítač ho musí zaokrouhlit, proto:

0.1 + 0.2 = 0.30000000000000004

Nejde o chybu počítače, ale o vlastnost formátu.

4.2 Formát IEEE 754

Definice 4.2 (Normalizované číslo)

x = (-1)^s \cdot (1.m)_2 \cdot 2^{e - b}

kde $s$ je znaménko, $e$ uložený exponent, $b$ posun a $m$ signifikant bez vedoucí jedničky, která se neukládá (skrytá jednička).

Přesnost	$t$ (bity $m$ )	$d$ (bity $e$ )	$b$
binary16	10	5	15
binary32	23	8	127
binary64	52	11	1023

32 bitů binary32: znaménko, exponent s posunem 127 a signifikant bez skryté jedničky.

Skrytá jednička dává o bit víc: jednoduchá přesnost má 24 platných cifer.

Příklad 4.3 (Převod −1/5 do binary32)

Zaokrouhlujeme k nejbližšímu.

Znaménko: $s = 1$ .
Normalizace: $1/5 = 1.6 \cdot 2^{-3}$ , protože $1 \le 1.6 < 2$ .
Exponent: $e = -3 + 127 = 124 = 01111100_2$ .
Signifikant: $0.6 \cdot 2^{23} = 5033164.8$ , zaokrouhleno na $5033165$ .
Výsledek: 1|01111100|10011001100110011001101

Postup pro zlomek: najdi $k$ , aby $2^k \le x < 2^{k+1}$ . Pak opakovaně násob zbytek dvěma a odečti jedničku, když to jde. Protože zbytků je konečně mnoho, začnou se bity opakovat.

4.3 Strojová přesnost a zaokrouhlení

Definice 4.4 (Strojová přesnost)

$\varepsilon_F$ je vzdálenost 1 od nejbližšího většího strojového čísla. Pro binary32 je $2^{-23}$ , pro binary64 $2^{-52}$ .

Definice 4.5 (Zaokrouhlovací jednotka)

$u$ je mez relativní chyby zaokrouhlení: $fl(x) = x(1 + \delta)$ , $|\delta| \le u$ . Směrem k nule je $u = \varepsilon_F$ , k nejbližšímu $u = \varepsilon_F / 2$ .

Každá operace je přesný výsledek jednou zaokrouhlený: $fl(x \circ y) = (x \circ y)(1 + \delta)$ . Pozor, pořadí se tím mění: sčítání strojových čísel není asociativní.

Poznámka 4.6 (Důsledek)

V binary64 platí $1 + 2^{-53} = 1$ , zatímco $1 + 2^{-52} \ne 1$ . Malé číslo se k velkému „nevejde“.

4.4 Ztráta platných cifer

Odečtením dvou blízkých čísel zmizí shodné cifry a zůstane šum.

Příklad 4.7 (Rozdíl odmocnin)

Počítáme $\sqrt{x + 1} - \sqrt{x}$ pro $x = 10^{15}$ v binary64. Přímý výpočet dá $1{,}8626 \cdot 10^{-8}$ . Přepis

\sqrt{x + 1} - \sqrt{x} = \frac{1}{\sqrt{x + 1} + \sqrt{x}}

dá $1{,}5811 \cdot 10^{-8}$ , což je správně. První výsledek má chybu 18 %, i když každá operace byla přesná na 16 cifer.

Jak se krácení vyhnout: přeformuluj výraz, použij rozvoj do řady, nebo jinou rovnost.

4.5 Dopředná a zpětná chyba

Definice 4.8 (Dvě chyby)

Dopředná chyba: o kolik je výsledek daleko od přesného. Zpětná chyba: jak moc by se musel změnit vstup, aby byl náš výsledek přesný. Algoritmus je zpětně stabilní, pokud je relativní zpětná chyba malá násobek $u$ .

Definice 4.9 (Podmíněnost)

Číslo podmíněnosti $C_r$ říká, jak citlivý je výstup na malou změnu vstupu. Je to vlastnost úlohy, ne algoritmu. Pro funkci

C_r = \left| \frac{x f'(x)}{f(x)} \right|.

Úloha	$C_r$	Závěr
$f(x) = \sqrt{x}$	$1/2$	dobře podmíněná
$f(x) = e^x$	$\lvert x \rvert$	špatně pro velká $\lvert x \rvert$
násobení	$\le 2$	dobře
odčítání blízkých čísel	$\frac{\lvert x\rvert + \lvert y\rvert}{\lvert x - y\rvert}$	špatně

Věta 4.10 (Hlavní vztah)

\text{relativní dopředná chyba} \lesssim C_r \times \text{relativní zpětná chyba}

Takže stabilní algoritmus na špatně podmíněné úloze stejně dá nepřesný výsledek.

4.6 Čtyři zdroje chyb

Chyba modelu, chyba dat, chyba algoritmu (metody) a zaokrouhlovací chyba. U ústní zkoušky se často začíná otázkou, odkud chyby pocházejí.

4.7 Typické chyby

Zapomenutý posun $b$ v exponentu.
Uložení vedoucí jedničky do $m$ .
Záměna $\varepsilon_F$ a $u$ .
Tvrzení, že zvýšení přesnosti vždy pomůže.
Podmíněnost jako vlastnost algoritmu.

4.8 Kvíz

Kvíz

1. Kolik platných bitů má binary32 včetně skryté jedničky? Odpověď:

2. Jaký je uložený exponent čísla

1/3

v binary32? 125 126 127 124

3. Jaké je

u

pro binary64 se zaokrouhlením k nejbližšímu?

2^{-52}

2^{-53}

2^{-23}

4. Co platí ve strojové aritmetice? Může být správně více možností, ale také žádná. Sčítání je asociativní Odčítání blízkých čísel ztrácí cifry Každá operace je jednou zaokrouhlená Vyšší přesnost vždy dá přesnější výsledek

5. Co je číslo podmíněnosti? Vlastnost algoritmu Vlastnost úlohy Počet kroků

6. Kolik je

C_r

pro

f(x) = e^x

v bodě

x = 10

? Odpověď:

7. Stabilní algoritmus dal špatný výsledek. Jak je to možné?

Ukázat řešení

Úloha může být špatně podmíněná. Dopředná chyba je přibližně číslo podmíněnosti krát zpětná chyba.

4.9 Příklady na procvičení

Cvičení 4.11

Převeď $2/3$ do binary32, zaokrouhlení k nejbližšímu.

Řešení

$2/3 = 1.\overline{3} \cdot 2^{-1}$ , tedy $s = 0$ a $e = 126 = 01111110_2$ . Dále $\frac{1}{3} \cdot 2^{23} = 2796202.\overline{6}$ se zaokrouhlí na $2796203$ .

Výsledek: 0|01111110|01010101010101010101011.

Cvičení 4.12

Sečti reprezentovaná čísla $-1/5$ a $2/3$ z příkladů výše a zaokrouhli. Je výsledek stejný jako reprezentace $7/15$ ?

Řešení

Součet reprezentací dá 0|01111101|11011101110111011110000. Reprezentace přesného $7/15$ je 0|01111101|11011101110111011101111.

Liší se v posledních bitech, protože sčítance už byly zaokrouhlené a jejich chyby se přenesly do součtu.

4.10 Tahák

Tahák

$x = (-1)^s (1.m)_2\, 2^{e-b}$ , binary32: $t = 23$ , $d = 8$ , $b = 127$ .
Exponent: najdi $2^k \le x < 2^{k+1}$ , $e = k + b$ .
$\varepsilon_F = 2^{-t}$ , $u = \varepsilon_F$ k nule, $\varepsilon_F / 2$ k nejbližšímu.
$fl(x \circ y) = (x \circ y)(1 + \delta)$ , $|\delta| \le u$ .
Blízká čísla neodčítej, přeformuluj výraz.
$C_r = |x f'/f|$ je vlastnost úlohy.
Dopředná chyba ≲ $C_r$ × zpětná chyba.

Kapitolu mám prostudovanou