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] • Ř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ě x^+i = g(xk) a Funkce g se nazývá iterační funkce Jiří Zelinka Numerické metody 3. přednáška, 4. března 2015 2/13 Podmínky konvergence O Pro každé x G / platí g(x) G I O Existuje L, 0 < L < 1, že pro každé x,y £ I platí \g{*)-g{y)\ < *-l*-y|- nebo: Pro každé x G / platí |g-'(x)| < L < 1. Pak x0 G / může být libovolné, iterační proces konverguje. Řád metody ,. \xk+i - £| i. |e/t+i| r , n *->oo |x/( — 4| fc->oo |e*| p - řád metody Věta: Nechť funkce g má v okolí bodu £ derivace až do řádu p > 1 včetně. Iterační metoda x*+i = g(x/c), /c = 0,1,... je řádu p tehdy a jen tehdy, když platí e = *(0. řw(0 = o, i<; [a, b] a nechť g má v bodě £ derivaci. • Je-li |g'(£)l < 1> Pak £ Je přitahující pevný bod. • Je-li |g'(£)l > 1- Pak £ Je odpuzující pevný bod. Jiří Zelinka Numerické metody 3. přednáška, 4. března 2015 6/13 Newtonova metoda, metoda tečen Uvažujme opět rovnici f (x) = 0. Zvolme x0 a řešení hledáme na tečně k f v bodě x0 jako její průsečík s osou x. -1 -0.5 0 0.5 1 Podobně pokračujeme dál: x^+i je průsečík tečny k funkci f v bodě Xk s osou x. Jiří Zelinka Numerické metody 3. přednáška, 4. března 2015 7/13 Veta Nechť f G C2[a, b]. Nechť £ G [a, b] je kořenem rovnice f(x) = 0 a /"'(£) 7^ 0. Pak existuje 5 > 0 tak, že posloupnost {x/c}^l0 generovaná Newtonovou metodou konverguje k bodu £ pro každou počáteční aproximaci x0 G [£ — ô, £ + 5] C [a, b]. Důsledek: Newtonova metoda je metoda druhého řádu pro jednoduchý kořen £. Příklad Výpočet v/ÍČ Konec opakování Jiří Zelinka Numerické metody 3. přednáška, 4. března 2015 8/13 Chování chyby u Newtonovy metody Věta Nechť jsou splněny předpoklady předchozí věty, M = max \f"{x)\, m = min \f'(x)\ > 0, / = [£ - 5,£ + 5]. Pak pro posloupnost {x/(}^l0 generovanou Newtonovou metodou platí a) |*fc+i-£l < ^(x.-02 b) |*fc+i-£| < ^(xfc+1-x,)2 Důkaz Z Taylorova rozvoje. Jiří Zelinka Numerické metody 3. přednáška, 4. března 2015 9/13 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" nemění znaménka na intervalu [a,b], přičemž f'(x) ^ 0, Vx e [a,b\. Nechť počáteční aproximace x0 je ten z krajních bodů a, b, v němž znaménko funkce je stejné jako znaménko f" na intervalu [a, b]. Pak posloupnost {x/(}^0 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. JiřT Zelinka Numerické metody 3. přednáška, 4. března 2015 10 / 13 Metoda sečen Derivaci v bodě Xk u Newtonovy metody nahradíme sěrnicí sečny v bodech [x*-i, f(x*-i) a ixk,f{xi<)- fM»W'fM, / = 1,2,... */c - xk i Výsledná iterační metoda J*+1=J*"^)-^(xfc_1)W' l = 1'2'- Jiří Zelinka Numerické metody 3. přednáška, 4. března 2015 11 / 13 Jiří Zelinka Numerické metody 3. přednáška, 4. března 2015 12 / 13 Veta Nechť rovnice f(x) = 0 má kořen £ a nechť derivace f, f" jsou spojité v okolí bodu £, přičemž /"'(£) 7^ 0. Posloupnost určená metodou sečen konverguje ke kořenu £, pokud zvolíme počáteční aproximace x0, x1 dostatečně blízko bodu £ a metoda je řádu (1 + VŠ)/2 = 1,618. Výpočet v^íĎ: Pozor! Při pokusu o co nejpřesnější výpočet může dojít k nedefinovanému výrazu typu 0/0. Důkaz Příklad Jiří Zelinka Numerické metody 3. přednáška, 4. března 2015 13 / 13