Numerické metody
5. přednáška, 19. března 2014
Jiří Zelinka
Jiří Zelinka Numerické metody 5. přednáška, 19. března 2014 1 / 21
Opakování
Quasi Newtonova metoda (plus/minus)
xk+1 = xk ±
f 2
(xk)
f (xk) − f (xk ± f (xk))
Iterační metody pro násobné kořeny – modifikovaná
Newtonova metoda pro ξ – kořen násobnosti M > 1:
xk+1
= xk
− M
f (xk
)
f (xk)
Urychlení konvergence – Aitkenova δ2
-metoda
ˆxk = xk −
(xk+1 − xk)2
xk+2 − 2xk+1 + xk
Steffensenova metoda
yk = g(xk), zk = g(yk), xk+1 = xk −
(yk − xk)2
zk − 2yk + xk
.
Jiří Zelinka Numerické metody 5. přednáška, 19. března 2014 2 / 21
Souvislost Steffensenovy a quasi Newtonovy
metody
Řešíme rovnici f (x) = 0.
Položíme g(x) = x + f (x).
Použijeme Steffensenovu metodu na funkcí g.
yk = g(xk) = xk + f (xk)
zk = g(yk) = yk + f (yk) = xk + f (xk) + f (xk + f (xk))
xk+1 = xk −
(yk − xk)2
zk − 2yk + xk
= xk −
(xk + f (xk) − xk)2
xk + f (xk) + f (xk + f (xk)) − 2(xk + f (xk)) + xk
= xk +
(f (xk))2
f (xk) − f (xk + f (xk))
Jiří Zelinka Numerické metody 5. přednáška, 19. března 2014 3 / 21
Müllerova metoda
Müllerova metoda je zobecněním metody sečen. U metody
sečen pro aproximace xk, xk−1 kořene ξ 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, 19. března 2014 4 / 21
Nechť 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, 19. března 2014 5 / 21
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, 19. března 2014 6 / 21
Polynomy
Πn: třída polynomů stupně nejvýše n s reálnými koeficienty.
P ∈ Πn:
P(x) = anxn
+ an−1xn−1
. . . + a1x + a0.
ξ1, ξ2, . . . , ξn kořeny (reálné i komplexní) polynomu P.
Věta: Hranice kořenů
Nechť A = max (|an−1|, . . . , |a0|) ,
B = max (|an|, . . . , |a1|) ,
kde ak, k = n, n − 1, . . . , 0, a0an = 0, jsou koeficienty
polynomu P ∈ Πn, Pak pro všechny kořeny ξk, k = 0, 1, . . . , n,
polynomu P platí
1
1 +
B
|a0|
≤ |ξk| ≤ 1 +
A
|an|
.
Jiří Zelinka Numerické metody 5. přednáška, 19. března 2014 7 / 21
Příklad
Polynom s kořeny ξ1 = 1, . . . , ξ5 = 5
P(x) = (x − 1)(x − 2)(x − 3)(x − 4)(x − 5)
= x5
− 15x4
+ 85x3
− 225x2
+ 274x − 120
A = B = 274,
1
1 +
274
|120|
=
60
197
≤ |ξk| ≤ 275.
Jiří Zelinka Numerické metody 5. přednáška, 19. března 2014 8 / 21
Věta
1. |ξk| ≤ max 1,
n−1
j=0
aj
an
2. |ξk| ≤ 2 max
an−1
an
,
an−2
an
, 3 an−3
an
, . . . , n a0
an
3. |ξk| ≤ max
a0
an
, 1 +
a1
an
, . . . , 1 +
an−1
an
.
Předchozí příklad:
P(x) = x5
− 15x4
+ 85x3
− 225x2
+ 274x − 120
1. |ξk| ≤ max {1, 719} = 719
2. |ξk| ≤ 2 max {30, 18.44, 12.16, 8.14, 5.21} = 30
3. |ξk| ≤ max {120, 275, 226, 86, 16} = 275.
Jiří Zelinka Numerické metody 5. přednáška, 19. března 2014 9 / 21
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 = 1, . . . , n .
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, 19. března 2014 10 / 21
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, 19. března 2014 11 / 21
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.
Jiří Zelinka Numerické metody 5. přednáška, 19. března 2014 12 / 21
Zobecněné Hornerovo schema
Polynom P dělíme kvadratickým trojčlenem
D(x) = x2
+ px + q:
P(x) = D(x) · Q(x) + Ax + B
pro Q(x) = bn−2xn−2
+ · · · + b1x + b0.
Platí:
bn−2 = an
bn−3 = an−1 − pbn−2
bn−4 = an−2 − pbn−3 − qbn−2
...
bk = ak+2 − pbk+1 − qbk+2
...
A = a1 − pb0 − qb1
B = a0 − qb0
Jiří Zelinka Numerické metody 5. přednáška, 19. března 2014 13 / 21
an an−1 an−2 an−3 . . . a1 a0
−p 0 −pbn−2 −pbn−3 −pbn−4 . . . −pb0 0
−q 0 0 −qbn−2 −qbn−3 . . . −qb1 −qb0
bn−2 bn−3 bn−4 bn−3 . . . A B
Jiří Zelinka Numerické metody 5. přednáška, 19. března 2014 14 / 21
Počet reálných kořenů polynomu
Nechť c1, . . . , cm je posloupnost reálných čísel různých od nuly.
Řekneme, že pro dvojici ck, ck+1 nastává znaménková
změna, jestliže
ckck+1 < 0.
Řekneme, že dvojice ck, ck+1 zachovává znaménko, jestliže
ckck+1 > 0.
Poznámka
Jestliže polynom P má násobné kořeny, pak dělením polynomu
P největším společným dělitelem P a P dostaneme polynom,
který má tytéž kořeny, ale všechny jednoduché.
Jiří Zelinka Numerické metody 5. přednáška, 19. března 2014 15 / 21
Definice
Posloupnost reálných polynomů
P = P0, P1, . . . , Pm
se nazývá Sturmovou posloupností příslušnou polynomu P,
jestliže
Všechny reálné kořeny polynomu P0 jsou jednoduché.
Je-li ξ reálný kořen polynomu P0, pak
signP1(ξ) = −signP0(ξ).
Pro i = 1, 2, . . . , m − 1,
Pi+1(α)Pi−1(α) < 0,
jestliže α je reálný kořen polynomu Pi .
Poslední polynom Pm nemá reálné kořeny.
Jiří Zelinka Numerické metody 5. přednáška, 19. března 2014 16 / 21
Konstrukce Sturmovy posloupnosti
P0(x) = P(x), P1(x) = −P0(x)
a sestrojme další polynomy Pi+1 rekurentně dělením polynomu
Pi−1 polynomem Pi :
Pi−1(x) = Qi (x)Pi (x) − ci Pi+1(x), i = 1, 2, . . . ,
kde
st Pi > st Pi+1
a konstanty ci jsou kladné, ale jinak libovolné. Lze říci, že Pi+1
je záporně vzatý zbytek při dělení Pi−1/Pi .
Protože stupně polynomů klesají, musí algoritmus končit po
m ≤ n krocích.
Jiří Zelinka Numerické metody 5. přednáška, 19. března 2014 17 / 21
Sturmova věta
Počet reálných kořenů polynomu P v intervalu a ≤ x < b je
roven W (b) − W (a), kde W (x) je počet znaménkových změn
ve Sturmově posloupnosti P0(x), . . . , Pm(x) v bodě x (z níž
jsou vyškrtnuty nuly).
Vliv malé změny hodnoty a na počet znaménkových změn
W (a) v posloupnosti pro a, které je kořenem některého
z polynomů Pi , i = 0, 1, . . . , m − 1:
a − h a a + h
Pi−1 − − −
Pi − 0 +
Pi+1 + + +
W (x) 1 1 1
a − h a a + h
Pi−1 + + +
Pi − 0 +
Pi+1 − − −
W (x) 1 1 1
Jiří Zelinka Numerické metody 5. přednáška, 19. března 2014 18 / 21
a − h a a + h
Pi−1 − − −
Pi + 0 −
Pi+1 + + +
W (x) 1 1 1
a − h a a + h
Pi−1 + + +
Pi + 0 −
Pi+1 − − −
W (x) 1 1 1
Jiří Zelinka Numerické metody 5. přednáška, 19. března 2014 19 / 21
a − h a a + h
P0 − 0 +
P1 − − −
W (x) 0 0 1
a − h a a + h
P0 + 0 −
P1 + + +
W (x) 0 0 1
Příklad
Určete počet reálných kořenů polynomu
P(x) = x3
− 3x + 1.
Řešení. Sestrojíme Sturmovu posloupnost příslušnou polynomu
P(x). Je
P0(x) = x3
− 3x + 1, P0(x) = 3x2
− 3,
P1(x) = −x2
+ 1.
Polynom P2 je záporně vzatý zbytek při dělení polynomu P0
polynomem P1, tj. P2(x) = 2x − 1 a dále P3(x) = −3/4.
Jiří Zelinka Numerické metody 5. přednáška, 19. března 2014 20 / 21
Sestavíme tabulku pro určení počtu reálných kořenů.
x P0(x) P1(x) P2(x) P3(x) W (x)
−∞ − − − − 0
+∞ + − + − 3
0 + + − − 1
−1 + 0 − − 1
−2 − − − − 0
1 − 0 + − 2
2 + − + − 3
Jiří Zelinka Numerické metody 5. přednáška, 19. března 2014 21 / 21