Numerické metody Jiří Zelinka Jiří Zelinka Numerické metody 1 / 14 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 Jiří Zelinka Numerické metody 2 / 14 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 / 14 Motivační příklad Pro kružnici k1 o poloměru r sestrojte kružnici k2 se středem na kružnici k1 o poloměru x 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 4 / 14 Uvedenou oblast rozdělíme na dvě kruhové úseče o obsazích S1 a S2 a označíme si úhly u středů k1 a k2. r x S1 S2 α2α k1 k2 S1 + S2 = 1 2 S S1 = 1 2 x2 (α − sin α) S2 = 1 2 r2 ((2π−2α)−sin(2π−2α)) Jiří Zelinka Numerické metody 5 / 14 Určíme vztah mezi x a r. r x 2 α 2 k1 k2 x/2 r = cos α 2 x = 2r cos α 2 Výslednou rovnici neumíme vyřešit přesně: α · cos α = sin α + π Jiří Zelinka Numerické metody 6 / 14 Chyby x: přesná hodnota, ˜x: aproximace x ˜x − x: absolutní chyba aproximace ˜x |˜x − x| ≤ ε: odhad absolutní chyby x−˜x x : relativní chyba x−˜x x ≤ δ: odhad relativní chyby Jiří Zelinka Numerické metody 7 / 14 Řešení nelineárních rovnic Řešíme rovnici f (x) = 0, funkce f je spojitá na I = [a, b] ξ ∈ I je řešení rovnice neboli kořen funkce f , jestliže f (ξ) = 0 Dostatečná podmínka pro existenci kořene na I: f (a) · f (b) ≤ 0 Proces hledání přibližného řešení Separace kořenů – nalezení intervalů, v nich leží právě jeden kořen Zpřesnění kořenů – konstrukce posloupnosti (xn)∞ n=0, xn → ξ Jiří Zelinka Numerické metody 8 / 14 Metoda půlení intervalu – bisekce f – spojitá na I = [a, b] f (a) · f (b) ≤ 0 Položíme a0 = a, b0 = b, c0 = a0+b0 2 Pokud f (a0) · f (c0) ≤ 0 položíme a1 = a0, b1 = c0, v opačném případě a1 = c0, b1 = b0 Obecně: Položíme ci = ai +bi 2 Pokud f (ai ) · f (ci ) ≤ 0 položíme ai+1 = ai , bi+1 = ci , v opačném případě ai+1 = ci , bi+1 = bi Jiří Zelinka Numerické metody 9 / 14 Odhad chyby u metody bisekce Kořen ξ leží v [ai , bi ] pro každé i ci je aproximace kořene ξ |ξ − ci | ≤ bi −ai 2 = b−a 2i+1 ci → ξ Logaritmováním dokážeme předem určit počet iterací potřebných k dosažení požadované přesnosti. Jiří Zelinka Numerické metody 10 / 14 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ě xi+1 = g(xi ) Funkce g se nazývá iterační funkce Jiří Zelinka Numerické metody 11 / 14 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 12 / 14 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. Důkaz: Položme f (x) = x − g(x). Pak g(a) ≥ a ⇒ f (a) = a − g(a) ≤ 0, g(b) ≤ b ⇒ f (b) = b − g(b) ≥ 0 Protože f je spojitá, existuje ξ takové, že f (ξ) = 0, tedy ξ − g(ξ) = 0, neboli ξ = g(ξ). Jiří Zelinka Numerické metody 13 / 14 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 funkce g je kontrakce na I, pak g má na tomto intervalu jediný pevný bod. Důkaz: Existence plyne z předchozí věty. Pokud by existovaly 2 pevné body ξ1 a ξ2, pak |ξ1 − ξ2| = |g(ξ1) − g(ξ2)| ≤ L|ξ1 − ξ2| < |ξ1 − ξ2| Spor. Poznámka: Tato věta platí obecně v úplných metrických prostorech. Jiří Zelinka Numerické metody 14 / 14