wyklad_9.pdf

(109 KB) Pobierz
Microsoft Word - alg_9_sm.doc
Wykład 9
Wielomiany jednej zmiennej
ƞ Definicja
Wielomianem stopnia n Î N È{0} nad pier Ļ cieniem K
nazywamy funkcj ħ P : K ® K okre Ļ lon Ģ wzorem:
P ( x ) = a n x n + a n -1 x n -1 +… + a 1 x 1 + a 0 ,
gdzie a i Î K dla i =0,1,..., n oraz a n ¹ 0. Ponadto przyjmujemy, Ň e
funkcja P ( x )º0 jest wielomianem stopnia ¥. Elementy a i Î K dla
i =0,1,..., n nazywamy współczynnikami wielomianu P ( x ).
Współczynnik a 0 nazywamy wyrazem wolnym , a współczynnik
a n nazywamy najwy Ň szym współczynnikiem wielomianu.
Liczb ħ n nazywamy stopieniem wielomianu P ( x ) i oznaczamy
przez deg( P ). Stopie ı wielomianu b ħ d Ģ cego funkcj Ģ stał Ģ jest
0.
ƛ Przykłady
 
P ( x ) = 2 x 3 – 1/3 x +12, deg(P)=3
 
P ( x ) = 2 ix 7 + 3/4 x 3 – (1+4 i ) x 2 + (2-3 i ), deg(P)=7
Mówimy, Ň e dwa wielomiany P ( x ) = a n x n + a n -1 x n -1 +… + a 1 x 1 +
a 0 i Q ( x ) = b m x m + b m -1 x m -1 +…+ b 1 x + b 0 s Ģ równe wtedy i tylko
wtedy, gdy n = m i a i = b i dla ka Ň dego i =1,2,..., n .
Oznaczymy przez K [ x ] zbiór wszystkich wielomianów jednej
zmiennej x nad pier Ļ cieniem K .
Je Ň eli P ( x ), Q ( x ) Î K [ x ], to mo Ň emy w sposób naturalny okre Ļ li ę
sum ħ , ró Ň nic ħ i iloczyn wielomianów, mianowicie:
( P + Q )( x ) = P ( x )+ Q ( x )
( P - Q )( x ) = P ( x )- Q ( x )
( P × Q )( x ) = P ( x ) Q ( x ).
217387377.003.png
2
ƛ Przykłady
P ( x ) = 3 x 2 + x -5 i Q ( x ) = 2 x +3.
Wtedy
( P + Q )( x ) = 3 x 2 +3 x -2,
( P - Q )( x ) = 3 x 2 - x -8,
( PQ )( x ) = 6 x 3 +11 x 2 -7 x -15.
ƚ Twierdzenie
Zbiór K [ x ] wszystkich wielomianów nad pier Ļ cieniem K
wzgl ħ dem dodawania i mno Ň enia jest pier Ļ cieniem
przemiennym z jedno Ļ ci Ģ .
ƚ Twierdzenie
Niech P ( x ), Q ( x ) b ħ d Ģ niezerowymi wielomianami pier Ļ cieni
K [ x ], wtedy
deg( P + Q ) £ max(deg P , deg Q )
deg( PQ ) = deg P +deg Q
Dowód. Niech P ( x ) = a n x n + a n -1 x n -1 +… + a 1 x 1 + a 0 i Q ( x ) =
b m x m + b m -1 x m -1 +…+ b 1 x + b 0 , gdzie a n ¹0 i b m ¹0. Wtedy P ( x )+ Q ( x )
= ( a s + b s ) x s + ( a s -1 + b s -1 ) x s -1 +… +( a 1 + b 1 ) x 1 + ( a 0 + b 0 ), gdzie
s =max(deg P , deg Q ). Poniewa Ň deg( P + Q ) £ s , to st Ģ d
otrzymujemy pierwszy warunek.
Drugi warunek wynika z faktu, Ň e wielomian P ( x ) Q ( x ) zawiera
niezerowy jednomian a n b m x n+m , poniewa Ň jego współczynnik
a n b m ¹0, jako iloczyn niezerowych elementów a n ¹0 i b m ¹0
pier Ļ cieni całkowitej K . Ƥ
ƛ Przykłady
217387377.004.png 217387377.005.png
3
1. P ( x ) = 3 x 2 + x -5 i Q ( x ) = 2 x +3.
( P + Q )( x ) = 3 x 2 +3 x -2,
deg(P)=2, deg(Q)=1
deg(P+Q)=2 =max{deg(P), deg(Q)}
2. P ( x ) = 3 x 2 + x -5 i Q ( x ) =-3x 2 - 2 x +3.
( P + Q )( x ) = - x -2,
deg(P)=2, deg(Q)=2
deg(P+Q)=1 <max{deg(P), deg(Q)}=2
ƚ Twierdzenie
Je Ň eli K jest pier Ļ cieniem całkowitym, to K [ x ] jest równie Ň
pier Ļ cieniem całkowitym.
Dowód. Niech P ( x ), Q ( x ) s Ģ niezerowymi wielomianami w K [ x ].
Wtedy deg( PG )=deg P +deg Q >0 i st Ģ d wynika, Ň e P ( x ) Q ( x )¹0. Ƥ
Algorytm Euklidesa
W pier Ļ cieni K [ x ] dla danych dwóch wielomianów P , Q Î K [ x ],
gdzie Q ¹0, nie zawsze istnieje taki wielomian S , Ň e P ( x ) =
Q ( x ) S ( x ), tzn. ze nie ka Ň dy wielomian P mo Ň na podzieli ę w
pier Ļ cieni K [ x ] przez dany ró Ň ny od zera wielomian Q .
ƞ Definicja
Mówimy, Ň e wielomian P Î K [ x ] jest podzielny przez
wielomian Q Î K [ x ], lub Q jest dzielnikiem wielomianu P , co
zapisujemy Q ( x ) | P ( x ), je Ļ li istnieje taki wielomian S Î K [ x ], Ň e
P ( x ) = Q ( x ) S ( x ).
ƞ Definicja
217387377.006.png 217387377.001.png
4
Wielomian P ( x )Î K [ x ] nazywamy unormowanym , je Ļ li P ( x ) ¹0
i najwy Ň szy współczynnik wielomianu P ( x ) jest równy 1, tj.
P ( x ) = x n + a n -1 x n -1 +… + a 1 x 1 + a 0 .
Poka Ň emy, Ň e je Ň eli K jest ciałem, to w pier Ļ cieniu K [ x ]
wykonane jest dzielenie z reszt Ģ , tzn. dla dowolnych
wielomianów P , Q Î K [ x ] istniej Ģ taki wielomiany S , R Î K [ x ],
Ň e dla ka Ň dego x Î K spełniony jest warunek
P ( x ) = Q ( x ) S ( x ) + R ( x )
oraz stopie ı reszty R jest mniejszy od stopnia dzielnika Q .
Wielomiany S ( x ) i R ( x ) nazywamy ilorazem i reszt Ģ
odpowiednio.
ƚ Twierdzenie (Algorytm Euklidesa)
Niech K b ħ dzie ciałem, oraz P ( x ), Q ( x ) Î K [ x ], Q ( x ) ¹ 0 i
deg P ( x ) ³ deg Q ( x ). Wtedy istniej Ģ jednoznacznie okre Ļ lone
wielomiany S ( x ), R ( x ) Î K [ x ] takie, Ň e
  P ( x ) = Q ( x ) S ( x ) + R ( x )
 
