Numerické metody 2. přednáška Jiří Zelinka 3. března 2016 1/18 Opakování Metoda pevného bodu, prostá iteracní metoda • Tato metoda se používá pro rovnici x = g{x) • Funkce g je spojitá na / = [a, b] v o Ř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(x0) • Obecně xk+1 = g(xk) o Funkce g se nazývá iterační funkce 2/18 Geometrická interpretace Pevný bod £ je průsečík grafu funkce g a přímky y = x. □ s Jiří Zelinka Numerické metody 2. přednáška 1= ^) c\ o 3/18 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)\ Jiří Zelinka Numerické metody 2. prednáška 4/18 Odhad chyby Věta: Nechť g je kontrakce s Lipschitzovou konstantou L na / a x0 G / je libovolné. Pak pro iterační posloupnost definovanou vztahem x^+i = g{x^) platí odhad xk-a< 1 - L Xq -Xi Určení konstanty L pomocí derivace Lagrangeova věta o střední hodnotě: «"(*) - g{y) = g\l>) ' (* - y) Pokud pro každé x G / platí |g"'(x)l — ^ < 1 a S zobrazuje / do sebe, je g kontrakce na /. L = max \gf{x) Konec opakování Jiří Zelinka Numerické metody 2. přednáška 5/18 Další typy iteračních funkcí (metod) Vícekroková metoda x/c+l — g{xk,Xk-li • • • ,Xfr_s+i) Nestacionární metoda X/c+l = gkM Nestacionární vícekroková metoda Jiří Zelinka Numerické metody 2. přednáška 1= ^) c\ o 6/18 Klasifikace pevných bodů Pevný bod £ funkce g se nazývá • přitahující (atraktivní) pevný bod, jestliže existuje takové okolí V tohoto bodu £, že pro každou počáteční aproximaci x0 G V posloupnost iterací {xk}™=0 konverguje k bodu £. • odpuzující (repulzivní) pevný bod, jestliže existuje takové okolí U bodu £, že pro každou počáteční aproximaci x° G (7,x0 7^ £, existuje takové /c, že 0 U. □ Jiří Zelinka Numerické metody 2. prednáška 7/18 Veta: Nechť g e C[a, b],g : [a, 6] —>► [a, 6] a nechť £ je pevný bod. • Jestliže pro všechna x/(z nějakého okolí V bodu £ platí g(*) - ár(0 < i pak £ je přitahující pevný bod. • Jestliže pro všechna x/(z nějakého okolí £7 bodu £ platí g(*) ~ gfé) x-£ > 1 pak £ je odpuzující pevný bod. 8/18 Důsledek: Nechť g e C[a, b], g : [a, b] —)► [a, 6] a nechť g má v bodě £ derivaci. • Je-li \gf{C)\ < 1. Pak £ je přitahující pevný bod. • Je-li > 1, pak £ je odpuzující pevný bod. 9/18 Hledání vhodného tvaru iterační funkce f(x) = o X — X — f(x) k f_(x) h(x) = X Jiří Zelinka Numerické metody 2. přednáška 10/18 Řád metody Rád konvergence posloupnosti Definice Mějme posloupnost (xn) lim = £. Chyba v /c-tém členu: — x/c — £ Existuje-li nyní reálné číslo p > 1 takové, že platí im k^řoc *k+i ~ £ im k^řoc řekneme, řád konvergence posloupnosti je p. Pokud posloupnost (xn) byla získána nějakou iterační metodou, říkáme, že metoda je řádu p. Poznámka: Definici lze použít pro libovolné (např. vícekrokové nebo nestacionární) iterační metody. Jiří Zelinka Numerické metody 2. přednáška 1= ^) c\ o 11/18 Rád prosté iteracní metody Věta: Nechť funkce g má v okolí bodu £ derivace až do řádu p > 1 včetně. Iteracní metoda x^+i = g"(x/c), /c = 0,1,... je řádu p tehdy a jen tehdy když platí £ = *(0, ř°')(0 = o, i<7 0 tak, že posloupnost {x^j^Q generovaná Newtonovou metodou konverguje k bodu £ pro každou počáteční aproximaci x° G [£ — 5, £ + ô] C [a, 6]. Důkaz Ukážeme, že na [£ — 5, £ + 5] je funkce g(x) = x — kontrakcí. Důsledek: Newtonova metoda je metoda druhého řádu pro jednoduchý kořen £. 1= ^) c\ o 15/18 Příklad Výpočet \/ÍÔ: f (x) = x3 - 10, x e I = [2,3] x3-10 2 10 g(x) = x---— = -x H--- &y ' 3x2 3 3x2 x0 = 2, xi = 2.1667, x2 = 2.1545, x3 = 2.1544 Jiří Zelinka Numerické metody 2. přednáška 16/18 Chování chyby u Newtonovy metody Věta Nechť jsou splněny předpoklady předchozí věty, M = max|ŕ~"(x)|, m = min \f'(x)\ > 0, / = [£-£,£ + <*]. Pak pro posloupnost {xk}^=Q generovanou Newtonovou metodou platí a) |xfc+i - £| < b) \xk+1 - £| < Důkaz Z Taylorova rozvoje. BIM-*")2 17/18 Fourierovy podmínky Veta Nechť f e C2[a, b] a nechť rovnice f(x) = 0 má v intervalu jediný kořen £. Nechť f'f f" nemění znaménka na intervalu [a, b], přičemž f (x) ^ 0, Vx £ [a, 6]. Nechť počáteční aproximace x0 je ten z krajních bodů a, 6, v němž znaménko funkce je stejné jako znaménko f" na intervalu [a, b]. Pak posloupnost {x/rj^Q určená Newtonovou metodou konverguje monotónně k bodu £. Příklady - volba počáteční iterace Výpočet převrácené hodnoty, funkce arctanx. 18/18