Wykład 10
Wielomiany cd.
Niech f(x), g(x) " K[x] będą wielomianami nad ciałem K. Wielomian
d(x) " K[x] nazywamy największym wspólnym dzielnikiem wielomia-
nów f(x) i g(x) jeśli:
1. d(x) jest unormowany,
2. d(x)|f(x) i d(x)|g(x),
3. jeśli c(x) jest wielomianem, takim że c(x)|f(x) i c(x)|g(x) to stc std.
Piszemy wtedy d(x) = NWD(f(x), g(x)).
Jeśli f(x) = q(x)g(x) + r(x) to NWD(f(x), g(x)) = NWD(g(x), r(x)).
1
Algorytm Euklidesa
Niech stf > stg, wtedy możemy podzielić wielomian f przez g z resztą, a
więc:
f(x) = q(x)g(x) + r(x), 0 str < stg,
można zauważyć, że NWD(f(x), g(x)) = NWD(g(x), r(x)), można więc kon-
tynuować proces dzielenia wielomianów z resztą:
g(x) = q1(x)r(x) + rr(x), 0 str1 < str,
r(x) = q2(x)r1(x) + r2(x), 0 str2 < str1,
r1(x) = q3(x)r2(x) + r3(x), 0 str3 < str2,
. . .
ciąg kolejnych reszt ma malejące stopnie, a więc dojdziemy do reszty, której
stopień będzie równy 0, zatem:
rn(x) = qn+2(x)rn+1(x) + rn+2(x),
rn+1(x) = qn+3(x)rn+2(x)
Można też zauważyć, że
NWD(f(x), g(x)) = NWD(r(x), r1(x)) = . . . = NWD(rn+2(x), 0),
zatem mamy NWD(f(x), g(x)) = rn+2(x) a to oznacza, że największy wspól-
ny dzielnik dwóch wielomianów jest równy ostatniej niezerowej reszcie w
powyższym ciągu. Podobnie jak w przypadku liczb całkowitych można, na
podstawie powyższego algorytmu, rozwiązywać równanie (wielomianowe) po-
staci:
f(x)v(x) + g(x)u(x) = NWD(f(x), g(x)).
1
Euklides matematyk grecki - dał podwaliny współczesnej geometrii
1
Zadanie Wyznaczyć NWD(x2, x5 + x + 1).
" "
3 3
Zadanie Wyznaczyć liczbę odwrotną do 1 + 2 + 4.
"
3
Rozwiązanie Zauważmy, że liczba 2 jest pierwiastkiem
"wielomianu f(x) =
" "
3 3 3
x3-2. Rozważmy wielomian g(x) = 1+x+x2. Wtedy g( 2) = 1+ 2+ 4, a
"
3
więc wartość wielomianu g(x) w punkcie 2 jest równy liczbie, którą chcemy
odwrócić. Zastosujmy algorytm euklidesa do wielomianów f(x) oraz g(x):
x3 - 2 = (x - 1)(x2 + x + 1) - 1
stÄ…d
1 = (x - 1)(x2 + x + 1) - (x3 - 2)
"
3
Po podstawieniu 2 za x mamy:
" " " "
3 3 3 3
1 = ( 2 - 1)(1 + 2 + 4) + (( 2)3 - 2)
a więc
" " "
3 3 3
1 = ( 2 - 1)(1 + 2 + 4)
" " " "
3 3 3 3
To oznacza, że liczbą odwrotną do 1 = ( 2 - 1)(1 + 2 + 4) jest 2 - 1
Macierze
Niech K będzie dowolnym ciałem i niech m, n " N. Układ mn elementów
ciała K ułożonych w prostokątną tablicę z m wierszy i n kolumn nazywamy
macierzą nad ciałem K i oznaczamy:
îÅ‚ Å‚Å‚
a11 a12 . . . a1n
ïÅ‚
a21 a22 . . . a2n śł
ïÅ‚ śł
A = ïÅ‚ śł
ðÅ‚ ûÅ‚
. . . . . . . . . . . .
am1 am2 . . . amn
gdzie aij " K, i " {1, . . . , m}, j " {1, . . . , n}. Czasem w skrócie będziemy
pisać A = [aij]m×n. Element aij poÅ‚ożony jest w i-tym wierszu i j-tej kolumnie
macierzy A.
Przykład
îÅ‚ Å‚Å‚
1 5 -3 0, 5
ïÅ‚ śł
A = 2 7 0 3 ûÅ‚
ðÅ‚
-1 1 1, 2 4
jest macierzÄ… 3 × 4 o współczynnikach z ciaÅ‚a R. Na przykÅ‚ad a24 = 3 jest
elementem z drugiego wiersza i czwartej kolumny.
2
Zbiór wszystkich macierzy m×n o współczynnikach z ciaÅ‚a K oznaczamy
przez Mm,n(K). W zbiorze Mm,n(K) można wprowadzić działanie dodawania
+:
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
a11 a12 . . . a1n b11 b12 . . . b1n
ïÅ‚
a21 a22 . . . a2n śł ïÅ‚ b21 b22 . . . b2n śł
ïÅ‚ śł ïÅ‚ śł
ïÅ‚ śł + ïÅ‚ śł =
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
. . . . . . . . . . . . . . . . . . . . . . . .
am1 am2 . . . amn bm1 bm2 . . . bmn
îÅ‚ Å‚Å‚
a11 + b11 a12 + b12 . . . a1n + b1n
ïÅ‚
a21 + b21 a22 + b22 . . . a2n + b2n śł
ïÅ‚ śł
ïÅ‚ śł
ðÅ‚ ûÅ‚
. . . . . . . . . . . .
am1 + bm1 am2 + bm2 . . . amn + bmn
Przykład
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
3 1 0 -2 1 -1 0 2 4 0 0 0
ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
ðÅ‚ 2 1 8 -2 + -2 1 1 2 = 0 2 9 0 ûÅ‚
ûÅ‚ ðÅ‚ ûÅ‚ ðÅ‚
5 3 2 1 4 -3 0 -1 9 0 2 0
Twierdzenie 1 Struktura (Mm,n(K), +) jest grupÄ… abelowÄ….
Niech A bÄ™dzie m×n macierzÄ…, a B macierzÄ… stopnia n×k, wtedy mamy:
A = [aij]m×n, B = [bij]n×k,
można wtedy wprowadzić dziaÅ‚anie mnożenia ·:
A · B = C = [cij]m×k,
gdzie:
n

