Opakování
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.
Xk+l = *k
Iterační funkce:
f'(x)
Podobně pokračujeme dál: x*+i je průsečík tečny k funkci f v bodě Xk s osou x.
Newtonova metoda je metoda druhého řádu pro jednoduchý kořen f.
Jiří Zelinka        Numerické metody 4. přednáška, 11. března 2015 2/10
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 x° 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 £.
Jiří Zelinka        Numerické metody 4. přednáška, 11. března 2015 3/10
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 4. přednáška, 11. března 2015 4/10
Jiří Zelinka        Numerické metody 4. přednáška, 11. března 2015 5/10
Příklad
Výpočet \/iô:
f {x) = x3 - 10, x G / = [2, 3] Volíme x0 = 2, x1 = 3, pak x2 = 2.1053, x3 = 2.1391, x4 = 2.11548, x5 = 2.11544.
Pozor! Při pokusu o co nejpřesnější výpočet může dojít k nedefinovanému výrazu typu 0/0.
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, x1 dostatečně blízko bodu £ a metoda je řádu (1 + vš)/2 = 1,618.
Jiří Zelinka        Numerické metody 4. přednáška, 11. března 2015 6/10
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+i =xk- -jt^—^—f(xk),      k = 0,1,..., t(xk) - t(xs)
kde s = s(k) je největší index takový, že f(xk)f(xs) < 0, přitom f(x0)f(x1) < 0 (tj. např. x0 = a, x1 = b).
Poznámka: pokud je funkce f konvexní nebo konkávni na [a, b], je xs jeden z krajní bodů intervalu.
Řád metody: 1
Jiří Zelinka        Numerické metody 4. přednáška, 11. března 2015 7/10
Quasi Newtonova metoda (plus/minus)
Tečnu u Newtonovy metody nahradíme sečnou procházející bodem (xk, f(xk)) a bodem (xk + f(xk), f(xk + f(xk))), respektive bodem (xk — f(xk), f(xk — f(xk))). Přitom pokud je bod xk blízko hledaného kořene £, pak hodnota f(xk) je blízká nule a sečna procházející uvedenými body je blízká tečně vedené bodem xk.
^ f(xk) - f(xk ± f(xk)) = f(xk) - f(xk ± f(xk)) {k)~    xk- {xk ± f(xk)) Tf(xk)
xk+i = xk-t{xk)——--—————— = xk^
f(xk) - f(xk ± f(xk)) f(xk) - f(xk ± f(xk))
Jiří Zelinka        Numerické metody 4. přednáška, 11. března 2015 8/10
Iteracní funkce:
f2 (x)
g{x)-X±f(x)-f(x±f(x))
Poznámka:
Quasi Newtonova metoda se také někdy nazývá Steffensenova
- viz dále.
Věta
Nechť f G C1 [a, b], £ G [a, b] nechť je řešením rovnice
f(x) = 0 a /"'(£) ý 0-      existuje e > 0 tak, že posloupnost
{x/c}^l0 generovaná quasi Newtonovou metodou konverguje
k bodu £ pro každou počáteční aproximaci
x° G [£ — £,£ + e] n [a, b]. Pokud má funkce f v okolí bodu £
spojitou druhou derivaci, je řád metody alespoň 2.
Důkaz: ĽHospitalovo pravidlo.
< □ ► < fll ► <!►<!►     I -O0.O Jiří Zelinka        Numerické metody 4. přednáška, 11. března 2015 9/10
Iterační metody pro násobné kořeny
Kořen £ násobnosti M
f(0 = o, f (0 = o,..., fW-Vfá = o,        ± o
Věta
Nechť kořen £ má násobnost M > 1. Pak modifikovaná Newtonova metoda
=xk- M
a*)
je metoda druhého řádu.
Jiří Zelinka        Numerické metody 4. přednáška, 11. března 2015 10 / 10