Numerické metody 5. přednáška, 21. března 2017
Jiří Zelinka
Jiří Zelinka        Numerické metody 5. prednáška, 21. března 2017 1/16
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, 21. března 2017 2/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 5. přednáška, 21. března 2017 3/16
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, 21. března 2017 4/16
Iterační metody pro násobné kořeny
Kořen £ násobnosti M
no = o. no = o,..., f^-Ho = o. f{MHo ± o
Věta
Nechť kořen £ má násobnost M > 1. Pak modifikovaná Newtonova metoda
*k+i = *k- M
je metoda druhého řádu
Obecný postup: Newtonova metoda pro u(x) =
Jiří Zelinka        Numerické metody 5. přednáška, 21. března 2017 5/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
= {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, 21. března 2017 6/16
Geometrická interpretace
Položme
e(xfr) = Xk-Xk+i = xk-£-(xk+i-£) = (xfc-£)(l-C + o(l))
e(xk) je tedy přibližně lineární funkcí chyby xk — £.
Rovnice přímky procházející body [x^e^)] a [xk+i,£(xk+i)]\
e(xfc) -^(xfc+i).        \ .   / \
y = -(x - x*) + e(xfc)
xk - xk+1
Průsečík s osou x (y = 0) je bod x*
Ä _    _ £JXk){xk - xk+1) _
e(xk) - £{xk+1)
(xk+1 - xk):
xk+2 - 2xk+1 + xk
Jiří Zelinka        Numerické metody 5. přednáška, 21. března 2017 7/16
0.25
0 .15
0 .05
-0 .05
0.05      0      0.05    0.1    0.15    0.2    0.25    0.3 0.35
Vyjádření pomocí diferencí: Axk = x*+i - xk
A2xk = Axk+1 - Axk = xk+2 ~ + xk A3xk = A2xk+1 - A2xk
Xk = Xk
(AXky
Konec opakování
Jiří Zelinka
Numerické metody 5. přednáška, 21. března 2017 8/16
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) = yk - zk. Tato iterační metoda se nazývá Steffensenova a může být popsána iterační funkcí tp:
xk+i =<p(xk)
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
Numerické metody 5. přednáška, 21. března 2017 9/16
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, 21. března 201710/16
Souvislost Steffensenovy a kvazinewtonovy metody
f(x) = o    —►   g(x) = x + f(x) Na funkci g aplikujeme Steffensenovu metodu:
Yk = g{xk) =Xk + f{*k),    zk = g(yk) = yk + f(yk)
xk+1   = xk
= xk
=   xk +
{yk - xk)2
zk - 2yk + xk
_{xk + f{xk) - xk)2
{yk + f{yk) -yk)-{xk + f M
(f M)2 f M - f{xk)
f{xk) - f{xk + f{xk))
- xk)
Podobně varianta „minus" pro g{x) — x —J{x).
1= <\(y
Jiří Zelinka        Numerické metody 5. prednáška, 21. března 2017 11 / 16
Múllerova metoda
Múllerova metoda je zobecněním metody sečen. U metody sečen aproximujeme funkci f přímkou procházející body [x^-i, f(xk_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 x/^, x/^i, xk 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 xk, 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, 21. března 2017 12 / 16
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, r"(x*_2)], [x/f_i, r"(xfc_i)], [xfc, r"(x*)], t.j. splňující podmínky P(x') = f(x'), i = k — 2, k — 1, k. Z nich plyne
c  = f(xk)
,     _    ixk-2 ~ xk)2 [f{xk-l) ~ f(xk)] ~ (Xk-1 ~ xkf [f{xk-2) ~ f(xk)]
(xk_2 ~ xk){xk-l - Xk)(xk_2 ~ xk-l)
_   {xk-2 ~ xk) [r"(xfc_i) - f{xk)] - (xfc_i - Xfr) [r"(xfc_2) - r"(x*)]
(x*_2 - xk)(xk_1 - x*)(xfc_i - x*_2)
Jiří Zelinka        Numerické metody 5. přednáška, 21. března 2017 13 / 16
Xk+1 - xk =
-b ± Vb2 - 4ac
-2c
2a b±Vb2-Aac
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
xk+1 = xk
b + (sign b) Vb2 — 4ac
Jiří Zelinka
Numerické metody 5. přednáška, 21. března 2017 14 / 16
Newtonova metoda v komplexním oboru
f(x) = X2 +1
x2+l       x2—1
Newtonova metoda: x^+i =    —=
Jiří Zelinka        Numerické metody 5. přednáška, 21. března 2017 15 / 16
Newtonova metoda pro rovnici x3 — 1 = 0.
Úkol: určete, pro kterou počáteční iteraci v komplexním oboru
metoda nekonverguje: