5. Numerická matematika: reprezentace čísel v počítači, chyby vznikající při výpočtech s pohyblivou řádovou čárkou, podmíněnost úlohy a stabilita numerických algoritmů. (NI-MPI)

---

Reprezentace čísel v počítači

Celá čísla

• Pro reprezentaci celých čísel se používá standartní dvojková soustava
• Pokud se mají používat i záporná čísla tak se používá jedno z kódováních:
  • Přímý kód: Nejvyšší byt zobrazuje znaménko: $-1=\underline{1}00 ... 001$
  • Doplňkový kód: Negace všech bytu a přičteni $1$ zobrazuje záporná čísla tedy: $13=001101$ pak $-13 = \text{NOT}(001101) + 1 = 110010 + 1 = 110011$
  • Kód s posunutou nulou: Cela osa se posune o konstantu aby polovina čísel byla záporná a druha polovina kladná tedy pro osmibitová čísla by to bylo: $-127=00000000$, $0=01111111$, $128=11111111$

Necelá čísla

• Pro reprezentaci necelých čísel se používá: vědecký zápis: $$x = \pm m \cdot 2^e$$
  • $m:$ Je mantisa mající pevný počet cifer / pevnou délku, těmto cifrám se také říká platné cifry
  • $e:$ Je exponent mající pevný počet cifer / pevnou délku.

IEEE-754

• Tento format používá vědecky zápis spolu s konkrétní implementaci pro reprezentaci binárních čísel.
• Celé binární číslo se rozdělí do 3 částí
  • $s:$ Signifikant určuje znaménko celého čísla $0$ jsou pro pozitivní čísla a $1$ pro negativní
  • $m:$ Mantisa určuje číslo které se následně posune o exponent
  • $e:$ Exponent Určuje posun mantisy o $2^e$ pozic
• Dale je fixní posunuti exponentu kterému se říká bias Toto posunuti funguje na principu kódu s posunutou $0$.
• Skryta jednička: Protože v binární soustavě můžeme definovat ze první bit ve vědeckém zápisu je vždy $1$ můžeme toto číslo brat implicitně a neukládat ho v IEEE-754

Přesnost	Délka mantisy ($m$)	Délka exponentu ($e$)	Bias
Poloviční (binary16, half precision)	10	5	15
Jednoduchá (binary32, single precision)	23	8	127
Dvojitá (binary64, double precision)	52	11	1023
Čtyřnásobná (binary128, quadruple precision)	112	15	16383

Určení reprezentace čísla

• Not a Number: Exponent je plny $1$ a mantisa se nerovná $0$
  • $e=2^{d-1}, \quad m\neq 0 \quad \rightarrow x=\text{NaN}$
• Nekonečno: Exponent je plny $1$ a mantisa se rovna $0$
  • $e=2^{d-1}, \quad m = 0 \quad \rightarrow x=(-1)^s \cdot \infty$
• Normalizovaná čísla: Exponent je mezi $0$ a max číslem pak se používá vědecký zápis se skrytou jedničkou. Nesmí se zapomenout na bias v exponentu
  • $0<e<2^{d-1} \quad \rightarrow \quad x = (-1)^s\cdot(1.m_2)_2\cdot 2^{e-b}$
• Subnormální čísla: Exponent se rovna $0$ a mantisa se nerovná $0$ pak se používá vědecký zápis a skryté nuly. Exponent se rovna $1-b$
  • $e=0 \quad m\neq 0 \quad \rightarrow \quad x = (-1)^s\cdot(0.m_2)_2\cdot 2^{1-b}$
• Nula: Pokud exponent i mantisa je $0$. Máme kladnou i zápornou nulu.
  • $e=0 \quad m = 0 \quad \rightarrow \quad x = (-1)^s \cdot 0$

Strojová čísla

