Numerické metody 2. přednáška Jiří Zelinka 28. února 2017 Jiří Zelinka Numerické metody 2. přednáška 1= ^) c\ o 1/21 Si + s2 = -s. 51 = -x2(a—sin a) 52 = ir2 [(27r-2a) -sin(27r - 2a)] Zelinka 3/21 x/2 a = cos — a x = 2r cos — 2 r < x < V2i TT 2tT - < a < — 2 3 a = tan a— 7T 2cosce Numerické metody 2. přednáška 4/21 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 5/21 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 6/21 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 7/21 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 8/21 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 9/21 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}™=Q konverguje k bodu £. • odpuzující (repulzivní) pevný bod, jestliže existuje takové okolí U bodu £, že pro každou počáteční aproximaci x0 G iV,x0 7^ £, existuje takové k, že x^ 0 U. 10/21 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. 1= ^T) <\ Q» 11/21 Důsledek: Nechť g G C[a, 6], g : [a, 6] —> [a, 6], £ je pevný bod a nechť g" má v okolí bodu £ spojitou derivaci. • Je-li < 1, pak £ je přitahující pevný bod. • Je-li > 1, pak £ je odpuzující pevný bod. 1= ^T) <\ O 12/21 Hledání vhodného tvaru iterační funkce f(x) = o Příklad Výpočet ýíÔ x — x — f_(x) k f_(x) h{x) = X Jiří Zelinka Numerické metody 2. přednáška 13/21 Řá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 ~ t *k-ď 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 14/21 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 Jiří Zelinka Numerické metody 2. přednáška 1= ^<\(y 17/21 Věta Nechť f G C2[a, b]. Nechť £ G [a, b] je kořenem rovnice ŕ(x) = 0 a r(£) 0. Pak existuje S > 0 tak, že posloupnost {x^j^Q generovaná Newtonovou metodou konverguje k bodu £ pro každou počáteční aproximaci x0 G [£ — 5, £ + 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 18/21 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 19/21 Chování chyby u Newtonovy metody Věta Nechť jsou splněny předpoklady předchozí věty, M = max|r~"(x)|, m = min |r"'(x)| > 0, / = [£-£,£ + <*]. Pak pro posloupnost {xk}^=Q generovanou Newtonovou metodou platí a) |xfc+i - £| < b) \xk+1 - £| < Důkaz Z Taylorova rozvoje. BIM-*")2 20/21 Domácí úkol: Výpočet převrácené hodnoty bez dělení pomocí Newtonovy metody 1= ^T) <\ O 21/21