Transcript
Moderní numerické metody Doc. RNDr. Jaromír Baštinec, CSc. RNDr. Michal Novák, Ph.D. ÚSTAV MATEMATIKY Moderní numerické metody 1 Obsah 1 Úvod Označení Princip numerických metod, teorie chyb, Banachova věta o pevném bodu Úvod Chyby při numerických výpočtech Šíření chyb při aritmetických operacích Podmíněnost úloh Richardsonova extrapolace Metriky, kontrakce, Banachova věta Shrnutí Řešení soustav lineárních rovnic Úvod Soustavy lineárních rovnic Základní pojmy Řešení soustav Gaussova eliminační metoda Úplný a částečný výběr hlavního prvku Metoda LU-rozkladu Řešení pomocí inverzní matice Iterační metody řešení Jacobiho iterační metoda Gaussova Seidelova iterační metoda Stabilita řešení numerické úlohy Relaxační metody Metoda největšího spádu Metoda sdružených gradientů Shrnutí Řešení rovnic Úvod Základní pojmy Startovací metody Grafická metoda Tabelování funkce Metoda bisekce půlení intervalu Iterační metody Metoda prosté iterace Metoda regula falsi Metoda sečen Příklady na procvičení Metoda tečen 2 Fakulta elektrotechniky a komunikačních technologií VUT v Brně 4.13 Modifikovaná Newtonova metoda Příklady na procvičení Newtonova metoda pro komplexní kořeny Kombinovaná metoda sečen a tečen Příklady na procvičení Řád metody Algebraické rovnice Příklady na procvičení Metoda Laguerrova Metoda Graeffova Lobačevského Metoda Schurova Shrnutí Vlastní čísla Úvod Základní pojmy Numerické metody pro hledání vlastních čísel Klasické metody určení koeficientů charakteristického polynomu Krylovova metoda Faddějevova-Leverrierova metoda Poloha a odhad vlastních čísel Geršgorinovy věty Metody výpočtu dominantního vlastního čísla Mocninná metoda Metoda Rayleighova podílu Výpočet dalších vlastních čísel mocninnou metodou Metody pro výpočet vlastních čísel a vlastních vektorů symetrických matic Jacobiho metoda Householderova matice zrcadlení Givensova-Householderova metoda QR-rozklad Konstrukce QR-rozkladu Srovnání algoritmů QR-rozklad a vlastní čísla matice A QR-algoritmus Podmíněnost problému vlastních čísel Globální číslo podmíněnosti Odhad chyby vypočítaného vlastního čísla Relativní chyba vypočítaného vlastního čísla Shrnutí Soustavy nelineárních rovnic Úvod Základní pojmy Iterační metoda Newtonova metoda Moderní numerické metody Shrnutí Řešení obyčejných diferenciálních rovnic Úvod Cauchyova úloha Základní analytické metody Lineární rovnice Bernoulliho rovnice Exaktní rovnice Jednokrokové metody Diferenční metody řešení Cauchyovy úlohy založené na diskretizaci proměnné Eulerova metoda První modifikace Eulerovy metody Druhá modifikace Eulerovy metody Příklady na procvičení Metody Rungeho Kuttovy Stabilita Vícekrokové metody Adamsovy metody Metoda prediktor korektor Metoda prediktor modifikátor korektor Příklady na procvičení Metody založené na užití derivací vyšších řádů Metody Taylorovy řady Shrnutí Diferenciální rovnice vyšších řádů Úvod Základní pojmy Metody pro rovnice druhé řádu Užití Taylorovy řady Shrnutí Řešení soustav obyčejných diferenciálních rovnic Úvod Základní pojmy Eulerova metoda pro soustavy dif.rovnic Příklady na procvičení Rungeho-Kuttova metoda pro soustavy dif.rovnic Příklady na procvičení Metoda Taylorovy řady Zaokrouhlovací chyby Další problémy, které mohou nastat Řízení délky kroku 4 Fakulta elektrotechniky a komunikačních technologií VUT v Brně 9.11 Shrnutí Řešení okrajových úloh pro obyčejné dif. rovnice Úvod Základní pojmy Metoda střelby Metoda konečných diferencí Metoda konečných objemů Příklady na procvičení Shrnutí Metoda konečných prvků Úvod Základní pojmy Shrnutí Parciální diferenciální rovnice Úvod Základní pojmy Parciální diferenciální rovnice prvního řádu Formulace počáteční úlohy Nejjednodušší příklady parciálních rovnic prvního řádu z(x, y) Rovnice typu = x z(x, y) Rovnice typu = f(x, y) x z(x, y) Rovnice typu = f 1 (x) f 2 (z) x 12.6 Řešené příklady Cvičení Lineární homogenní parciální rovnice prvního řádu Shrnutí Parciální diferenciální rovnice druhého řádu Úvod Klasifikace rovnic na hyperbolické, parabolické a eliptické) Transformace proměnných Řešené příklady Cvičení Metoda konečných diferencí pro PDR Shrnutí Metoda konečných prvků pro parciální dif. rovnice Úvod Základní pojmy Shrnutí Moderní numerické metody 5 15 Výsledky Metoda sečen Modifikovaná Newtonova metoda Kombinovaná metoda sečen a tečen Algebraické rovnice Vícekrokové metody řešení počátečních úloh Eulerova metoda pro soustavy Metody Rungeho Kuttovy pro soustavy Metoda konečných diferencí Dodatky Ukázky zadání 6 Fakulta elektrotechniky a komunikačních technologií VUT v Brně Seznam obrázků 4.1 Problém malého úhlu ϕ Geometrický smysl metody sečen Geometrický smysl metody tečen Problém u metody tečen Geometrický smysl modifikované metody tečen Geometrický smysl kombinované metody sečen a tečen Příklad řešení diferenciální rovnice Geometrický smysl Eulerovy metody Geometrický smysl první modifikace Eulerovy metody Geometrický smysl druhé modifikace Eulerovy metody Geometrický smysl metody střelby Počáteční křivka z příkladu Zobrazení řešení příkladu Hranice oblasti Problém u metody konečných diferencí Moderní numerické metody 7 1 Úvod Motto: Učitel Vám může pootevřít dvéře, vstoupit už musíte sami. Čínské přísloví Cílem předmětu Moderní numerické metody je naučit Vás použití vybraných numerických metod při řešení úloh, které obecně nejdou řešit analytickým způsobem. Snahou autorů bylo, aby jste zvládli nejen praktické použití numerických metod, ale aby jste se naučili i poznávat jejich možnosti, omezení a nedostatky. Text obsahuje i řadu příkladů pro samostatnou práci, včetně jejich výsledků. Uvítáme Vaše názory, připomínky a komentáře. Autoři 8 Fakulta elektrotechniky a komunikačních technologií VUT v Brně 1.1 Označení N množina přirozených čísel Z množina celých čísel R množina reálných čísel Q množina racionálních čísel I množina iracionálních čísel C množina komplexních čísel P n (x) polynom n-tého stupně proměnné x A m,n matice typu m, n (s m řádky a n sloupci) A = (a ij ) matice s prvky a ij I jednotková matice O nulová matice det A = A determinant matice A A 1 matice inverzní k matici A adj A matice adjungovaná k matici A A ks algebraický doplněk prvku a ks hod (A) hodnost matice A (R n, +,.) vektorový prostor všech uspořádaných n-tic dim P dimenze prostoru P. a a skalární součin vektorů a, b x norma vektoru x konec důkazu A lineární obal množiny A MA A matice přechodu od báze A k bázi A a b vektor a je ortogonální na vektor b f V = g zúžení funkce na podmnožinu A B kartézský součim množin A, B a b vektorový součin vektorů a, b [a, b, c] smíšený součin vektorů a, b, c Moderní numerické metody 9 2 Princip numerických metod, teorie chyb, Banachova věta o pevném bodu. 2.1 Úvod Cílem této kapitoly je seznámit čtenáře se základy teorie chyb, rozdělením chyb a jejich šíření při provádění základních aritmetických operací. Dále si připomeneme Banachovu větu o pevném bodě, která je teoretickým základem pro všechny iterační metody. Seznámí se s podmínkami, které nám zaručují konvergenci jednotlivých iteračních metod k přesnému řešení. Budeme se věnovat odhadům přesnosti výpočtu. 2.2 Chyby při numerických výpočtech. Omyly člověka, poruchy stroje či zařízení jsou také chybami, ale těmi se nebudeme zabývat. Slovo chyba budeme užívat ve smyslu odchylek, které jsou pravidelným a nerozlučným doprovodem každého numerického řešení. Rozeznáváme chyby: vstupních dat chyby měření chyby způsobené zobrazením vstupních dat v počítači, (Příklad π, e, 2,... ). numerické metody limitu nahradíme členem posloupnosti s dosti vysokým indexem. Například: nahrazení funkce jejím rozvojem do Taylorovy řady. sin x = x x3 3! + x5 5! x7 7! +... Volme x = 1, potom při použití prvních tří členů řady budeme mít chybu nejvýše 1 7!. úlohu nahradíme jednodušší. Například: Určit povrch Země. Použijeme-li vztah S = 4πr 2 pro povrch koule o polměru r, potom se dopouštíme chyby, protože jsme Zemi - geoid nahradili koulí. zaokrouhlovací číslo s nekonečným dekadickým rozvojem nahradíme číslem s konečným počtem členů, velká čísla se v počítači zobrazují v semilogaritmickém tvaru, všechny nepřesnosti způsobené realizací algoritmu v počítači, včetně nepřesného provádění aritmetických operací. 10 Fakulta elektrotechniky a komunikačních technologií VUT v Brně Přitom je vhodné mít na paměti, že při řešení konkrétní úlohy se obvykle vyskytují všechny druhy chyb současně. Při výpočtech jsme často nuceni nahradit číslo x jeho aproximací x n. x x n = x absolutní chyba aproximace x n. x x n ε(x n ) odhad absolutní chyby s ní se pracuje x x = x x n relativní chyba aproximace x, x 0 n x x x n x ε(x n) odhad relativní chyby. = δ(x n ) x Absolutní hodnota relativní chyby se často uvádí v procentech. 2.3 Šíření chyb při aritmetických operacích Věta 2.1 Absolutní chyba součtu ( rozdílu ) je rovna součtu ( rozdílu ) absolutních chyb. (x ± y) = x ± y. Důkaz: Máme x ± y = (x n + x) ± (y n + y) = (x n ± y n ) + ( x ± y). Odečtením získáme tvrzení věty. Věta 2.2 Důkaz: (x y) x n y + y n x. x y = (x n + x) (y n + y) = x n y n + x n y + y n x + x y, tvrzení věty dostaneme, jestliže zanedbáme člen x y, o kterém předpokládáme, že je dostatečně malý. Věta 2.3 Důkaz: Obdobně ( ) x x x n y y y n (y n ). 2 x y = x n + x y n + y = x ( n + x 1 + y ) 1 = y n y n poslední závorku vpravo chápeme jako součet geometrické řady a dostáváme = x ( n + x 1 y ) +... y n y n a zanedbáním vyšších řádů dostaneme Odečtením dostaneme tvrzení věty. x n + x x n y y n y n (y n ) 2 Moderní numerické metody 11 Věta 2.4 δ(xy) δ(x) + δ(y), ( ) x δ δ(x) + δ(y). y Relativní chyba součinu či podílu nepřevýší součet relativních chyb činitelů. Důkaz: Analogicky. Samostatně. Definice 2.1 Necht A (množina vstupních dat), B (množina výstupních dat) jsou metrické normované prostory. Řekneme, že úloha y = U(x), x A, y B je korektní na (A, B) jestliže 1) x A!y B takové, že platí y = U(x). 2) Toto řešení spojitě závisí na vstupních datech, t.j. x n x, U(x n ) = y n U(x n ) U(x) = y. Poznámka 2.1 Jestliže A, B jsou Banachovy prostory 1, pak ke spojité závislosti řešení stačí y n y B L x n x A, L = const. Symbol. B označuje normu v prostoru B. Mnohdy dostačuje jen jiná formulace úlohy, aby se z nekorektní úlohy stala úloha korektní. Příklad 2.1 Určit všechny kořeny polynomu. Stačí doplnit podmínku jednoznačnosti: Určit největší reálný kořen a máme korektní úlohu. Běžně se za korektní úlohy považují i úlohy, které lze pouhou změnou formulace převést na korektní. Příklad 2.2 Nekorektní úloha z Mladého světa Kolik stojí kilo hrušek, když v poli stojí jedna? 2.4 Podmíněnost úloh Definice 2.2 Řekneme, že korektní úloha je dobře podmíněna, jestliže malá změna ve vstupních datech vyvolá malou změnu řešení. y y relativní chyba řešení C p = = relativní chyba vstupu x x nazýváme číslem podmíněnosti úlohy y = U(x). 1 Jsou definovány dále, viz poznámka (2.4) 12 Fakulta elektrotechniky a komunikačních technologií VUT v Brně Protože většinou umíme stanovit pouze odhady, tak C p δ(y) δ(x). Jestliže C p 1 je úloha velmi dobře podmíněn. Pro C p velké jde o špatně podmíněnou úlohu. Ale tento pojem je velmi relativní. V praxi se hovoří o špatně podmíněné úloze pro C p 100. Někteří autoři místo o dobré či špatné podmíněnosti používají termín malá či velká citlivost vzhledem ke vstupním datům. Příklad 2.3 p(x) = x 2 + x 1150, ( ) 100 p(33) = 28, p 5.6, 3 (x) = 1 3 (y) = 22.4 C p Přitom jde o hodnoty blízké ke kořenu x = Příklad 2.4 Podmíněnost matic. Necht máme soustavu lineárních algebraických rovnic Ax = b, kde A je matice koeficientů, b je sloupec pravých stran a x je sloupec neznámých. Necht x n je aproximace řešení této soustavy. Označme r = b Ax n, kde r je reziduum. Je-li r malé, ještě to nic neříká o přesnosti výpočtu. r = Ax Ax n = A(x x n ), A 1 r = x x n a jsou-li prvky matice A 1 dostatečně velké, může být i rozdíl x x n velký i pro velmi malé r. Platí C p = A 1 A. Symbolem. označujeme normu matice, viz definici (2.12). Příklad 2.5 b = ( ) x = ( A = ( ) 1, b = 0 ), ( ) x = ( Jde o špatně podmíněnou soustavu s C p ( pro Eukleidovskou normu dostáváme C p 1622 ). Řešení špatně podmíněné soustavy musíme interpretovat velmi opatrně. Je to vlastnost dané matice a proto je vhodné se jim vyhýbat a hledat jiné způsoby řešení problémů. ) Moderní numerické metody 13 Poznámka 2.2 Teoreetické odhady chyb bývají značně pesimistické. Horní hranice chyb bývá většinou jen zřídka dosaženo, protože v průběhu výpoźtu dochází k určité vzájemné kompenzaci chyb. Příkladem může být Eratosthenovo 2 měření obvodu Země. 2.5 Richardsonova extrapolace Jde o univerzální postup, který nám umožňuje pomocí základní metody s nižší přesností vytvářet metody s přesností vyšší. Necht je základní metoda representovaná funkcí F (h) s parametrem h (může jím být například velikost kroku dané metody). Pomocí této metody umíme spočítat hodnotu F (h) pro malé h 0. Chceme co nejp5esn2ji aproximovat hodnotu F (0), kterou ale neumíme určit přímo z funkce F (h). Necht funkci F (h) můžeme zapsat ve tvaru mocninné řady F (h) = a 0 + a 1 h 2 + a 2 h 4 + a 3 h (2.1) Pro malé h můžeme položit h = 0 a dostaneme aproximaci F (0) a 0. Hledejme lepší aproximaci. Podle (2.1) platí F ( ) ( h h = a 0 + a ) 2 + a 2 ( h 2 ) 4 ( ) 6 h + a (2.2) 2 Odstraníme z rovnic (2.1) a (2.2) člen obsahující ( druhou ) mocninu. Ten totiž představuje h největší chybu v rozdílu a 0 F (h) i a 0 F. Rovnici (2.2) vynásobíme čtyřmi a 2 odečteme od ní (2.1), dostaneme ( ) h ( 4F F (h) = 4a 0 + 4a h ) 2 ( h ) 4 ( 4a2 2 + h ) 6 4a a 0 a 1 h 2 a 2 h 4 a 3 h 6... = 3a 0 + 4a 2 ( h 2 ) 4 a2 h 4 + 4a 3 ( h 2 ) 6 a3 h = 3a 0 + a 2 ( 1 4 1) h 4 + a 3 ( 1 8 1) h Eratosthenés z Kýreny ( př.n.l.) rodák z Kýreny v nynější Lybii. Základní vzdělání získal v Athénách. Později působil v Alexandrii, pracoval společně s Eukleidem, Apoloniem z Pergy ( př.n.l.), byl přítelem Archimedovým ( př.n.l.). Eratosthenés byl všestranným pracovníkem věnoval se gramatice, literární historii, matematice, astronomii, chronologii, etice,geografii a kartografii. Pokusil se změřit a vypočítat obvod Země. Jeho výsledek je neuvěřitelně přesně (chyba je asi 0,8%). Jeho kolegové a spolupracovníci mu za jeho pracovitost a dosažené výsledky přezdívali Pentathlos, t.j. atlet pětibojař, který dosahuje výborných výsledků v různých oblastech, ale ani v jedné z nich se nestane nejlepším. Tato přezdívka je spojena s jemnou výčitkou. Stoupenci specializace mu s jistou povýšeností přezdívali Beta (název čísla 2) t.j. druhořadý. Někdy je také tato přezdívka vysvětlována tím, že Eratosthenés byl jako padesátiletý povolán ke dvoru Ptolemaia III. (vládl př.n.l.), kde se stal vychovatelem následníka trůnu. A s tímto titulem, asi jako finanční zabezpečení, byl jmenován i druhým hlavním knihovníkem alexandrijské knihovny. Eratosthenés ke konci života oslepl a dobrovolně odešel ze světa. Z celého jeho rozsáhlého díla se dochovaly pouze zlomky jako citace pozdějších autorů. Eratosthénovo síto k určení prvočísel v množině {1, 2,..., n} se stalo východiskem pro celou jednu část teorie čísel 14 Fakulta elektrotechniky a komunikačních technologií VUT v Brně Rovnici vydělíme třemi a dostaneme novou funkci F 2 (h) = 4F ( h 2 ) F (h) 3 = a 0 + a (2) 2 h 4 + a (2) 3 h (2.3) Přitom platí, že a (2) i a i, i = 2, 3,... Proto je F 2 (h) lepší aproximací pro a 0 než F (h). ( ) h Pro dosti malá h je také F 2 (h) lepší aproximací než F, protože rozdíl F 2 (h) a 0 2 začíná až čtvrtou mocninou h. Dostali jsme tak metodu F 2, která ja pro dostatečně malá h lepší než metoda F. Analogickým způsobem můžeme odstranit z F 2 čtvrtou mocninu a získáme ještě lepší aproximaci F (0). Podle (2.3) platí ( ) h F 2 = a 0 + a (2) 2 h 4 + a (3) 3 h (2.4) 2 Rovnici (2.4 vynásobíme 16 a odečteme od ní rovnici (2.3), výsledek dělíme 15. Dostaneme F 3 (h) = 16F ( h ) 2 2 F2 (h) = a 0 + a (3) 3 h Takto můžeme pokračovat dále a získávat stále lepší aproximace pro které platí ( F i+1 (h) = 4i F h ) i 2 Fi (h) 4 i 1 = a 0 + a (i+1) i+1 h2i přičemž F 1 (h) = F (h). Výpočet si můžeme zapsat do tabulky (vyplňuje se po řádcích) T 00 T 10 T 11 T 20 T 21 T 22 T 30 T 31 T 32 T přičemž ( ) h T s0 = F, s = 0, 1,... 2 s T si = 4i T s,i 1 T s 1,i 1. 4 i 1 Výpočet ukončíme a hodnotu T ss považujeme za dostatečně přesnou, jestliže T ss T s,s 1 ε, kde ε je předem zadaná požadovaná přesnost. Se speciálním případem Richardsonovy extrapolace jste se setkali v předmětu BMA3, když jste si při numerické integraci vyjádřili Simpsonovu metodu pomocí lichoběžníkového pravidla. Moderní numerické metody Metriky, kontrakce, Banachova věta Definice 2.3 Necht M je neprázdná množina. Zobrazení d : M M R splňující pro všechna x, y, z M následující axiomy 1. d(x, y) 0 d(x, y) = 0 x = y, ( nezápornost ) 2. d(x, y) = d(y, x), ( symetrie ) 3. d(x, y) d(x, z) + d(z, y), ( trojúhelníková nerovnost ) nazveme metrikou a dvojici (M, d) metrickým prostorem. Příklad 2.6 a) M R, d(x, y) = x y b) M R n, d(x, y) = n (x i y i ) 2 ( Eukleidovská metrika ) i=1 c) M R n, d(x, y) = max i y i i=1,...,n ( krychlová metrika ) n d) M R n, d(x, y) = x i y i ( oktaetická metrika ) i=1 Definice 2.4 Bod x M je limitou posloupnosti {x n } n=1 v metrickém prostoru (M, d), jestliže ε 0 n 0 N, takové, že n n 0 : d(x n, x) ε. Posloupnost, která má limitu, se nazývá konvergentní. Označení lim n x n = x. Věta 2.5 Každá posloupnost v (M, d) může mít nejvýše jednu limitu. Důkaz byl provedem v 1. semestru. Definice 2.5 Posloupnost {x n } n=1 se nazývá cauchyovská 3, jestliže ε 0 n 0 N takové, že n n 0 p N : d(x n, x n+p ) ε. Věta 2.6 Každá konvergentní posloupnost je cauchyovská. Důkaz: Protože je {x n } konvergentní, existuje limita x = lim x n. To ale (podle předchozích n definic) znamená, že ε/2 0 n 0 N takové, že n n 0 : d(x n, x) 1 ε. Potom ale i 2 p N je i d(x n+p, x) 1 ε. Takže máme (s využitím trojúhelníkové nerovnosti) 2 d(x n, x n+p ) d(x n, x) + d(x n+p, x) 1 2 ε ε = ε. 3 L.A.Cauchy ( ) Francouzský matematik, jeden z tvůrců moderní matematiky. Je autorem více než 800 prací z teorie čísel, algebry, matematické analýzy, diferenciálních rovnic, mechaniky, aj. S využitím pojmu limity vybudoval systematicky základy analýzy. Po červencové revoluci 1830 pobýval nějakou dobu v Praze. 16 Fakulta elektrotechniky a komunikačních technologií VUT v Brně Poznámka 2.3 Z následujícího příkladu vyplývá, že větu nelze obrátit. Příklad 2.7 M = R + = (0, + ), x n = 1 n, lim x n = 0 M. Protože každá posloupnost v (M, d) může mít nevýše jednu limitu, je tento příklad příkladem posloupnosti, která je cauchyovská, ale není v (M, d) konvergentní. Definice 2.6. Metrický prostor (M, d) se nazývá úplný, jestliže v něm má každá cauchyovská posloupnost limitu. Příklad 2.8 Každá uzavřená neprázdná podmnožina metrického prostoru. Definice 2.7 Na množině M je definována binární operace : M M M, jestliže x, y M platí (x y) M. Příklad 2.9 Na množině celých čísel tvoří sčítání binární operaci, protože součet libovolných dvou celých čísel je opět celé číslo. Na množině celých čísel dělení netvoří binární operaci, protože dělení nulou není definováno a existuje nekonečně mnoho dvojic celých čísel, jejichž podíl není číslo celé, jako například čísla 2 a 3. Definice 2.8 Necht M je množina a ( ) je binární operace na M. Uspořádaná dvojice (M, ) se nazývá grupou, jestliže platí A) (x y) z = x (y z), x, y, z M, B) e M : e x = x e = x, x M, C) x M x 1 M : x x 1 = x 1 x = e. Definice 2.9 Pokud v grupě (M, ) platí navíc komutativní zákon D) x y = y x, x, y M, pak mluvíme o komutativní grupě (abelovské grupě). Definice 2.10 Necht (L, +) je komutativní grupa, a necht je dále definována operace : R L L, (α, x) α x, která splňuje následující podmínky x, y L, α, β R: 1. α (β x) = (αβ) x asociativita pro násobení 2. α (x + y) = (α x) + (α y) distributivita I. (α + β) x = (α x) + (β x) distributivita II x = x Potom uspořádaná trojice (L, +, ) tvoří vektorový prostor nad R. Prvky z L budeme nazývat vektory, prvky z R skaláry. Značit budeme vektory malými písmeny latinky a skaláry malými písmeny řecké abeced
