Numerické metody
5. přednáška, 22. března 2019
Jiří Zelinka
Jiří Zelinka Numerické metody 5. přednáška, 22. března 2019 1 / 20
Opakování
Newtonova metoda, metoda tečen
xk+1 = xk −
f (xk)
f (xk)
Newtonova metoda je metoda druhého řádu pro jednoduchý
kořen ξ.
Metoda sečen
Derivaci v bodě xi u Newtonovy metody nahradíme sěrnicí
sečny v bodech [xk−1, f (xk−1)] a [xk, f (xk)].
xk+1 = xk −
xk − xk−1
f (ki ) − f (xk−1)
f (xk), i = 1, 2, . . .
Metoda je řádu (1 +
√
5)/2
.
= 1,618.
Jiří Zelinka Numerické metody 5. přednáška, 22. března 2019 2 / 20
Metoda regula falsi
Předpokládejme f (a)f (b) < 0, f ∈ 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)
f (xk), k = 0, 1, . . . ,
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ávní na
[a, b], je xs jeden z krajní bodů intervalu.
Řád metody: 1
Jiří Zelinka Numerické metody 5. přednáška, 22. března 2019 3 / 20
Kvazinewtonova 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))].
Iterační funkce:
g(x) = x ±
f 2
(x)
f (x) − f (x ± f (x))
xk+1 = xk ±
f 2
(xk)
f (xk) − f (xk ± f (xk))
Metoda je řádu alespoň 2.
Jiří Zelinka Numerické metody 5. přednáška, 22. března 2019 4 / 20
Iterační metody pro násobné kořeny
Kořen ξ násobnosti M
f (ξ) = 0, f (ξ) = 0, . . . , f (M−1)
(ξ) = 0, f (M)
(ξ) = 0
Věta
Nechť kořen ξ má násobnost M > 1. Pak modifikovaná
Newtonova metoda
xk+1 = xk − M
f (xk)
f (xk)
je metoda druhého řádu.
Obecný postup: Newtonova metoda pro u(x) = f (x)
f (x)
Jiří Zelinka Numerické metody 5. přednáška, 22. března 2019 5 / 20
Urychlení konvergence – Aitkenova δ2
-metoda
Věta
Nechť je dána posloupnost {xk}∞
k=0, xk = ξ, k = 0, 1, 2, . . .,
lim
k→∞
xk = ξ, a nechť tato posloupnost splňuje podmínky
xk+1−ξ = (C+γk)(xk−ξ), k = 0, 1, 2, . . . , |C| < 1, lim
k→∞
γk = 0.
Pak posloupnost
ˆxk = xk −
(xk+1 − xk)2
xk+2 − 2xk+1 + xk
je definována pro všechna dostatečně velká k a platí
lim
k→∞
ˆxk − ξ
xk − ξ
= 0,
tj. posloupnost {ˆxk} konverguje k limitě ξ rychleji než
posloupnost {xk}.
Jiří Zelinka Numerické metody 5. přednáška, 22. března 2019 6 / 20
Geometrická interpretace
Položme
ε(xk) = xk −xk+1 = xk −ξ−(xk+1 −ξ) = (xk −ξ)(1−C +o(1))
ε(xk) je tedy přibližně lineární funkcí chyby xk − ξ.
Rovnice přímky procházející body [xk, ε(xk)] a [xk+1, ε(xk+1)]:
y =
ε(xk) − ε(xk+1)
xk − xk+1
(x − xk) + ε(xk)
Průsečík s osou x (y = 0) je bod ˆxk
ˆxk = xk −
ε(xk)(xk − xk+1)
ε(xk) − ε(xk+1)
= xk −
(xk+1 − xk)2
xk+2 − 2xk+1 + xk
.
Jiří Zelinka Numerické metody 5. přednáška, 22. března 2019 7 / 20
−0.05 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35
−0.05
0
0.05
0.1
0.15
0.2
0.25
x2x3x4x5
x^
2
ε(x2)
ε(x3)
Vyjádření pomocí diferencí:
∆xk = xk+1 − xk
∆2
xk = ∆xk+1 − ∆xk = xk+2 − 2xk+1 + xk
∆3
xk = ∆2
xk+1 − ∆2
xk
...
ˆxk = xk −
(∆xk)2
∆2xk
Konec opakování
Jiří Zelinka Numerické metody 5. přednáška, 22. března 2019 8 / 20
Steffensenova metoda
Buď g iterační funkce pro rovnici x = g(x). Položme
yk = g(xk), zk = g(yk),
xk+1 = xk −
(yk − xk)2
zk − 2yk + xk
.
V tomto případě je tedy ε(xk) = xk − yk, ε(yk) = yk − zk.
Tato iterační metoda se nazývá Steffensenova a může být
popsána iterační funkcí ϕ:
xk+1 = ϕ(xk),
kde
ϕ(x) = x −
(g(x) − x)2
g(g(x)) − 2g(x) + x
=
xg(g(x)) − g2
(x)
g(g(x)) − 2g(x) + x
.
Jiří Zelinka Numerické metody 5. přednáška, 22. března 2019 9 / 20
Věta
1 ϕ(ξ) = ξ implikuje g(ξ) = ξ.
2 Jestliže 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 xk+1 = g(xk) je
řádu p pro bod ξ.
Pak pro p > 1 je iterační metoda xk+1 = ϕ(xk) řádu 2p − 1.
Pro p = 1 je tato metoda řádu alespoň 2 za předpokladu
g (ξ) = 1.
Jiří Zelinka Numerické metody 5. přednáška, 22. března 201910 / 20
Souvislost Steffensenovy a kvazinewtonovy metody
f (x) = 0 −→ 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 −
(yk − xk)2
zk − 2yk + xk
= xk −
(xk + f (xk) − xk)2
(yk + f (yk) − yk) − (xk + f (xk) − xk)
= xk −
(f (xk))2
f (yk) − f (xk)
= xk +
f 2
(xk)
f (xk) − f (xk + f (xk))
Podobně varianta „minus“ pro g(x) = x − f (x).
Jiří Zelinka Numerické metody 5. přednáška, 22. března 201911 / 20
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
[xk−1, f (xk−1)], [xk, 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−2, xk−1, 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 xk+1. Touto metodou lze najít
i násobné a komplexní kořeny.
Jiří Zelinka Numerické metody 5. přednáška, 22. března 201912 / 20
xk−2, xk−1, xk jsou již vypočtené aproximace. Sestrojme
polynom
P(x) = a(x − xk)2
+ b(x − xk) + c
procházející body [xk−2, f (xk−2)], [xk−1, f (xk−1)], [xk, f (xk)],
t.j. splňující podmínky P(xi
) = f (xi
), i = k − 2, k − 1, k.
Z nich plyne
c = f (xk)
b =
(xk−2 − xk)2
[f (xk−1) − f (xk)] − (xk−1 − xk)2
[f (xk−2) − f (xk)]
(xk−2 − xk)(xk−1 − xk)(xk−2 − xk−1)
a =
(xk−2 − xk) [f (xk−1) − f (xk)] − (xk−1 − xk) [f (xk−2) − f (xk)]
(xk−2 − xk)(xk−1 − xk)(xk−1 − xk−2)
Jiří Zelinka Numerické metody 5. přednáška, 22. března 201913 / 20
xk+1 − xk =
−b ±
√
b2 − 4ac
2a
=
−2c
b ±
√
b2 − 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+1 bude nejbližší xk. Je tedy
xk+1 = xk −
2c
b + (signb)
√
b2 − 4ac
.
Jiří Zelinka Numerické metody 5. přednáška, 22. března 201914 / 20
Newtonova metoda v komplexním oboru
f (x) = x2
+ 1
Newtonova metoda: xk+1 = xk −
x2
k +1
2xk
=
x2
k −1
2xk
x0 = 1 + i
x1 =
1
4
+
3
4
i
x2 = −
3
40
+
39
40
i
x3 =
7
4000
+
370
371
i
...
Jiří Zelinka Numerické metody 5. přednáška, 22. března 201915 / 20
Polynomy
Πn: třída polynomů stupně nejvýše n s reálnými koeficienty.
¯Πn ⊆ Πn: třída polynomů s jedničkou u xn
.
P ∈ Πn:
P(x) = anxn
+ an−1xn−1
. . . + a1x + a0.
ξ1, ξ2, . . . , ξn kořeny (reálné i komplexní) polynomu P.
Dělení polynomů se zbytkem
P, Q – polynomy, Pak existují polynomy S, R, že platí
P = Q · S + R,
přičemž st R < st Q.
Jiří Zelinka Numerické metody 5. přednáška, 22. března 201916 / 20
Hornerovo schema
P(x) = anxn
+ an−1xn−1
. . . + a1x + a0, c ∈ R.
Vydělíme polynom P(x) lineárním polynomem x − c:
P(x) = (x − c)Q(x) + A,
kde
Q(x) = bn−1xn−1
+ · · · + b1x + b0 .
Koeficienty bi , i = 0, . . . , n určíme z rekurentních vztahů:
bn−1 = an
bk−1 = ak + cbk, k = n − 1, . . . , 1
A = a0 + cb0 .
Pak je zřejmě P(c) = A.
an an−1 an−2 · · · a2 a1 a0
c bn−1 bn−2 bn−3 · · · b1 b0 A
Jiří Zelinka Numerické metody 5. přednáška, 22. března 201917 / 20
Označíme polynom Q jako Q1 a hodnotu A jakožto A0,
v dalším kroku dostaneme podíl Q2 a hodnotu A1
Qk(x) = (x − c) · Qk+1(x) + Ak.
Hornerovo schema pak (symbolicky zkráceno):
P
c Q1 A0
c Q2 A1
c Q3 A2
... ...
c An
Jiří Zelinka Numerické metody 5. přednáška, 22. března 201918 / 20
Pro polynom P pak dostáváme
P(x) = (x − c)Q1(x) + A0 =
= (x − c)((x − c)Q2(x) + A1) + A0 =
= (x − c)2
Q2(x) + A1(x − c) + A0 =
= (x − c)2
((x − c)Q3(x) + A2) + A1(x − c) + A0 =
= (x − c)3
Q3(x) + A2(x − c)2
+ A1(x − c) + A0 = · · · =
= An(x − c)n
+ An−1(x − c)n−1
+ · · · + A1(x − c) + A0
Hodnoty An, . . . , A0 jsou tedy koeficienty polynomu P
posunutého do bodu c – Taylorův rozvoj.
Ak =
P(k)
(c)
k!
Jiří Zelinka Numerické metody 5. přednáška, 22. března 201919 / 20
Hranice kořenů
Věta
Nechť
P(x) = anxn
+ an−1xn−1
. . . + a1x + a0,
A = max (|an−1|, . . . , |a0|) ,
B = max (|an|, . . . , |a1|) ,
kde a0an = 0. Pak pro všechny kořeny ξk, k = 1, . . . , n,
polynomu P platí
1
1 +
B
|a0|
≤ |ξk| ≤ 1 +
A
|an|
.
Jiří Zelinka Numerické metody 5. přednáška, 22. března 201920 / 20