Algorytmy i struktury danych. ...

[ Pobierz całość w formacie PDF ]
Rachunek macierzowy
Laboratorium: Algorytmy i struktury danych
Spis tre±ci
1 Wst¦p
1
2 Operacje na macierzach 4
2.1 Dodawanie i odejmowanie . . . . . . . . . . . . . . . . . . . . 4
2.2 Iloczyn macierzowy . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3 Transpozycja . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.4 Macierz odwrotna . . . . . . . . . . . . . . . . . . . . . . . . 5
2.4.1 Denicja . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.4.2 Wyznaczanie . . . . . . . . . . . . . . . . . . . . . . . 5
2.4.3 Przykªad . . . . . . . . . . . . . . . . . . . . . . . . . 5
3 wiczenia do wykonania
6
1 Wst¦p
wiczenie ma na celu zapoznanie studentów z komputerow¡ implementa-
cj¡ rachunku macierzowego. Szczególn¡ uwag¦ zwraca si¦ na implementacj¦
wyznaczania wyznacznika macierzy, oraz macierzy odwrotnej.
Aby instrukcje byªy czytelne nale»y rozpocz¡¢ od przypomnienia sobie na-
st¦puj¡cych denicji.
Macierz¡ prostok¡tn¡, albo krótko macierz¡ o wymiarach M N nazy-
wamy odwzorowanie M N !R, gdzie R { zbiór liczb rzeczywistych.
A =
2
4
a
11
a
12
::: a
1N
a
21
a
22
::: a
2N
. .
.
.
.
.
a
M1
a
M2
::: a
MN
3
5
(1)
1
Wektor kolumnowy, N-wymiarowy:
x =
2
4
x
1
x
2
.
x
N
3
5
(2)
jest macierz¡ o wymiarach N 1.
Macierz¡ jednostkow¡ I , nazywamy macierz kwadratow¡ o postaci:
2
1 0 ::: 0
0 1 ::: 0
. .
.
.
.
.
0 0 ::: 1
3
I =
4
5
(3)
Macierz trójk¡tna górna jest to macierz kwadratowa (N N) w której
wszystkie elementy ponad diagonal¡ s¡ równe zeru.
8
i;j
i > j ) a
ij
= 0
(4)
Macierz trójk¡tna dolna jest to macierz kwadratowa (N N) w której
wszystkie elementy poni»ej diagonali s¡ równe zeru.
8
i;j
i < j ) a
ij
= 0
(5)
Wyznacznikiem macierzy kwadratowej A nazywamy pewn¡ liczb¦ rzeczy-
wist¡ przypisan¡ do niej detA.
detA =
X
(1)
k
a
2l
1
a
1l
2
:::a
nl
n
(6)
P(l
1
;l
2
;:::;l
n
)
gdzie:
P(l
1
;l
2
;::: ;l
n
) { jest permutacj¡ liczb l
1
;l
2
;::: ;l
n
k { jest liczb¡ przestawie« wzgl¦dem sekwencji pocz¡tkowej
Rozwa»my przykªad permutacji trzech liczb 1,2 i 3:
Sekwencja k
123
0
132
1
213
1
231
2
312
2
321
3
2
Przykªadowo dla macierzy 2 2.
A =
a
11
a
12
a
21
a
22
! detA = a
11
a
22
a
12
a
21
(7)
Poniewa» liczba permutacji n elementów wynosi n! to w praktyce korzysta
si¦ z nast¦puj¡cej zale»no±ci:
detA = detLU = detLdetU
(8)
gdzie
Q
detL =
i=1
l
ii
Q
(9)
n
i=1
u
ii
detU =
Mo»na pokaza¢, »e otrzymanej za pomoc¡ eliminacji Gaussa macierzy górnej
U odpowiada macierz dolna L, której wszystkie elementy na diagonali s¡
równe 1. St¡d
Eliminacja
Gaussa
(A) = U) detA = detU
(10)
Eliminacja Gaussa korzysta z wªasno±ci, »e operacje podstawowe (mno»e-
nie wiersza przez liczb¦ i dodawanie wierszy) nie zmienia rozwi¡zania ukªadu
równa«:
2
a
11
a
12
::: a
1N
a
21
a
22
::: a
2N
. .
.
.
.
.
a
N1
a
N2
::: a
NN
3
2
x
1
x
2
.
x
N
3
2
b
1
b
2
.
b
N
3
4
5
4
5
=
4
5
(11)
i-ta iteracja polega na przemno»eniu pierwszego wiersza przez
a
i1
a
11
, a nast¦p-
nie odejmujemy go od i-tego wiersza, otrzymujemy wówczas:
2
a
11
a
12
a
13
::: a
1N
a
(1)
3
2
4
3
5
=
2
b
1
b
(1)
3
x
1
x
2
x
3
.
x
N
4
22
a
(1)
23
::: a
(1)
2N
5
4
2
b
(1)
5
32
a
(1)
33
::: a
(1)
.
.
.
.
.
3N
3
.
b
(1)
a
(1)
a
(1)
::: a
(1)
N2
N3
NN
N
gdzie
a
11
a
1j
b
(1
i
= b
i
a
i1
ij
= a
ij
a
i1
a
11
b
1
W nast¦pnym kroku post¦pujemy podobnie w stosunku do macierzy bez
pierwszego wiersza i kolumny:
2
a
11
a
12
a
13
::: a
1N
a
(1)
3
2
4
3
5
=
2
b
1
b
(1)
3
x
1
x
2
x
3
.
x
N
4
22
a
(1)
23
::: a
(1)
2N
5
4
2
b
(2)
5
33
::: a
(2)
.
.
.
.
3N
3
.
b
(2)
N3
::: a
(2)
NN
N
3
n
a
(1)
.
a
(1)
a
(2)
.
a
(2)
gdzie
ij
= a
(1)
ij
a
(1)
i2
a
(1)
22
a
(1)
2j
i
a
(1)
i
= b
(1)
i2
a
(1)
22
b
(1)
2
Ostatecznie po n 1 krokach otrzymujemy:
2
4
a
11
a
12
a
13
::: a
1N
a
(1)
22
a
(1)
23
::: a
(1)
2N
3
5
2
4
x
1
x
2
x
3
.
x
N
3
5
=
2
4
b
1
b
(1)
3
5
33
::: a
(2)
.
.
.
.
a
(n1)
3N
3
.
b
(n1)
NN
N
gdzie
ij
= a
(n2)
ij
a
(n2)
i;n1
a
(n2)
n1;n1
a
(n2)
n1;j
a
(n2)
i;n1
a
(n2)
n1;n1
i
= b
(n2)
i
b
(n2)
n1
2 Operacje na macierzach
2.1 Dodawanie i odejmowanie
Suma (ró»nica) macierzy A i B jest macierz¡:
C = AB
(12)
o elementach:
c
mn
= a
mn
b
mn
; m = 1;::: ;M; n = 1;::: ;N:
I jest okre±lona tylko wtedy, gdy macierz A ma wymiary M N i s¡ one
identyczne jak macierzy B.
2.2 Iloczyn macierzowy
Iloczyn macierzowy A i B jest macierz¡:
C = AB
(13)
o elementach:
N
n=1
a
mn
b
nk
; m = 1;::: ;M; k = 1;::: ;K:
I jest okreslony tylko wtedy, gdy macierz A ma wymiary M N, a macierz
B wymiary N K.
c
mk
=
P
4
a
(2)
b
(2)
2
b
(2)
a
(2)
a
(n1)
b
(n1)
2.3 Transpozycja
Transpozycja macierzy powoduje przestawienie elementów w macierzy
zgodnie ze wzorem:
A
T
= [a
ij
] ) a
ij
= a
ji
(14)
Przykªadowo transpozycja wektora kolumnowego x (Równanie 2) powoduje
przeksztaªcenie go w wektor wierszowy:
x
T
=
x
1
x
2
::: x
N
2.4 Macierz odwrotna
2.4.1 Denicja
Macierz odwrotna macierzy kwadratowej A o rozmiarach N N jest ozna-
czana przez A
1
. Macierz A nazywamy odwracaln¡ je±li istnieje takie A
1
dla którego:
A
1
A = I = AA
1
(15)
2.4.2 Wyznaczanie
Niech A
1
= [x
1
; x
2
;::: ; x
n
], a I = [e
1
; e
2
;::: ; e
n
] wówczas równanie macie-
rzowe (15) mo»na zamieni¢ na ukªad równa«:
Ax
i
= e
i
; i = 1; 2;::: ;n
Do ka»dego z równa« mo»na zastosowa¢ eliminacj¦ Gaussa, ale poniewa»
macierz ka»dego ukªadu jest taka sama wygodniej jest przeksztaªca¢ macierz
[Aje
1
; e
2
;::: ; e
n
] = [AjI]
za pomoc¡ operacji podstawowych. Poniewa» operacje podstawowe nie zmie-
niaj¡ ukªadu równa«, to je»eli
Operacje
podstawowe
([AjI]) = [IjB]
to
AA
1
= I =)IA
1
= B =)A
1
= B
(16)
2.4.3 Przykªad
Niech dana b¦dzie kwadratowa macierz:
A =
1 1
3 0
(17)
5
[ Pobierz całość w formacie PDF ]