PA081: Programování numerických výpočtů Aleš Křenek jaro 2012 PA081: Programování numerických výpočtů A. Křenek O čem to bude (De)motivační příklad Obsah předmětu Předpoklady a návaznosti Zkouška Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítání Katastrofální zrušení Násobení a dělení Měření rychlosti výpočtu Přetečení a podtečeni Porovnávání Numerická stabilita Domácí úkol Shrnutí 1/37 O čem to bude zajímá nás chování skutečného světa ► problémy přírodovědné, technické, humanitní... popisujeme matematickými prostředky ► zejména pomocí reálných čísel ► umělý aparát, leckdy zcela neodpovídá skutečnosti ► za staletí celkem zvládnutý, vyučovaný od základní školy, obecně přijímaný (De)motivační příklad Předpoklady a návaznosti Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítání Katastrofální zrušení Násobení a dělen Měření rychlosti výpočtu Přetečení a podtečení Porovnávání Numerická stabilita Domácí úkol Shrnutí □ 4 ► 4 ■= * < ► 2/37 O čem to bude zákonitosti zkoumaných systémů typicky vyjádřeny rovnicemi zajímavé systémy — složité rovnice ► reprezentativní příklad - Schrôdingerova rovnice ifr^-Y(x,r) =/TF(x,í) ot ► analyticky řešitelná jen pro triviální případy ► izolovaná částice, částice v potenciálové jámě, ..., atom vodíku ► i tak je řešení dost komplikované numerické řešení je jediný realisticky možný přístup (De)motivační příklad Předpoklady a návaznosti Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítání Katastrofální zrušení Násobení a délen M éře ní rychlosti výpočtu Přetečení a podtečení Porovnávání Numerická stabilita Domácí úkol Shrnuti □ 4 ► 4 ■= * < ► 3/37 O čem to bude ► numerická matematika ► řešení matematicky formulovaného problému aritmetickými prostředky ► zpravidla algoritmický postup - numerická metoda ► disciplina podstatně starší než počítače PA081: Programování numerických výpočtů A. Křenek O čem to bude (De)rnotivační příklad Obsah předmětu Předpoklady a návaznosti Zkouška Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítání Katastrofální zrušení Násobení a dělení Měření rychlosti výpočtu Přetečení a podtečeni Porovnávání Numerická stabilita Domácí úkol Shrnutí 4/37 O čem to bude ► numerická matematika ► řešení matematicky formulovaného problému aritmetickými prostředky ► zpravidla algoritmický postup - numerická metoda ► disciplina podstatně starší než počítače ► metody jsou známé, naprogramujeme je a je hotovo ► ne tak docela (De)motivační příklad pro dané n vypočítejte integrál En xnex 1dx O čem to bude (De)motivačni příklad Obsah předmětu Predpoklady a návaznosti Zkouška Čísla v plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítání Katastrofální zrušení Násobení a děleni Měřeni rychlosti výpočtu Přetečeni a podtečení Porovnávání Numerická stabilita Domácí úkol Shrnutí 5/37 (De)motivační příklad pro dané n vypočítejte integrál En = xnex~ldx Jo očekávané vlastnosti ► E0 = [e*-i]l = 1 - i ► pro 0 < x < 1 platí xn > 0 a 0 < ex_1 < 1, tedy En > 0 podobně -i : En < I xndx =- a tedy lim En = 0 1 71 + 1 n-oo (De)motivacní přiklad Předpoklady a návaznosti Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítáni Katastrofální zrušení Násobení a délen M éře ní rychlosti výpočtu Přetečení a podtečeni Porovnávání Numerická stabilita Domácí úkol Shrnutí □ 4 ► 4 ■= * < ► 5/37 (De)motivační příklad ► integrací per-partes u = xn, dv = ex~ldx i f1 En = [xnex-1](j - J nxn-1ex-1dx = 1 PA081: Programování numerických výpočtů A. Křenek H O čem to bude (De)motivační příklad fl,Eji — X Obsah předmětu Předpoklady a návaznosti Zkouška Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítání Katastrofální zrušení Násobení a délení Měření rychlosti výpočtu Přetečení a podtečeni Porovnávání Numerická stabilita Domácí úkol Shrnutí □ 4 ► 4 ■= * < ► 6/37 (De)motivační příklad ► integrací per-partes u = xn, dv = ex~ldx i f1 En = [xnex_1]o - J nxn~1ex~1dx = 1 - nEn-i (De)motivační příklad Předpoklady a návaznosti Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítáni Katastrofálni zrušeni Násobeni a délen M éře ni rychlosti výpočtu Přetečeni a podtečeni Porovnáváni Numerická stabilita Domácí úkol Shrnuti □ 4 ► 4 ■= * < ► 6/37 (De)motivační příklad 1: 0.367879 2: 0.264241 3: 0.207277 4: 0.170893 5: 0.145534 6: 0.126796 7: 0.112430 8: 0.100563 9: 0.094933 10: 0.050674 11: 0.442581 12: -4.310974 13: 57.042664 14: -797.597290 15: 11964.958984 16: -191438.343750 17: 3254452.750000 18: -58580148.000000 19: 1113022848.000000 (De)motivační příklad co je špatně? pracujeme s konečnou reprezentací reálného čísla ► společný problém ručního i strojového zpracování ► v počítači daleko plíživější podoba (nevidíme mezivýsledky) (De)motivační příklad Předpoklady a návaznosti Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítání Katastrofální zrušení Násobení a dělení Měření rychlosti výpočtu Přetečení a podtečení Porovnávání Numerická stabilita Domácí úkol Shrnutí 8/37 (De)motivační příklad co je špatně? pracujeme s konečnou reprezentací reálného čísla ► společný problém ručního i strojového zpracování ► v počítači daleko plíživější podoba (nevidíme mezivýsledky) v proměnné E [n] není uloženo přesně En už na začátku zatíženo chybou, E[0] = Eq + e (De)motivační příklad Předpoklady a návaznosti Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítání Katastrofální zrušení Násobení a dělen Měření rychlosti výpočtu Přetečeni a podtečeni Porovnáváni Numerická stabilita Domácí úkol Shrnuti □ 4 ► 4 = ► < -Š ► 8/37 (De)motivační příklad co je špatně? pracujeme s konečnou reprezentací reálného čísla ► společný problém ručního i strojového zpracování ► v počítači daleko plíživější podoba (nevidíme mezivýsledky) v proměnné E [n] není uloženo přesně En už na začátku zatíženo chybou, E[0] = Eq + e i při zcela přesném výpočtu: E[l] = 1-E[0] = l-E0-e = E1-e E[2] = 1 - 2E[1] = 1 - 2£i + 2e = E2 + 2e E[3] = 1 - 3E[2] = 1 - 3E2 - 3(2e) = E3 - 3(2e) E[n] (-l)nn\e (De)motivační příklad Předpoklady a návaznosti Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítání Katastrofální zrušení Násobení a délení M éře ní rychlosti výpočtu Přetečení a podtečení Porovnávání Numerická stabilita Domácí úkol Shrnuti □ 4 ► 4 ■= * < ► 8/37 O čem to tedy bude představení numerických metod pro řešení vybraných problémů ► pragmaticky, bez rozsáhlé teoretické analýzy, okrajových podmínek atd. formulace přiměřeně přesného a efektivního algoritmu ► matematicky korektní metoda nestačí ► pro různá použití jsou vhodné různé alternativy použití na smysluplném příkladu (De)motivační příklad Předpoklady a návaznosti Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítání Katastrofální zrušení Násobení a dělen Měření rychlosti výpočtu Přetečení a podtečení Porovnávání Numerická stabilita Domácí úkol Shrnutí □ 4 ► 4 ■= * < ► 9/37 Obsah předmětu ► obecné zásady psaní numerického kódu ► nelineárni rovnice f (x) = y *■ optimalizace (hledání lokálního minima) ► lineárni úlohy Ax = B ► automatické derivování ► diferenciální rovnice (zlehka) ► modelování dynamických systémů Předpoklady a návaznosti předpokládané znalosti ► návrh algoritmů, elementární schopnost programování ► porozumět kódu v C ► programovat ve svém oblíbeném jazyce (C++, Java, Fortran, Python,...) ► základy lineární algebry a matematické analýzy ► základní orientace v architektuře a assembleru x86 ► http://www.i ntel.com/products/processor/manuals/ ► pro referenci, netřeba číst všechno ;-) (De)motivační příklad Předpoklady a návaznosti Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítání Katastrofální zrušení Násobení a délen M éře ní rychlosti výpočtu Přetečení a podtečení Porovnávání Numerická stabilita Domácí úkol Shrnutí □ 4 ► 4 = ► < -Š ► 11/37 Předpoklady a návaznosti předpokládané znalosti ► návrh algoritmů, elementární schopnost programování ► porozumět kódu v C ► programovat ve svém oblíbeném jazyce (C++, Java, Fortran, Python,...) ► základy lineární algebry a matematické analýzy ► základní orientace v architektuře a assembleru x86 ► http://www.i ntel.com/products/processor/manuals/ ► pro referenci, netřeba číst všechno ;-) návaznosti ► M4180: Numerické metody I ► PV027: Optimalizace ► IA039: Architektura superpočítačů a intenzivní výpočty ► PV192: Paralelní technické systémy ► PV197: GPU Programming ► diplomové práce (De)motivační příklad Předpoklady a návaznosti Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítání Katastrofální zrušení Násobení a délen M éře ní rychlosti výpočtu Přetečení a podtečení Porovnávání Numerická stabilita Domácí úkol Shrnutí □ 4 ► 4 ■= * < ► 11/37 Zkouška ► znalosti v rozsahu přednášek ► písemná část ► teorie i praktický příklad ► 10 příkladů na cca. 1 hodinu ► extenzivnější příprava na ústní část ► ústní část ► povídání nad písemkou ► co se zvládne doplnit a opravit, to se počítá PA081: Programování numerických výpočtů A. Křenek O čem to bude (De)motivační příklad Obsah předmětu Předpoklady a návaznosti Zkouška Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítání Katastrofální zrušení Násobení a délení Měření rychlosti výpočtu Přetečení a podtečení Porovnávání Numerická stabilita Domácí úkol Shrnutí □ 4 ► 4 ■= * < ► 12/37 Domácí úkoly a konzultace ► domácí úkoly ► dobrovolné, slouží k lepšímu pochopení problematiky ► zadávány průběžně několikrát za semestr ► řešení do dalšího týdne ► drobné body k dobru ke zkoušce ► konzultace ► v mezích možností kdykoli po domluvě emailem ► ÚVT, Šumavská 15 (Gotex), 3. patro (CERIT-SC) Čísla v plovoucí řádové čárce standard IEEE 754 ► vychází návrhu reprezentace čísel v koprocesoru Intel 8087 základní formát ±l.mmmmmmmmm... x 2±ee- ► znaménko mantisy (1 bit) ► mantisa l.mmmmmmmm ► binárně, absolutní hodnota ► číslo v intervalu [1, 2) v dané přesnosti ► nekonečná množina pokryta konečným počtem hodnot ► základní zdroj nepřesnosti ► exponent ► binární číslo v rozsahu 1 až např. 254 ► znamená hodnoty exponentu -126 až +127 ► speciální význam hodnot 00... 00 a 11... 11 - kódování ±0, ±oo, ±NaN (De)motivační příklad Předpoklady a návaznosti Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítání Katastrofální zrušení Násobení a délen M éře ní rychlosti výpočtu Přetečení a podtečeni Porovnávání Numerická stabilita Domácí úkol Shrnutí □ 4 ► 4 = ► < -Š ► 14/37 Čísla v plovoucí řádové čárce nejběžnější typy - velikosti v bitech a rozsah exponentu typ exp. mantis a celkem rozsah exp. Single (float) 8 23 32 127 Double 11 52 64 1023 Quad (long double) 15 112 128 16383 tj. např. největší číslo typu float je 2127 nej menší nenulové 2~126 = 1CT37 relativní chyba je omezena 2~25 = 10~8 ► tedy počítáme na cca. 8 platných cifer 10 38 (De)motivační přiklad Předpoklady a návaznosti Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítáni Katastrofálni zrušeni Násobeni a délen M éře ni rychlosti výpočtu Přetečeni a podtečeni Porovnáváni Numerická stabilita Domácí úkol Shrnutí 15/37 Problémy konečné reprezentace Ztráta přesnosti sčítání pro zjednodušení v desítkové soustavě a na 3 platné cifry mantisy sečtěme 1.23e3 a l.OOeO ► nutné sjednocení exponentů: 1.23e3 +0.001e3 = 1.231e3 = 1.23e3 ► v rámci dané přesnosti korektní výsledek (De)motivační příklad Předpoklady a návaznosti Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítání Katastrofální zrušení Násobení a délen M éře ní rychlosti výpočtu Přetečení a podtečení Porovnávání Numerická stabilita Domácí úkol Shrnutí □ 4 S1 ► < ■= * < ► 16/37 Problémy konečné reprezentace Ztráta přesnosti sčítání ► pro zjednodušení v desítkové soustavě a na 3 platné cifry mantisy ► sečtěme 1.23e3 a l.OOeO ► nutné sjednocení exponentů: 1.23e3 +0.001e3 = 1.231e3 = 1.23e3 ► v rámci dané přesnosti korektní výsledek ► k 1.23e3 desetkrát přičtěme l.OOeO ► opakované aplikování předchozího postupu dává opět 1.23e3 ► nemusí to být to, co jsme chtěli ► 1.23e3 + (l.OOeO + ■ ■ ■ + l.OOeO) = 1.24e3 Problémy konečné reprezentace Ztráta přesnosti sčítání ► pro zjednodušení v desítkové soustavě a na 3 platné cifry mantisy ► sečtěme 1.23e3 a l.OOeO ► nutné sjednocení exponentů: 1.23e3 +0.001e3 = 1.231e3 = 1.23e3 ► v rámci dané přesnosti korektní výsledek ► k 1.23e3 desetkrát přičtěme l.OOeO ► opakované aplikování předchozího postupu dává opět 1.23e3 ► nemusí to být to, co jsme chtěli ► 1.23e3 + (l.OOeO + ■ ■ ■ + l.OOeO) = 1.24e3 ► operace v plovoucí řádové čárce nejsou asociativní ► ani tam, kde jsme na to z algebry zvyklí Problémy konečné reprezentace Ztráta přesnosti sčítání Rada #1 Čekáme-li kumulativní efekt, sčítání a odčítání je třeba provést nejprve na číslech se srovnatelným exponentem. (De)motivační příklad Předpoklady a návaznosti Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítání Katastrofální zrušení Násobení a délen M éře ní rychlosti výpočtu Přetečení a podtečení Porovnávání Numerická stabilita Domácí úkol Shrnuti □ 4 ► 4 = ► < -Š ► 17/37 Problémy konečné reprezentace Katastrofální zrušení ► odečtení dvou vzájemně blízkých čísel vede k výrazné ztrátě přesnosti (De)motivacní příklad Píedpokliuiy a návazností Čísla v plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítání Katastrofální zrušeni Násobeni a dělení Měření rychlosti výpočtu Pŕeteifľi:i .1 podtečení Porovnávání Numerická stabilita Domácí úkol Shrnutí 18/37 Problémy konečné reprezentace Katastrofální zrušení odečtení dvou vzájemně blízkých čísel vede k výrazné ztrátě přesnosti rozdíl dvou měření s přesností na 3 platné cifry: 1.23 - 1.22 binární reprezentace: 1.0011101 a 1.0011100 ► zatížena chybami 0.3 % a 0.1 % (De)motivační příklad Předpoklady a návaznosti Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítání Katastrofální zrušení Násobení a délen M éře ní rychlosti výpočtu Přetečení a podtečení Porovnávání Numerická stabilita Domácí úkol Shrnutí □ 4 S1 ► < ■= * < ► 18/37 Problémy konečné reprezentace Katastrofální zrušení odečtení dvou vzájemně blízkých čísel vede k výrazné ztrátě přesnosti rozdíl dvou měření s přesností na 3 platné cifry: 1.23 - 1.22 binární reprezentace: 1.0011101 a 1.0011100 ► zatížena chybami 0.3 % a 0.1 % odečtením dostaneme binárně 0.0000001, tj. 0.0078125 ► správný výsledek byl 0.01, relativní chyba 22 % ► navíc působí dojmem falešné přesnosti (De)motivační příklad Předpoklady a návaznosti Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítání Katastrofální zrušení Násobení a délen M éře ní rychlosti výpočtu Přetečení a podtečení Porovnávání Numerická stabilita Domácí úkol Shrnutí □ 4 ► 4 ■= * < ► 18/37 Problémy konečné reprezentace Katastrofální zrušení ► odečtení dvou vzájemně blízkých čísel vede k výrazné ztrátě přesnosti ► rozdíl dvou měření s přesností na 3 platné cifry: 1.23 - 1.22 ► binární reprezentace: 1.0011101 a 1.0011100 ► zatížena chybami 0.3 % a 0.1 % ► odečtením dostaneme binárně 0.0000001, tj. 0.0078125 ► správný výsledek byl 0.01, relativní chyba 22 % ► navíc působí dojmem falešné přesnosti Rada #2 Vyhněme se odčítání dvou blízkých čísel. Je-li to i tak nezbytné, počítejme s výsledkem zatíženým potenciálně velkou chybou. Problémy konečné reprezentace Násobení a dělení ► samo o sobě nezanáší významnou chybu ► zachovává existující chybu PA081: Programování numerických výpočtů A. Křenek O čem to bude (De)motivační příklad Obsah předmětu Předpoklady a návaznosti Zkouška Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítání Katastrofální zrušení Násobení a délení Měření rychlosti výpočtu Přetečení a podtečení Porovnávání Numerická stabilita Domácí úkol Shrnuti □ 4 ► 4 = ► < -Š ► 19/37 Problémy konečné reprezentace Násobení a dělení ► samo o sobě nezanáší významnou chybu ► zachovává existující chybu ► příklad: (a + b)2 pro a = 1.23, b = 0.0155, na 3 cifry ► přesný výsledek je 1.55127025 PA081: Programování numerických výpočtů A. Křenek O čem to bude (De)motivační příklad Obsah předmětu Předpoklady a návaznosti Zkouška Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítání Katastrofální zrušení Násobení a délení Měření rychlosti výpočtu Přetečení a podtečení Porovnávání Numerická stabilita Domácí úkol Shrnutí □ 4 ► 4 š ► < -E ► 19/37 Problémy konečné reprezentace Násobení a dělení ► samo o sobě nezanáší významnou chybu ► zachovává existující chybu ► příklad: (a + b)2 pro a = 1.23, b = 0.0155, na 3 cifry ► přesný výsledek je 1.55127025 ► přímý výpočet na 3 platné cifry: a + b = 1.23 + 0.02 = 1.25 ► tedy (a + b)2 = 1.56, chyba 0.56% ► není to tak zlé, ale může být lepší PA081: Programování numerických výpočtů A. Křenek O čem to bude (De)motivační příklad Obsah předmětu Předpoklady a návaznosti Zkouška Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítáni Katastrofální zrušeni Násobení a děleni Měřeni rychlosti výpočtu Přetečeni a podtečeni Porovnáváni Numerická stabilita Domácí úkol Shrnuti □ 4 ► 4 ■= * < ► 19/37 Problémy konečné reprezentace Násobení a dělení ► po transformaci (a + b)2 = a2 + 2ab + b2 1.51 + 2 x 0.0191 + 0.000240 1.51 + 0.0382 + 0.000240 ► chyba 0.082 %, tedy téměř o řád menší za cenu 6 aritmetických operací místo 2 ► bude 3x pomalejší Problémy konečné reprezentace Násobení a dělení ► po transformaci (a + b)2 = a2 + 2ab + b2 1.51 + 2 x 0.0191 + 0.000240 1.51 + 0.0382 + 0.000240 ► chyba 0.082 %, tedy téměř o řád menší za cenu 6 aritmetických operací místo 2 ► bude 3x pomalejší ... uvidíme Měření rychlosti výpočtu Naivní přístup POSrX volání getti meofdayQ getti meofdayC&start,NULL) ; c = a + b; c *= c; getti meofdayC&stop,NULL); současné CPU 2-3 GHz 1 aritmetická operace ~ 1-10 ns nemáme tak přesné hodiny (De)motivační příklad Předpoklady a návaznosti Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítání Katastrofální zrušení Násobení a délen M éře ní rychlosti výpočtu Přetečení a podtečení Porovnávání Numerická stabilita Domácí úkol Shrnutí □ trpí stejným problémem ► záludnější podoba a komplikovanější řešení ► chci porovnat přesné hodnoty x a y ► znám jen přibližná (spočtená) x = x ± ex, ý i-•-1 x y y y (De)motivační příklad Předpoklady a návaznosti Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítání Katastrofální zrušení Násobení a délen M éře ni rychlosti výpočtu Přetečeni a podtečeni Porovnáváni Numerická stabilita Domácí úkol Shrnuti □ 4 ► 4 š ► < -E ► 31/37 Problémy konečné reprezentace Porovnávání ► porovnávání < a > trpí stejným problémem ► záludnější podoba a komplikovanější řešení ► chci porovnat přesné hodnoty x a y ► znám jen přibližná (spočtená) x = x ± ex, ý = y ± ey: i-•-1 x y y opatrný („miserly") přístup ► intervaly se i částečně překrývají => tvrdíme x = y ► jinak porovnáme x $ y (De)motivační příklad Předpoklady a návaznosti Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítání Katastrofální zrušeni Násobení a délen M éře ní rychlosti výpočtu Přetečení a podtečeni Porovnávání Numerická stabilita Domácí úkol Shrnutí 31/37 Problémy konečné reprezentace Porovnávání ► porovnávání < a > trpí stejným problémem ► záludnější podoba a komplikovanější řešení ► chci porovnat přesné hodnoty x a y ► znám jen přibližná (spočtená) x = x ± ex, ý = y i-•-1 x y y opatrný („miserly") přístup ► intervaly se i částečně překrývají: ► jinak porovnáme x $ y tvrdíme x = y hladový („eager") přístup ► chceme vědět, že mohlo nastat x > y porovnávame x + ex > y - e y- (De)motivační příklad Předpoklady a návaznosti Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítání Katastrofální zrušení Násobení a dělen Měření rychlosti výpočtu Přetečení a podtečení Porovnávání Numerická stabilita Domácí úkol Shrnutí 31/37 Problémy konečné reprezentace Porovnávání Rada #5 Na rovnost porovnávejme vždy s tolerancí. U porovnaní na nerovnost si uvědomme, co chceme vědět PA081: Programování numerických výpočtů A. Křenek O čem to bude (De)motivační příklad Obsah předmětu Předpoklady a návaznosti Zkouška Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítání Katastrofální zrušení Násobení a délení Měření rychlosti výpočtu Přetečení a podtečení Porovnávání Numerická stabilita Domácí úkol Shrnutí □ 4 ► 4 = ► < -Š ► 32/37 Numerická stabilita (Pseudo)definice ► „metoda počítá sice špatně, ale jenom trochu špatně" ► žádoucí a přitom realistická vlastnost všech numerických algoritmů Numerická stabilita (Pseudo)defiiiice ► „metoda počítá sice špatně, ale jenom trochu špatně" ► žádoucí a přitom realistická vlastnost všech numerických algoritmů ► pro vstup x hledáme řešení y = f (x) ► ve skutečnosti ► na aproximaci vstupu x = x + ex ► nepřesnou numerickou metodou / ► dostaneme výsledek y = y + ey (De)motivační přiklad Předpoklady a návaznosti Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítáni Katastrofální zrušení Násobení a délen M éře ní rychlosti výpočtu Přetečení a podtečeni Porovnávání Numerická stabilita Domácí úkol Shrnutí □ 4 ► 4 ■= * < ► 33/37 Numerická stabilita (Pseudo)defúiice ► „metoda počítá sice špatně, ale jenom trochu špatně" ► žádoucí a přitom realistická vlastnost všech numerických algoritmů ► pro vstup x hledáme řešení y = f (x) ► ve skutečnosti ► na aproximaci vstupu x = x + ex ► nepřesnou numerickou metodou / ► dostaneme výsledek y = y + ey ► algoritmus je stabilní, £ existuj e-li pro každé x malé ex tak, že ey je malé ► „malé e" znamená zpravidla |e| < \5x\ (De)motivacni příklad Předpoklady a návaznosti Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítáni Katastrofální zrušeni Násobení a délen M éře ni rychlosti výpočtu Přetečeni a podtečeni Porovnáváni Numerická stabilita Domácí úkol Shrnuti □ 4 ► 4 š ► < -E ► 33/37 Numerická stabilita (Pseudo)definice ► „metoda počítá sice špatně, ale jenom trochu špatně" ► žádoucí a přitom realistická vlastnost všech numerických algoritmů ► pro vstup x hledáme řešení y = f (x) ► ve skutečnosti ► na aproximaci vstupu x = x + ex ► nepřesnou numerickou metodou / ► dostaneme výsledek y = y + ey ► algoritmus je stabilní, £ existuj e-li pro každé x malé ex tak, že ey je malé ► „malé e" znamená zpravidla |e| < \5x\ silnější definice zpětné stability 0 (De)motivační příklad Předpoklady a návaznosti Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítání Katastrofální zrušení Násobení a délen M éře ní rychlosti výpočtu Přetečení a podtečení Porovnávání Numerická stabilita Domácí úkol Shrnuti □ 4 (5 ► 4 š ► < -E ► 33/37 Numerická stabilita (Pseudo)definice ► „metoda počítá sice špatně, ale jenom trochu špatně" ► žádoucí a přitom realistická vlastnost všech numerických algoritmů ► pro vstup x hledáme řešení y = f (x] ► ve skutečnosti ► na aproximaci vstupu x = x + ex *■ nepřesnou numerickou metodou / ► dostaneme výsledek y = y + ey ► algoritmus je stabilní, 6 existuj e-li pro každé x malé ex tak, že ey je malé ► „malé e" znamená zpravidla |e| < \ôx\ silnější definice zpětné stability 0 pro speciální druhy problémů jiné definice stability ► např. numerické integrování - „systém nevybuchne" (De)motivační příklad Předpoklady a návaznosti Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítání Katastrofální zrušení Násobení a délen M éře ní rychlosti výpočtu Přetečeni a podtečeni Porovnávání Numerická stabilita Domácí úkol Shrnutí Numerická stabilita Příklady ► addss je numericky stabilní implementace sčítání y = x\ + x2 ► zvolíme 5 = 2~22 ► relatívni chyba sčítání v typu float je \5a\ < 2~25 ► relativní chyba uložení čísel 5^2 < 2~25 ý = adds(xi, x2) = (*i + x2)(l + 5a) = xi(l + 5i)(l + 5fl)+x2(l + 52)(l + 5fl) = (xi + x2) + xi(5i + 5a + 5i5a) + x2(52 + 5a - ► i v nejhorším případě \ 5\t2 + 5a + 5\t25a\ < 3 x 2 ► pro nejhorší případ x\ = x2 nastane - 525a) -25 \y - y\ |2xi(5i 5\5a \5y\ (De)motivační příklad Předpoklady a návaznosti Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítání Katastrofální zrušení Násobení a délen M éře ní rychlosti výpočtu Přetečení a podtečení Porovnávání Numerická stabilita Domácí úkol Shrnuti □ 4 ► 4 = ► < -Š ► 34/37 Numerická stabilita Příklady ► sčítání řady čísel 1230 + 1 + 1 + 1 + ... je nestabilní ► stabilní alternativa - setřídit a začít od nejmenšího PA081: Programování numerických výpočtů A. Křenek O čem to bude (De)motivační příklad Obsah předmětu Předpoklady a návaznosti Zkouška Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítáni Katastrofální zrušeni Násobení a déleni Měřeni rychlosti výpočtu Přetečeni a podtečeni Porovnáváni Numerická stabilita Domácí úkol Shrnuti □ 4 ► 4 = ► < -Š ► 35/37 Numerická stabilita Příklady ► sčítání řady čísel 1230 + 1 + 1 + 1 + ... je nestabilní ► stabilní alternativa - setřídit a začít od nejmenšího ► úvodní příklad En = 1 - nEn-i ► pro dostatečně velké N položíme Em = 0 ► počítáme 1-En -fcn-l - - n ► v každém kroku je chyba redukována faktorem 1/n Domácí úkol ► vhodně instrumentujte program: a změřte dobu trvání každé iterace cyklu zvlášť pozorujte různé chování programu při volbě -ffast-math kompilátoru gcc odevzdejte ► instrumentovaný program ► dobu trvání pro jednotlivé iterace ► komentáře k zajímavým průvodním jevům termín 29.2. (De)motivační příklad Předpoklady a návaznosti Čísla V plovoucí řádové čárce Reprezentace IEEE 754 Nepřesné sčítáni Katastrofální zrušení Násobení a délen M éře ní rychlosti výpočtu Přetečení a podtečení Porovnávání Numerická stabilita Domácí úkol Shrnutí Shrnutí ► matematické modely reality ► použití idealizovaného aparátu reálných čísel ► konečná reprezentace čísel je zdrojem problémů ► různé projevy pro různé operace ► míra závadnosti formalizována pojmem numerické stability ► cílem je najít numericky stabilní metodu ► rychlost kritické části výpočtu ► změření nemusí být triviální ► příště se pustíme do konkrétních problémů