• Reálna čísla která se dají popsat IEEE-754, ( či jiným způsobem aby mela přesnou reprezentaci v počítací ) nazýváme strojová čísla
• Tuto množinu čísel můžeme označit jako: $F = (|m|,|e|,b)$
• Strojová přesnost: Je vzdálenost $1$ od nejbližšího většího čísla. značí se: $\varepsilon_F$
• Vzdálenost libovolného normalizovaného čísla od jeho souseda je minimálně: $\varepsilon_F\frac{|x|}{2}$, maximálně: $\varepsilon_F|x|$

Typy chyb

• Chyby můžeme definovat ve dvou stylech. Mějme přibližné číslo $\alpha \in F$ a přibližnou hodnotu $a \in \mathbb{R}$:
  • Absolutní chyba: $|\alpha - a|$
  • Relativní chyba: $\frac{|\alpha - a|}{|a|}, \quad a \neq 0$
• Kategorizace chyb
  • Chyba modelu: matematický model řešené úlohy je nějakým způsobem zjednodušený, např. je zanedbáno tření
  • Chyba dat: data často pocházejí z měření, která nemají absolutní přesnost
  • Chyba algoritmu: nemusíme mít k dispozici algoritmus, který v konečném počtu kroků najde přesné řešení.
  • Chyba při výpočtu:
    • Přetečení/Podtečení: Vzniká při práci s čísly které se nevejdou do podporovaného rozsahu
    • Krácení: (Ztráta platných cifer) Počítáme na přesnost $10$ čísel zbytek je $0$ například při odečítaní
    • Zaokrouhlovací chyba: Vzniká při práci s čísly které nejde strojově definovat
• Maximální chyba při odečítaní
  • Mějme normalizovaná strojová čísla $x$ a $y$ a platí $x>y>0$. Pokud $2^{-p}\leq 1-\frac{y}{x} \leq 2^{-q}$ pro nějaká kladná celá $p$ a $q$, tak platí, že nejvíce $p$ a nejméně $q$ platných binárních bitů je ztraceno při provedení odečítání $x - y$
• Vlastnosti:
  • Zvýšení přesnosti nemusí dát přesnější výsledek
  • Krácení může být někdy výhodné – lze tak vyrušit zaokrouhlovací či jiné chyby
  • Málo operací s malými čísly neznamená, že chyba bude malá.

Podmíněnost a stabilita úloh

• Iterační metody hledají přibližná řešení matematických problémů tak, že konstruují posloupnost přibližných řešení kde každé další přibližné řešení je odvozeno z předchozího

Stabilita úloh

• Jedna se o algoritmy které pro všechny vstupy je chyba relativně malá:
  • Zpětně stabilní: Zpětná chyba je vždy malá
• Mějme algoritmus jehož teoretický (přesný) výstup označíme $V^∗(d)$, kde $d$ jsou vstupní data. Výsledek vypočtu algoritmu v strojové přesnosti označíme: $V(d)$
  • Dopředná/Přímá chyba: je odchylka spočítaného řešení od přesného řešení.
    • $\Delta v = V^∗(d) − V (d)$
  • Zpětná chyba: Jedná se promítnutí chyby algoritmu V do jeho vstupu – jaký problém byl ve skutečnosti vyřešen.
    • $\Delta d: \text{min}\{V^∗(d+\Delta d) = V (d)\}$

Podmíněnost úloh

• Podmíněnost úlohy vyjadřuje závislost změny výstupu na změně vstupních dat - jejich malé perturbaci $\delta d$
• $$C_r = \lim_{\varepsilon \to 0^+} \sup_{d+\delta d \in D, \|\delta d\| \leq \varepsilon} \frac{\frac{\|V^*(d + \delta d) - V^*(d)\|}{\|V^*(d)\|}} { \frac{\|\delta d\|}{\|d\|}}$$
  • Interpretace:
    • $C_r \approx 1$: dobře podmíněná úloha
    • $C_r \gg 1$: špatně podmíněná úloha