Numerické metody Jiří Zelinka jaro 2016 □ S1 Jiří Zelinka Numerické metody 1= ^T) <\ O 1/15 • 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 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 o Lineární algebra • Diferenciální počet v IR (IR") • Integrální počet v IR Jiří Zelinka Numerické metody 1= ^T) <\ O 3/15 Chyby x: přesná hodnota, x: aproximace x x — x: absolutní chyba aproximace x x — x < a: odhad absolutní chyby relativní chyba < S: odhad relativní chyby x—x Jirí Zelinka Numerické metody 1= ^T) <\ O 4/15 Symbolika O, o f - funkce definovaná v okolí bodu a (může být i a = ±oc) g - funkce nenulová v prstencovém okolí bodu a f(x) f(x) = 0(g(x)) pro x —>► a nmsup < oc. Význam: funkce f se v okolí bodu a chová „podobně11 jako funkce g\ r(x) = o(g-(x)) pro x —> a I im|íM=0. Význam: funkce Z7 konverguje v bodě a k nule „rychleji11 než funkce g\ □ e Jiří Zelinka Numerické metody 1= ^) c\ o 5/15 Podobně an = 0(bn) nebo an = o(bn) pro n —>► oc, kde jsou prvky posloupností. Dodatek „pro x —>► a" se často vynechává, pokud je jasné, o které a se jedná. Např. an = 0(1//?), /r(/7) = o(h3). Příklad: Taylorův rozvoj f(X + h) = f(X) + f'{x)h + h2 f{x+h) = f{x)+f'{x)h+0{h2), f{x+h) = f{x)+f'{x)h+o{h) □ e Jiří Zelinka Numerické metody Motivační příklad Pro kružnici ki o poloměru r sestrojte kružnici l<2 se středem na kružnici ki tak, aby oblast ohraničena oběma kružnicemi měla poloviční obsah než vnitřek kružnice k\. Jiří Zelinka Numerické metody 1= ^<\(y 7/15 Ú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 1= ^T) <\ O 8/15 Řešení nelineárních rovnic Řešíme rovnici f(x) = 0 na uzavřeném intervalu / = [a, b], pro reálnou spojitou funkci f, £ - řešení rovnice, Iteračníproces: vytváříme posloupnost (x/J^q, —>► £. (x/c)/^L0 ~ 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, 6i = x0, jinak ai = x0, bi = tedy £ G [ai,ŕ>i]. □ e Jiří Zelinka Numerické metody 9/15 Obecně: známe a*, bk, f{^k) * f{bk) < 0, tedy £ G [a/c, položíme Xk = (a/c + bk)/2. Pokud f(ak) ' f{xk) < 0 volíme 3/c+i = a*, bk+i = x*, jinak tedy £ G [a*+i,£*+i]. Odhad absolutní chyby v /c-tém kroku: fe-a 2^+i Algoritmus končí, pokud je absolutní chyba dostatečně malá □ e Jiří Zelinka Numerické metody 1= ^T) <\ O 10/15 Metoda pevného bodu, prostá iterační metoda • Tato metoda se používá pro rovnici x = g(x) • Funkce g je spojitá na / = [a, b] • Řešení £ této rovnice nazýváme pevným bodem funkce g Iterační proces • Zvolíme x0 G / a položíme xi = g(xo) • Obecně xk+1 = g(xk) • Funkce g se nazývá iterační funkce □ e Jiří Zelinka Numerické metody 11/15 Geometrická interpretace Pevný bod £ je průsečík grafu funkce g a přímky y = x. □ S Jiří Zelinka Numerické metody 1= ^) c\ o 12/15 Existence pevného bodu Věta: Jestliže spojitá funkce g zobrazuje interval / do sebe, tj. pro každé x G / platí g(x) G /, pak na intervalu / existuje alespoň jeden pevný bod £ funkce g. Jednoznačnost pevného bodu Definice Funkce g zobrazující interval / do sebe se nazývá kontrakce na /, jestliže existuje taková konstanta L (Lipschitzova konstanta), 0 < L < 1, že pro každé x,y G / platí \g{*) ~g(y)\