Numerické metody 3. přednáška, 7. března 2016 Jiří Zelinka Jiří Zelinka Numerické metody 3. prednáška, 7. března 2016 1/13 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 Jiří Zelinka Numerické metody 3. přednáška, 7. března 2016 2/13 Podmínky konvergence O Pro každé x G / platí g(x) G / O Existuje L, 0 < L < 1, že pro každé x,y G / platí lárW -#(y)l < z.|x-y. nebo: Pro každé x G / platí |g'(x)| < L < 1. Pak x0 G / může být libovolné, iterační proces konverguje Jiří Zelinka Numerické metody 3. přednáška, 7. března 2016 3/13 Rád metody P - im 1-Típ k^oo \Xk — q\ řád metody im k^řoc 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í £ = ř(/)(0 = o, i li Pa^ £ Je odpuzující pevný bod. □ s 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. Iterační funkce: Podobně pokračujeme dál: x/c+i je průsečík tečny k funkci f v bodě xk s osou x. Jiří Zelinka Numerické metody 3. přednáška, 7. března 2016 7/13 Věta Nechť f G C2[a, b]. Nechť £ G [a, b] je kořenem rovnice ŕ(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, £ + 5] C [a, 6]. Rád Newtonovy metody je roven 2 pro jednoduchý kořen £. Odhad chyby: a) |x*+i - £| < b) |x*+i - £| < - í)2 Domáci úkol Konec opakovaní Jirí Zelinka Numerické metody 3. přednáška, 7. března 2016 8/13 Fourierovy podmínky Veta Nechť f G C2[a, b] a nechť rovnice f(x) = 0 má v intervalu jediný kořen £. Nechť P, f" nemění znaménka na intervalu [a, b], přičemž P{x) ^ 0, Vx e [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 P' na intervalu [a, b\. Pak posloupnost {x/rj^Q určená Newtonovou metodou konverguje monotónně k bodu £. □ Jiří Zelinka Numerické metody 3. přednáška, 7. března 2016 9/13 Príklady • Výpočet odmocnin o Funkce arctan x 1. 5 5 i_i_i_i_i_i_i -3-2-1 0 1 2 3 x • Vícenásobný kořen - pomalá konvergence Jiří Zelinka Numerické metody 3. přednáška, 7. března 2016 10 / 13 Metoda sečen Derivaci v bodě u Newtonovy metody nahradíme směrnicí sečny v bodech [x/c_i, f(xk-i)] a [xk, f{xk)]. f M - f(xk-i) xk - Xk_i / = 1,2,... Výsledná iterační metoda Xk — xk-l r t \ Xk+i =xk- ľ-77-^r{xk) f(xk) - / = 1,2,... □ Jiří Zelinka Numerické metody 3. přednáška, 7. března 2016 12 /13 Věta Nechť rovnice f(x) = 0 má kořen £ a nechť derivace fř, fřř jsou spojité v okolí bodu £, přičemž ^ 0. Posloupnost určená metodou sečen konverguje ke kořenu £, pokud zvolíme počáteční aproximace x0, xi dostatečně blízko bodu £ a metoda je řádu (1 + VŠ)/2 = 1,618. Důkaz Příklad Výpočet \/ÍÔ: Pozor! Při pokusu o co nejpřesnější výpočet může dojít k nedefinovanému výrazu typu 0/0. Jiří Zelinka Numerické metody 3. přednáška, 7. března 2016 13 /13