Numerické metody 4. přednáška, 17. března 2016
Jiří Zelinka
Jiří Zelinka        Numerické metody 4. prednáška, 17. března 2016 1/16
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.
Iterační funkce:
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 £.
Numerické metody 4. přednáška, 17. března 2016 2/16
Jiří Zelinka
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 G [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 f" na intervalu [a, 6]. Pak posloupnost {x/rj^Q určená Newtonovou metodou konverguje monotónně k bodu
Jiří Zelinka
Numerické metody 4. přednáška, 17. března 2016 3/16
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 4. přednáška, 17. března 2016 4/16
Jiří Zelinka
Numerické metody 4. přednáška, 17. března 2016 5/16
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.
Jiří Zelinka
Numerické metody 4. přednáška, 17. března 2016 6/16
Řád metody pomocí symboliky o
(x*+i-0   =   (x*-0(x*_i-0(*- + °(l)), t.j. ek+1  =  ekek-i{L + o(l)), L>0
Metoda je řádu p > 1:
im
ek+i
ek
ek
ek+i
ek
=  C > 0
=  (C+ o(l))
e*|'(C + o(l)) e*_i|"(C + o(l))
Jiří Zelinka
Numerické metody 4. přednáška, 17. března 2016 7/16
\ek+l\ ek\p(C + o(l))
\ek\p-\C + o(l))
(kik-irr^c + oci^cc + oci))
p2-p-i
(C + o(l))" =
eit| |ek_i||/. + o(l) ek| |efc_i||Z. + o(l) efc_i||/. +o(l)| e*_i||L + o(l)|
L + o(l)|
p2-p-l = 0=^p =
1 +V5
Konec opakování
Jiří Zelinka
Numerické metody 4. přednáška, 17. března 2016 8/16
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, 17. března 2016 9/16
Kvázi n ewto nova metoda (plus/minus)
Tečnu u Newtonovy metody nahradíme sečnou procházející bodem (x*, 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(xk) - f(xk ± f(xk))
= xk±
f2M
f(xk) - f(xk ± f(xk))
Jiří Zelinka
Numerické metody 4. přednáška, 17. března 2016 10 / 16
Iteracní funkce:
x±
f(x)-f(x±f(x))
Poznámka:
Kvazinewtonova metoda se také někdy nazývá Steffensenova -
viz dále.
Věta
Nechť f G Cx[a, b], £ G [a, b] nechť je řešením rovnice
f(x) = 0 a f(£)    0. Pak existuje e > 0 tak, že posloupnost
{x/c}^L0 generovaná kvazinewtonovou metodou konverguje
k bodu £ pro každou počáteční aproximaci
x° G [£ — 5, £ + e] n [a, 6]. 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, 17. března 2016 11 / 16
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, 17. března 2016 12 /16
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, 17. března 2016 13 / 16
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í
lim-- = 0,
fc->oo Xfc — £
tj. posloupnost {xk} konverguje k limitě £ rychleji než posloupnost {xk}. ^ n > 4 „
Jiří Zelinka        Numerické metody 4. prednáška, 17. března 2016 14 / 16
Geometrická interpretace
Položme
sM = Xk-Xk+i = xk-C-(xfc+i-0 = (x*-£)(l + C + o(l))
e(xk+i) = xk+1 - xk+2 = (x*+i - £)(1 + C + o(l)) = = (x, - 0(C + o(l))(l + C + o(l)) = e(x*)(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, 17. března 2016 15 / 16
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, 17. března 2016 16 / 16