Dowód. Je Ļ li deg P ( x ) < deg Q ( x ) lub P ( x ) =0 to P ( x ) =0× Q ( x )
+ P ( x ), i dowód twierdzenia jest zako ı czony.
Niech P ( x ) = a n x n + a n -1 x n -1 +… + a 1 x 1 + a 0 ¹ 0 oraz a n ¹ 0, wi ħ c
deg P ( x ) = n . Niech Q ( x ) = b m x m + b m -1 x m -1 +… + b 1 x 1 + b 0 oraz b m ¹
0, wi ħ c deg Q ( x ) = m . Przypu Ļę my, Ň e m £ n . Dowód b ħ dziemy
prowadzi ę przez indukcj ħ za wzgl ħ du na deg P ( x ).
Je Ň eli n =0, to P ( x ) = a 0 ¹ 0. Poniewa Ň m £ n , to m =0 i Q ( x ) =
b 0 ¹ 0. Dlatego istnieje b 0 -1 i P ( x ) = ( a 0 b 0 -1 ) b 0 +0, sk Ģ d
S ( x ) = a 0 b 0 -1 i R ( x ) =0.
R ( x ) =0 lub deg R ( x ) < deg Q ( x )
217387377.002.png
5
Załó Ň my, Ň e twierdzenie jest udowodnione dla wszystkich
wielomianów stopnia < n .
Rozpatrzmy wielomian
H ( x ) = P ( x ) - ( a n b m -1 ) x n - m Q ( x ).
Wielomian H ( x ) jest ró Ň nic Ģ dwóch wielomianów stopnia n z
współczynnikami najwy Ň szymi a n , sk Ģ d wynika, Ň e deg H ( x ) < n .
Wtedy wobec zało Ň enia indukcji
H ( x ) = Q ( x ) T ( x ) + R ( x ),
gdzie T ( x ), R ( x ) Î K [ x ] i R ( x ) =0 lub deg R ( x ) < m . Wobec tego
P ( x ) = H ( x ) + Q ( x )( a n b m -1 ) x n-m
= Q ( x ) T ( x ) + R ( x ) + ( a n b m -1 ) x n-m Q ( x )
= Q ( x )[ T ( x ) +( a n b m -1 ) x n-m ] + R ( x )
= Q ( x ) S ( x ) + R ( x ).
Poka Ň emy, Ň e wielomiany S ( x ) i R ( x ) s Ģ okre Ļ lone
jednoznaczne. Przypu Ļę my, Ň e
P ( x ) = Q ( x ) S ( x )+ R ( x ) = Q ( x ) S 1 ( x )+ R 1 ( x ).
Wtedy
Q ( x )[ S ( x ) - S 1 ( x )] = R 1 ( x ) - R ( x ).
Je Ň eli S ( x ) - S 1 ( x ) ¹0, to deg Q ( x )[ S ( x ) - S 1 ( x )] = m , natomiast
deg [ R 1 ( x ) - R ( x )] < m . Ta sprzeczno Ļę pokazuje, Ň e
S ( x ) - S 1 ( x ) =0, sk Ģ d S ( x ) = S 1 ( x ) oraz R 1 ( x ) = R ( x ). Ƥ
Przykład
Podzieli ę wielomian P ( x ) = x 3 +2x 2 +x+2 przez Q(x) = x 2 +2 w
pier Ļ cieni Z 3 [x].
x 3 +2x 2 +x+2 = (x 2 +2)(x+2) + (2x+1)
Schemat Hornera

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin