Warszawskiego Józef Chaber, Elżbieta Pol i Roman Pol 1 Komentarz. Materia odpowiada programowi zajeć z algebry liniowej na Wydziale l
Zarzadzania UW i jest oparty na naszym doświadczeniu w prowadzeniu tych
zajeć.
W przewidzianym na zajecia czasie nie ma wiele miejsca na uzasadnia-
nie metod. Wydaje sie jednak ważne, aby podkreślać ścis zwiazek tych ly
metod z uk równań i eliminacja Gaussa. Do aczyliśmy, wydzielajac je ladami l
trójkatami . . . , objaśnienia w tym duchu do wszystkich, poza cześcia
dotyczaca wyznaczników, zagadnień przewidzianych w programie. Sadzimy,
że takie wyjaśnienia powinny być latwo dostepne dla studentów, nawet jeśli
w klasie nie ma na nie czasu. Przyk zamieszczone w tekście sa zbliżone do zadań, jakie przera- lady bialiśmy w klasie. Za aczone zestawy zadań dawaliśmy studentom do sa- l
modzielnej pracy, a nasze kolokwia i egzaminy by ściśle powiazane z tymi ly
zadaniami. 2 1. Wektory i macierze, dzia algebraiczne i operacje elemen- lania tarne na macierzach.
Przestrzeń Rn z opisanymi dzia laniami dodawania wektorów i mnożenia
wektorów przez skalary jest przestrzenia liniowa. Symbolem 0 oznaczamy
wektor zerowy w tej przestrzeni, tzn. wektor o wszystkich wspó lrzednych
równych zeru. 1.2. Operacja mnożenia xT y. Iloczyn wektora - wiersza przez wektor - kolumne tego samego wymiaru,
ł łł y1 ł śł y2 ł śł ł śł T = [x1, x2, . . . , xn], = , x y . ł śł . ł . ł yn 3 określamy formu a l n = x1y1 + x2y2 + + xnyn = xiyi. xT y i=1 Jest to operacja liniowa: T T T T T
w ( + = w + w w (a = a(w dla w, " Rn, a " R. x y) x y, x) x), x, y T T Zauważmy także, że = x y y x. 1.3. Macierze. Macierza o m wierszach i n kolumnach, krótko (m n)-macierza, na-
. . . ł ł ł ł am1 . . . amn wm T 5 ł łł b11 . . . b1k ł śł . . ł śł . . B = = [ . . . , " Rn, b1, bk], bj . . ł ł bn1 . . . bnk beda macierzami takimi, że liczba kolumn macierzy A jest równa liczbie
wierszy macierzy B. Iloczyn AB jest (m k)-macierza określona formu a l ł łł w1 . . . w1 T b1 T bk ł śł . . ł śł . . AB = , . . ł ł wm . . . wm T b1 T bk tzn. na przecieciu i-tego wiersza i j-tej kolumny macierzy AB stoi iloczyn
i-tego wiersza macierzy A i j-tej kolumny macierzy B, n wi bj = ailblj. T l=1
Przy interpretacji A i B jako przekszta liniowych B : Rk Rn i lceń
A : Rn Rm, iloczyn AB określa przekszta liniowe AB : Rk Rm, lcenie które jest z lceń: lożeniem tych przekszta (AB) = A(B x x). Przyk lady.
2 3 1 2 0 1. Niech A = , B = 4 0 3 -1 0 (a) Znalezć AB
(b) Sprawdzić, że dla " R3, (AB) = A(B x x x).
0 1 0 1 2. Niech A = , B = . Pokazać, że AB = BA.
-1 0 1 0
1 -1 0 0 3. Niech C = . Sprawdzić, że C2 = CC = . 1 -1 0 0 (C) W lań lasności algebraiczne dzia na macierzach. W podanych niżej formu zak sie, że wymiary macierzy pozwalaja lach lada
na wykonanie wskazanych operacji na macierzach: A(B + C) = AB + AC, (B + C)A = BA + CA, A(BC) = (AB)C, a(AB) = (aA)B = A(aB). 6 Dwie pierwsze regu to rozdzielność mnożenia wzgledem dodawania, ly
trzecia regu oznacza, że mnożenie macierzy jest laczne, a ostatnia wia że la
operacje iloczynu macierzy z operacja mnożenia macierzy przez skalary. Naj-
mniej widoczna z tych regu laczność mnożenia, staje sie jasna, jeśli in- l
terpretuje sie macierze jako przekszta liniowe, zob. (B), bo sk lcenia ladanie
przekszta jest operacja laczna. lceń
Dla każdego n określamy (n n)-macierz jednostkowa ł łł 1 0 ł śł . ł śł . In = , . ł ł 0 1 w której na przekatnej stoja jedynki, a poza nia zera. Ponieważ In = x x
dla " Rn, przekszta In : Rn Rn jest identycznościa. Dla każdej x lcenie
(m n)-macierzy A, ImA = AIn = A. 1.6. Operacje elementarne na wierszach macierzy. Postać schod- kowa macierzy. (I) Operacja elementarna (I)(i)(k) na wierszach macierzy A polega na zamianie i-tego wiersza macierzy A z k-tym. (II) Operacja elementarna (II)(i)+a(k), gdzie i = k, polega na dodaniu do
i-tego wiersza macierzy A wiersza k-tego pomnożonego przez skalar a. (III) Operacja elementarna (III)c(i), gdzie c = 0 polega na pomnożeniu
i-tego wiersza macierzy A przez skalar c. Pierwszy niezerowy wyraz wiersza nazywać bedziemy wyrazem wiodacym
tego wiersza. Mówimy, że macierz A ma postać schodkowa, jeśli
(S1) żaden wiersz zerowy macierzy A nie poprzedza wiersza niezerowego, (S2) wyrazy wiodace kolejnych niezerowych wierszy macierzy stoja w
kolumnach o rosnacych numerach.
Wyjaśnimy, w jaki sposób dowolna m n-macierz można sprowadzić do postaci schodkowej operacjami elementarnymi typu (I) i (II) na wierszach tej macierzy. Algorytm, który opiszemy, nazywany jest metoda eliminacji Gaussa. Niech A bedzie (mn)-macierza niezerowa. Zamieniajac wiersze macierzy
A miejscami (operacja typu (I)) można umieścić jako pierwszy wiersz, w 7 którym wyraz wiodacy stoi w kolumnie o możliwie najmniejszym numerze
aij1 macierzy A1 pierwszy wiersz pomnożony przez (czyli wykonujac opera- a1j1 aij cje (II)(i)- (1)) otrzymujemy macierz A2, w której kolumny o numerach 1
a1j 1 mniejszych niż j1 sa zerowe, a jedynym niezerowym wyrazem w kolumnie o numerze j1 jest a1j : 1 ł łł 0 . . . 0 a1j a1j +1 . . . a1n 1 1 ł 0 . . . 0 0 a . . . a śł ł śł 2j1+1 2n ł śł A2 = . . . . . . ł śł . . . . . ł . . . . . ł 0 . . . 0 0 a . . . a mj1+1 mn Nastepnie powtarzamy procedure dla macierzy powsta z A2 przez opusz- lej
czenie pierwszego wiersza, uzyskujac (m n)-macierz A3, stosujemy proce-
dure do macierzy powsta z A3 przez opuszczenie dwóch pierwszych wierszy, lej
otrzymujac (m n)-macierz A4 i po kolejnych analogicznych krokach docho-
dzimy do (m n)-macierzy w postaci schodkowej. Przyk Sprowadzić nastepujace macierze do postaci schodkowej ope- lad.
racjami elementarnymi typu (I) lub (II) : ł łł ł łł 0 0 0 0 0 1 1 2 3 1 ł śł ł 0 1 2 -1 2 2 śł ł śł ł śł 2 4 6 1 ł śł ł śł 1. ł śł 2. 0 0 0 1 3 5 ł śł ł -3 -6 -9 1 ł ł śł 0 ł -2 -4 5 7 14 ł 1 2 3 0 1 2 3 4 5 6 ł łł ł łł 2 4 2 0 1 1 -1 0 ł śł -1 -2 -1 ł śł ł śł 3. ł śł 4. 0 -1 3 -1 -2 ł ł ł ł 1 5 3 1 1 1 1 2 8 1 -2 8 2. Uk równań liniowych. lady 2.1. Uk m równań z n niewiadomymi. lady Uk m równań z n niewiadomymi nazywamy uk ladem lad ńł ł a11x1 + a12x2 + + a1nxn = b1 ł ł ł ł a21x1 + a22x2 + + a2nxn = b2 (1) , . . . . ł . . . . ł . . . . ł ł ół am1x1 + am2x2 + + amnxn = bm gdzie liczby aij i bi sa dane, a x1, . . . , xn sa niewiadomymi. Uk ten lad bedziemy zapisywać w postaci macierzowej
Jeśli b = 0, to uk bedziemy nazywać jednorodnym. lad
Oznaczajac kolumny i wiersze macierzy A odpowiednio przez
ł łł a1j ł śł śł . = T aj ł . " Rm, wi = [ai1, . . . , ain], wi " Rn, . ł ł amj to znaczy piszac ł łł w1 T ł śł . ł śł . A = [ . . . , = , a1, an] . ł ł wm T możemy przedstawić uk równań (1) w postaci wektorowej lad (3) x1 + . . . + xn = b, a1 an lub też, zapisać go w postaci ńł ł w1 = b1 T x ł ł . . . . (4) . . . ł ł ół wm = bm T x 9 2.2. Rozwiazywanie uk równań metoda eliminacji. ladów
Rozpatrzmy uk równań (4). Dla każdej pary wskazników i = k, uk lad lady równań
wkT = bk wkT = bk x x , oraz wiT = bi (wi + awk)T = bi + abk x x sa równoważne, tzn. maja ten sam zbiór rozwiazań.
Wynika stad, że jeśli z uk równań (2) zwia żemy macierz [A, ladem b],
dopisujac do A kolumne b, a nastepnie przekszta [A, operacjami ele- lcimy b]
mentarnymi na wierszach do postaci [A , to uk równań b ], lad
(5) A = b x bedzie równoważny z uk wyjściowym (2). ladem
Metoda eliminacji polega na sprowadzaniu macierzy [A, operacjami ele- b] mentarnymi na wierszach do macierzy w postaci schodkowej [A , i opisaniu b ] zbioru rozwiazań uk (5) (identycznego ze zbiorem rozwiazań uk (2)). ladu ladu
Dla podkreślenia, że w macierzy [A, ostatnia kolumna gra role inna, niż b]
pozosta zob. (3), bedziemy zapisywać te macierz w postaci [A | b]. le,
Niech ł łł T c1 u1 ł śł ł śł . . ł śł . . (6) [A | b ] = , . . ł śł ł ł T cm um a wiec (5) jest uk równań ladem
(7) uiT = ci, i = 1, . . . , m, x
i za óżmy, że macierz [A | b ] jest schodkowa. l Możliwe sa dwa przypadki: T x (A) dla pewnego i, ui = 0, ale ci = 0 wówczas i-te równanie 0 = ci
jest sprzeczne, a zatem uk równań (5) nie ma rozwiazań; lad
(B) sytuacja opisana w (A) nie ma miejsca wówczas uk równań (5) lad jest niesprzeczny i cofajac sie od ostatniego niezerowego równania w (7) do
pierwszego, można wyznaczyć wszystkie rozwiazania.
Opiszemy dok przypadek (B). Niech u1T , . . . , urT beda niezerowy- ladniej
mi wierszami macierzy A i niech wyrazy wiodace kolejnych wierszy u1T , . . . , urT
stoja w kolumnach o numerach j1 < j2 < . . . < jr. 10 Uk równań (7) nie nak żadnych ograniczeń na zmienne xj z in- lad lada deksami różnymi od j1, . . . , jr sa to zmienne wolne, które traktujemy jako parametry rozwiazań.
Rozwiazywanie uk (7) zaczynamy od równania urT = cr, wyzna- ladu x
czajac zmienna xj w zależności od zmiennych wolnych parametrów xj, r
gdzie j > jr. Nastepnie z równania T x = cr-1 wyznaczamy zmienna xj ur-1 r-1
w zależności od zmiennych xj o indeksach j > jr-1, i podobnie, wyznaczamy kolejne zmienne xj , . . . , xj . W rezultacie, każda zmienna xj wyznaczona r-2 1 k jest w zależności od zmiennych wolnych xj z indeksami j > jk. Przypomnij- my, że zmienne xj dla j < j1 sa także zmiennymi wolnymi. Przyk Wyjaśnić, czy uk równań jest niesprzeczny i jeśli tak, lady. lad opisać wszystkie jego rozwiazania w zależności od zmiennych wolnych para-
3. Podprzestrzenie liniowe przestrzeni Rm, liniowa niezależność wektorów, bazy, przestrzeń zerowa N(A) i obraz R(A) macierzy A. 3.1. Kombinacje liniowe wektorów. Kombinacjami liniowymi wektorów . . . , " Rm nazywamy wektory v1, vn postaci n (1) = t1 + . . . + tn = tj tj " R. v v1 vn j=1 vj, 11
Niepusty zbiór wektorów V " Rm jest przestrzenia liniowa, jeśli każda
kombinacja liniowa wektorów vj " V jest elementem V .
Dla ustalonego uk wektorów . . . , " Rm, zbiór Lin( . . . , ladu v1, vn v1, vn) wszystkich kombinacji liniowych (1) jest przestrzenia liniowa; nazywamy
ja przestrzenia rozpieta na wektorach v1, . . . , vn, albo pow liniowa tego loka
uk wektorów. ladu 3.2. Liniowa niezależność wektorów. Uk wektorów . . . , " Rm jest liniowo niezależny, jeśli uk równań lad v1, vr lad (2) x1 + . . . + xr = 0 v1 vr ma tylko trywialne rozwiazanie x1 = x2 = . . . = xr = 0. Oznacza to, że w
uk równań liniowych zapisanym formu a (2) nie ma zmiennych wolnych, ladzie l
wiec dla dowolnego b " Lin( . . . , (nie tylko dla b = 0), uk równań v1, vr) lad
(3) x1 + . . . + xr = b v1 vr ma dok jedno rozwiazanie. ladnie
Uwaga. Uk wektorów . . . , " Rm jest liniowo niezależny wtedy lad v1, vr i tylko wtedy, gdy po sprowadzeniu macierzy [ . . . , | 0] operacjami ele- v1, vr mentarnymi na wierszach do macierzy w postaci schodkowej, otrzymuje sie
macierz, w której wyraz wiodacy i-tego wiersza stoi w i-tej kolumnie, dla
i = 1, 2, . . . , r, a pozosta wiersze sa zerowe. le Jeśli (2) ma nietrywialne rozwiazania, to uk wektorów . . . , na- lad v1, vr
Twierdzenie. Każda przestrzeń liniowa V " Rm jest rozpieta na pew-
nym liniowo niezależnym uk wektorów . . . , gdzie r d" m. ladzie v1, vr, 12 Konstruujemy uk . . . wektorów w V wybierajac najpierw lad v1, v2,
= 0, a potem kolejno " Lin( . . . , dla i > 1. Z Uwagi wynika, v1 vi v1, vi-1) że po każdym kroku konstrukcji mamy uk liniowo niezależny, a liczba lad wystepujacych w tym uk wektorów (równa liczbie niezerowych wierszy ladzie
odpowiedniej macierzy w postaci schodkowej) nie jest wieksza niż m (liczba
wierszy tej macierzy). Zatem dla pewnego r d" m wybór nastepnego wektora
nie bedzie możliwy, czyli Lin( . . . , = V . vr+1 v1, vr)
3.3. Bazy w przestrzeniach liniowych V " Rm.
Uk wektorów . . . , w V jest baza przestrzeni liniowej V " Rm, lad v1, vr jeśli V = Lin( . . . , oraz uk . . . , jest liniowo niezależny. v1, vr), lad v1, vr Równoważne określenie bazy . . . , w V : każdy wektor " V zapisuje v1, vr v sie jednoznacznie jako kombinacja liniowa = t1 +. . .+tr (wspó v v1 vr lczynniki
t1, . . . , tr interpretuje sie jako wspó v v1, vr). lrzedne wektora w bazie . . . ,
jest baza w Rm; nazywać ja bedziemy baza standardowa w Rm.
Niech V = Lin( a2, . . . , bedzie przestrzenia rozpieta na uk a1, an) ladzie
wektorów w Rm. Opiszemy, w jaki sposób można wybrać wektory , . . . , aj aj 1 r z tego uk aby otrzymać baze V , a ponadto, jak zapisać każdy z pozo- ladu,
sta wektorów jako kombinacje liniowa poprzedzajacych go wektorów lych ai
wybranych. Macierz A = [ . . . , której kolumnami sa wektory z danego uk a1, an], ladu, sprowadzamy operacjami elementarnymi na wierszach do postaci schodkowej (4) [ . . . , b1, bn]. Niech j1 < . . . < jr beda numerami kolumn, w których stoja wyrazy
wiodace niezerowych wierszy macierzy (4). Wówczas uk wektorów lad
(5) , . . . , aj aj 1 r jest baza V . 13 Aby zapisać dowolny wektor i = j1, . . . , jr, jako kombinacje liniowa ai,
poprzedzajacych go wektorów z uk (5), zwiazujemy z macierza schod- ladu
kowa (4) uk równań lad (6) x1 + . . . + xn = 0. b1 bn W uk (6) zmienne xj dla j = j1, . . . , jr sa wolne, przyjmijmy xi = ladzie -1, oraz xj = 0 dla pozosta zmiennych wolnych, a nastepnie wyznaczmy lych
z uk (6) wartości sj , sj , . . . , sj pozosta zmiennych (zauważmy, że ladu lych r r-1 1 dla jk > i, sj = 0). k Wówczas (7) = sj + . . . + sj , gdzie jq < i. ai aj aj 1 1 q q Opisana procedura wyboru bazy z uk rozpinajacego przestrzeń V ladu
odpowiada konstrukcji z dowodu Twierdzenia w 3.2. Dla uzasadnienia tej procedury rozpatrzmy uk równań lad (8) x1 + . . . + xn = 0. a1 an Uk (8) jest równoważny uk (6), bo macierz [ . . . , | 0] otrzymuje lad ladowi b1, bn sie z macierzy [ . . . , | 0] w wyniku operacji elementarnych na wierszach. a1, an
Znajdujac sj , . . . , sj tak, że - +. . .+sj = 0 (i sj = 0 dla jk > i), bi+sj bj bj 1 r 1 1 r r k zapewniamy wiec (7). W szczególności, dla każdego i, " Lin( , . . . , ), ai aj aj 1 r
skad V = Lin( , . . . , ). aj aj 1 r
Liniowa niezależność uk (5) wynika z Uwagi w 3.2, bo w macierzy ladu schodkowej [ , . . . , | 0] wyraz wiodacy i-tego wiersza stoi w i-tej kolumnie bj bj 1 r
dla i = 1, . . . , r, a pozosta wiersze sa zerowe. le Przyk Z danego uk wektorów wybrać baze przestrzeni rozpietej lad. ladu
na tym uk i zapisać każdy z pozosta wektorów tego uk jako ladzie lych ladu kombinacje liniowa poprzedzajacych go wektorów wybranych.
Twierdzenie. Każda przestrzeń liniowa V " Rm ma baze, każdy liniowo
niezależny uk wektorów w V można uzupe do bazy V i każde dwie bazy lad lnić w V maja tyle samo elementów. Pierwsza cześć tezy wynika z Twierdzenia w 3.2, a druga z nastepujacej
obserwacji: jeśli V jest rozpieta na uk wektorów . . . , . . . , i ladzie a1, ak, u1, ul
wektory . . . , sa liniowo niezależne, to Uwaga w 3.2 zapewnia, że wy- a1, ak bierajac z tego uk baze V nie usuniemy żadnego z wektorów ladu ai.
Jeśli mamy teraz dwie bazy . . . , oraz w1, . . . , wq w przestrzeni V , v1, vr, to zgodnie z ta obserwacja, kolejno: wybierajac z uk w1, . . . , baze ladu v1, vr
V , dopisujac na poczatku wybranej bazy w2 i wybierajac z tego uk baze ladu
V , a nastepnie powtarzajac te procedure dla wektorów w3, w4, . . ., po k kro-
kach dostajemy baze wk, wk-1, . . . , w1, , . . . , przestrzeni V . Za każdym vj vj 1 p
razem, dopisujac wi i wybierajac baze, zmniejszamy liczbe wektorów w ba- vj
zie (bo dopisujac do bazy wektor wi dostajemy uk liniowo zależny wektor lad
wi daje sie zapisać jako kombinacja liniowa rozszerzonego uk wektorów ladu
na dwa różne sposoby). W rezultacie, w q krokach usuwamy co najmniej q wektorów wiec q d" r i z symetrii za także r d" q. vj, lożeń,
Wymiarem dimV przestrzeni liniowej V " Rm nazywamy liczbe ele-
mentów dowolnej bazy w V .
Z Twierdzenia wynika, że jeśli V " W " Rm sa przestrzeniami liniowymi, to dimV d" dimW . Jeśli ponadto dimV = dimW , to V = W . 3.4. Przestrzeń zerowa N(A) i obraz R(A) macierzy A. Przestrzeń zerowa (m n)-macierzy A,
(9) N(A) = { " Rn : A = 0} x x
jest przestrzenia liniowa w Rn z z rozwiazań jednorodnego uk lożona ladu
równań A = 0. x Zapiszmy macierz A w postaci kolumnowej (10) A = [ . . . , " Rm a1, an], aj i przypomnijmy (zob. 2.1), że ł łł x1 ł śł . ł śł . (11) A = x1 + . . . + xn = " Rn. x a1 an, x . ł ł xn 15 Przestrzeń
(12) R(A) = {A : " Rn} = Lin( . . . , " Rm x x a1, an) rozpieta na kolumnach macierzy A nazywamy obrazem macierzy A.
Baze w przestrzeni R(A) można znalezć metoda opisana w 3.3. Aby
znalezć baze w przestrzeni N(A), przyjmijmy oznaczenia z 3.3 i rozpatrzmy
uk równań (6). Dla każdego i " {1, . . . , n} \ {j1, . . . , jr} wyznaczmy lad rozwiazanie wi uk (6), przyjmujac xi = 1, oraz xj = 0 dla pozosta ladu lych
zmiennych wolnych xj. Uk n-r wektorów wi, i " {1, . . . , n}\{j1, . . . , jr} lad jest baza przestrzeni zerowej N(A) macierzy (10). Niech I = {1, . . . , n}\{j1, . . . , jr} oznacza zbiór wszystkich zmiennych wolnych uk (6). Rozważmy wektor w = Łi"Itiwi bedacy kombinacja li- ladu
niowa wektorów wi. Wektor w jest jedynym rozwiazaniem (6) majacym
zmienne wolne xi = ti dla i " I. Każde rozwiazanie (6) można wiec jed-
noznacznie zapisać jako kombinacje liniowa wektorów wi, i " I. Ponieważ
uk równań (6) jest równoważny uk (8), uk wektorów wi, i " I lad ladowi lad jest baza N(A), zob. (9) i (11). Ponieważ, zgodnie z (5), dimR(A) = r, otrzymujemy formu e l
(13) dimN(A) + dimR(A) = n. Przyk Znalezć baze przestrzeni zerowej N(A) macierzy A, gdzie lad.
Rzedem macierzy A nazywamy liczbe rankA = dimR(A).
Rozpatrzmy uk równań lad
(14) A = b. x Zgodnie z 2.1, dla A = [ . . . , uk (14) można zapisać w postaci a1, an] lad x1 + . . . + xn = b. a1 an 16
Zatem uk równań (14) ma rozwiazanie wtedy i tylko wtedy, gdy b " R(A), lad
co można też wyrazić formu a l
(15) rankA = rank[A | b]. Niech w1, . . . , wp bedzie baza przestrzeni zerowej N(A) macierzy A. Jeśli
zachodzi (15), można wybrać wektor taki, że A = b. Wówczas dowolne v v rozwiazanie uk (14) zapisuje sie jednoznacznie w postaci ladu
(16) = + t1w1 + . . . + tpwp. x v
Istotnie, jeśli A = b, to A( - = 0, tzn. - " N(A), a wiec x x v) x v
- zapisuje sie jednoznacznie jako kombinacja liniowa wektorów z bazy x v
w1, . . . , wp.
Przyk Wyjaśnić, czy uk równań A = b jest niesprzeczny i jeśli lad. lad x tak, zapisać jego rozwiazanie ogólne w postaci (16), gdzie w1, . . . , wp jest
baza przestrzeni zerowej N(A), a t1, . . . , tp sa parametrami. ł łł ł łł 2 3 1 2 3 ł śł ł śł
3. A = ł śł , b = ł śł ł ł ł ł 0 0 5 0 5 1 2 2 3 2 5 1 Uwaga 1. Jeśli A jest (m n)-macierza i B jest (n k)-macierza, to
R(AB) " R(A) i w szczególności (17) rank(AB) d" rankA. Uwaga 2. Jeśli macierz B powstaje z macierzy A w wyniku operacji elementarnych na wierszach, to A i B maja identyczne rzedy. Istotnie, z
równoważności uk równań A = 0 i B = 0 wynika, że N(A) = N(B), ladów x x a wiec równość rzedów jest konsekwencja formu (13). ly
17 3.6. Transponowanie macierzy. Macierz transponowana AT macierzy A powstaje z A przez zamiane ko-
lumn na wiersze, tzn. ł łł T a1 ł śł ł śł . [ . . . , = aj a1, an]T . , " Rm. . ł ł T an Zauważmy, że (18) (AT )T = A, (A + B)T = AT + BT , (AB)T = BT AT , przy czym w drugiej równości zak sie, że macierze A, B maja te same lada
wymiary, a w trzeciej, że liczba kolumn macierzy A jest równa liczbie wierszy macierzy B. Bardzo ważny jest nastepujacy fakt
(19) rankA = rankAT Równość rzedów A i AT oznacza, że przestrzenie rozpiete na kolumnach
i wierszach macierzy A maja te same wymiary. Rozpatrzmy (m n)-macierz A. Niech B bedzie (m r)-macierza,
której kolumny sa baza przestrzeni R(A). Utwórzmy (r n)-macierz C, wpisujac w j-ta kolumne C wspó lczynniki przy przedstawieniu j-tej kolumny
macierzy A jako kombinacji liniowej kolumn macierzy B. Wówczas A = BC, skad AT = CT BT , zob. (18), a wiec R(AT ) " R(CT ), zob. (17). Zatem
dimR(AT ) d" r, bo CT ma r kolumn. Otrzymaliśmy nierówność rankAT d" rankA. Podstawiajac w tej nierówności AT zamiast A, dostajemy nierówność
przeciwna rankA = rank(AT )T d" rankAT . 4. Macierze odwracalne. 4.1. Odwracanie macierzy. Mówimy, że (n n)-macierz A jest odwracalna, jeśli istnieje (n n)- macierz B taka, że (1) AB = In. Jeśli taka macierz B istnieje, jest wyznaczona jednoznacznie; nazywamy ja macierza odwrotna do A i oznaczamy symbolem A-1. 18 Twierdzenie. Macierz A wymiaru n n jest odwracalna wtedy i tylko wtedy, gdy rankA = n. Niech
(2) A = [ . . . , ai " Rn. a1, an], Sprowadzmy macierz (3) [A | In] = [ . . . , | . . . , a1, an e1, en] operacjami elementarnymi na wierszach do macierzy schodkowej (4) [C | D]. Jeśli rankC < n (tzn. macierz schodkowa C ma wiersz zerowy), macierz A nie jest odwracalna. Jeśli rankC = n, dalszymi operacjami elementarnymi na wierszach macierzy schodkowej (4) sprowadzamy ja do postaci (5) [In | B] = [ . . . , | b1, . . . , e1, en bn]. Wówczas (6) B = A-1. Uzasadnimy Twierdzenie i opisana procedure odwracania macierzy.
Jeśli A jest odwracalna, to (1) daje rank(AB) = n, a wiec rankA = n,
zob. 3.5 (17). Jeśli zaś rankA = n, to zgodnie z Uwaga 2 w 3.5, rankC = n i macierz [A | In] można sprowadzić operacjami elementarnymi na wierszach do postaci (5).
Ponieważ uk równań A = oraz In = bj sa równoważne, dla lady x ej, x j = 1, . . . , n, oraz In = bj, otrzymujemy A = dla j = 1, . . . , n, bj bj ej, co oznacza dok (1). Warunek rankA = n zapewnia ponadto, że dla ladnie każdego j d" n uk równań A = ma dok jedno rozwiazanie, wiec lad x ej ladnie
(1) wyznacza B jednoznacznie. Uwaga 1. Dla (n n)-macierzy odwracalnej A przekszta liniowe lcenie
A : Rn Rn jest odwracalne. Równość AA-1 = In, zob. (1), oznacza wiec,
że macierz odwrotna A-1 określa przekszta A-1 : Rn Rn odwrotne lcenie do A, a stad wynika, że także A-1A = In.
Przyk Wyjaśnić, czy macierz A jest odwracalna i jeśli tak, znalezć lady. A-1. 19 ł łł ł łł ł łł 1 0 0 0 1 1 0 1 4 2 ł śł 0 1 1 0 ł śł ł śł ł śł 1. A = 0 1 2 2. A = ł śł 3. A = 3 5 2 ł ł ł ł ł ł 0 0 0 1 0 3 5 0 2 1 1 1 0 1 ł łł b1 ł śł b2 ł śł
4. Dla dowolnego wektora b = ł śł rozwiazać uk równań lad
4 6 1 1 1 2 0 6. Niech A = , B = , C = . 7 11 2 3 1 -1 1 Znalezć (2 3)-macierz X taka, że AX = 3BX + C.
Uwaga 2. Jeśli A i B sa (n n)-macierzami odwracalnymi, to (AB)-1 = B-1A-1, oraz (AT )-1 = (A-1)T . Istotnie, (B-1A-1)(AB) = B-1(A-1A)B = B-1B = In, oraz AT (A-1)T = (A-1A)T = In. 5. Rzut ortogonalny na przestrzeń liniowa i zagadnienie naj- mniejszych kwadratów. 5.1. Ortogonalność wektorów i norma wektora.
Mówimy, że wektory " Rn sa ortogonalne (= prostopad co zapi- u, v le), sujemy v, jeśli T = 0. uĄ" u v
Norme (= d v l lugość) wektora " Rn określamy formu a
1 2 = ( T . v v v) 20 Wektory ortogonalne wyznaczaja trójkat, dla którego spe jest u, v lniona
formu Pitagorasa la (1) - 2= 2 + 2. u v u v Istotnie, jeżeli T = 0, to - 2= ( - ( - = T - 2 T + u v u v u v)T u v) u u u v T = 2 + 2. v v u v
5.2. Rzut ortogonalny na przestrzeń liniowa V " Rn.
Mówimy, że wektor " Rn jest ortogonalny do przestrzeni liniowej V " u
Rn, co zapisujemy , jeśli v dla każdego " V . uĄ"V uĄ" v
Twierdzenie Niech V " Rn bedzie przestrzenia liniowa. Dla każdego
b " Rn istnieje dok ladnie jeden wektor P ( " V taki, że b - P ( . b) b)Ą"V
Wektor P ( nazywamy rzutem ortogonalnym b na V . Opiszemy metode b)
wyznaczania rzutu ortogonalnego. Znajdujemy baze . . . , przestrzeni V , a nastepnie, dla macierzy a1, ar
A = [ . . . , znajdujemy wektor w " Rr taki, że a1, ar], (2) AT Aw = AT b. Wówczas (3) P ( = Aw. b) Aby uzasadnić te procedure, sprawdzimy przede wszystkim, że uk lad
równań (4) AT A = AT x b ma dok jedno rozwiazanie. W tym celu pokażemy, że (r r)-macierz ladnie
AT A jest odwracalna.
Za óżmy, że rankAT A < r i niech " Rr bedzie niezerowym wektorem l x
takim, że AT A = 0. Wektor = A spe v, bo z 3.6 (18) T = x v x lnia vĄ" v v
T AT A = T = 0. Zatem || = 0, czyli = 0, ale to przeczy liniowej x x x 0 v|| v niezależności kolumn macierzy A. Ponieważ przestrzeń V jest rozpieta na wektorach . . . , dla uzasad- a1, ar,
nienia, że b - AwĄ"V wystarczy sprawdzić, że b - Aw), dla i = 1, . . . , r, aiĄ"(
co macierzowo można zapisać w postaci AT ( - Aw) = 0 równoważnej (2). b 21 Zauważmy na koniec, że (3) implikuje P ( " R(A) = V i z jedno- b) znaczności rozwiazania (4) wynika jednoznaczność rzutu.
Odnotujmy dwa szczególne przypadki rzut ortogonalny na przestrzeń rozpieta na jednym niezerowym wektorze i rzut ortogonalny na przestrzeń
wektorów prostopad do niezerowego wektora: lych T a b
(5) jeśli V = Lin( = 0, to P ( = ( ) a), a b) a, aT a T a b
(6) jeśli V = { : a}, = 0, to P ( = b - ( ) x xĄ" a b) a. aT a T a b Dla uzasadnienia tych formu rozpatrzmy = ( ) " Lin( Po- l, c a a). aT a
nieważ T ( - = 0, b - a), stad wynika natychmiast (5). Jed- a b c) cĄ"Lin(
nocześnie zauważmy, że dla przestrzeni V opisanej w (6), b - " V , oraz c
b - ( - = , skad wynika (6). b c) cĄ"V
ł łł 1 ł śł 0 ł śł
Przyk Znalezć rzut ortogonalny wektora b = ł śł " R4 na prze- lad. ł ł 1 5
(D) V = { " R4 : T = 0}, T = (-1, -2, 0, 1). x a x a 22 5.3. Zagadnienie najmniejszych kwadratów.
Niech A bedzie (n r)-macierza rzedu r i niech b " Rn. Należy znalezć
wektor w " Rr taki, że
(7) b - Aw = min{ b - A : " Rr}. x x
Zagadnienie to nabiera znaczenia, jeśli uk równań A = b jest sprzecz- lad x
ny. Warunek (7) opisuje wówczas wektor w, dla którego odleg Aw od b, lość mierzona pierwiastkiem z sumy kwadratów różnic wspó lrzednych, jest mini-
malna. Zgodnie z 5.2, jednoznacznym rozwiazaniem tego zagadnienia jest wektor
w spe lad lniajacy uk równań (4).
Istotnie, Aw = P ( jest rzutem ortogonalnym wektora b na przestrzeń b) V = R(A) rozpieta na kolumnach A. Dla dowolnego " V , z formu v ly
Pitagorasa, b - 2= b - P ( + P ( - 2e" b - P ( 2, a zatem v b)2 b) v b) Aw spe (7). lnia W szczególności, rozpatrzmy nastepujace zagadnienie. Mierzymy dwie
zależne od siebie wielkości t, y i ustalamy, że wartościom t1, . . . , tn pierwszej z nich odpowiadaja wartości y1, . . . , yn drugiej. Chcemy określić m i c tak, aby funkcja y = mt + c minimalizowa odchylenie kwadratowe la n
E2 = [(mti + c) - yi]2. i=1
m Rozwiazaniem tego zagadnienia jest wektor w = , który spe waru- lnia
c nek (7) dla ł łł ł łł t1 1 y1 ł śł ł śł . . . ł śł ł śł . . . A = , b = . . . . ł ł ł ł tn 1 yn Istotnie, odchylenie kwadratowe zapisuje sie w postaci
m E2 = A - 2, = . x b x c 23 ł łł ł łł 1 -2 1 ł śł ł śł
Przyk 1. Niech A = -1 1 , b = 1 . lady. ł ł ł ł 1 1 -3
Znalezć min{ b - A : " R2}. x x 2. W wyniku pomiarów ustalono, że wartościom 2,3,5,6 wielkości t odpo- wiadaja wartości 1,2,6,8 wielkości y. Znalezć m i c takie, że funkcja y = mt+c minimalizuje odchylenie kwadratowe od obserwowanych wielkości. 5.4. Macierzowy opis rzutu ortogonalnego.
Niech . . . , bedzie baza przestrzeni liniowej V " Rn. Macierz A = a1, ar [ . . . , ma rzad r, wiec (r r)-macierz AT A jest odwracalna (zob. uza- a1, ar]
sadnienie jednoznaczości rozwiazań uk (4) w (5.2)). Formu 5.2 (2),(3) ladu ly
opisujace rzut ortogonalny b " Rn na V można zatem zapisać w postaci
macierzowej (8) P ( = A(AT A)-1AT b) b. Przyk Znalezć macierz opisujaca rzut ortogonalny na V lad.
ł łł ł łł 1 1 ł śł ł śł 1 2 1. V = Lin( a2), gdzie = ł śł , = ł śł " R4, a1, a1 ł śł a2 ł śł ł -1 ł ł -1 ł 0 1 ł łł -1 -1 1 0 ł śł 2. V = N(C), gdzie C = 1 0 -1 -1 . ł ł -2 -1 2 1 Formu (8) prowadzi też do opisu przestrzeni V uk równań jedno- la ladem rodnych
(9) (A(AT A)-1AT - In) = 0, x
bo " V wtedy i tylko wtedy, gdy P ( - = 0. x x) x Uk (9) ma n równań, ale przestrzeń V rozwiazań tego uk ma lad ladu
wymiar r, wiec zgodnie z 3.4 (13), rzad macierzy tego uk wynosi n - r. ladu
24 Przestrzeń V można opisać uk n - r równań ladem
(10) BT = 0, B = [ . . . , gdzie . . . , jest baza N(AT ). x u1, un-r], u1, un-r Niech W = N(BT ) bedzie przestrzenia rozwiazań uk (10). Po- ladu
nieważ rankAT = rankA = r, z 3.4 (13) wynika, że dim N(AT ) = n - r = rankB = rankBT i dimW = n - (n - r) = r = dimV .
Przestrzeń N(AT ) rozwiazań jedorodnego uk równań AT = 0 jest ladu x
zbiorem wektorów ortogonalnych do każdej z kolumn macierzy A. Zatem dla " N(AT ) mamy u uĄ"R(A) = V , co daje V " W . Z równości wymiarów tych przestrzeni wynika V = W , zob. 3.3. Przyk Znalezć jednorodny uk równań opisujacy przestrzeń V " lad. lad
ł -1 0 ł ł ł 0 1 6. Wyznacznik macierzy kwadratowej. 6.1. Określenie wyznacznika. Każdej (nn)-macierzy A można przyporzadkować w sposób jednoznacz-
ny liczbe detA wyznacznik macierzy A tak, aby spe by nastepujace lnione ly
warunki: (i) zamiana kolejności dwóch wierszy macierzy zmienia znak jej wyznacz- nika, (ii) dodanie do wiersza macierzy innego wiersza pomnożonego przez ska- lar nie zmienia jej wyznacznika, (iii) wyznacznik macierzy kwadratowej majacej same zera poniżej przekat-
nej jest iloczynem wyrazów na przekatnej.
Z w lasność lasności (i), (ii), (iii) wynika także w (iv) jeśli A powstaje z macierzy B w wyniku operacji elementarnej (III)c(i), to detA = c detB. 25 Uwaga 1. Niech ł łł a11 . . . a1n ł śł . . ł śł . . A = . . . ł ł an1 . . . ann Wyznacznik detA można określić nastepujaco. Z kolejnych wierszy wybie-
ramy wyrazy a1(1), a2(2), . . . , an(n), przy czym z każdej kolumny wybieramy tylko jeden element (tzn. (i) = (j) dla i = j) i tworzymy iloczyn
(1) (-1)l()a1(1)a2(2) . . . an(n) gdzie l() jest liczba par wskazników 1 d" i < j d" n, dla których (i) > (j) (tzn. liczba par wierszy, dla których z wcześniejszego wiersza wybraliśmy element z dalszej kolumny). Wyznacznik detA jest suma wszystkich możliwych iloczynów postaci (1). Dla n = 2 dostajemy wzór
a11 a12 det = a11a22 - a12a21, a21 a22 a dla n = 3 wzór Sarrusa ł łł a11 a12 a13 ł det a21 a22 a23 śł = a11a22a33+a12a23a31+a13a21a32-a13a22a31 ł ł a31 a32 a33 -a12a21a33 - a11a23a32.
Uwaga 2. Niech b, beda liniowo niezależnymi wektorami w R3 i niech a, c
T , T , wT beda wierszami macierzy B powsta z macierzy u v lej
ł łł T a ł śł
A = ł ł bT T c w wyniku operacji elementarnych na wierszach typu (I), lub (II). Wówczas równoleg w przestrzeni trójwymiarowej o krawedziach wyznaczonych lościan
przez b, ma objetość równa objetości równoleg a, c lościanu o krawedziach wy-
znaczonych przez w. Macierz A można przekszta operacjami typu (I) u, v, lcić i (II) do postaci ł łł r 0 0 ł śł B = 0 s 0 , ł ł 0 0 t 26 w której wektory - wiersze sa parami prostopad i wyznaczaja prostopad le lościan o objetości | rst |=| detB |=| detA |. Wynika stad, że modu wyznacznika A l
jest objetościa równoleg a, c. lościanu o krawedziach wyznaczonych przez b,
Podobnie, dla (2 2)-macierzy A, | detA | jest polem równoleg na loboku p laszczyznie, którego boki sa wyznaczone przez wektory - wiersze A. Uwaga 3. Z Uwagi 1 wynika, że dla (n n)-macierzy A, detA = detAT , zatem przy określaniu wyznacznika wiersze można zastapić kolumnami ma-
cierzy. Przyk lady. 1. Znalezć pole równoleg na p loboku laszczyznie o krawedziach P Q, P R,
gdzie P = (1, 2), Q = (6, 7), R = (3, 8). 2. Znalezć objetość równoleg lościanu w przestrzeni o krawedziach P Q, P R, P S,
gdzie P = (1, -1, 1), Q = (2, 6, 2), R = (-3, -5, 4), S = (4, 2, -1). 6.2. Obliczanie wyznacznika. Niech A bedzie (n n)-macierza. Operacjami elementarnymi typu (I),
lub (II) sprowadzamy macierz A do postaci schodkowej ł łł a1 ł śł . ł śł . A = , . ł ł 0 an zmieniajac znak wyznacznika przy każdej operacji typu (I) i nie zmieniajac
wyznacznika przy operacji typu (II). Zatem detA = (-1)pdetA = (-1)pa1 . . . an, gdzie p jest liczba wykonanych operacji typu (I). Przyk Obliczyć wyznaczniki nastepujacych macierzy: lady
ł łł ł łł ł łł 1 -1 1 -2 0 3 5 1 0 4 1 3 ł śł ł śł ł śł 1 3 -1 3 3 3 1 8 0 2 2 1 ł śł ł śł ł śł 1. ł śł 2. ł śł 3. ł śł ł -1 2 0 4 1 3 1 2 ł ł -2 0 2 1 ł ł ł -3 0 -8 -13 1 3 4 3 2 2 1 4 27 6.3. Formu Cauchy ego. la Dla (n n)-macierzy A i B, (2) det(AB) = detA detB. Zauważmy najpierw, że jeśli macierz A powstaje z A w wyniku ope- racji elementarnych na wierszach, to z definicji iloczynu macierzy w 1.5.(B) wynika, że te same operacje na wierszach macierzy AB sprowadzaja ja do macierzy A B (wystarczy to sprawdzić dla jednej operacji każdego typu). Jeśli rankA < n to z powyższej obserwacji (zob. też 3.5 (17)) wynika, że rank(AB) < n, a wiec, zgodnie z 6.2, obie strony (2) sa równe zeru.
Jeśli rankA = n, to operacjami elementarnymi na wierszach typu (I) lub (II) można sprowadzić A do postaci diagonalnej ł łł a1 0 ł śł . ł śł . A = . . ł ł 0 an Niech p ozacza liczbe wykonanych operacji typu (I). Mamy wtedy detA =
(-1)p detA i z powyższej obserwacji, również det(AB) = (-1)pdet(A B). Dla dowodu (2) wystarczy wiec sprawdzić, że det(A B) = detA detB, a to
wynika z łł ł łłł ł łł ł łł łł T T T
a1 0 b1 a1b1 b1 łł ł śłł ł śł ł śł śł łł ł śłł ł . śł ł śł . . . śł . . . . det łł ł śłł = det ł śł = a1 . . . an det ł śł . . . . . ł ł ł łłł ł ł ł ł T T 0 an bnT
anbn bn Przyk lad ł łł ł łł 4 2 1 2 2 1 ł śł ł śł Niech A = 4 1 2 , B = 0 1 0 . Znalezć det(A5B-7). ł ł ł ł 4 1 1 0 5 1 6.4. Macierz adjA stowarzyszona z macierza kwadratowa A i formu Cramera. ly Niech A bedzie (n n)-macierza. Dla każdej pary indeksów 1 d" i, j d"
n, oznaczamy przez A(i, j) macierz otrzymana z A przez skreślenie i-tego wiersza i j-tej kolumny i określamy 28 Aij = (-1)i+jdetA(i, j). Macierz ł łłT A11 . . . A1n ł śł . . ł śł . . adjA = . . ł ł An1 . . . Ann stowarzyszona z A ma nastepujaca w lasność
(3) A adjA = detA In. W szczególności, 1 (4) jeśli detA = 0, to A-1 = adjA.
detA Formu (4) pozwala zapisać rozwiazanie uk równań la ladu
(5) A = b, gdzie detA = 0, x w postaci 1 (6) = (detAadjA) x b. Jeśli ł łł x1 ł śł . ł śł . A = [ . . . , " Rn, b " Rn, = , a1, an], ai x . ł ł xn rozwiazanie (6) prowadzi do formu Cramera l
1 (7) xi = det[ . . . , b, . . . , i = 1, . . . , n. a1, ai-1, ai, an], detA Formu Cramera (7) maja g ównie znaczenie teoretyczne. Wynika z nich ly l
na przyk że jeśli detA = 1, oraz wyrazy A i wspó lad, lrzedne wektora b sa
liczbami ca x ladu lkowitymi, to rozwiazanie uk równań (5) jest wektorem o
wspó lkowitych, zob. Uwaga 1 w 6.1. lrzednych ca
Przyk Znalezć adjA i sprawdzić, że spe jest formu (3). lady. lniona la ł łł
7 1 2 3 4 ł śł 1. A = 2. A = 2 -1 -1 ł ł 5 6 3 1 3 7. Model Leontiewa przep l lywów miedzyga eziowych.
Rozpatrujemy n ga ezi gospodarki. Niech xi > 0 bedzie produkcja global- l
na i-tej ga ezi, xij e" 0 bedzie cześcia produkcji i-tej ga ezi zużywana przez l l
29 j-ta ga a z do produkcji, zaś di e" 0 bedzie produktem końcowym i-tej ga ezi l l
(sprzedawanym na rynku). Informacje te zapisujemy w postaci macierzy przep miedzyga eziowych lywów l
Leontiewa. Macierz ł łł a11 . . . a1n ł śł . . ł śł . . (2) . . ł ł an1 . . . ann jest macierza (sta wspó l lych) lczynników produkcji. Dla każdej ga ezi mamy,
zob. (1), (3) xi = xi1 + . . . + xin + di = ai1x1 + . . . + ainxn + di, co można zapisać w postaci macierzowej jako równanie ł łł ł łł x1 d1 ł śł ł śł x2 d2 ł śł ł śł ł śł ł śł = A + d, = , d = , x x x . . ł śł ł śł . . ł . ł ł . ł xn dn albo też w postaci
(4) (In - A) = d. x Macierz In - A nazywa sie macierza Leontiewa.
Twierdzenie. Jeśli produkty końcowe di każdej ga lezi gospodarki sa do-
datnie, to macierz Leontiewa In - A jest odwracalna, a wektor produkcji globalnej jest opisany formu la x
= (In - A)-1d. x 30 Mnożac, dla j = 1, 2, . . . , n, j-ta kolumne macierzy In - A przez xj i
korzystajac z (1), otrzymujemy macierz
ł łł x1 - x11 -x12 . . . -x1n ł ł -x21 x2 - x22 . . . -x2n śł śł ł śł B = . . . . ł śł . . . ł . . . ł -xn1 -xn2 . . . xn - xnn Przypuśćmy, że n n-macierz In - A nie jest odwracalna, to znaczy, że jej kolumny sa liniowo zależne (zob. 4.1). Wtedy kolumny B też sa liniowo
zależne, wiec istnieje niezerowy wektor w = [w1, . . . , wn]T taki, że Bw = 0.
Zastepujac, w razie potrzeby, w przez wektor -w możemy dodatkowo za lożyć,
że w ma dodatnia wspó lrzedna.
Wybierzmy i d" n takie, że wi e" wj dla j = i i zbadajmy i-ta wspó lrzedna
wektora Bw = 0:
n n n 0 = xiwi- xijwj e" xiwi- xijwi = (xi- xij)wi = diwi > 0. j=1 j=1 j=1 Otrzymana sprzeczność dowodzi, że macierz In - A jest odwracalna. Przyk W modelu Leontiewa dla trzech ga ezi gospodarki dana jest lad. l
macierz przep miedzyga eziowych: lywów l
ł łł 2 0 1 5 8 ł śł ł śł 2 3 0 7 12 ł śł . ł ł 0 0 1 3 4 (a) Znalezć macierz Leontiewa i i macierz do niej odwrotna.
(b) O ile wzrosna produkty końcowe, jeśli produkty globalne wzrosna o "x1 = 1, "x2 = 2, "x3 = 3? (c) Ustalić plan produkcji globalnej tak, aby pierwsza ga a z wytwarza l la produkt końcowy o wartości 9, druga o wartości 6 i trzecia o wartości 9. 8. Nierówności liniowe.
Dla " Rn, = [u1, . . . , un]T , = [v1, . . . , vn]T , nierówność d" u, v u v u v
oznacza, że uj d" vj, dla j = 1, 2, . . . , n. Jeśli e" 0, bedziemy mówili, że u
wektor jest nieujemny. u
Ustalmy wektory w1, . . . , wm " Rn i liczby b1, . . . , bm " R i niech
(1) W = { " Rn : e" 0, wiT d" bi, i = 1, 2, . . . m}. x x x 31
Dla n = 2, każda nierówność wi d" bi opisuje pó laszczyzne w R2, zatem T x lp
W jest albo zbiorem pustym, albo wielokatem (być może nieograniczonym)
leżacym w pierwszej ćwiartce p laszczyzny. Podobnie, dla n = 3, albo W =
", albo też W jest wielościanem (być może nieograniczonym), z lożonym z wektorów nieujemnych. Zauważmy, że zamiast (1) możemy rozważać zbiory postaci
(1) W = { " Rn : e" 0, wi e" bi, i = 1, 2, . . . m}, x x T x bo nierówność wi e" bi jest równoważna nierówności (-wi)T d" -bi. T x x
Ustalmy p " Rn. Bedziemy rozpatrywać nastepujace zagadnienie:
(2) znalezć x0 " W takie, że pT x0 = min{ T : " W }. p x x Jest to zagadnienie minimalizacji funkcji liniowej p przy ogranicze- T x, niach zadanych nierównościami liniowymi, opisujacymi zbiór W .
(A) Zagadnienie planu produkcji. Producent produkuje n towarów. Do wytworzenia jednostki j-tego to- waru potrzeba aij jednostek i-tego środka produkcji, i d" m. Dostepnych jest
bi jednostek i-tego środka produkcji, dochód ze sprzedaży jednostki j-tego towaru wynosi cj. Określić ilości xj jednostek j-tego towaru, przy których zysk jest maksymalny. Przyjmujac
ł łł ł łł ai1 c1 ł śł ł śł ai2 c2 ł śł ł śł ł śł ł śł wi = , - = , p . . ł śł ł śł . . ł . ł ł . ł ain cn mamy rozwiazać zagadnienie (2), gdzie W jest opisane formu a (1). l
(B) Zagadnienie diety optymalnej. Mamy n produktów żywnościowych. Produkt j-ty zawiera m sk ladników odżywczych, w proporcjach a1j, a2j, . . . , amj (w stosunku do ca lkowitej masy). Przy odżywianiu należy dostarczyć co najmniej bi jednostek i-tego sk ladnika. Cena jednostki j-tego produktu wynosi cj. Dobrać xj jednostek każdego pro- duktu, aby zapewnić dostarczenie wystarczajacej ilości każdego ze sk ladników
(4) W = { " Rn : e" 0, A d" b}. x x x Każda nierówność wiT d" bi jest równoważna uk z x ladowi lożonemu z równania wiT + yi = bi i nierówności yi e" 0. x Zatem, wprowadzajac
x
(5) B = [A, Im], = " Rn+m, z
y
(6) Z = { " Rn+m : e" 0, B = b}, z z z oraz
p
(7) = " Rn+m, q
0 zagadnienie (2) można sformu równoważnie w nastepujacy sposób: lować
(8) znalezć z0 " Z takie, że T z0 = min{ T : " Z}. q q z z Dok lożony ladniej, jeśli z0 jest rozwiazaniem (8), wektor x0 z z pierw-
szych n wspó lrzednych wektora z0 jest rozwiazaniem (2), a jeśli x0 jest
rozwiazaniem (2), dopisujac wektor y0 = b - Ax0, otrzymujemy rozwiazanie
(8), zob. (5). Opiszemy procedure, pozwalajaca na wyjaśnienie, czy zagadnienie (8) ma
rozwiazanie i jeśli tak, na wskazanie pewnego rozwiazania tego zagadnienia.
Odwracalne (m m)- podmacierze macierzy B nazywać bedziemy ma-
cierzami bazowymi. 33 Każda macierz bazowa E wyznacza jednoznacznie wektor uE = E-1 b
spe lniajacy równanie EuE = b i niech zE " Rn+m bedzie wektorem, którego
wspó lrzednymi wektora uE, dla indeksów wska- lrzedne pokrywaja sie ze wspó
zujacych kolumny macierzy E, a pozosta wspó le lrzedne sa zerami.
Jeśli żaden z wektorów uE nie jest nieujemny, zbiór Z opisany formu a l (6) jest pusty, a zatem zagadnienie (8) nie ma rozwiazania.
W przeciwnym razie, spośród nieujemnych wektorów z wyznaczonych E przez macierze bazowe E, wybierzmy jako z0 wektor, dla którego liczba T z0 q jest minimalna. Wektor x0 utworzony z pierwszych n wspó lrzednych wektora z0 jest roz-
wiazaniem zagadnienia (2).
Uzasadnienie opisanej metody opiera sie na nastepujacej obserwacji.
Niech D bedzie (m k)-macierza rzedu mniejszego niż k, U = { " Rk : u
e" 0, D = b} i niech " Rk. u u v T Jeśli u0 " U spe warunek u0 = min{ T : " U}, to istnieje lnia v v u u T T " U takie, że u0 = i wektor ma co najmniej jedna wspó u v v u u lrzedna
zerowa.
Istotnie, z warunku rankD < k wynika istnienie wektora w " Rk takiego,
że
Dw = 0, w = 0.
Niech ut = u0 + tw, t " R.
Wówczas T T T
Dut = b, ut = u0 + t w. v v v Możemy zak że wszystkie wspó ladać, lrzedne u0 sa dodatnie (inaczej, przyj-
mujemy = u0) i wówczas, dla dostatecznie ma wartości |t|, ut e" 0. Dla u lych T T takich t, ut " U i z minimalności u0 wynika, że t w e" 0, niezależnie od v v T znaku t. To oznacza, że w = 0, a wiec dla dowolnego t, v
T T
Dut = b, ut = u0. v v
Ponieważ w = 0, zastepujac ewentualnie w przez wektor -w, możemy za lożyć,
że co najmniej jedna wspó lrzedna wektora w jest ujemna, skad
s = sup{t e" 0 : ut e" 0} < + ".
34 T T
Ponieważ us e" 0, us " U i us = u0, oraz co najmniej jedna wspó v v lrzedna
wektora us jest zerowa, możemy przyja ć = us. u 9. Liniowe jednorodne równania rożniczkowe o sta wspó lych l- czynnikach. W zbiorze C(R) funkcji ciag na prostej rzeczywistej określone jest lych
w naturalny sposób dzia dodawania funkcji (f + g)(x) = f(x) + g(x) lanie i mnożenie funkcji przez liczby (af)(x) = af(x). Bedziemy interpretować
funkcje jako wektory, a liczby jako skalary, przenoszac do C(R) pojecia kom-
binacji liniowej wektorów, liniowej niezależności wektorów i podprzestrzeni liniowej. Zbiór rozwiazań równania różniczkowego
(1) y = by + cy. jest przestrzenia liniowa V(b, c) w przestrzeni C(R). Pokażemy, że w każdej przestrzeni V(b, c) można wskazać baze z z dwóch wektorów. lożona
Twierdzenie. Przyjmijmy " = b2 + 4c. Wówczas nastepujaca para
funkcji y1(x), y2(x) jest baza przestrzeni rozwiazań równania (1):
(i) jeśli " = 0 i jest podwójnym pierwiastkiem równania x2 = bx + c, to y1(x) = ex, y2(x) = xex, (ii) jeśli " > 0 i 1, 2 sa różnymi pierwiastkami równania x2 = bx + c, 1 2 to y1(x) = e x, y2(x) = e x, " b 1 (iii) jeśli " < 0, ą = , = -", to y1(x) = eąx cos x, y2(x) = 2 2 eąx sin x. W każdym z przypadków (i) (iii) bezpośrednim rachunkiem spraw- dza sie, że wskazane funkcje sa rozwiazaniami równania (1).
Pozostaje upewnić sie, że każde rozwiazanie y = y(x)równania (1) zapi-
suje sie jednoznacznie w postaci y = a1y1 + a2y2, gdzie a1, a2 sa sta a lymi,
y1, y2 funkcjami wskazanymi w odpowiednim punkcie twierdzenia. Wyjaśnimy to w przypadku (iii) (pozosta przypadki uzasadnia sie po- le
dobnie). Za óżmy najpierw, że funkcja f " C(R) spe warunek l lnia
(2) f = bf + cf i f(0) = 0, f (0) = 0. Pokażemy, że (3) f(x) = 0 dla każdego x " R. 35 W tym celu rozpatrzmy (4) g(x) = f(x)e-ąx. Wówczas g (x) = (f (x) - 2ąf (x) + ą2f(x))e-ąx i ponieważ z (2), f = bf + cf = 2ąf + cf, mamy g (x) = (ą2 + c)f(x)e-ąx = -2f(x)e-ąx. Zatem, zob. (4) i (2), (5) g = -2g, g(0) = 0, g (0) = 0. Ponieważ [(g )2 + 2g2] = 2g g + 22g g, z (5) wynika, że ta pochodna jest stale zerem, a wiec (g )2 + 2g2 jest funkcja sta a i przyjmuje wartość l
zero. To oznacza w szczególności, że g jest funkcja zerowa i dostajemy (3), zob. (4). Niech teraz y = y(x) bedzie dowolnym rozwiazaniem (1). Ponieważ ma-
cierz
y1(0) y2(0) 1 0 =
y1(0) y2(0) ą jest odwracalna, istnieja jednoznacznie wyznaczone liczby a1, a2 takie, że
y1(0) y2(0) a1 y(0) = .
y1(0) y2(0) a2 y (0) Wówczas f = y - (a1y1 + a2y2) spe (2), zatem z (3), y = a1y1 + a2y2, lnia przy czym wspó lczynniki a1, a2 sa wyznaczone jednoznacznie. Uwaga. Zbiór rozwiazań równania
(6) y = ay jest przestrzenia jednowymiarowa.
Istotnie, wszystkie rozwiazania (6) sa postaci y(x) = ceax, gdzie c jest
sta a. l
10. Równania różnicowe drugiego rzedu i potegowanie macierzy
kwadratowych. Dla ciagu x0, x1, . . . przyjmijmy oznaczenie
(3) "2xn + ą"xn + xn = 0, x0 = a0, x1 = a1. Rozwiazanie równania (3) polega na znalezieniu wszystkich opisanych tym
równaniem ciagów o pierwszych dwóch wyrazach a0, a1.
Zgodnie z (1) i (2) zagadnienie (3) można opisać równoważnie w postaci rekurencyjnej (4) xn+2 = bxn+1 + cxn, x0 = a0, x1 = a1. co z kolei zapisuje sie w postaci macierzowej
xn+2 xn+1 b c (5) = A , A = , x0 = a0, x1 = a1. xn+1 xn 1 0 Ponieważ (5) oznacza, że dla n = 1, 2, . . .
xn+1 a1 b c (6) = An , A = , xn a0 1 0 rozwiazanie równania różnicowego (3) sprowadza sie do wyznaczenia dowol-
nej potegi (2 2)-macierzy.
Pokażemy jak to zrobić dla macierzy
b c (7) A = , gdzie (b - d)2 + 4c > 0. 1 d Warunek (b - d)2 + 4c > 0 zapewnia, że wielomian zmiennej (8) det(A - I2) = 2 - (b + d) + (bd - c) ma dwa różne pierwiastki rzeczywiste 1, 2. W tej sytuacji macierz
1 - d 2 - d (9) M = 1 1 jest odwracalna i mnożac odpowiednie macierze można sprawdzić, że
1 0 (10) AM = M . 0 2 Mnożac obie strony (10) z prawej strony przez M-1 dostajemy równość
37
1 0 A = M M-1, 0 2 z której można latwo wyprowadzić wzór na potegi macierzy A
n 0 1 (11) An = M M-1. 0 n 2 Przyk 1 (Ciag Fibonacciego). Znajdziemy rozwiazania równania lad
xn+2 = xn+1 + xn, x0 = 0, x1 = 1. Dla macierzy, zob. (4) i (5),
1 1 A = 1 0 wielomian, zob. (8), det(A - I2) = 2 - - 1 ma dwa różne pierwiastki " " 1- 5 1+ 5 1 = , 2 = . 2 2 Niech, zob. (9),
1 2 M = . 1 1 Wówczas
1 -2 1 M-1 = , 1-2 -1 1 a wiec, zgodnie z (6) i (11),
Yn = C(n) + I(n), C(n + 1) = łYn, I(n + 1) = ą(C(n + 1) - C(n)), gdzie ł " (0, 1) jest (sta a) sk lym) l lonnościa do oszczedzania i ą > 0 jest (sta
wspó lczynnikiem akceleracji. 38 Eliminujac C(n) i I(n) otrzymujemy równanie
Yn+2 = ł(1 + ą)Yn+1 - ąłYn. Przyjmujac, że wielkości Y0 = a0, Y1 = a1 sa znane, mamy zatem
Yn+1 a1 ł(1 + ą) -ął = An , A = . Yn a0 1 0 Z macierza A zwiazany jest wielomian (zob. (8))
ł(1 + ą) - -ął det = 2 - ł(1 + ą) + ął, 1 - który ma dwa różne pierwiastki rzeczywiste 1, 2 jeśli spe jest waru- lniony nek ł(1 + ą)2 - 4ą > 0. Wówczas potegi An sa opisane formu a (11), gdzie l
M jest macierza z (9) dla d = 0. Przyk 3. Interesujacy nas obiekt (np. wybrana ga a z gospodarki) lad l
może znajdować sie w jednym z czterech stanów, przy czym sytuacje w danej
chwili opisuje wektor ł łł p1 ł śł p2 ł śł p = ł śł , pi > 0, p1 + p2 + p3 + p4 = 1,
ł ł p3 p4 gdzie pi jest interpretowane jako prawdopodobieństwo tego, że obiekt jest w stanie i. Za óżmy, że po up sta jednostki czasu obiekt pozostaje w tym l lywie lej samym stanie z prawdopodobieństwem ą " [0, 1], lub przechodzi w inny stan 1-ą z prawdopodobieństwem , dla kazdego ze stanów innych niż wyjściowy. 3 Jeśli wiec w danej chwili stan obiektu opisany jest wektorem p, to po
up jednostki czasu, jego stan opisuje wektor lywie ł łł 1-ą 1-ą 1-ą ą 3 3 3 ł 1-ą 1-ą 1-ą śł ą ł śł 3 3 3 = P p , gdzie P = ł śł. q 1-ą 1-ą 1-ą ł ł ą 3 3 3 1-ą 1-ą 1-ą ą 3 3 3 Interesuje nas jakie jest prawdopodobieństwo tego, że obiekt, który w chwili poczatkowej by w stanie 1 z prawdopodobieństwem 1, po up n l lywie
jednostek czasu bedzie w tym samym stanie. Chcemy zatem wyznaczyć, dla
39 n n n = 1, 2, . . ., pierwsza wspó e1, lrzedna wektora P czyli wyraz macierzy P
stojacy w pierwszym wierszu i pierwszej kolumnie.
Pomijajac oczywisty przypadek ą = 1, możemy zapisać
ł łł 1 1 1 ł śł 1 1 1 ł śł 1-ą 3ą (12) P = Q , Q = ł śł , = . 3 1-ą ł ł 1 1 1 1 1 1 Mnożac macierz Q przez siebie, latwo dostrzec, że kolejne potegi Q maja
postać ł łł xn yn yn yn ł yn xn yn yn śł ł śł (13) Qn = ł śł, ł ł yn yn xn yn yn yn yn xn przy czym x0 = 1, y0 = 0 oraz xn+1 = xn + 3yn, yn+1 = xn + ( + 2)yn, a wiec
xn+1 xn 3 (14) = A , A = , yn+1 yn 1 + 2 Stad, dla n = 1, 2, . . .,
xn 1 (15) = An . yn 0 Macierz A zdefiniowana w (14) spe warunek (7), przy czym pierwiastkami lnia
- 3 wielomianu det , zob. (8), sa 1 = - 1 i 2 = + 3. 1 ( + 2) - Dla macierzy opisanej formu a (9) mamy wiec l
ł śł 1 3 ł śł = , = ł śł x y ł ł 3 1 1 (a) Znalezć CA. (b) Znalezć AB - BA. (c) Znalezć C(B znalezć CB i sprawdzić, że C(B = (CB) x); x) x. (d) Znalezć D y. 4. Czy dla dowolnych (2 2)-macierzy A i B spe jest równanie lnione (A - B)(A + B) = A2 - B2? 42 ZADANIA II 1. Sprowadzić nastepujace macierze operacjami elementarnymi na wier-
2. Znalezć rzut ortogonalny wektora b = 2 " R3 na przestrzeń ł ł 3
V " R3, gdzie ł łł 1 ł śł (A) V = Lin( = -2 , a), a ł ł -2
(B) V = { " R3 : T = 0}, T = (2, -1, 5). x a x a ł łł ł łł 1 3 1 ł śł ł śł 1 2 2 ł śł ł śł
3. Niech A = ł śł , b = ł śł. ł ł ł ł 0 1 2 1 1 1
Znalezć min{ b - A : " R2}. x x 4. Wartościom 1, 4, 8, 11 wielkości t odpowiadaja wartości 1, 2, 4, 5 wielkości y. Znalezć m i c takie, że funkcja y = mt + c minimalizuje odchylenie kwa- dratowe od obserwowanych pomiarów. 5. Opisać przestrzeń V rozpieta na wektorach
2 1 1 1 0 1 1 1 1 1 2 3 1 2 ł śł ł śł ł śł ł śł ł 4 1 0 , , 2 1 2 , 1 2 2 , 0 1 2 . ł ł ł ł ł ł ł 3 4 -2 2 1 1 1 2 1 3 1 0 0 1 4. (A) Uzasadnić, że jeśli wszystkie wyrazy (33)-macierzy A sa liczbami ca lkowita. lkowitymi, to wyznacznik det A jest liczba ca
(B) Uzasadnić, że jeśli wszystkie wyrazy (4 4)-macierzy A sa liczbami ca lkowitymi i det A = 1, to wszystkie wyrazy macierzy odwrotnej A-1 sa liczbami ca lkowitymi. 48 ZADANIA VII. 1. W modelu Leontiewa dla trzech ga ezi gospodarki dana jest macierz l
przep miedzyga eziowych: lywów l
ł łł 3 0 2 1 6 ł śł ł śł 0 6 2 4 12 ł śł . ł ł 1 6 0 1 8 (a) O ile powinny wzrosna ć produkcje globalne xi, jeśli produkty końcowe maja wzrosna ć o "d1 = 0, "d2 = 1, "d3 = 3? (b) O ile wzrosna produkty końcowe, jeśli produkcja globalna każdej ga ezi l
podwoi sie?
2. W modelu Leontiewa dla trzech ga ezi gospodarki dana jest macierz l
przep miedzyga eziowych: lywów l
ł łł 2 2 0 1 5 ł śł ł śł 0 6 1 3 10 ł śł . ł ł 1 2 1 1 5 (a) Ustalić plan produkcji globalnej tak, aby pierwsza ga a z wytwarza l la produkt końcowy o wartości 2, druga o wartości 3, a trzecia o wartości 6. (b) O ile wzrosna produkty końcowe, jeśli produkty globalne wzrosna o "x1 = 1, "x2 = 1, "x3 = 2? 49 ODPOWIEDZI I
ł śł ł śł 7 28 4 8 ł śł ł śł (c) B = ; C(B = ł śł; CB = ł śł. x x) ł ł ł ł 13 43 7 12 47 5 14 ł łł 16 ł śł 8 ł śł (d) D = ł śł. y ł -1 ł 14 4. (A - B)(A + B) = A2 + AB - BA - B2, wiec równanie nie jest na ogó l
spe ((2 2)-macierze A, B z zadań 1,2 i 3 pokazuja, że AB może sie lnione
różnić od BA). 50 ODPOWIEDZI II 1. Postać schodkowa macierzy nie jest wyznaczona jednoznacznie, niezmiene sa jedynie numery kolumn, w których wystepuja kolejne schodki. Dla ma-
cierzy z (A) sa to kolumny o numerach 1, 2; z (B) 1, 2; z (C) 1, 2, 3, 4; z (D) 1, 2, 4, 5; z (E) 1, 2, 4. 2. Zapis zbioru rozwiazań nie jest jednoznaczny, niezmiena jest liczba para-
metrów (zmiennych niezależnych). Podane niżej rozwiazania sa otrzymane
w wyniku zastosowania standardowej metody opisanej w tekście (przedsta- wienie rozwiazania jako sumy wektorów ma na celu u latwienie identyfikacji poszczególnych elementów tego rozwiazania).
(B) Wektor b w (ii) jest różnica dwóch ostatnich kolumn macierzy A, wiec bez redukcji do postaci schodkowej widać, że uk jest niesprzeczny lad
(ma rozwiazanie x1 = x2 = x3 = 0, x4 = 1, x5 = -1), a jego wszystkie
rozwiazania można zapisać (jako sume tego rozwiazania i dowolnego wektora
z N(A)) w postaci ł łł ł łł ł łł 0 -2 -8 ł śł ł śł ł śł ł śł ł śł ł śł 0 0 3 ł śł ł śł ł śł ł śł ł śł ł śł (ii) = 0 + s 1 + t 0 . x ł śł ł śł ł śł ł śł ł śł ł śł 1 0 ł ł ł ł ł -2 ł -1 0 4 W celu rozwiazania (i) (oraz (ii), jeśli ktoś nie zauważy opisanego wyżej l
rozwiazania) trzeba zredukować macierz A z dopisana kolumna wyrazów wol-
nych b z (i) (oraz kolumna z (ii)). Uk z (i) jest sprzeczny, a standardowe b lad 52 rozwiazanie uk z (ii) (otrzymane jako suma rozwiazania dla x3 = x5 = 0 ladu
ł łł ł łł -3 3 -1 -3 2 2 2 ł śł 2 -2 -1 ł śł ł śł 1 1 X = BA-1 = 2 -3 2 2 , Y = A-1C = ł śł. ł ł 5 5 ł ł 2 3 4 1 1 1 1 2 -2 -1 1 4. Dodajac do obu stron -1BX dostajemy AX - BX = C, czyli (A - 2 2 1 1 B)X = C. Ponieważ A - B jest odwracalna macierza z zadania 1(C), 2 2 1 1 mnożac z lewej strony przez (A - B)-1 dostajemy X = (A - B)-1C, czyli 2 2 ł łł ł łł ł łł 4 -1 -1 -1 a b 4a - d - c 4b - c ł śł ł śł ł śł -1 4 -1 -1 0 c -a - d - c -b + 4c ł śł ł śł ł śł 1 1 X = ł śł ł śł = ł śł. 5 5 ł -1 -1 4 -1 d 0 ł ł ł ł -a + 4d - c -b - c ł -1 -1 -1 4 c 0 -a - d + 4c -b - c
-3 2 5. (A) A-1 = . 2 -1 (B) Mnożac drugie równanie z prawej strony przez A i odejmujac stronami
5. Warunek P ( - = 0 daje (po wymnożeniu obu stron przez 11) uk x) x lad
równań Q = 0, gdzie x ł łł -9 1 4 1 ł śł 1 -5 2 -5 ł śł Q = ł śł jest macierza rzedu 2.
ł ł 4 2 -3 2 1 -5 2 -5 Wiersze Q można interpretować jako wektory prostopad do V . Ta obser- le wacja prowadzi do innej, bardziej bezpośredniej, metody znajdowania uk ladu równań opisujacego V (zob. 5.4 (10)).
Wektory prostopad do V spe dwa warunki: T = 0 i T = 0. u le lniaja a1 u a2 u
1 0 2 1 0 Rozwiazujac uk równań = lad x
0 1 0 -1 0 dostajemy dwa liniowo niezależne wektory prostopad do V . Dla u1, u2 le macierzy B = [ u1, u2]
-2 0 1 0 BT = -1 1 0 1 jest macierza innego jednorodnego uk równań, który również opisuje V . ladu 55 ODPOWIEDZI VI 1. Wartości wyznaczników: 4, -2, -24, 2, 2. 2. det A = 23, det B = -6, wiec z formu Cauchy ego dostajemy: ly