Polynomy nn: třída polynomů stupně nejvýše n s reálnými koeficienty. nn ^ nn: třída polynomů s jedničkou u x". Penn-. P(x) = anxn + an_ixn_1... + aix + a0. 6)^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 6. přednáška, 25. března 2015 2/18 Homérovo schema 3ix + a0, c G P(x) = anxn + a^ix"-1.. Vydělíme polynom P(x) lineárním polynomem x — c: P{x) = {x - c)Q{x) + A, kde = = (x - c)2((x - c)Q3(x) + A2) + A1(x-c) + A0 = = (x - c)3Q3(x) + A2{x -c)2 + A1(x-c) + A0 = --- = = An(x - c)n + An i(x - c)"-1 + • • • + 4i(x - c) + AQ Hodnoty An,... ,A0 jsou tedy koeficienty polynomu P posunutého do bodu c - Taylorův rozvoj. JiřT Zelinka Numerické metody 6. přednáška, 25. března 2015 5/18 Zobecněné Homérovo schema Polynom P dělíme kvadratickým trojčlenem D(x) = x2 + px + q: P(x) = D(x) • -«flP> 1 -o^O- Jin Zelinka Numerické metody 6. přednáška, 25. března 2015 10 / 18 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é. Nechť q,..., cm je posloupnost reálných čísel různých od nuly. Řekneme, že pro dvojici Ck,Ck+i nastává znaménková změna, jestliže CkCk+i < 0. Řekneme, že dvojice c*, c*+i zachovává znaménko, jestliže CkCk+i > 0. Jiří Zelinka Numerické metody 6. přednáška, 25. března 2015 11/18 Definice Posloupnost reálných polynomů P = Pq, Pí, ■ ■ ■, Pm se nazývá Sturmovou posloupností příslušnou polynomu P, jestliže a Všechny reálné kořeny polynomu P0 jsou jednoduché. • Je-li £ reálný kořen polynomu Po. pak signPtit) =-signPfá). • Pro / = 1, 2,..., m — 1, P;+i(a)P;-i(a) < 0, jestliže a je reálný kořen polynomu P\. • Poslední polynom Pm nemá reálné kořeny. « □ ► < S ► I -O0.O Jiří Zelinka Numerické metody 6. přednáška, 25. března 2015 12 / 18 Konstrukce Sturmovy posloupnosti P0(x) = P(x), P1{x) = -P0{x) a sestrojme další polynomy P(+i rekurentně dělením polynomu P; i polynomem P,\ P;-i(x) = Qi{x)P;{x) - C/P/+i(x), i = 1,2,..., kde St P; > St P/+i a konstanty c(- jsou kladné, ale jinak libovolné. Lze říci, že P(+i je záporně vzatý zbytek při dělení P/ i/P/. Protože stupně polynomů klesají, musí algoritmus končit po m < n krocích. Jiří Zelinka Numerické metody 6. přednáška, 25. března 2015 13 / 18 Sturmova veta Počet reálných kořenů polynomu P v intervalu a < x < b je roven 1/1/(6) — W(a), kde W(x) je počet znaménkových změn ve Sturmově posloupnosti Po{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 l/l/(a) v posloupnosti pro a, které je kořenem některého z polynomů P,, 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 Pí 1 Pi Pi+i + + + - 0 + W(x) 1 1 1 Jiří Zelinka Numerické metody 6. přednáška, 25. března 2015 14 / 18 a — h a a + h P + O - Pj+l + + + W(x) 1 1 1 a-h a a + h Pi-l + + + Pi Pi+1 + 0 W(x) 1 1 1 Jiří Zelinka Numerické metody 6. přednáška, 25. března 201515/18 a-h a a + h a-h a a + h Po — 0 + Po + 0 Pl — — — Pi + + + IrV(x) 0 0 1 IrV(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, P'0(x) = 3x2 - 3, Px(x) = -x2 + l. Polynom P2 je záporně vzatý zbytek při dělení polynomu P0 polynomem Plt tj. P2(x) = 2x - 1 a dále ^3(x^= -3/A_. Jiří Zelinka Numerické metody 6. přednáška, 25. března 2015 16 / 18 Sestavíme tabulku pro určení počtu reálných kořenů. X Pi(x) P2(x) P3(x) W(x) — oo +00 0 -1 0 + + + - + -+ - -0 - - 0 3 1 1 0 2 3 — z 1 2 + 0 + -- + - Jiří Zelinka Numerické metody 6. přednáška, 25. března 2015 17 / 18 Odhady počtu kořenů polynomu Veta (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 koeficientu ao,..., a„ 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ů: Počet kladných kořenů: Počet záporných kořenů: 1,-2,8,3,-1,1,-10 5 nebo 3 nebo 1 1 Jiří Zelinka Numerické metody 6. přednáška, 25. března 2015 18 / 18