Numerické metody Jiří Zelinka Jaro 2017 Jiří Zelinka Numerické metody 1 / 18 Literatura Horová I., Zelinka J.: Numrické metody, 2. rozšířené vydání, MU, 2004 Ralston A.: Základy numerické matematiky, Academia, 1978 Vitásek E.: Numerické metody, SNTL, 1987 Mathews, J.H., Fink, K.D.: Numerical methods using MATLAB, Pearson Prentice Hall, 2003 Stoer, J., Bulirsch R.: Introduction to Numerical Analysism Spriger, 1992 Jiří Zelinka Numerické metody 2 / 18 Osnova Řešení nelineárních rovnic Polynomy Řešení soustav lineárních rovnic – přímé metody Řešení soustav lineárních rovnic – iterační metody Řešení soustav nelineárních rovnic Předpoklady Lineární algebra Diferenciální počet v R (Rn ) Integrální počet v R Jiří Zelinka Numerické metody 3 / 18 Chyby x: přesná hodnota, ˜x: aproximace x ˜x − x: absolutní chyba ˜x |˜x − x| ≤ α: odhad absolutní chyby x−˜x x : relativní chyba x−˜x x ≤ δ: odhad relativní chyby Řekneme, že aproximace ˜x čísla x má s platných cifer, jestliže s je největší celé nezáporné číslo takové, že platí x − ˜x x ≤ 5.10−s . Nechť x je reálné číslo, které má obecně nekonečné dekadické vyjádření. Číslo x(d) , které má d desetinných míst, je správně zaokrouhlenou hodnotou čísla x, platí-li |x − x(d) | ≤ 1 2 10−d . Ve správně zaokrouhleném čísle jsou všechny cifry platné. Jiří Zelinka Numerické metody 4 / 18 Podmíněnost úloh Ř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í. Je-li y + ∆y resp. y řešení odpovídající vstupním datům x + ∆x resp. x, potom číslo Cp = ∆y y ∆x x = |relativní chyba na výstupu| |relativní chyba na vstupu| nazýváme číslem podmíněnosti úlohy. Je-li Cp ≈ 1, je úloha velmi dobře podmíněna. Pro velká Cp (> 100) je úloha špatně podmíněna. Jiří Zelinka Numerické metody 5 / 18 Typické špatně podmíněné úlohy: dělení malým číslem odečítání dvou přibližně stejných čísel zvětšování chyby v iteračním výpočtu An = n · An−1 Jiří Zelinka Numerické metody 6 / 18 Celková chyba výpočtu Daný problém Matematická formulace Numerická metoda Algoritmus- - Y = F(x1, . . . , xn) y = f (x1, . . . , xn) ˜y = ˜f (˜x1, . . . , ˜xn) Y − y: chyba metody f (x1, x2, . . . , xn) − f (˜x1, . . . , ˜xn): chyba primární f (˜x1, . . . , ˜xn) − ˜f (˜x1, . . . , ˜xn): chyba sekundární Odhad primární chyby: |f (x1, . . . , xn) − f (˜x1, . . . , ˜xn)| ≤ n i=1 Ai αi , kde Ai = sup ∂f ∂xi (x1, . . . , xn) , i = 1, . . . , n. Jiří Zelinka Numerické metody 7 / 18 Symbolika O, o f – funkce definovaná v okolí bodu a (může být i a = ±∞) g – funkce nenulová v prstencovém okolí bodu a f (x) = O(g(x)) pro x → a lim sup x→a |f (x)| |g(x)| < ∞ . Význam: funkce f se v okolí bodu a chová „podobně“ jako funkce g. f (x) = o(g(x)) pro x → a lim x→a |f (x)| |g(x)| = 0 . Význam: funkce f konverguje v bodě a k nule „rychleji “ než funkce g. Jiří Zelinka Numerické metody 8 / 18 Podobně an = O(bn) nebo an = o(bn) pro n → ∞ , kde an, bn jsou prvky posloupností. Dodatek „pro x → a“ se často vynechává, pokud je jasné, o které a se jedná. Např. an = O(1/n), f (h) = o(h3 ). Příklad: Taylorův rozvoj f (x + h) = f (x) + f (x)h + f (ξ) 2 h2 f (x+h) = f (x)+f (x)h+O(h2 ), f (x+h) = f (x)+f (x)h+o(h) Jiří Zelinka Numerické metody 9 / 18 Motivační příklad Pro kružnici k1 o poloměru r sestrojte kružnici k2 se středem na kružnici k1 tak, aby oblast ohraničena oběma kružnicemi měla poloviční obsah než vnitřek kružnice k1. r x k1 k2 Jiří Zelinka Numerické metody 10 / 18 Úloha ze starého Egypta Stojíš před stěnou, za kterou je studna Lotosu jako kruh Slunce. Vedle studny je položen jeden kámen, jedno dláto a dva stvoly třtiny. Jeden stvol je dlouhý tři míry, druhý je dlouhý dvě míry. Stvoly (opřené ve stabilní poloze v diametrálně protilehlých bodech na okraji dna) se kříží na povrchu vody ve studni Lotosu a ten povrch je jednu míru nade dnem. Kdo určí velikost nejdelší délky, kterou lze umístit do dna studny Lotosu, ten si vezme oba stvoly a bude knězem boha Ra. Jiří Zelinka Numerické metody 11 / 18 Řešení nelineárních rovnic Řešíme rovnici f (x) = 0 na uzavřeném intervalu I = [a, b], pro reálnou spojitou funkci f , ξ – řešení rovnice, Iterační proces: vytváříme posloupnost (xk)∞ k=0, xk → ξ. (xk)∞ k=0 – iterační posloupnost. Metoda půlení intervalu – bisekce f (a) · f (b) ≤ 0, a0 = a, b0 = b, položíme x0 = (a0 + b0)/2. Pokud f (a0) · f (x0) ≤ 0 volíme a1 = a0, b1 = x0, jinak a1 = x0, b1 = b0, tedy ξ ∈ [a1, b1]. Jiří Zelinka Numerické metody 12 / 18 Obecně: známe ak, bk, f (ak) · f (bk) ≤ 0, tedy ξ ∈ [ak, bk], položíme xk = (ak + bk)/2. Pokud f (ak) · f (xk) ≤ 0 volíme ak+1 = ak, bk+1 = xk, jinak ak+1 = xk, bk+1 = bk, tedy ξ ∈ [ak+1, bk+1]. Odhad absolutní chyby v k-tém kroku: |xk − ξ| ≤ b − a 2k+1 Algoritmus končí, pokud je absolutní chyba dostatečně malá. Jiří Zelinka Numerické metody 13 / 18 Metoda pevného bodu, prostá iterační metoda Tato metoda se používá pro rovnici x = g(x) Funkce g je spojitá na I = [a, b] Řešení ξ této rovnice nazýváme pevným bodem funkce g Iterační proces Zvolíme x0 ∈ I a položíme x1 = g(x0) Obecně xk+1 = g(xk) Funkce g se nazývá iterační funkce Jiří Zelinka Numerické metody 14 / 18 Geometrická interpretace Pevný bod ξ je průsečík grafu funkce g a přímky y = x. 0 0.2 0.4 0.6 0.8 1 1.2 1.4 0 0.2 0.4 0.6 0.8 1 1.2 1.4 g(x) y=x ξ Jiří Zelinka Numerické metody 15 / 18 Existence pevného bodu Věta: Jestliže spojitá funkce g zobrazuje interval I do sebe, tj. pro každé x ∈ I platí g(x) ∈ I, pak na intervalu I existuje alespoň jeden pevný bod ξ funkce g. Jednoznačnost pevného bodu Definice Funkce g zobrazující interval I do sebe se nazývá kontrakce na I, jestliže existuje taková konstanta L (Lipschitzova konstanta), 0 ≤ L < 1, že pro každé x, y ∈ I platí |g(x) − g(y)| ≤ L|x − y|. Banachova věta o pevném bodě Jestliže g je kontrakce na I, pak g má na tomto intervalu jediný pevný bod a iterační posloupnost definovaná vztahem xk+1 = g(xk) konverguje k pevnému bodu funkce g pro libovolné x0 ∈ I. Jiří Zelinka Numerické metody 16 / 18 Odhad chyby Věta: Nechť g je kontrakce s Lipschitzovou konstantou L na I a x0 ∈ I je libovolné. Pak pro iterační posloupnost definovanou vztahem xk+1 = g(xk) platí odhad |xk − ξ| ≤ Lk 1 − L |x0 − x1| Jiří Zelinka Numerické metody 17 / 18 Určení konstanty L pomocí derivace Lagrangeova věta o střední hodnotě: g(x) − g(y) = g (µ) · (x − y) Bod µ leží mezi x a y. Pokud pro každé x ∈ I platí |g (x)| ≤ L < 1 a g zobrazuje I do sebe, je g kontrakce na I. L = max x∈I |g (x)| Jiří Zelinka Numerické metody 18 / 18