Numerické metody 4. přednáška, 14. března 2017
Jiří Zelinka
Jiří Zelinka        Numerické metody 4. prednáška, 14. března 2017 1/14
Opakování
Newtonova metoda, metoda tečen
Uvažujme opět rovnici f{x) = 0. Zvolme xq a řešení hledáme na tečně k f v bodě x0 jako její průsečík s osou x.
X
Podobně pokračujeme dál: x/c+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 £.
Jiří Zelinka
Numerické metody 4. přednáška, 14. března 2017 2/14
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 £ [a, 6]. Nechť počáteční aproximace x° 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 4. přednáška, 14. března 2017 3/14
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 (**-i)
# = 1,2,...
Výsledná iterační metoda
*k     xk-l       r ŕ x Xk+l =*k~ ~Tí   \-77-\f\xk)
f M ~ f{*k-l)
i = 1,2,...
Jiří Zelinka        Numerické metody 4. přednáška, 14. března 2017 4/14
Jiří Zelinka
Numerické metody 4. přednáška, 14. března 2017 5/14
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ž        ^ 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.
Konec opakování
Jiří Zelinka
Numerické metody 4. přednáška, 14. března 2017 6/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 4. přednáška, 14. března 2017 7/14
Kvázi n ewto nova 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 [x^ — 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))
xk - (xk ± f{xk))
TfM
xk+i = xk-f(xk)
TfM
f M - f(xk ± f(xk))
= xk±
f2M
f(xk) - f(xk ± f(xk))
Jiří Zelinka
Numerické metody 4. přednáška, 14. března 2017 8/14
Iteracní funkce:
x±
f(x)-f(x±f(x))
Poznámka:
Kvazinewtonova metoda se také někdy nazývá Steffensenova -
b        v/v _
viz priste. Věta
Nechť f G Cx[a, b], £ G [a, 6] nechť je řešením rovnice
f(x) = 0 a f(£)    0. Pak existuje 5 > 0 tak, že posloupnost
{x/c}^L0 generovaná kvazinewtonovou metodou konverguje
k bodu £ pro každou počáteční aproximaci
x° G [£ — 5, £ + s] n [a, b]. Pokud má funkce f v okolí bodu £
spojitou druhou derivaci, je řád metody alespoň 2.
Důkaz: ĽHospitalovo pravidlo.
□
Jiří Zelinka
Numerické metody 4. prednáška, 14. března 2017 9/14
Iterační metody pro násobné kořeny
Kořen £ násobnosti M
Věta
Nechť kořen £ má násobnost M > 1. Pak modifikovaná Newtonova metoda
,, f(xk) Xk+i = ><k - M
je metoda druhého řádu.
Jiří Zelinka        Numerické metody 4. přednáška, 14. března 2017 10 /14
Násobnost kořene zpravidla neznáme =>* univerzální volba:
0(x) = W)
Funkce u má stejné kořeny jako funkce f, ale násobnosti 1, takže můžeme použít Newtonovu metodu pro funkci u.
Tento postup nefunguje pro funkci, která má všechny derivace nulové - např. f{x) = e~^.
Pro tuto funkci selhávají i kriteria zastavení konvergence:
-*k <
Xk+l -		Xk
	Xk+1	
< e.
f{xk)\ < £
Jiří Zelinka
Numerické metody 4. přednáška, 14. března 2017 11 / 14
Urychlení konvergence - Aitkenova ^2-metoda
Veta
Nechť je dána posloupnost {xk}™=Q,     ^ £, k = 0,1, 2,...,
im Xk = £, a nechť tato posloupnost splňuje podmínky
xm-e = (C+o(l))(x/f-0, /f = 0,1,2,..., \C\ <1, lim o(l) = 0.
Pak posloupnost
*fc = xk
(xk+1 - xky
xk+2 - 2xk+1 + xk
je definována pro všechna dostatečně velká k a platí
I-     ** ~£ n lim-- = 0,
/r-S-oo Xfc — ^
tj. posloupnost {xk} konverguje k limitě £ rychleji než posloupnost {x*}. <n
Jiří Zelinka        Numerické metody 4. prednáška, 14. března 2017 12 / 14
Geometrická interpretace
Položme
e{xk) = xk-xk+1 = xk-£-{xk+1-£) = (xk-£)(l-C + o(l))
e{xk+1) = xk+1 - xk+2 = {xk+1 - £)(1 - C + o(l)) = = (x, - 0(C + o(l))(l - C + o(l)) = s(xk)(C + o(l))
O . 25
0.2
O . 15
O . 1
O . 05
■O . 05
-0.05      O      0.05    0.1     0.15    0.2     0.25    0.3 0.35
Jiří Zelinka        Numerické metody 4. přednáška, 14. března 2017 13 / 14
Rovnice přímky:
g(xfc) - e{xk+1) y - e(xk) =-(x - xk)
xk - xk+1
Průsečík s osou x (y — 0) je bod xk Ä _    _ eM(xk - xk+1) _
Xfa — ^k /    \        /        \   — ^k
e(xk) - £{xk+1)
(xk+i - xk):
xk+2 - 2xk+1 + xk
Vyjádření pomocí diferencí:
Axk = xk+1 - xk
A2xk = Axk+1 - Axk = xk+2 - 2xk+1 + xk A3xk = A2xk+1 - A2xk
Xk = Xk
(Axky A2xk
Jiří Zelinka        Numerické metody 4. přednáška, 14. března 2017 14 / 14