Numerické metody
6. přednáška, 29. března 2019
Jiří Zelinka
Jiří Zelinka Numerické metody 6. přednáška, 29. března 2019 1 / 12
Opakování
Polynomy
P(x) = anxn
+ an−1xn−1
. . . + a1x + a0.
Věta – hranice kořenů
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 = 0, 1, . . . , n,
polynomu P platí
1
1 +
B
|a0|
≤ |ξk| ≤ 1 +
A
|an|
.
Jiří Zelinka Numerické metody 6. přednáška, 29. března 2019 2 / 12
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 6. přednáška, 29. března 2019 3 / 12
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 6. přednáška, 29. března 2019 3 / 12
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} = 60
3. |ξk| ≤ max {120, 275, 226, 86, 16} = 275.
Jiří Zelinka Numerické metody 6. přednáška, 29. března 2019 4 / 12
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} = 60
3. |ξk| ≤ max {120, 275, 226, 86, 16} = 275.
Jiří Zelinka Numerické metody 6. přednáška, 29. března 2019 4 / 12
Počet reálných kořenů polynomu
Poznámka - odstranění násobných kořenů
Jestliže P má kořen ξ násobnosti k > 1, pak ξ je kořenem P
násobnosti k − 1. Takže dělením polynomu P největším
společným dělitelem P a P dostaneme polynom, který má
stejné kořeny jako P, ale všechny jednoduché.
Příklad: P(x) = (x − 1)4
= x4
− 4x3
+ 6x2
− 4x + 1
Definice
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.
Jiří Zelinka Numerické metody 6. přednáška, 29. března 2019 5 / 12
Počet reálných kořenů polynomu
Poznámka - odstranění násobných kořenů
Jestliže P má kořen ξ násobnosti k > 1, pak ξ je kořenem P
násobnosti k − 1. Takže dělením polynomu P největším
společným dělitelem P a P dostaneme polynom, který má
stejné kořeny jako P, ale všechny jednoduché.
Příklad: P(x) = (x − 1)4
= x4
− 4x3
+ 6x2
− 4x + 1
Definice
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.
Jiří Zelinka Numerické metody 6. přednáška, 29. března 2019 5 / 12
Počet reálných kořenů polynomu
Poznámka - odstranění násobných kořenů
Jestliže P má kořen ξ násobnosti k > 1, pak ξ je kořenem P
násobnosti k − 1. Takže dělením polynomu P největším
společným dělitelem P a P dostaneme polynom, který má
stejné kořeny jako P, ale všechny jednoduché.
Příklad: P(x) = (x − 1)4
= x4
− 4x3
+ 6x2
− 4x + 1
Definice
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.
Jiří Zelinka Numerické metody 6. přednáška, 29. března 2019 5 / 12
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 6. přednáška, 29. března 2019 6 / 12
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 6. přednáška, 29. března 2019 6 / 12
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 6. přednáška, 29. března 2019 6 / 12
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 6. přednáška, 29. března 2019 6 / 12
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 6. přednáška, 29. března 2019 6 / 12
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 6. přednáška, 29. března 2019 7 / 12
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 6. přednáška, 29. března 2019 7 / 12
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).
Důkaz
Kořen polynomu Pi nemůže být kořenem Pi+1.
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:
α − h α α + h
P0 − 0 +
P1 − − −
W (x) 0 0 1
α − h α α + h
P0 + 0 −
P1 + + +
W (x) 0 0 1
Jiří Zelinka Numerické metody 6. přednáška, 29. března 2019 8 / 12
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).
Důkaz
Kořen polynomu Pi nemůže být kořenem Pi+1.
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:
α − h α α + h
P0 − 0 +
P1 − − −
W (x) 0 0 1
α − h α α + h
P0 + 0 −
P1 + + +
W (x) 0 0 1
Jiří Zelinka Numerické metody 6. přednáška, 29. března 2019 8 / 12
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).
Důkaz
Kořen polynomu Pi nemůže být kořenem Pi+1.
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:
α − h α α + h
P0 − 0 +
P1 − − −
W (x) 0 0 1
α − h α α + h
P0 + 0 −
P1 + + +
W (x) 0 0 1
Jiří Zelinka Numerické metody 6. přednáška, 29. března 2019 8 / 12
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).
Důkaz
Kořen polynomu Pi nemůže být kořenem Pi+1.
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:
α − h α α + h
P0 − 0 +
P1 − − −
W (x) 0 0 1
α − h α α + h
P0 + 0 −
P1 + + +
W (x) 0 0 1
Jiří Zelinka Numerické metody 6. přednáška, 29. března 2019 8 / 12
α − h α α + h
Pi−1 − − −
Pi − 0 +
Pi+1 + + +
W (x) 1 1 1
α − h α α + h
Pi−1 + + +
Pi − 0 +
Pi+1 − − −
W (x) 1 1 1
α − h α α + h
Pi−1 − − −
Pi + 0 −
Pi+1 + + +
W (x) 1 1 1
α − h α α + h
Pi−1 + + +
Pi + 0 −
Pi+1 − − −
W (x) 1 1 1
Jiří Zelinka Numerické metody 6. přednáška, 29. března 2019 9 / 12
α − h α α + h
Pi−1 − − −
Pi − 0 +
Pi+1 + + +
W (x) 1 1 1
α − h α α + h
Pi−1 + + +
Pi − 0 +
Pi+1 − − −
W (x) 1 1 1
α − h α α + h
Pi−1 − − −
Pi + 0 −
Pi+1 + + +
W (x) 1 1 1
α − h α α + h
Pi−1 + + +
Pi + 0 −
Pi+1 − − −
W (x) 1 1 1
Jiří Zelinka Numerické metody 6. přednáška, 29. března 2019 9 / 12
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 6. přednáška, 29. března 201910 / 12
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 6. přednáška, 29. března 201910 / 12
P0(x) = x3
− 3x + 1
P1(x) = −x2
+ 1
P2(x) = 2x − 1
P3(x) = −3/4
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
0 + + − − 1
+∞ + − + − 3
−2 − − − − 0
−1 + 0 − − 1
1 − 0 + − 2
2 + − + − 3
Jiří Zelinka Numerické metody 6. přednáška, 29. března 201911 / 12
Odhady počtu kořenů polynomu
Věta (Descartes)
Počet kladných kořenů polynomu P (počítáno s násobností) je
roven počtu znaménkových změn v posloupnosti koeficientů
a0, . . . , an nebo o sudé číslo menší.
Jsou-li všechny koeficienty a0, . . . , an různé od nuly, pak počet
záporných kořenů je roven počtu zachování znamének v této
posloupnosti nebo o sudé číslo menší.
Příklad
P(x) = x6
− 2x5
+ 8x4
+ 3x3
− x2
+ x − 10
Posloupnost koeficientů: 1, −2, 8, 3, −1, 1, −10
Počet kladných kořenů: 5 nebo 3 nebo 1
Počet záporných kořenů: 1
Jiří Zelinka Numerické metody 6. přednáška, 29. března 201912 / 12
Odhady počtu kořenů polynomu
Věta (Descartes)
Počet kladných kořenů polynomu P (počítáno s násobností) je
roven počtu znaménkových změn v posloupnosti koeficientů
a0, . . . , an nebo o sudé číslo menší.
Jsou-li všechny koeficienty a0, . . . , an různé od nuly, pak počet
záporných kořenů je roven počtu zachování znamének v této
posloupnosti nebo o sudé číslo menší.
Příklad
P(x) = x6
− 2x5
+ 8x4
+ 3x3
− x2
+ x − 10
Posloupnost koeficientů: 1, −2, 8, 3, −1, 1, −10
Počet kladných kořenů: 5 nebo 3 nebo 1
Počet záporných kořenů: 1
Jiří Zelinka Numerické metody 6. přednáška, 29. března 201912 / 12