Numerické metody 3. přednáška, 10. března 2015
Jiří Zelinka
Jiří Zelinka        Numerické metody 3. prednáška, 10. března 2015 1/14
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, 10. března 2015 2/14
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, 10. března 2015 3/14
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<y<P, ár(p)(0^o.
Jiří Zelinka
Numerické metody 3. přednáška, 10. března 2015 4/14
f (x) = O       —►       g (x) = x
f(x)
g[x) = x -
g(X) = x -
k
f_(x) h(x)
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í {x/J^ 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 i7,x0 ^ £, existuje takové k, že x^ 0 iV.
Jiří Zelinka        Numerické metody 3. přednáška, 10. března 2015 5/14
Určení typu pevných bodů:
Nechť g G C[a, b], g : [a, b] —» [a, 6] a nechť g- má v bodě £ derivaci.
• Je-li < li Pa^ C Je přitahující pevný bod.
• Je-li > li Pa^ £ Je odpuzující pevný bod.
Jiří Zelinka        Numerické metody 3. přednáška, 10. března 2015 6/14
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á bodě xk s osou x.
xk+i je průsečík tečny k funkci f v
Jiří Zelinka
Numerické metody 3. přednáška, 10. března 2015 7/14
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].
Rád Newtonovy metody je roven 2 pro jednoduchý kořen £.
Odhad chyby:
a) |x*+i - £| <
b) |x*+i - £| <
(x*+i - X/J2
2m
2m
Jirí Zelinka
Numerické metody 3. prednáška, 10. brezna 2015 8/14
Veta
Nechť f e C2[a, b] a nechť rovnice f(x) = 0 má v intervalu jediný kořen £. Nechť ff, 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, 6, v němž znaménko funkce je stejné jako znaménko f" na intervalu [a, /?]. Pak posloupnost {x/rj^Q určená Newtonovou metodou konverguje monotónně k bodu £.
Konec opakování
Jiří Zelinka        Numerické metody 3. přednáška, 10. března 2015 9/14
Příklady
• Výpočet odmocnin
• Výpočet převrácené hodnoty
• Funkce arctan x
• Vícenásobný kořen - pomalá konvergence
Metoda sečen
Derivaci v bodě u Newtonovy metody nahradíme směrnicí sečny v bodech [x/c_i, ^(x/c-i) a f{*k)-
f M - f (**-i)
# = 1,2,...
Výsledná iterační metoda
*k     xk-l       r ŕ x Xk+l =*k~ ~Tí   \-77-\fVxk)
f M ~ f{*k-l)
i = 1,2,...
Jiří Zelinka        Numerické metody 3. přednáška, 10. března 2015 11 / 14
Jiří Zelinka
Numerické metody 3. přednáška, 10. března 2015 12 / 14
Věta
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, 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, 10. března 2015 13 / 14
Metoda regula falsi
Předpokládejme f(a)f(b) < 0, f <G C[a,b]. Použijeme metodu sečen, přitom vybíráme iterace tak, aby ve dvou po sobě jdoucích měla f opačné znaménko:
xk+1 = xk
xk - xs
f(xk) - f(xs)
k — 0,1,....
kde s = s(/c) je největší index takový, že f(xk)f(xs) < 0, přitom f(x0)f(xi) < 0 (tj. např. x0 = a, xi = b).
Poznámka: pokud je funkce f konvexní nebo konkávni na [a, b], je xs jeden z krajní bodů intervalu.
Rád metody: 1
Jiří Zelinka
Numerické metody 3. přednáška, 10. března 2015 14 / 14