Numerické metody
13. přednáška, 14. května 2014
Jiří Zelinka
Jiří Zelinka Numerické metody 13. přednáška, 14. května 2014 1 / 9
Komplexní kořeny reálných polynomů
Π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.
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.
Jiří Zelinka Numerické metody 13. přednáška, 14. května 2014 2 / 9
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
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 13. přednáška, 14. května 2014 3 / 9
Hodnota polynomu v komplexním čísle:
z ∈ C, polynom P dělíme
D(x) = (x − z)(x − ¯z) = x2
+ px + q, p = −2R(z), q = |z|2
Pak P(z) = Az + B.
Bairstowova metoda
Podstatou Bairstowovy metody je myšlenka nalezení
kvadratického trojčlenu, který je dělitelem daného polynomu
P.
Označme z, ¯z, z = u + i v, dvojici komplexně sdružených
kořenů polynomu P. Čísla z, ¯z jsou kořeny kvadratického
trojčlenu D(x) = x2
+ px + q, p = −2u, q = u2
+ v2
. Chceme
najít čísla p, q tak, aby polynom D dělil polynom P beze
zbytku.
Jiří Zelinka Numerické metody 13. přednáška, 14. května 2014 4 / 9
P(x) = D(x)Q(x) + Ax + B,
kde
D(x) = x2
+ px + q,
Q(x) = Q(x, p, q) je polynom st. n − 2,
A = A(p, q),
B = B(p, q).
Je třeba určit p, q tak, aby
A(p, q) = 0, B(p, q) = 0.
Jedná se o systém nelineárních rovnic a budeme ho řešit
Newtonovou metodou pro systémy nelineárních rovnic.
Jiří Zelinka Numerické metody 13. přednáška, 14. května 2014 5 / 9
Považujeme-li kvadratický trojčlen Dk(x) = x2
+ pkx + qk za
aproximaci dělitele, dostaneme další aproximaci
Dk+1(x) = x2
+ pk+1x + qk+1, pk+1 = pk + h, qk+1 = qk + g




∂A
∂p
∂A
∂q
∂B
∂p
∂B
∂q




h
g
= −
A(p, q)
B(p, q)
Označme
∂A
∂p
= Ap,
∂A
∂q
= Aq,
∂B
∂p
= Bp,
∂B
∂q
= Bq, pak
A(p, q) + Ap(p, q)h + Aq(p, q)g = 0,
B(p, q) + Bp(p, q)h + Bq(p, q)g = 0.
Jiří Zelinka Numerické metody 13. přednáška, 14. května 2014 6 / 9
Derivujme vztah P(x) = D(x)Q(x) + Ax + B podle p a q:
0 = xQ(x) + Qp(x)D(x) + Apx + Bp
0 = Q(x) + Qq(x)D(x) + Aqx + Bq
Odtud
(a) xQ(x) = −Qp(x)D(x) − Apx − Bp,
(b) Q(x) = −Qq(x)D(x) − Aqx − Bq.
−Ap, −Bp resp. −Aq, −Bq jsou koeficienty lineárních zbytků
při dělení polynomu xQ(x) polynomem D(x), resp. Q(x)
polynomem D(x). Položme
a = −Aq, b = −Bq.
Tato čísla lze opět získat zobecněným Hornerovým algoritmem
pro dělení polynomů Q(x)/D(x).
Jiří Zelinka Numerické metody 13. přednáška, 14. května 2014 7 / 9
Vypočet Ap, Bp:
xQ(x) = −xQq(x)D(x) + ax2
+ bx
xQ(x) = a(x2
+ px + q) + bx − xQq(x)D(x) − apx − aq,
a tedy
xQ(x) = a − xQq(x) D(x) + (b − ap)x − aq.
xQ(x) = −xQq(x)D(x) + ax2
+ bx
a po úpravě můžeme tento vztah zapsat ve tvaru
xQ(x) = a(x2
+ px + q) + bx − xQq(x)D(x) − apx − q,
a tedy
xQ(x) = a − xQq(x) D(x) + (b − ap)x − aq.
Porovnáním rovností dostaneme
Ap = ap − b, Bp = aq.
Jiří Zelinka Numerické metody 13. přednáška, 14. května 2014 8 / 9
Soustavu pro h a g můžeme nyní zapsat takto:
(ap − b)h − ag + A = 0,
aqh − bg + B = 0.
Vyřešením této soustavy získáme čísla h, g a kvadratický
trojčlen Dk+1(x).
Jiří Zelinka Numerické metody 13. přednáška, 14. května 2014 9 / 9