cij = ailblj.
l=1
Inaczej mówiąc element cij z i-tego wiersza i j-tej kolumny macierzy C po-
wstaje przez wymnożenie i-tego wiersza [ai1, ai2, . . . , ain] macierzy A przez
îÅ‚ Å‚Å‚
bj1
ïÅ‚ śł
bj2
ïÅ‚ śł
ïÅ‚ śł
j-tÄ… kolumnÄ™ macierzy B. Mamy zatem:
.
ïÅ‚ śł
.
ðÅ‚ . ûÅ‚
bjn
îÅ‚ Å‚Å‚
bj1
ïÅ‚ śł
bj2
ïÅ‚ śł
ïÅ‚ śł
cij = [ai1, ai2, . . . , ain] · = ai1b1j + ai2b2j + · · · + ainbnj.
.
ïÅ‚ śł
.
ðÅ‚ . ûÅ‚
bjn
3
Przeanalizujmy mnożenie macierzy na przykładach:
Przykłady
1.
îÅ‚ Å‚Å‚
2
ïÅ‚ śł
1
ïÅ‚ śł
[2, 3, 4, 5] · ïÅ‚ śł = [2 · 2 + 3 · 1 + 4 · 3 + 5 · 6] = [47],
ðÅ‚ ûÅ‚
3
6
ponieważ pierwsza macierz ma wymiar 1 × 4, a druga 4 × 1 to wynik jest
macierzÄ… 1 × 1.
2.
îÅ‚ Å‚Å‚
2
ïÅ‚ śł
1
ïÅ‚ śł
ïÅ‚ śł · [2, 3, 4, 5] = C
ðÅ‚ ûÅ‚
3
6
jest to iloczyn macierzy 4 × 1 i 1 × 4, zatem wynik jest macierzÄ… 4 × 4. Mamy
więc:
îÅ‚ Å‚Å‚
c11 c12 c13 c14
ïÅ‚
c21 c22 c23 c24 śł
ïÅ‚ śł
C = ïÅ‚ śł
ðÅ‚ ûÅ‚
c31 c32 c33 c34
c41 c42 c43 c44
gdzie:
c11 = a11b11 = 2 · 2 c12 = a11b12 = 2 · 3 c13 = a11b13 = 2 · 4 c14 = a11b14 = 2 · 5
c21 = a21b11 = 1 · 2 c22 = a21b12 = 1 · 3 c23 = a21b13 = 1 · 4 c24 = a21b24 = 1 · 5
c31 = a31b11 = 3 · 2 c32 = a31b12 = 3 · 3 c33 = a31b13 = 3 · 4 c34 = a31b14 = 3 · 5
c41 = a41b11 = 6 · 2 c42 = a41b12 = 6 · 3 c43 = a41b13 = 6 · 4 c44 = a41b14 = 6 · 5
zatem:
îÅ‚ Å‚Å‚
4 6 8 10
ïÅ‚ śł
2 3 4 5
ïÅ‚ śł
C = ïÅ‚ śł
ðÅ‚ ûÅ‚
6 9 12 15
12 18 24 30
3.
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 3 5 0 2 -1
ïÅ‚ śł ïÅ‚ śł
ðÅ‚ -1 0 2 · 1 3 2 = C
ûÅ‚ ðÅ‚ ûÅ‚
4 -1 1 3 -2 -1
Jest to iloczyn dwóch macierzy wymiaru 3 × 3. Zatem wynik jest również
macierzÄ… 3 × 3 i mamy:
îÅ‚ Å‚Å‚
c11 c12 c13
ïÅ‚
C = c21 c22 c23 śł
ðÅ‚ ûÅ‚
c31 c32 c33
4
gdzie:
c11 = a11b11 + a12b21 + a13b31 = 1 · 0 + 3 · 1 + 5 · 3 = 18
c12 = a11b12 + a12b22 + a13b32 = 1 · 2 + 3 · 3 + 5 · (-2) = 1
c13 = a11b13 + a12b23 + a13b33 = 1 · (-1) + 3 · 2 + 5 · (-1) = 0
c21 = a21b11 + a22b21 + a23b31 = (-1) · 0 + 0 · 1 + 2 · 3 = 6
c22 = a21b12 + a22b22 + a23b32 = (-1) · 2 + 0 · 3 + 2 · (-2) = -6
c23 = a21b13 + a12b21 + a13b31 = (-1) · (-1) + 0 · 2 + 2 · (-1) = -1
c31 = a31b11 + a32b21 + a33b31 = 4 · 0 + (-1) · 1 + 1 · 3 = 2
c32 = a31b12 + a32b22 + a33b32 = 4 · 2 + (-1) · 3 + 1 · (-2) = 3
c33 = a31b13 + a32b23 + a33b33 = 4 · (-1) + (-1) · 2 + 1 · (-1) = -7
5