Univerzita Karlova v Praze Pedagogická fakulta
SEMINÁRNÍ PRÁCE Z POLYNOMICKÉ ALGEBRY
POLYNOM
2001/2002
CIFRIK
Zadání: Vyšetřete všemi probranými prostředky polynom f (x ) = x 4 − 2 x 3 + x 2 − 10 x − 20 . Vypracování:
Racionální kořeny Podle věty: p ∈ Q je kořen polynomu f (x ) = a 0 x n + K + a n −1 x + a n . Pak p a n , q a 0 . q
Nechť
určíme množinu M všech racionálních čísel, které mohou být kořeny: V našem případě je p ∈ {± 1,±2,±4,±5,±10,±20} q ∈ {± 1}
a proto
M = {± 1,±2,±4,±5,±10,±20}.
Tuto množinu M ještě omezíme, neboť platí věta: p ∈ Q je kořen polynomu f (x ) = a 0 x n + K + a n −1 x + a n , nechť c ∈ Z . q Pak (qc − p ) f (c ), (qc + p ) f (− c ) (používá se nejčastěji pro c = 1 , kdy dostáváme
Nechť
p podmínky (q − p ) f (1), (q + p ) f (− 1) ). q
pro kořen
Nejprve zjistíme, že f (1) = −30, f (− 1) = −6 . Další výpočet zapíšeme do tabulky: p q
p q
q + p − 6 q − p − 30 výsledek
2 -2 4 -4 5
3 -1 5 -3 6
-1 3 -3 5 -4
ano ano ne ano ne
q + p − 6 q − p − 30 výsledek
-5 10 -10 20 -20
-4 11 -9 21 -19
6 -9 11 -19 21
ne ne ne ne ne
Zjistili jsme, že M 1 = {2,−2,−4} . Hornerovým schématem vyšetříme, které prvky z M 1 jsou kořeny polynomu f : 2
1 0 1
-2 2 0
1 0 1
-10 -20 2 -16 -8 -36
-2
1 0 1
-2 -2 -4
1 8 9
-10 -20 -18 56 -28 36
4
1 0 1
-2 4 2
1 -10 -20 8 36 104 9 26 84
Z vypočítaných hodnot plyne závěr – polynom f (x ) = x 4 − 2 x 3 + x 2 − 10 x − 20 nemá racionální kořeny. 1
Odhad počtu reálných kořenů a jejich polohy Descartesova věta: Počet kladných kořenů polynomu f (x ) = a0 x n + K + a n −1 x + a n je buď roven počtu znaménkových změn v posloupnosti a0 , a1 , K, a n jeho koeficientů, nebo je o sudý počet menší. • V polynomu f (x ) = x 4 − 2 x 3 + x 2 − 10 x − 20 jsou 3 znaménkové změny. Počet kladných kořenů je tedy buď 3 nebo 1. Všechny reálné kořeny polynomu f (x ) = a0 x n + K + a n −1 x + a n leží v intervalu − 1 − A, 1 + A , kde A = max ( a 0 , a1 , K , a n ) • V našem případě je
A = max ( 1 , − 2 , 1 , − 10 , − 20 ) = 20
proto všechny reálné kořeny polynomu f (x ) = x 4 − 2 x 3 + x 2 − 10 x − 20 leží v intervalu − 21; 21 Další odhady polohy reálných kořenů polynomu f (x ) = a0 x n + K + a n −1 x + a n . Předpokládejme, že aspoň jeden z koeficientů polynomu f je záporný. Označme ai ar as B
… … … …
nejmenší záporný koeficient, první záporný koeficient největší kladný koeficient před prvním záporným koeficientem, největší z absolutních hodnot záporných koeficientů.
Pak pro každý reálný kořen α polynomu f (x ) = a0 x n + K + a n −1 x + a n platí: ai
Maclaurinova věta
α < 1+
Lagrangeova věta
α < 1+ r B ,
Tillotova věta
α < 1 + r −s
a0
,
ai as
• Pro náš polynom f (x ) = x 4 − 2 x 3 + x 2 − 10 x − 20 platí: ai = a 4 = −20 a r = a1 = −2 a s = a0 = 1 B = 20
2
Maclaurinova věta:
Tillotova věta:
ai
α < 1+
a0 − 20
α < 1+
α < 1 + r −s α < 1 + 1−0
1
α < 21
ai as − 20 1
α < 21
Lagrangeova věta: α < 1 + B r
α < 1 + 1 20 α < 21
Použití těchto vět nám původní odhad − 21; 21 nezlepšilo. Dolní odhady kořenů polynomu f získáme opakováním postupu pro polynom g , pro který platí g (x ) = f (− x )
(protože n je sudé, kdyby bylo liché, platilo by g (x ) = − f (− x ) ). Polynom g tedy je g (x ) = f (− x ) = x 4 + 2 x 3 + x 2 + 10 x − 20
a protože má jedenu znaménkovou změnu, má i jeden kladný kořen. Proto má polynom f jeden záporný kořen. Pro polynom g (x ) = x 4 + 2 x 3 + x 2 + 10 x − 20 platí: ai = a 4 = −20 a r = a 4 = −20 a s = a3 = 10 B = 20
Maclaurinova věta:
α < 1+
Tillotova věta:
ai a0 − 20
α < 1+
1
α < 21
α < 1 + r −s α < 1 + 4 −3
ai as − 20 10
α <3
Lagrangeova věta: α < 1 + B r
α < 1 + 4 20 < 3,115
Zjistili jsme, že reálné kořeny polynomu f (x ) = x 4 − 2 x 3 + x 2 − 10 x − 20 leží v intervalu − 3; 21 . Jeden kořen je záporný a buď tři nebo jeden je kladný.
3
Separace kořenů Separovat kořeny polynomu f znamená určit intervaly, v nichž leží právě jeden kořen polynomu f . Sturmův řetězec: Nechť f ∈ R[x ]. Sturmovým řetězcem polynomu f nazýváme konečnou posloupnost polynomů f i , i = 1,2, K, m , definovaných takto: f1 (x ) = f (x ),
f 2 (x ) = f ′(x ),
f j −1 (x ) = q j −1 (x ) f j (x ) − f j +1 (x ), f m −1 (x ) = q m −1 (x ) f m (x )
j = 2, K , m − 1
(polynom − f j +1 je zbytek při dělení polynomu f j −1 polynomem f j , f m je D( f , f ′) ). Sturmova věta: Buď f ∈ R[x ]. Nechť je α < β a f (α ) f (β ) ≠ 0 . Pak počet navzájem různých kořenů polynomu f (x ) = a0 x n + K + a n −1 x + a n ležících v intervalu α , β je roven číslu σ (α ) − σ (β ) , kde σ (x ) je počet znaménkových změn ve Sturmově řetězci polynomu f (x ) = a0 x n + K + a n −1 x + a n . (Pomocí této věty můžeme určit přesný počet kořenů daného polynomu v daném intervalu.) Sturmův řetězec polynomu f (x ) = x 4 − 2 x 3 + x 2 − 10 x − 20 má tyto členy: f1 (x ) = f (x ) = x 4 − 2 x 3 + x 2 − 10 x − 20
f 2 (x ) = f ′(x ) = 4 x 3 − 6 x 2 + 2 x − 10 1 2 29 85 x + x+ 4 4 4 f 4 (x ) = −3200 x − 10360 f 3 (x ) =
f 5 (x ) = −
79591 32400
(jednotlivé výpočty členů posloupnosti jsou uvedeny v dodatku). Protože je st (D( f , f ′)) = 0 , nemá polynom f (x ) = x 4 − 2 x 3 + x 2 − 10 x − 20 vícenásobné kořeny (tj. má pouze jednoduché kořeny).
4
Sestrojme nyní tabulku znamének polynomu ze Sturmova řetězce v intervalu − 3; 21 , k výpočtu znamének hodnot v jednotlivých bodech můžeme využít také Hornerovo schéma (ukázka v dodatku): + + – – – – – + +
– – – – – + + + +
+ + + + + + + + +
– – – – – – – – –
– – – – – – – – –
3 3 2 2 2 2 2 1 1
…
…
…
…
…
…
f1(x) f2(x) f3(x) f4(x) f5(x) σ (x )
…
x -3 -2 -1 0 1 2 3 4 5
20
+
+
+
–
–
1
Z tabulky vidíme, že polynom f má jeden jednoduchý kořen v intervalu (− 2,−1) a jeden jednoduchý kořen v intervalu (3, 4) .
5
Iterakční metody hledání reálných kořenů polynomu
f ∈ R[x ]
Metoda půlení intervalu: Hledáme kořen α polynomu f s přesností ε > 0 . Buď c1 , c 2 takový interval, že znaménka čísel f (c1 ), f (c 2 ) jsou různá (pak v intervalu (c1 , c 2 ) leží aspoň jeden 1 2
kořen polynomu f . Označme c3 = (c1 + c 2 ) . Pak buď f (c3 ) = 0 a α = c3 , nebo f (c3 ) ≠ 0 . Ke konstrukci bodu c 4 použijeme ten z intervalů c1 , c3 , c3 , c 2 , pro
který platí f (ci ) f (c3 ) < 0 (tj. ten interval, v jehož krajních bodech má funkce f opačná znaménka). Popsaným způsobem pokračujeme tak dlouho, až nalezneme buď přímo kořen α , nebo až platí ci −1 − ci < ε .
Metoda tečen (Newtonova metoda): Předpokládejme, že polynom f ∈ R[x ] má jednoduché kořeny. Nechť α , β je takový interval, uvnitř kterého leží jediný kořen α polynomu f , a nechť na celém intervalu α , β je f ′( x) ≠ 0, f ′′( x) ≠ 0 . Označme c1 to z čísel α , β , pro něž platí f (c1 ) f ′′(c 2 ) > 0 , d1 druhé z čísel α , β , tj. číslo, pro něž platí f (d1 ) f ′′(d 2 ) < 0 . Utvořme posloupnosti c1 , c 2 = c1 −
f (c1 ) f (c 2 ) , c3 = c 2 − , K, f ′(c1 ) f ′(c 2 )
d1 , d 2 = d1 −
f (d1 ) f (d 2 ) , d3 = d2 − , K. f ′(c1 ) f ′(c 2 )
Potom jedna z posloupností je klesající, druhá rostoucí a obě posloupnosti konvergují ke kořenu α polynomu f .
Metoda sečen (metoda regula falsi): Předpokládejme, že polynom f ∈ R[x ] má jednoduché kořeny. Nechť α , β je takový interval, uvnitř kterého leží jediný kořen α polynomu f , a nechť na celém intervalu α , β je f ′( x) ≠ 0, f ′′( x) ≠ 0 . Označme c1 =
α f (β ) − β f (α ) . f (β ) − f (α )
Sestrojme posloupnost {c n } předpisem cn =
c n −1 f (β ) − β f (c n −1 ) , n = 2,3, K . f (β ) − f (c n −1 )
Pak posloupnost {c n } konverguje ke kořenu α polynomu f .
6
Aproximace kořenů Platí f ′(x ) = 4 x 3 − 6 x 2 + 2 x − 10, f ′′(x ) = 12 x 2 − 12 x + 2 . Uvažujme nejprve interval (− 2,−1) . Protože f (− 2) > 0, f (− 1) < 0, f ′(x ) < 0, f ′′(x ) > 0 , můžeme použít kteroukoli z uvedených iterakčních metod. Použijme například Newtonovu metodu: c1 = −2
f (c1 ) = 36
f ′(c1 ) = -70
c 2 = c1 −
f (c 2 ) = 8,49584
f ′(c 2 ) = -39,333458
f (c3 ) = 1,002566
f ′(c3 ) = -30,400648
f (c 4 ) = 0,0196407
f ′(c4 ) = -29,217155
f (c1 ) = -1,48571 f ′(c1 ) f (c 2 ) = -1,26972 c3 = c 2 − f ′(c 2 ) f (c3 ) = -1,23674 c 4 = c3 − f ′(c3 ) f (c 4 ) = -1,23607 c5 = c 4 − f ′(c 4 ) d1 = −1
f (d 1 ) = -6
d 2 = d1 −
f (d 2 ) = -4,014943
f (d1 ) = -1,118779 f ′(c1 ) f (d 2 ) = -1,23283 d3 = d2 − f ′(c 2 ) f (d 3 ) = -1,23606 d4 = d3 − f ′(c3 )
f (d 3 ) = -1,369229 f (d 4 ) = -0,09439
Víme, že posloupnost {c n } je rostoucí, posloupnost {d n } klesající a x1 = lim c n = lim d n . Proto n→∞
n →∞
x1 ∈ (c5 , d 4 ) = (− 1,23607,−1,23606)
7
I v druhém intervalu (3, 4) můžeme použít Newtonovu metodu, protože f (3) < 0, f (4 ) > 0, f ′(x ) > 0, f ′′(x ) > 0 . c1 = 4
f (c1 ) = 84
f ′(c1 ) = 158
c 2 = c1 −
f (c 2 ) = 18,609368
f ′(c 2 ) = 91,64985
f (c3 ) = 2,06131675
f ′(c3 ) = 71,81895
f (c 4 ) = 0,03712353
f ′(c4 ) = 69,24115
f (c1 ) = 3,468354 f ′(c1 ) f (c 2 ) = 3,265306 c3 = c 2 − f ′(c 2 ) f (c3 ) c 4 = c3 − = 3,236604 f ′(c3 ) f (c 4 ) = 3,236068 c5 = c 4 − f ′(c 4 ) d1 = 3
f (d 1 ) = -14
d 2 = d1 −
f (d 2 ) = -9,2721034
f (d1 ) = 3,088608 f ′(c1 ) f (d 2 ) = 3,189776 d3 = d2 − f ′(c 2 ) f (d 3 ) = 3,233065 d4 = d3 − f ′(c3 ) f (d 4 ) = 3,23606 d5 = d4 − f ′(c 4 )
f (d 3 ) = -3,1089784 f (d 4 ) = -0,2073528
Víme, že posloupnost {c n } je klesající, posloupnost {d n } rostoucí a x 2 = lim c n = lim d n . Proto n→∞
n →∞
x 2 ∈ (d 5 , c 4 ) = (3,23606; 3,236068)
Závěr: Polynom f (x ) = x 4 − 2 x 3 + x 2 − 10 x − 20 má dva reálné jednoduché kořeny. První z nich v intervalu x1 ∈ (− 1,23607,−1,23606) a druhý v intervalu x 2 ∈ (3,23606; 3,236068) . Polynom je stupně 4, proto má další dva komplexní kořeny. • Program DERIVE všechny kořeny vypočetl takto: x1 = 1 + 5 x2 = 1 − 5 x3 = i 5 x 4 = −i 5
8
DODATKY Hornerovo schéma ve vybraných bodech -2
1 0 1
-2 -2 -4
1 8 9
-10 -20 -18 56 -28 36
3
1 0 1
-2 3 1
1 -10 -20 3 12 6 4 2 -14
-1
1 0 1
-2 -1 -3
1 3 4
-10 -20 -4 14 -14 -6
4
1 0 1
-2 4 2
1 8 9
-10 -20 36 104 26 84
Výpočty polynomů Sturmova řetězce
f1 (x ) = f (x ) = x 4 − 2 x 3 + x 2 − 10 x − 20
f 2 (x ) = f ′(x ) = 4 x 3 − 6 x 2 + 2 x − 10 f1 (x ) : f 2 (x )
(x 4 − 2x 3
+ x 2 − 10 x − 20) : (4 x 3 − 6 x 2 + 2 x − 10) =
1 1 x − 4 8
3 3 1 2 5 x + x − x) 2 2 2 1 3 1 2 15 − x + x − x − 20 2 2 2 1 3 3 2 1 5 −( − x + x − x + ) 2 4 4 4 1 2 29 85 − x − x − 4 4 4 1 29 85 1 1 x 4 − 2 x 3 + x 2 − 10 x − 20 = x − 4 x 3 − 6 x 2 + 2 x − 10 − x 2 + x+ 8 4 4 4 4 1 29 85 f 3 (x ) = x 2 + x+ 4 4 4 − (x 4 −
(
)
f 2 (x ) : f 3 (x ) (4 x 3
− 6x 2
+ 2x
1 29 85 x + ) = − 10) : ( x 2 + 4 4 4 2 − 40) : ( x + 29 x + 85) = 16 x − 488
= (16 x 3 − 24 x 2 + 8x − (16 x 3 + 464 x 2 + 1360 x) − 488 x 2 − 1352 x − 40 2 − ( − 488 x − 14152 x − 41480) 12800 x + 41440 29 85 1 x + − (− 3200 x − 10360 ) 4 x 3 − 6 x 2 + 2 x − 10 = (16 x − 488) x 2 + 4 4 4 f 4 (x ) = − 3200 x − 10360
9
f 3 (x ) : f 4 (x )
1 2351 1 29 85 + ) : (−3600 x − 10360) = − x x − ( x2 + 14400 1296000 4 4 4 1 2 259 85 −( x + + ) x 4 360 4 2351 85 + x 360 4 2351 608909 −( x + ) 360 32400 79591 32400 1 2 29 85 1 2351 79591 x + x+ x− = − (− 3600 x − 10360) − − 4 4 4 14400 1296000 32400 79591 f 5 (x ) = − 32400
LITERATURA • NOVOTNÁ, J. – TRCH, M.: Algebra a teoretická aritmetika. Polynomická algebra. Univerzita Karlova v Praze – Pedagogická fakulta, Praha 2000. • ŠISLER, M. – ANDRYS, J.: O řešení algebraických rovnic. Mladá fronta, Praha 1966.
OBSAH Racionální kořeny ................................................................................................. 1 Odhad počtu reálných kořenů a jejich polohy ...................................................... 2 Separace kořenů .................................................................................................... 4 Iterakční metody hledání reálných kořenů polynomu f ∈ R[x ] ............................. 6 DODATKY ........................................................................................................... 9 LITERATURA.................................................................................................... 10 OBSAH ............................................................................................................... 10
10
