Numerické metody
6. přednáška, 26. března 2014
Jiří Zelinka
Jiří Zelinka Numerické metody 6. přednáška, 26. března 2014 1 / 13
Opakování
P(x) = anxn
+ an−1xn−1
. . . + a1x + a0.
Hranice kořenů
A = max (|an−1|, . . . , |a0|) ,
B = max (|an|, . . . , |a1|) ,
1
1 +
B
|a0|
≤ |ξk| ≤ 1 +
A
|an|
.
Jiří Zelinka Numerické metody 6. přednáška, 26. března 2014 2 / 13
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
.
Jiří Zelinka Numerické metody 6. přednáška, 26. března 2014 3 / 13
Sturmova posloupnost
P = P0, P1, . . . , Pm
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, 26. března 2014 4 / 13
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, 26. března 2014 5 / 13
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).
Konec opakování
Jiří Zelinka Numerické metody 6. přednáška, 26. března 2014 6 / 13
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, 26. března 2014 7 / 13
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, 26. března 2014 7 / 13
Newtonova metoda a její modifikace
Problém – volba počáteční aproximace
Věta
Nechť P ∈ Πn je polynom stupně n ≥ 2. Nechť všechny kořeny
ξi ,
ξ1 ≥ ξ2 ≥ . . . ≥ ξn,
jsou reálné. Pak posloupnost {xk}∞
k=0 určená Newtonovou
metodou je konvergentní klesající posloupnost pro každou
počáteční aproximaci x0 > ξ1 a platí lim
k→∞
xk = ξ1.
Jiří Zelinka Numerické metody 6. přednáška, 26. března 2014 8 / 13
Příklad
P(x) = (x − 1)(x − 2)(x − 3)(x − 4)(x − 5)(x − 6)
= x6
− 21x5
+ 175x4
− 735x3
+ 1624x2
− 1764x + 720
|ξi | < 1765
x0 = 1765
x1
.
= 1 226.8
x2
.
= 1 022.9
x3
.
= 859.99
x4
.
= 711.41
...
x10
.
= 287.99
...
x20
.
= 49.48
Jiří Zelinka Numerické metody 6. přednáška, 26. března 2014 9 / 13
Zdvojená Newtonova metoda
Pro velké xk:
xk+1
= xk
−
(xk
)n
+ . . .
n(xk)n−1 + . . .
≈ xk
1 −
1
n
,
Věta
Nechť P ∈ Πn, n ≥ 2, a nechť všechny kořeny ξi , i = 1, . . . , n
polynomu P jsou reálné a ξ1 ≥ ξ2 ≥ . . . ≥ ξn. Nechť α1 je
největší kořen P :
ξ1 ≥ α1 ≥ ξ2.
Pro n = 2 předpokládejme ξ1 > ξ2. Pak pro každé z > ξ1 jsou
čísla
z = z −
P(z)
P (z)
, y = z − 2
P(z)
P (z)
, y = y −
P(y)
P (y)
definována a platí
α1 < y, ξ1 ≤ y ≤ z .
Jiří Zelinka Numerické metody 6. přednáška, 26. března 2014 10 / 13
Algoritmus
Začneme s počáteční aproximací x0 > ξ1 a zdvojenou
metodou:
xk+1 = xk − 2
P(xk)
P (xk)
, k = 0, 1, . . .
Mohou nastat dva případy:
1 P(x0)P(xk) > 0 pro všechna k. Pak
x0 > x1 > . . . > xk > . . . ≥ ξ1, lim
k→∞
xk = ξ1
2 Existuje xk tak, že P(xk)P(x0) < 0, P(xk−1)P(x0) > 0.
V tomto případě tedy došlo k „přestřelení“ bodu ξ1 a platí
x0 > x1 > . . . > xk−1 > ξ1 > xk > α1 > ξ2.
Položme y0 = xk a pokračujme dále klasickou
Newtonovou metodou s touto počáteční aproximací:
yk+1 = yk −
P(yk)
P (yk)
, k = 0, 1, 2, . . .
Jiří Zelinka Numerické metody 6. přednáška, 26. března 2014 11 / 13
Snižování stupně
P1(x) = P(x)
x−˜ξ1
– numerické nepřesnosti v koeficientech.
Příklad
P – polynom s kořeny ξ1 = 10, . . . , ξ10 = 1
Aproximace kořenů:
˜ξ1
.
= 10.000000040624446
˜ξ2
.
= 8.999999654991576
˜ξ3
.
= 8.000001300611824
...
˜ξ7
.
= 4.000018865503898
...
˜ξ10
.
= 0.99999962963847448
Jiří Zelinka Numerické metody 6. přednáška, 26. března 2014 12 / 13
Snižování stupně
P1(x) = P(x)
x−˜ξ1
– numerické nepřesnosti v koeficientech.
Příklad
P – polynom s kořeny ξ1 = 10, . . . , ξ10 = 1
Aproximace kořenů:
˜ξ1
.
= 10.000000040624446
˜ξ2
.
= 8.999999654991576
˜ξ3
.
= 8.000001300611824
...
˜ξ7
.
= 4.000018865503898
...
˜ξ10
.
= 0.99999962963847448
Jiří Zelinka Numerické metody 6. přednáška, 26. března 2014 12 / 13
Maehlyova metoda
P1(x) =
P (x)
x − ˜ξ1
−
P(x)
(x − ˜ξ1)2
,
Dosazením tohoto vyjádření do vzorce pro Newtonovu metodu
pro polynom P1 dostaneme:
xk+1
= xk
−
P1(xk
)
P1(xk)
= xk
−
P(xk
)
P (xk) −
P(xk
)
xk − ˜ξ1
Jiří Zelinka Numerické metody 6. přednáška, 26. března 2014 13 / 13
Obecně, jestliže jsme již nalezli aproximace kořenů ˜ξ1, . . . , ˜ξj ,
postupujeme obdobně a sestrojíme polynom
Pj (x) =
P(x)
(x − ˜ξ1) . . . (x − ˜ξj )
,
Pj (x) =
P (x)
(x − ˜ξ1) . . . (x − ˜ξj )
−
P(x)
(x − ˜ξ1) . . . (x − ˜ξj )
j
i=1
1
x − ˜ξi
Newtonova metoda pro nalezení kořene ξj+1 je tvaru
xk+1
= Φj (xk
), Φj (x) = x −
P(x)
P (x) −
j
i=1
P(x)
x − ˜ξi
.
Jiří Zelinka Numerické metody 6. přednáška, 26. března 2014 14 / 13