Numerické metody 6. přednáška, 28. března 2017 Jiří Zelinka Jiří Zelinka Numerické metody 6. prednáška, 28. března 2017 1/18 Polynomy n^: třída polynomů stupně nejvýše n s reálnými koeficienty. rin C n^: třída polynomů s jedničkou u xn. PeUn: P(x) = anxn + 3n-xxn~x... + aix + a0. £i>£2> • • • >£#? kořeny (reálné i komplexní) polynomu P. Dělení polynomů se zbytkem P, Q - polynomy, Pak existují polynomy S, P, že platí P = Q • S + P, přičemž st R < st Q. Jiří Zelinka Numerické metody 6. přednáška, 28. března 2017 2/18 Homérovo schema P(x) = anxn + an_ix"_1... + aix + a0, c G M. Vydělíme polynom P(x) lineárním polynomem x — c: P(x) = (x-c)Q(x) + A kde A2(x - cf + A^x -c) + A0 = - = An(x - c)n + i4n_i(x - c)""1 + • • • + Ax{x -c) + A Hodnoty Ani..., AQ jsou tedy koeficienty polynomu P posunutého do bodu c - Taylorův rozvoj. o Au = PW(c) k\ Jiří Zelinka Numerické metody 6. přednáška, 28. března 2017 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) ■ Q(x) + Ax+B pro Q (x) = bn_2* H-----h 6i x + b0. Platí: bn-2 = 3n bn-3 = 3n-l bn-4 = 3n-2 - - qbn-2 bk = ak+2 - pbk+i - qbk+2 A = ai - pb0 - qbi B = a0 - qbo □ e Jirí Zelinka Numerické metody 6. přednáška, 28. března 2017 6/18 an än-l än-2 än-3 3\ 30 -p 0 —pbn-2 -pb„-3 —pbn-4 -pbo 0 -q 0 0 —qbn-2 —qbn-3 ■ ■ ■ -qbi -q bo bn-2 bn-3 bn-4 bn-3 A B Jiří Zelinka Numerické metody 6. přednáška, 28. března 2017 7/18 Hranice kořenů Veta Nechť P(x) A B anxn + an-ixn 1... + 3Xx + a0, = max(|a„-i|,..., |a0|) = max (\an i • ■ ■ i kde 3o3„ 0. Pak pro všechny kořeny /c = polynomu P platí 0,1,..., n, 1 + B 30 < & < 1 + A Jiří Zelinka Numerické metody 6. přednáška, 28. března 2017 8/18 Příklad Polynom s kořeny £1 = 1,..., £5 = 5 P(x) = (x - l)(x - 2)(x - 3)(x - 4)(x - 5) = x5 - 15x4 + 85x3 - 225x2 + 274x - 120 A = B = 274 60 1 + 274 197 < & < 275. 120 Jiří Zelinka Numerické metody 6. přednáška, 28. března 2017 9/18 Veta n-l 1. I&l < max <{ 1,^2 7=0 2. & < 2 max 3,7-1 3n-3 tl ] •v a„ 1 a„ i ■ ■ ■ i \ a„ J 3. £k < max 1 + ai a„ 1 + an-i a„ Předchozí príklad: P(x) = x5 - 15x4 + 85x3 - 225x2 + 274x - 120 1. |&| < max{1,719} = 719 2. \£k\ < 2 max {30, 18.44, 12.16, 8.14, 5.21} 3. |&| < max{120, 275, 226, 86, 16} = 275. = 60 1= <\(y Jiří Zelinka Numerické metody 6. prednáška, 28. března 2017 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ť Ci,..., cm je posloupnost reálných čísel různých od nuly. Řekneme, že pro dvojici c^, c^+i nastává znaménková změna, jestliže QcQc+i < 0. Řekneme, že dvojice c^, c^+i zachovává znaménko, jestliže QcQc+i > 0. Jiří Zelinka Numerické metody 6. přednáška, 28. března 2017 11 / 18 Definice Posloupnost reálných polynomů P — Po? Pi? • • • ? Pm se nazývá Sturmovou posloupností příslušnou polynomu P, jestliže • Všechny reálné kořeny polynomu Po jsou jednoduché. • Je-li £ reálný kořen polynomu P0, pak signPi(0 = signP^)- • 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. Konstrukce Sturmovy posloupnosti P0(x) = P(x), P1(x) = -/*(x) a sestrojme další polynomy P,-+i rekurentně dělením polynomu P,_i polynomem P,\ P;_l(x) = Qi(x)P;{x) - qP/+1(x), /' = 1, 2.... 1 '-I kde St P; > St P/+i a konstanty q 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, 28. března 201713/18 Sturmova veta 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 Po(*), • • •, 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 1/V(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 a-h a a + h Pi-l — — — Pi-i + + + P; — 0 + P; — 0 + Pi+i + + + Pi+i — — — W(x) 1 1 1 W(x) 1 1 1 4 "= k -=_ -=_ Jiří Zelinka Numerické metody 6. prednáška, 28. března 2017 14 / 18 a — h a a + h Pi-1 p, Pi+l + 0 -+ + + W(x) 111 a — h a a + h Po Pi - 0 + W{x) 0 0 1 a — h a a + h Pi-1 p, Pi+l + + + + 0 - W(x) 111 a — h a a + h Po Pi + 0 -+ + + W{x) 0 0 1 Jiří Zelinka Numerické metody 6. přednáška, 28. března 2017 15 / 18 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 + l, P£(x) = 3x2-3, p^x) = -x2 + l. Polynom P2 je záporně vzatý zbytek při dělení polynomu Po polynomem Plf tj. P2{x) — 2x — 1 a dále Ps(x) = —3/4. Jiří Zelinka Numerické metody 6. přednáška, 28. března 2017 16 / 18 Po(x) Pii*) x3 - 3x + 1 -x2 + 1 = 2x-l = -3/4 Sestavíme tabulku pro určení počtu reálných kořenů. x —oo 0 +oo -2 -1 1 2 P0(x) P1(x) P2(x) P3(x) + + + + + + 0 0 + + W{x) 0 1 3 0 1 2 3 Jiří Zelinka Numerické metody 6. přednáška, 28. března 2017 17 / 18 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ů 3o,..., 3n nebo o sudé číslo menší. Jsou-li všechny koeficienty 3o,..., 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 < n ► <[fj]^ ^ ^)Q,o Jiří Zelinka Numerické metody 6. přednáška, 28. března 2017 18 / 18