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
Definicja . . . . . . . . . . . . . . . . . . . . . . . . . .
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ą implementacją 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 definicji.
Macierzą prostokątną, albo krótko macierzą o wymiarach M × N nazywamy odwzorowanie M × N → R, gdzie R – zbiór liczb rzeczywistych.
a
11
a12
. . .
a1N
a21
a22
. . .
a2N
A =
.
.
.
.
(1)
..
..
. .
..
aM1 aM2 . . .
aMN
1
Wektor kolumnowy, N -wymiarowy:
x
1
x2
¯
x =
.
(2)
..
xN
jest macierzą o wymiarach N × 1.
Macierzą jednostkową I , nazywamy macierz kwadratową o postaci:
1
0
. . .
0
0
1
. . .
0
I = .
.
.
.
(3)
.. ..
. .
..
0
0
. . .
1
Macierz trójkątna górna jest to macierz kwadratowa (N × N ) w której wszystkie elementy ponad diagonalą są równe zeru.
∀i,ji > j ⇒ aij = 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.
∀i,ji < j ⇒ aij = 0
(5)
Wyznacznikiem macierzy kwadratowej A nazywamy pewną liczbę rzeczywistą przypisaną do niej det A.
X
detA =
(−1)ka2l a
. . . a
(6)
1
1l2
nln
P (l1,l2,... ,ln)
gdzie:
• P (l1, l2, . . . , ln) – jest permutacją liczb l1, l2, . . . , ln
• 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
11
a12
A =
−→ det A = a
a
11 ∗ a22 − a12a21
(7)
21
a22
Ponieważ liczba permutacji n elementów wynosi n! to w praktyce korzysta się z następującej zależności:
det A = det LU = det L det U
(8)
gdzie
det L = Qn
l
i=1 ii
(9)
det U = Qn
u
i=1
ii
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 ⇒ det A = det U
(10)
Eliminacja Gaussa korzysta z własności, że operacje podstawowe (mnożenie wiersza przez liczbę i dodawanie wierszy) nie zmienia rozwiązania układu równań:
a
11
a12
. . .
a1N
x1
b1
a21
a22
. . .
a2N x2
b2
.
.
.
.
.
=
.
(11)
..
..
. .
..
..
..
aN1 aN2 . . .
aNN
xN
bN
i-ta iteracja polega na przemnożeniu pierwszego wiersza przez ai1 , a następ-a11
nie odejmujemy go od i-tego wiersza, otrzymujemy wówczas:
a
11
a12
a13
. . .
a1N
x
b
1
1
(1)
(1)
(1)
(1)
a
a
. . .
a
b
22
23
x2
2
2N
(1)
(1)
(1)
(1)
a
a
. . .
a
x3
b
32
33
3N
= 3
.
.
.
.
.
.
.
..
..
. .
..
.
.
.
(1)
(1)
(1)
(1)
a
a
. . .
a
xN
b
N 2
N 3
N N
N
gdzie
(1)
a
= a
a
ij
ij − ai1
a
1j
11
(1)
b
= b
b
i
i − ai1
a
1
11
W następnym kroku postępujemy podobnie w stosunku do macierzy bez pierwszego wiersza i kolumny:
a
11
a12
a13
. . .
a1N
x
b
1
1
(1)
(1)
(1)
(1)
a
a
. . .
a
b
22
23
x2
2
2N
(2)
(2)
(2)
a
. . .
a
x3
b
33
3N
= 3
.
.
.
.
.
.
..
. .
..
.
.
.
(2)
(2)
(2)
a
. . .
a
xN
b
N 3
N N
N
3
(1)
(2)
(1)
(1)
a
= a
i2 a
ij
ij
− a(1)
a
2j
22
(1)
(2)
(1)
(1)
b
= b
i2 b
i
i
− a(1)
a
2
22
Ostatecznie po n − 1 krokach otrzymujemy:
a
11
a12
a13
. . .
a1N
x
b
1
1
(1)
(1)
(1)
(1)
a
a
. . .
a
b
22
23
x2
2
2N
(2)
(2)
(2)
a
. . .
a
x3
b
33
3N
=
3
.
.
.
.
.
. .
..
.
.
.
(n
(n
a −1)
x
−1)
N
b
N N
N
gdzie
(n−2)
(n
(n
a
(n
a −1) = a −2)
i,n−1
a −2)
ij
ij
− (n
a
−2)
n−1,j
n−1,n−1
(n−2)
(n
(n
a
(n
b −1) = b −2)
i,n−1
b −2)
i
i
− (n
a
−2)
n−1
n−1,n−1
2
Operacje na macierzach
2.1
Dodawanie i odejmowanie
Suma (różnica) macierzy A i B jest macierzą: C = A ± B
(12)
o elementach:
cmn = amn ± bmn, 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:
cmk = PN
a
n=1
mnbnk,
m = 1, . . . , M ;
k = 1, . . . , K.
I jest okreslony tylko wtedy, gdy macierz A ma wymiary M × N , a macierz B wymiary N × K.
4
Transpozycja
Transpozycja macierzy
powoduje przestawienie elementów w macierzy
zgodnie ze wzorem:
T
A
= [aT
ij ] ⇒ aT
ij = aji
(14)
Przykładowo transpozycja wektora kolumnowego ¯
x (Równanie 2) powoduje
przekształcenie go w wektor wierszowy:
¯
xT = x
1
x2 . . .
xN
2.4
Macierz odwrotna
2.4.1
Definicja
Macierz odwrotna macierzy kwadratowej A o rozmiarach N × N jest ozna-czana przez
−1
−1
A
. Macierz A nazywamy odwracalną jeśli istnieje takie A dla którego:
−1
−1
A
A = I = AA
(15)
2.4.2
Wyznaczanie
Niech
−1
A
= [¯
x1, ¯
x2, . . . , ¯
xn], a I = [¯
e1, ¯
e2, . . . , ¯
en] wówczas równanie macie-
rzowe (15) można zamienić na układ równań:
A ¯
xi = ei, 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
[A|¯
e1, ¯
e2, . . . , ¯
en] = [A|I]
za pomocą operacji podstawowych. Ponieważ operacje podstawowe nie zmie-niają układu równań, to jeżeli
Operacje
([A|I]) = [I|B]
podstawowe
to
−1
−1
−1
AA
= I =⇒ IA
= B =⇒ A
= B
(16)
2.4.3
Przykład
Niech dana będzie kwadratowa macierz:
1
1
A =
(17)
3
0
5
1
1
1
0
[A|I] =
|
3
0
0
1
Zastosujmy elementarne operacje na wierszach:
• Trzykrotnie odejmujemy wiersz 1 od wiersza 2, w wyniku czego otrzymujemy:
1
1
1
0
[A|I] =
|
0
−3
−3 1
• Dzielimy wiersz 2 przez −3, w wyniku czego otrzymujemy:
1
1
1
0
[A|I] =
|
0
1
1
−13
• Odejmujemy wiersz 2 od wiersza 1, w wyniku czego otrzymujemy:
1
0
0
1
[A|I] =
|
3
0
1
1
−13
Ostatni zapis jest w formacie
−1
I|A
, wiec:
−1
0
1
A
=
3
1
−13
Sprawdzenie:
−1
1
1
0
1
1
0
AA
=
3
=
= I
3
0
1
−1
0
1
3
3
Ćwiczenia do wykonania
1. Zaimplementować programy obliczające sumę, różnicę oraz iloczyn macierzy zadanych przez użytkownika na początku programu.
2. Utworzyć schemat blokowy i zaimplementować program wyznaczający wyznacznik macierzy zadanej przez użytkownika na początku programu.
3. Utworzyć schemat blokowy i zaimplementować program wyznaczający macierz odwrotną zadaną przez użytkownika na początku programu.
4. Sprawozdanie powinno zawierać:
• Schematy blokowe.
• Listingi najważniejszych partii programu.
• Wyniki testów.
6
[1] Andrzej Marciniak, Dorota Gregulec, Jan Kaczmarek: Numerical pro-cedures.
[2] Texas A&M University: Topics in Linear Algebra.
http://sunset3.math.tamu.edu/∼mike.stecher/Linear-Algebra/
[3] Mathematics Archives Lessons, Tutorials, and Lecture Notes.
http://archives.math.utk.edu/tutorials.html
[4] http://www.maths.abdn.ac.uk/∼igc/tch/eg1508/notes/node26.html
[5] http://femur.wpi.edu/Learning-Modules/Linear-Algebra/solving/
determinant/definition.html
7