Numerické metody 5. přednáška, 24. března 2016
Jiří Zelinka
Jiří Zelinka        Numerické metody 5. prednáška, 24. března 2016 1/13
Newtonova metoda, metoda tečen
Xk+l =*k~
Newtonova metoda je metoda druhého řádu pro jednoduchý kořen £.
Metoda sečen
Derivaci v bodě x; u Newtonovy metody nahradíme sěrnicí sečny v bodech [x/c_i, f(xk-i)\ a [xk, f{xk)]-
xk - xk_i
i = 1,2,...
xk+1 =xk-
f(ki) - r(x*_i)
Metoda je řádu (1 + y/Š)/2 = 1,618.
Numerické metody 5. prednáška, 24. března 2016 2/13
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 5. přednáška, 24. března 2016 3/13
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 [x/c + f{xk), f(xk + f{xk))], respektive bodem [xk — f(xk), f(xk — f(xk))].
Iterační funkce:
g(x) =x±
P(x)
*k+l = Xk ±
Metoda je řádu alespoň 2
f(x)-f(x±f(x)) f(xk) - f(xk ± f(xk))
Jiří Zelinka        Numerické metody 5. přednáška, 24. března 2016 4/13
Iterační metody pro násobné kořeny
Kořen £ násobnosti M
ř-(0 = o, f(0 = o,..., fw-vit) = o, f<M>(0 ^ o
Věta
Nechť kořen £ má násobnost M > 1. Pak modifikovaná Newtonova metoda
Xk+i = Xk ~ M
je metoda druhého řádu.
Obecný postup: Newtonova metoda pro u(x) = Konec opakování
_ IM.
f'(x)
Jiří Zelinka        Numerické metody 5. přednáška, 24. března 2016 5/13
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
= {C+lk){xk-Š)i * = 0,1,2,..., |C| < 1, lim 7* = 0.
k^oc
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,
tj. posloupnost {xk} konverguje k limitě £ rychleji než posloupnost {xk}. ^ n > 4 „
Jiří Zelinka        Numerické metody 5. prednáška, 24. března 2016 6/13
Geometrická interpretace
Položme
e(xk) = xk-xk+1 = xk - £ - (xk+1 - g) = (xfc-£)(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)) = e(x*)(C + o(l))
0.25
0 . 2 h
0 .15h
0 . lh
0 .05h
-0 .05
0.05      0      0.05    0.1    0.15    0.2    0.25    0.3 0.35
Jiří Zelinka        Numerické metody 5. přednáška, 24. března 2016 7/13
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
Ä _    _ £JXk){xk ~ Xfc+i) _
X k X k xx        (        x X k
e(xk) - £{xk+1)
(xk+1 - xk):
xk+2 - 2xk+1 + xk
Jiří Zelinka        Numerické metody 5. přednáška, 24. března 2016 8/13
Buď g iterační funkce pro rovnici x = g(x). Položme
Yk = g{xk),      zk = g(yk)
Xk+l = xk
{yk - xk):
zk - 2yk + xk
V tomto případě je tedy e(xk) = xk - yk, e(yk) = y* - zk. Tato iterační metoda se nazývá Steffensenova a může být popsána iterační funkcí tp:
Xk+i =<pM
kde
ip(x) =
x —
{g{x) - x)
xg{g{x)) - g2{x)
g(g{x)) - 2g(x) + x    g{g{x)) - 2g(x) + x'
Jiří Zelinka
□       g ►  < ! ►  < =        1 vrjcvo Numerické metody 5. přednáška, 24. března 2016 9/13
Veta
O <p{£) = C implikuje g(£) = £.
O Jestliže g(g) = £, g'(£) existuje a g'(£) / 1, pak
Věta
Nechť funkce g" má spojité derivace až do řádu p + 1 včetně v okolí bodu x = £. Nechť iterační metoda x/c+i = g"(x/c) je řádu p pro bod e
Pak pro p > 1 je iterační metoda x^+i = (p(xk) řádu 2p — 1. Pro p = 1 je tato metoda řádu alespoň 2 za předpokladu
g'(0 ŕ i-
Jiří Zelinka
Numerické metody 5. přednáška, 24. března 201610/13
Souvislost Steffensenovy a kvázi newtonovy metody
f (x) = o    —►   g{x) =x + f{x) Na funkci g aplikujeme Steffensenovu metodu:
Yk = g{xk) = Xk + f{xk),   zk = g(yk) = yk + f(yk)
xk+1   = xk
= xk
= xk
=   xk +
{yk - xk)2
zk - 2yk + xk
_{xk + f{xk) - xk)2
{yk + f{yk) -yk)-{xk + f{xk)
{f{xk)f
f M - f{xk)
f2{xk)
- xk)
f{xk) - f{xk + f{xk)
Podobně varianta „minus" pro g{x) — x —J{x).
Jiří Zelinka        Numerické metody 5. prednáška, 24. března 2016 11 / 13
Múllerova metoda
Múllerova metoda je zobecněním metody sečen. Metoda sečen v podstatě znamená, že pro dané aproximace x^, x^_i bodu £ aproximujeme funkci f přímkou procházející body [x/^i, ^(x/^i)], [x^, f(xk)] a za další aproximaci bodu £ vezmeme průsečík této přímky s osou x. Múllerova metoda užívá tři aproximace Xk_2t Xk_i,     a křivku y = f (x) aproximujeme parabolou určenou těmito body. Průsečík této paraboly s osou x, který je nejbližší k x^, vezmeme za další aproximaci x^+i. Touto metodou lze najít i násobné a komplexní kořeny.
Jiří Zelinka        Numerické metody 5. přednáška, 24. března 2016 12 / 13
xk-2, xk-i< xk jsou již vypočtené aproximace. Sestrojme polynom
P(x) = a(x - xk)2 + b(x -xk) + c
procházející body [x*_2, f(x*_2)], [xk-i, f(xfc_i)], [xk, f{xk)], t.j. splňující podmínky P(x') = ^(x'), i = k — 2, k — 1, k. Z nich plyne
c  = f(xk)
,   _   {xk-2 ~ xk)2 [r~(x*_i) - f{xk)] - (xk-i - xk)2 [f{xk_2) ~ f{*k)]
(xk_2 ~ X*)(x*_i - Xfc)(Xfc_2 - Xfc_i)
_    (Xfr-2 ~ Xk) [f(xfc_i) ~ f{xk)] - (xfc_i ~ Xfr) [f(xfc_2) ~ f (**)]
(x*_2 - Xk)(xk_1 - X*)(xfc_i - X*_2)
Jiří Zelinka        Numerické metody 5. přednáška, 24. března 2016 13 / 13
-2c
xk+1 - xk =
b±Vb2-4ac'
Znaménko u odmocniny vybereme tak, aby bylo shodné se znaménkem b. Tato volba znamená, že jmenovatel zlomku bude v absolutní hodnotě největší a tedy výsledná hodnota xk+i bude nejbližší xk. Je tedy
2c
X*+i = xk
b + (sign b) Vb2 — 4ac
Jiří Zelinka
Numerické metody 5. přednáška, 24. března 2016 13 / 13