Zakres zagadnień Algebra z geometrią 1 Trochę filozofii o wektorach Mnożenie macierzy, macierz odwrotna, metoda Gaussa-Jordana, 2 Graficzne wyobrażenie wektorów dekompozycja LU 3 Wektory w przyrodzie i w technice 4 Kolor jako trójwymiarowy wektor 5 Podstawowe działania na wektorach Adam Dąbrowski 6 Mnożenie macierzy Politechnika Poznańska 7 Macierz odwrotna Wydział Informatyki Katedra Sterowania i Inżynierii Systemów 8 Eliminacja metodą Gaussa powtórka Pracownia Układów Elektronicznych i Przetwarzania Sygnałów 9 Redukcja macierzy według Gaussa-Jordana 10 Obliczanie macierzy odwrotnej metodą Gaussa-Jordana 7 listopada 2012 11 Dekompozycja LU 12 Mały oddech pojęcia: MAC, flop i flops 13 Równoważne układy równań operacje elementarne 14 Metoda eliminacji według Gaussa dla zaawansowanych 15 Dekompozycja LU dla zaawansowanych Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 1 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 2 / 111 Trochę filozofii o wektorach Co to za wektor? Ą# ń# 100 ó# 100Ą# ó# Ą# ó# Ą# Ł# 1 Ś# 1 Na razie nie wiadomo! skrócony zapis jeszcze o tym nie mówi, należy bowiem określić bazowe wektory składowe e1, e2, e3, e4: niech e1 oznacza naukowiec w skali od -? do ? niech e2 oznacza inżynier w skali od -? do ? niech e3 oznacza grywający na fortepianie w skali od -? do ? niech e4 oznacza pisujący wiersze w skali od -? do ? Teraz już wszystko jest jasne ten wektor to ja! Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 3 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 4 / 111 Dowód? dla e3 Dowód? dla e4 Od algebry wierszyk prędki do studenta i studentki Studencie, Studentko, żyje się tylko raz więc choć nie masz czasu (bo żyjesz zbyt prędko), to dla mnie algebry, poświęcaj wciąż swój czas! Przekonaj się o tym, że jestem ciekawa, i odsuń od siebie nęcące głupoty. Tam czeka Cię nuda, a ze mną zabawa w poranki, wieczory, w niedziele, w soboty. Studentko, studencie, przekonaj się o tym jakże pięknie w liczb jest zespolonych ciele w poranki, wieczory, w niedziele, w soboty. w poranki, wieczory, w soboty, w niedziele. Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 5 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 6 / 111 Co to za wektor? Co to za wektor? Ą# ń# 100 ó# 100Ą# ó# Ą# ó# Ą# ó# Ą# 1 Ą# ń# ó# Ą# ó# Ą# 100 1 ó# Ą# ó# ó# Ą# 100Ą# ó# Ą# ? ó# Ą# ó# Ą# ó# Ą# Ł# 1 Ś# ? Ł# Ś# 1 ? Tak więc ten wektor to ja. Ale to jest tylko uproszczony model mnie Tak więc ten wektor to ja. Ale to jest tylko uproszczony model mnie rzut na podprzestrzeń czterowymiarową: rzut na podprzestrzeń czterowymiarową: e1 oznacza naukowiec w skali od -? do ? e1 oznacza naukowiec w skali od -? do ? e2 oznacza inżynier w skali od -? do ? e2 oznacza inżynier w skali od -? do ? e3 oznacza grywający na fortepianie w skali od -? do ? e3 oznacza grywający na fortepianie w skali od -? do ? e4 oznacza pisujący wiersze w skali od -? do ? e4 oznacza pisujący wiersze w skali od -? do ? Prawidłowy model powinien być uzupełniony o szereg dlaszych składowych! Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 7 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 8 / 111 Więc czym są wektory? Skrócony zapis wektorów (Przeczytać i zapomnieć lub wcale nie czytać!): ścisła odpowiedz, która Ponieważ przy stałej bazie e1, e2, . . . , en w zapisie Ą# ń# Ą# ń# jednak niczego normalnym ludziom (tzn. tym, którzy nie są fanatykami f1 e1 matematyki) nie wyjaśnia, to taka, że wektory są elementami grupy ó# Ą# ó# Ą#
f2 e2 ó# Ą# ó# Ą# abelowej V, która nieprecyzyjnie bywa nazywana przestrzenią liniową nad f = e1 e1 en ó# . Ą# = f1 f2 fn ó# . Ą# ó# Ą# ó# Ą# . . Ł# . Ś# Ł# . Ś# ciałem F , choć naprawdę przestrzenią liniową nad ciałem F jest zestaw fn en (V, F , +, ). Wezmy pod uwagę tzw. bazę (to pojęcie będzie wyjaśnione pózniej) wektor f jest jednoznacznie określony przez zestaw liczb np. rzeczywistych e1, e2, . . . , en pewnej przestrzeni liniowej V nad ciałem F o elementach f f1, f2, . . . , fn, nazywanych składowymi (lub elementami) wektora f, to (poniżej z indeksami). Każdy wektor f tej przestrzeni można wyrazić jako często (choć nie ściśle) wektory utożsamiamy z zestawami ich składowych i zapisujemy f = f1e1 + f2e2 + + fnen , Ą# ń# f1 ó# Ą# co symbolicznie zapisujemy także w następujący sposób:
f2 ó# Ą# Ą# ń# Ą# ń# ó# Ą# fk = lub fw = f1 f2 fn . ó# Ą# f1 e1 . Ł# . Ś# ó# Ą# ó# Ą#
f2 e2 ó# Ą# ó# Ą# fn f = e1 e1 en ó# . Ą# = f1 f2 fn ó# . Ą# ó# Ą# ó# Ą# . . Ł# . Ś# Ł# . Ś# Mówimy w pierwszym i w drugim przypadku odpowiednio o: T fn en wektorze kolumnowym fk i wektorze wierszowym fw = fk . Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 9 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 10 / 111 Wektory na prostej, na płaszczyznie i w przestrzeni ... Graficzne wyobrażenie wektorów Rozważmy kartezjańskie układy współrzędnych na prostej (oś liczbową), Diabeł jest pojęciem abstrakcyjnym, ale na co dzień wygodnie jest na płaszczyznie i w otaczającej nas przestrzeni. Jako tzw. bazy naturalne używać jakiegoś jego wyobrażenia, np. przyjmijmy odpowiednio e =[1] na osi liczbowej
1 0 e1 = oraz e2 = 0 1 Podobnie jest z wektorami. Wyobrażamy je sobie jako strzałki. na płaszczyznie i Ą# ń# Ą# ń# Ą# ń# 1 0 0 ó# Ą# ó# Ą# ó# Ą# e1 = 0 , e2 = 1 oraz e3 = 0 Ł# Ś# Ł# Ś# Ł# Ś# 0 0 1 w otaczającej nas przestrzeni trójwymiarowej (3D). Wniosek Wektory (o elementach rzeczywistych) to początek układu współrzędnych (0D), punkty prostej (1D), płaszczyzny (2D), przestrzeni (3D, 4D itd.) Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 11 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 12 / 111 Wektory w przyrodzie i w technice Kody kreskowe i ich odczytywanie Popularne kody kreskowe W przyrodzie wiele zjawisk wymaga opisu za pomocą wielkości wektorowych. Wektorami są np.: prędkość przyspieszenie natężenie pola elektrycznego natężenie pola magnetycznego można odczytywać za pomocą kamer skanujących linie indukcja magnetyczna i wiele innych. W technice szereg zagadnień rozwiązuje się stosując wektory: wektorami są np. kody kreskowe złożone z liczb (cyfr dziesiętnych) wektorami są sygnały tworzone przez kamery skanujące linie takie kamery mogą służyć do odczytywania kodów kreskowych. Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 13 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 14 / 111 Kamery skanujące linie Kolor jako wektor Kamera skanująca linie Kolorowa kamera skanująca linie może mieć trzy czujniki liniowe rejestrujące trzy składowe koloru: R składową czerwoną, zawiera liniowy czujnik CMOS lub CCD, który rejestruje wektor G składową zieloną i B składową niebieską. Kolor jest wektorem! jaskrawości obserwowanej powierzchni wzdłuż określonej linii Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 15 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 16 / 111 Kolor jako wektor Obrazy składowe i histogramy R, G, B obrazu kolorowego 5000 4500 Kolor (barwa) jest punktem (wektorem) w trójwymiarowej przestrzeni1 4000 3500 barw . Na przykład, stosując współrzędne (R, G , B) i związaną z nimi 3000 2500 bazę r, g, b, kolor c jest określony zależnością 2000 Ą# ń# 1500 1000 R 500 ó# Ą# 0 c = Rr + G g + Bb =[ r g b ] G 0 50 100 150 200 250 300 Ł# Ś# 6000 B 5000 4000 3000 2000 1000 0 0 50 100 150 200 250 300 6000 5000 4000 3000 2000 1 1000 Ponieważ obszar, w którym są określone barwy jest kostką, to nie jest przestrzenią w 0 ścisłym znaczeniu. 0 50 100 150 200 250 300 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 17 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 18 / 111 Podstawowe działania na wektorach Macierz jako przetwornik wektora w wektor a b Rozważmy stałą oraz wektory
A Ą# ń# Ą# ń# v1 w1 ó# Ą# ó# Ą# v2 w2 ó# Ą# ó# Ą# ó# Ą# ó# Ą# v = i w = . . ó# Ą# ó# Ą# Mówiąc językiem technicznym macierz A przetwarza wektor a wwektor b . . Ł# . Ś# Ł# . Ś# vm wm b = Aa . Wektory te mogą nawet leżeć w różnych przestrzeniach. Jeśli macierz ma Iloczynem wektora przez stałą i sumą obu wektorów są odpowiednio wymiar m n, to przekształca wektor n-wymiarowy w m-wymiarowy. wektory Ą# ń# Ą# ń# Macierz, która niczego nie robi, czyli zwraca wektor a, nazywa się v1 v1 + w1 ó# Ą# ó# Ą# macierzą jednostkową I v2 v2 + w2 ó# Ą# ó# Ą# Ą# ń# ó# Ą# ó# Ą# v = i v + w = . . ó# Ą# ó# Ą# 1 0 0 . . Ł# . Ś# Ł# . Ś# ó# 0 1 0Ą# ó# Ą# vm vm + wm ó# I = . . .Ą# . ó# . . . .Ą# . Ł#. . .Ś# 0 0 1 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 19 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 20 / 111 Macierz jako przetwornik wektora w wektor Czy a = b? Ą# ń# 3
Niech a = e1 e2 e3 ó#2Ą#. Rozpatrzmy teraz trzy wektory f1, f2, f3 Ł# Ś# a b
5 A Ą# ń# 3
i wyznaczmy b = f1 f2 f3 ó#2Ą#. Wektor b może być inny niż wektor a, Ł# Ś# 5 Macierz jest liniowym przetwornikiem wektora w wektor, tzn. spełniona czyli b = a, choć mają te same współrzędne.
jest tzw. zasada superpozycji. Wniosek Zasada superpozycji Jedynie wówczas, gdy wszystkie rozpatrywane wektory są wyrażone za Odpowiedz na superpozycję wymuszeń jest taką samą superpozycją pomocą tych samych wektorów (tej samej bazy), można stosować odpowiedzi na każde z tych wymuszeń z osobna: skrócony zapis, tzn. zadowolić się zapisem Ą# ń# Ą# ń# 3 3
b1 = Aa1 i b2 = Aa2 ! b1 + b2 = A(a1 + a2) ó# a = 2Ą# zamiast a = e1 e2 e3 ó#2Ą# Ł# Ś# Ł# Ś# 5 5 b = Aa ! cb = A(ca) (przy skróconym zapisie opuszczono indeks k , pisząc a zamiast ak) Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 21 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 22 / 111 Inne współrzędne wektora b Inne współrzędne wektora b, c. d. Ą# ń# Ą# ń# 3 3
b = Aa Niech a = e1 e2 e3 ó#2Ą# a b = f1 f2 f3 ó#2Ą# załóżmy, że Ł# Ś# Ł# Ś# 5 5 przy czym Ą# ń# Ą# ń# wektory f1, f2, f3 można wyrazić za pomocą wektorów e1, e2, e3, tzn. Ą# ń# Ą# ń# Ą# ń# 3 a11 a12 a13 ó# ó# a11 a12 a13 ó# ó# ó# a = 2Ą# oraz A = a21 a22 a23Ą# Ł# Ś# Ł# Ś# f1 = e1 e2 e3 a21Ą#, f2 = e1 e2 e3 a22Ą#, f3 = e1 e2 e3 a23Ą# Ł# Ś# Ł# Ś# Ł# Ś# 5 a31 a32 a33 a31 a32 a33 Zatem wówczas Ą# ń# Ą# ń# Ą# ń# Ą# ń# Ą# ń# Ą#Ą# ń#Ą# ń#Ą# ń#ń#Ą# ń# Ą# ń#Ą# ń# ! a11 a12 a13 3 a11 a12 a13 a11 a12 a13 3 a11 a12 a13 3 ó#ó# ó# ó# ó# ó# Ą# b = a21 a22 a23Ą# ó#2Ą# = 3 a21Ą# + 2 a22Ą# + 5 a23Ą# Ł# Ś# Ł# Ś# Ł# Ś# Ł# Ś# Ł# Ś# b = e1 e2 e3 ó#Ł#a21Ą#ó#a22Ą#ó#a23Ą#Ą#ó#2Ą# = e1 e2 e3 ó#a21 a22 a23Ą#ó#2Ą# Ś#Ł# Ś#Ł# Ś#Ś#Ł# Ś# Ł# Ś#Ł# Ś# Ł# a31 a32 a33 5 a31 a32 a33 a31 a32 ! a33 5 a31 a32 a33 5 Ą# ń# a11 a12 a13 Wniosek ó# i stosując skrócony zapis b = Aa przy czym A = a21 a22 a23Ą# Wektor b jest kombinacją liniową kolumn macierzy A, wyznaczoną przez Ł# Ś# a31 a32 a33 kolejne elementy wektora a. Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 23 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 24 / 111 Iloczyn BA jako złożenie przekształceń liniowych Iloczyn AB jako zestaw przekształceń wektorów Niech Niech b = Aa i c = Bb c = Ab wówczas Rozważmy teraz zestaw p wektorów b1, b2, . . . , bp, za pomocą których c = B(Aa) =(BA)a = Ca można utworzyć wektory przy czym c1 = Ab1 , c2 = Ab2 , . . . , cp = Abp C = BA co zapisujemy jako Wniosek
Iloczyn macierzy BA to złożenie przekształceń liniowych, c1 c2 cp = A b1 b2 bp reprezentowanych przez te macierze. Złożenie przekształceń polega na tym, że na wynik przekształcenia lub dokonanego za pomocą macierzy A działamy macierzą B. C = AB Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 25 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 26 / 111 Mnożenie macierzy przykład Mnożenie macierzy metodą wierszowo-kolumnową Uwaga Uwaga Element w k-tym wierszu i l-tej kolumnie wyniku mnożenia macierzy jest Warunkiem wykonalności mnożenia macierzy jest to, że pierwsza musi iloczynem skalarnym k-tego wiersza pierwszej macierzy i l-tej kolumny mieć tyle kolumn ile druga ma wierszy. drugiej macierzy, czyli n
Macierz, która jest wynikiem mnożenia, ma tyle wierszy ile ma ich ckl = akbl pierwsza macierz i tyle kolumn ile ma ich druga. =1 np. c32 = 7 4 + 3 0 + 0 5 = 28 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 27 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 28 / 111 Mnożenie macierzy metodą kolumnową Mnożenie macierzy metodą wierszową Uwaga Uwaga k-ta kolumna wyniku mnożenia macierzy jest kombinacją liniową kolumn k-ty wiersz wyniku mnożenia macierzy jest kombinacją liniową wierszy pierwszej macierzy, wyznaczoną przez k-tą kolumnę drugiej macierzy. drugiej macierzy, wyznaczoną przez k-ty wiersz pierwszej macierzy. Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 29 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 30 / 111 Mnożenie macierzy metodą kolumnowo-wierszową Mnożenie macierzy blokowych Uwaga Uwaga n
Mnożone macierze mogą być podzielone na bloki, które mnożymy tak jak wynik mnożenia = -ta kol. I. macierzy -ty wiersz II. macierzy elementy metodą wierszowo-kolumnową. Podział musi być dokonany tak, =1 Kolumny każdej z sumowanych macierzy są wielokrotnością pewnego że liczby kolumn kolejnych (kolumnowo) bloków pierwszej macierzy muszą wektora kolumnowego. Podobie wiersze każdej z nich są wielokrotnością być równe liczbom wierszy kolejnych (wierszowo) bloków macierzy drugiej. pewnego wektora wierszowego. Te macierze mają jednowymiarową Podział na bloki macierzy wynikowej odpowiada podziałowi wierszowemu przestrzeń kolumnową i jednowymiarową przestrzeń wierszową. macierzy pierwszej i podziałowi kolumnowemu macierzy drugiej. Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 31 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 32 / 111 Macierz odwrotna Macierz odwrotna Definicja macierzy odwrotnej Definicja macierzy odwrotnej Macierzą odwrotną A-1 macierzy kwadratowej A stopnia n nazywamy Macierzą odwrotną A-1 macierzy kwadratowej A stopnia n nazywamy macierz spełniającą warunek macierz spełniającą warunek AA-1 = A-1A = In . AA-1 = A-1A = In . Przykład Przykład Istotnie
1 -2 1 -3 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 33 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 34 / 111 Macierz odwrotna Macierz odwrotna Definicja macierzy odwrotnej Definicja macierzy odwrotnej Macierzą odwrotną A-1 macierzy kwadratowej A stopnia n nazywamy Macierzą odwrotną A-1 macierzy kwadratowej A stopnia n nazywamy macierz spełniającą warunek macierz spełniającą warunek AA-1 = A-1A = In . AA-1 = A-1A = In . Przykład Przykład Istotnie Istotnie
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 35 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 36 / 111 Macierz odwrotna Macierz odwrotna Definicja macierzy odwrotnej Definicja macierzy odwrotnej Macierzą odwrotną A-1 macierzy kwadratowej A stopnia n nazywamy Macierzą odwrotną A-1 macierzy kwadratowej A stopnia n nazywamy macierz spełniającą warunek macierz spełniającą warunek AA-1 = A-1A = In . AA-1 = A-1A = In . Przykład Przykład Istotnie Istotnie
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 37 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 38 / 111 Macierz odwrotna Macierz odwrotna Definicja macierzy odwrotnej Definicja macierzy odwrotnej Macierzą odwrotną A-1 macierzy kwadratowej A stopnia n nazywamy Macierzą odwrotną A-1 macierzy kwadratowej A stopnia n nazywamy macierz spełniającą warunek macierz spełniającą warunek AA-1 = A-1A = In . AA-1 = A-1A = In . Przykład Przykład Istotnie Istotnie
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 39 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 40 / 111 Macierz odwrotna Macierz odwrotna Definicja macierzy odwrotnej Definicja macierzy odwrotnej Macierzą odwrotną A-1 macierzy kwadratowej A stopnia n nazywamy Macierzą odwrotną A-1 macierzy kwadratowej A stopnia n nazywamy macierz spełniającą warunek macierz spełniającą warunek AA-1 = A-1A = In . AA-1 = A-1A = In . Przykład Przykład Istotnie Istotnie
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 41 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 42 / 111 Macierz odwrotna Macierz odwrotna Definicja macierzy odwrotnej Definicja macierzy odwrotnej Macierzą odwrotną A-1 macierzy kwadratowej A stopnia n nazywamy Macierzą odwrotną A-1 macierzy kwadratowej A stopnia n nazywamy macierz spełniającą warunek macierz spełniającą warunek AA-1 = A-1A = In . AA-1 = A-1A = In . Przykład Przykład
3 -6 3 -6 Czy istnieje macierz odwrotna do macierzy ? Czy istnieje macierz odwrotna do macierzy ? NIE! 1 -2 1 -2
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 43 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 44 / 111 Macierz odwrotna Macierz odwrotna Definicja macierzy odwrotnej Definicja macierzy odwrotnej Macierzą odwrotną A-1 macierzy kwadratowej A stopnia n nazywamy Macierzą odwrotną A-1 macierzy kwadratowej A stopnia n nazywamy macierz spełniającą warunek macierz spełniającą warunek AA-1 = A-1A = In . AA-1 = A-1A = In . Twierdzenie Twierdzenie Macierz odwrotna A-1 istnieje wtedy i tylko wtedy, gdy macierz Macierz odwrotna A-1 istnieje wtedy i tylko wtedy, gdy macierz kwadratowa A jest nieosobliwa (czyli np. nie istnieje niezerowy wektor x kwadratowa A jest nieosobliwa, czyli są spełnione następujące równoważne spełniający równanie Ax = 0). warunki: kolumny macierzy A są liniowo niezależne Dowód wiersze macierzy A są liniowo niezależne Konieczność: nie istnieje niezerowy wektor x spełniający równanie Ax = 0 Ax = 0 ! A-1Ax = A-10 ! x = 0 . det A = 0.
Dostateczność: dowód poprzez konstrukcję macierzy odwrotnej. Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 45 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 46 / 111 Macierz odwrotna Eliminacja metodą Gaussa Definicja macierzy odwrotnej Macierzą odwrotną A-1 macierzy kwadratowej A stopnia n nazywamy macierz spełniającą warunek AA-1 = A-1A = In . Twierdzenie Macierz odwrotna A-1 istnieje wtedy i tylko wtedy, gdy macierz kwadratowa A jest nieosobliwa (czyli np. det A = 0).
Dowód Konieczność: det A det A-1 = det(AA-1) =det In = 1 , zatem det A = 0.
Dostateczność: dowód poprzez konstrukcję macierzy odwrotnej. Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 47 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 48 / 111 Eliminacja metodą Gaussa-Jordana Eliminacja metodą Gaussa-Jordana, c. d. Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 49 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 50 / 111 Camille Jordan Eliminacja metodą Gaussa-Jordana, dwa równania Marie Ennemond Camille Jordan urodził się 5. stycznia 1838 r. a zmarł 22. stycznia 1922 r. Z wykształcenia był inżynierem, choć zasłynął jako francuski matematyk. Jest znany zwłaszcza z osiągnięć w dziedzinie algebry abstrakcyjnej i teorii miary. Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 51 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 52 / 111 Eliminacja metodą Gaussa-Jordana, dwa równania Eliminacja metodą Gaussa-Jordana, dwa równania Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 53 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 54 / 111 Eliminacja metodą Gaussa-Jordana, dwa równania Eliminacja metodą Gaussa-Jordana, dwa równania Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 55 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 56 / 111 Eliminacja metodą Gaussa-Jordana, dwa równania Eliminacja metodą Gaussa-Jordana, dwa równania Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 57 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 58 / 111 Obliczanie macierzy odwrotnej metodą Gaussa-Jordana Przypomnienie przykładu eliminacji według Gaussa Ą# ń# Ą# ń# Ą# ń# Ą# ń# 1 2 1 1 2 1 x1 x2 x3 1 0 0 ó# ó# ó# A = 3 8 1Ą# Ł# Ś# AA-1 = I np. 3 8 1Ą# ó#y1 y2 y3Ą# = 0 1 0Ą# Ł# Ś# Ł# Ś# Ł# Ś# 0 4 1 0 4 1 z1 z2 z3 0 0 1 Ą# ń# Ą# ń# Ą# ń# Ą# ń# 1 0 0 1 0 0 1 2 1 1 2 1 Zatem, stosując procedurę eliminacji metodą Gaussa-Jordana, piszemy ó# ó# E32E21A = 0 1 0Ą# ó# 1 0Ą# ó#3 8 1Ą# = 0 2 -2Ą# = U Ł# Ś# Ł#-3 Ś# Ł# Ś# Ł# Ś# Ą# ń# Ą# ń# Ą# ń# 1 2 1 1 0 0 1 2 1 1 0 0 1 2 1 1 0 0 0 -2 1 0 0 1 0 4 1 0 0 5 ó# ó# ó# 3 8 1 0 1 0Ą# 0 2 -2 -3 1 0Ą# 0 2 -2 -3 1 0Ą# Ł# Ś# Ł# Ś# Ł# Ś# Uwaga: Macierz U jest górnotrójkątna. 0 4 1 0 0 1 0 4 1 0 0 1 0 0 5 6 -2 1 Uwaga: 1, 2, 5 to elementy osiowe eliminacji według Gaussa. Ą# ń# Ą# ń# Ą# ń# Ą# ń# Ą# ń# Ą# ń# 1 2 1 1 0 0 1 2 0 -0.2 0.4 -0.2 1 0 0 0.4 0.2 -0.6 1 0 0 1 0 0 1 0 0 ó# Ą# Ą# Ą# ó# ó# 0 1 Ś# Ł# Ś# Ł# Ł# -1 -1.5 0.5 0 ó#0 1 0 -0.3 0.1 0.2 ó#0 1 0 -0.3 0.1 0.2 Ś# E32E21 = 0 1 0Ą# ó# 1 0Ą# = 1 0Ą# Ł# Ś# Ł#-3 Ś# Ł#-3 Ś# 0 0 1 1.2 -0.4 0.2 0 0 1 1.2 -0.4 0.2 0 0 1 1.2 -0.4 0.2 0 -2 1 0 0 1 6 -2 1 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 59 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 60 / 111 Przypomnienie przykładu eliminacji według Gaussa Przypomnienie przykładu eliminacji według Gaussa Ą# ń# Ą# ń# 1 2 1 1 2 1 ó# ó# A = 3 8 1Ą# A = 3 8 1Ą# Ł# Ś# Ł# Ś# 0 4 1 0 4 1 Ą# ń# Ą# ń# Ą# ń# Ą# ń# Ą# ń# Ą# ń# Ą# ń# Ą# ń# 1 0 0 1 0 0 1 2 1 1 2 1 1 0 0 1 0 0 1 2 1 1 2 1 ó# ó# ó# ó# E32E21A = 0 1 0Ą# ó# 1 0Ą# ó#3 8 1Ą# = 0 2 -2Ą# = U E32E21A = 0 1 0Ą# ó# 1 0Ą# ó#3 8 1Ą# = 0 2 -2Ą# = U Ł# Ś# Ł#-3 Ś# Ł# Ś# Ł# Ś# Ł# Ś# Ł#-3 Ś# Ł# Ś# Ł# Ś# 0 -2 1 0 0 1 0 4 1 0 0 5 0 -2 1 0 0 1 0 4 1 0 0 5 Uwaga: Macierz U jest górnotrójkątna. Uwaga: Macierz U jest górnotrójkątna. Uwaga: 1, 2, 5 to elementy osiowe eliminacji według Gaussa. Uwaga: 1, 2, 5 to elementy osiowe eliminacji według Gaussa. Ą# ń# Ą# ń# Ą# ń# Ą# ń# Ą# ń# Ą# ń# 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 ó# ó# ó# ó# E32E21 = 0 1 0Ą# ó# 1 0Ą# = 1 0Ą# E32E21 = 0 1 0Ą# ó# 1 0Ą# = 1 0Ą# Ł# Ś# Ł#-3 Ś# Ł#-3 Ś# Ł# Ś# Ł#-3 Ś# Ł#-3 Ś# 0 -2 1 0 0 1 6 -2 1 0 -2 1 0 0 1 6 -2 1 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 61 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 62 / 111 Przypomnienie przykładu eliminacji według Gaussa Dekompozycja LU Ą# ń# 1 2 1 Ą# ń# ó# 1 2 1 A = 3 8 1Ą# Ł# Ś# ó# A = 3 8 1Ą# Ł# Ś# 0 4 1 0 4 1 Ą# ń# Ą# ń# Ą# ń# Ą# ń# 1 0 0 1 0 0 1 2 1 1 2 1 Ą# ń# Ą# ń# Ą# ń# Ą# ń# ó# ó# 1 0 0 1 0 0 1 2 1 1 2 1 E32E21A = 0 1 0Ą# ó# 1 0Ą# ó#3 8 1Ą# = 0 2 -2Ą# = U Ł# Ś# Ł#-3 Ś# Ł# Ś# Ł# Ś# ó# ó# E32E21A = 0 1 0Ą# ó# 1 0Ą# ó#3 8 1Ą# = 0 2 -2Ą# = U Ł# Ś# Ł#-3 Ś# Ł# Ś# Ł# Ś# 0 -2 1 0 0 1 0 4 1 0 0 5 0 -2 1 0 0 1 0 4 1 0 0 5 A = E-1E-1U 21 32 Uwaga: Macierz U jest górnotrójkątna. Ą# ń# Ą# ń# Ą# ń# Uwaga: 1, 2, 5 to elementy osiowe eliminacji według Gaussa. 1 0 0 1 0 0 1 0 0 ó# ó# E-1E-1 = 3 1 0Ą# ó#0 1 0Ą# = 3 1 0Ą# = U Ą# ń# Ą# ń# Ą# ń# Ł# Ś# Ł# Ś# Ł# Ś# 21 32 1 0 0 1 0 0 1 0 0 0 0 1 0 2 1 0 2 1 ó# ó# E32E21 = 0 1 0Ą# ó# 1 0Ą# = 1 0Ą# Ł# Ś# Ł#-3 Ś# Ł#-3 Ś# A = LU 0 -2 1 0 0 1 6 -2 1 L macierz dolnotrójkątna, U macierz górnotrójkątna L macierz dolnotrójkątna, U macierz górnotrójkątna Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 63 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 64 / 111 Dekompozycja LU Dekompozycja LU Ą# ń# Ą# ń# 1 2 1 1 2 1 ó# ó# A = 3 8 1Ą# A = 3 8 1Ą# Ł# Ś# Ł# Ś# 0 4 1 0 4 1 Ą# ń# Ą# ń# Ą# ń# Ą# ń# Ą# ń# Ą# ń# Ą# ń# Ą# ń# 1 0 0 1 0 0 1 2 1 1 2 1 1 0 0 1 0 0 1 2 1 1 2 1 ó# ó# ó# ó# E32E21A = 0 1 0Ą# ó# 1 0Ą# ó#3 8 1Ą# = 0 2 -2Ą# = U E32E21A = 0 1 0Ą# ó# 1 0Ą# ó#3 8 1Ą# = 0 2 -2Ą# = U Ł# Ś# Ł#-3 Ś# Ł# Ś# Ł# Ś# Ł# Ś# Ł#-3 Ś# Ł# Ś# Ł# Ś# 0 -2 1 0 0 1 0 4 1 0 0 5 0 -2 1 0 0 1 0 4 1 0 0 5 A = E-1E-1U A = E-1E-1U 21 32 21 32 Ą# ń# Ą# ń# Ą# ń# Ą# ń# Ą# ń# Ą# ń# 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 ó# ó# ó# ó# E-1E-1 = 3 1 0Ą# ó#0 1 0Ą# = 3 1 0Ą# = L E-1E-1 = 3 1 0Ą# ó#0 1 0Ą# = 3 1 0Ą# = L Ł# Ś# Ł# Ś# Ł# Ś# Ł# Ś# Ł# Ś# Ł# Ś# 21 32 21 32 0 0 1 0 2 1 0 2 1 0 0 1 0 2 1 0 2 1 A = LU A = LU L macierz dolnotrójkątna, U macierz górnotrójkątna L macierz L macierz dolnotrójkątna, U macierz górnotrójkątna L macierz dolnotrójkątna, U macierz górnotrójkątna dolnotrójkątna, U macierz górnotrójkątna Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 65 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 66 / 111 Dekompozycja LU Zastosowanie dekompozycji LU Ą# ń# 1 2 1 ó# A = 3 8 1Ą# Ł# Ś# 0 4 1 Ą# ń# Ą# ń# Ą# ń# Ą# ń# 1 0 0 1 0 0 1 2 1 1 2 1 ó# ó# E32E21A = 0 1 0Ą# ó# 1 0Ą# ó#3 8 1Ą# = 0 2 -2Ą# = U Ł# Ś# Ł#-3 Ś# Ł# Ś# Ł# Ś# 0 -2 1 0 0 1 0 4 1 0 0 5 A = E-1E-1U 21 32 Ą# ń# Ą# ń# Ą# ń# 1 0 0 1 0 0 1 0 0 ó# ó# E-1E-1 = 3 1 0Ą# ó#0 1 0Ą# = 3 1 0Ą# = L Ł# Ś# Ł# Ś# Ł# Ś# 21 32 0 0 1 0 2 1 0 2 1 A = LU Wszystkie mnożniki eliminacji występujące w macierzach elementarnych E-1, E-1 pozostają na swoich miejscach w macierzy L. 21 32 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 67 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 68 / 111 Macierz dolnotrójkątna L Macierz górnotrójkątna U Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 69 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 70 / 111 Macierz dolnotrójkątna L i podstawianie w przód Macierz dolnotrójkątna L i podstawianie w przód Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 71 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 72 / 111 Macierz górnotrójkątna U i podstawianie wstecz Zastosowanie dekompozycji LU podsumowanie Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 73 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 74 / 111 Operacje arytmetyczne na liczbach zmiennoprzecinkowych Operacje arytmetyczne na liczbach zmiennoprzecinkowych Flop (MAC) i Flops Flop oraz Flip-Flop flop to skrót nazwy floating-point operation , czyli operacja zmiennoprzecinkowa , Nie należy mylić pojęć flop oraz flip-flop: jeden flop składa się z jednego mnożenia zmiennoprzecinkowego flop floating-point operation operacja zmiennoprzecinkowa , i z jednego dodawania (odejmowania) zmiennoprzecinkowego jest flip-flop w elektronice to przerzutnik (multiwibrator) bistabilny np. więc zmiennoprzecinkową realizacją operacji MAC, typu SR ( set-reset ), D ( data ), T ( toggle ) i JK, MAC to skrót nazwy multiply and accumulate , czyli mnóż poza tym flip-flop ma jeszcze bardzo wiele innych znaczeń, np.: i akumuluj MAC to podstawowa operacja algebry i cyfrowego flip-flop w polityce to nagła zmiana opinii na przeciwną, przetwarzania sygnałów, flip pstrykać, rzucać, przewracać flops to skrót nazwy floating-point operations per second , czyli flop klapa, klapki; zrobić klapę , klapnąć, klapać liczba operacji zmiennoprzecinkowych na sekundę we flopsach flap klapa, panika; machać, łopotać mierzy się wydajność procesorów zmiennoprzecinkowych, flip-flops klapki (można je nosić w domu i na plaży). komputer osobisty z procesorem Pentium 4 lub Athlon 64 i zegarem 2 GHz, a także procesor sygnałowy TMS320C6701 firmy Texas Instruments o architekturze VelociTI mają wydajność rzędu 1 Gflopsa. Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 75 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 76 / 111 Operacje arytmetyczne na liczbach zmiennoprzecinkowych Operacje arytmetyczne na liczbach zmiennoprzecinkowych Flip i Flap, Flip-Flop oraz Flop i Flops Nie należy mylić pojęć: Flip i Flap, Flip-Flop oraz Flop i Flops. Flop oraz Flip-Flop Niestety dalsze analizowanie tych zagadnień wykracza poza wąsko pojętą Nie należy mylić pojęć flop oraz flip-flop: algebrę z geometrią. flop floating-point operation operacja zmiennoprzecinkowa , Wszystkich, którzy chcieliby dowiedzieć się więcej na te i inne pasjonujące flip-flop w elektronice to przerzutnik (multiwibrator) bistabilny np. tematy zapraszam do wybrania specjalności typu SR ( set-reset ), D ( data ), T ( toggle ) i JK, SYSTEMY WIZYJNE!!! poza tym flip-flop ma jeszcze bardzo wiele innych znaczeń, np.: flip-flop w polityce to nagła zmiana opinii na przeciwną, flip pstrykać, rzucać, przewracać flop klapa, klapki; zrobić klapę , klapnąć, klapać flap klapa, panika; machać, łopotać flip-flops klapki (można je nosić w domu i na plaży). Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 76 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 77 / 111 Przekształcanie układu równań w układ równoważny Przekształcanie układu równań w układ równoważny Operacje elementarne Operacje elementarne Jeśli układ równań Transformacji układu równań Ax = b Ax = b będziemy reprezentować za pomocą macierzy rozszerzonej [A|b], to operacje elementarne możemy sformułować jako: w równoważny układ równań pomnożenie wiersza macierzy rozszerzonej przez niezerową stałą, Ć x = b , dodanie jednego wiersza do drugiego wiersza macierzy rozszerzonej, zmianę kolejności wierszy macierzy rozszerzonej. dokonujemy za pomocą tzw. operacji elementarnych, wśród których wyróżniamy trzy rodzaje operacji: Macierz przekształcenia E pomnożenie równania przez niezerową stałą, Macierz rozszerzoną układu równań po przekształceniu możemy wyrazić dodanie jednego równania do drugiego równania, jako zmianę kolejności równań. Ć [|b] =E[A|b] . Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 78 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 79 / 111 Pomnożenie wiersza macierzy rozszerzonej przez stałą m Dodanie jednego wiersza do drugiego Pomóżmy j-ty wiersz macierzy rozszerzonej [A|b] przez stałą m = 0.
Dodajmy j-ty wiersz do i-tego wiersza macierzy rozszerzonej [A|b]. Macierz Sjj (zmiany skali) Macierz Eij przekształcenia przekształcenia Ć [|b] =Sjj[A|b] . Ć [|b] =Eij[A|b] . wyraża się wzorem wyraża się wzorem j Ą# ń# j 1 Ą# ń# ó# Ą# 1 . . ó# Ą# . ó# Ą# ó# Ą# . . ó# Ą# ó# Ą# . 1 ó# Ą# ó# Ą# ó# Ą# ó# Ą# 1 . ó# Ą# ó# Ą# . Eij = . ó# Ą# ó# Ą# ó# m Ą# Sjj = j ó# Ą# ó# Ą# ó# Ą# i 1 1 ó# Ą# ó# Ą# 1 ó# Ą# ó# Ą# . . ó# Ą# . Ł# . Ś# . Ł# Ś# . 1 1 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 80 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 81 / 111 Dodanie m-krotności jednego wiersza do drugiego Zmiana kolejności wierszy Dodajmy j-ty wiersz pomnożony przez stałą m = 0 do i-tego wiersza
Zamieńmy miejscami i-ty oraz j-ty wiersz macierzy rozszerzonej [A|b]. macierzy rozszerzonej [A|b]. Macierz Pij (permutacji, inwersji i, j) Macierz Eij przekształcenia przekształcenia Ć [|b] =Pij[A|b] . Ć [|b] =Eij[A|b] . wyraża się wzorem wyraża się wzorem j i Ą# ń# j Ą# ń# 1 1 ó# Ą# . . ó# Ą# ó# Ą# . . . ó# Ą# ó# Ą# . ó# Ą# ó# Ą# j 0 1 ó# Ą# ó# Ą# 1 ó# Ą# ó# Ą# . ó# Ą# ó# Ą# . Pij = . . ó# Ą# ó# Ą# . Eij = . ó# Ą# ó# Ą# ó# Ą# ó# Ą# i 1 0 ó# Ą# ó# Ą# i m 1 ó# Ą# ó# Ą# . . Ł# ó# Ą# . Ś# . . Ł# . Ś# 1 1 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 82 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 83 / 111 Gaussa metoda eliminacji Gaussa metoda eliminacji bez zmiany kolejności wierszy Pierwszy (podstawowy) krok eliminacji metodą Gaussa Przekształcanie układu równań Rozpatrujemy element a11 macierzy A i (na razie, aby uniknąć permutacji
Ax = b wierszy macierzy A) zakładamy, że a11 = 0. Na tej podstawie obliczamy współczynniki w układ równoważny mi1 = ai1/a11 , i = 2, 3, . . . , n Ux = y przez które kolejno mnożymy pierwsze równanie (pierwszy rząd macierzy z górnotrójkątną macierzą U polega na sukcesywnym eliminowaniu rozszerzonej) i kolejno odejmujemy od pozostałych wierszy. W ten sposób pewnych niezerowych elementów macierzy A za pomocą odpowiednich eliminujemy elementy ai1, i = 2, 3, . . . , n pierwszej kolumny macierzy kolejnych operacji elementarnych. Procedura ta jest nazywana rozszerzonej, sprowadzając je do zera. Obliczamy przy tym nowe wartości pozostałych elementów macierzy rozszerzonej Gaussa metodą eliminacji (1) aij = aij - mi1a1j , i, j = 2, 3, . . . , n lub eliminacją metodą Gaussa nie zaś jak mówi wielu metodą eliminacji Gaussa lub jeszcze gorzej eliminacją Gaussa . (1) bi = bi - mi1b1 , i = 2, 3, . . . , n Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 84 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 85 / 111 Przekształcanie macierzy rozszerzonej Przekształcanie macierzy rozszerzonej W implementacjach komputerowych przechowywanie zer nie jest celowe. Natomiast współczynniki m21, m31, . . . , mn1 mogą się jeszcze przydać. Dlatego zapisuje się je, dobrze wykorzystując wolne komórki pamięci, Wskutek wykonania pierwszego kroku eliminacji metodą Gaussa macierz w miejscach zer rozszerzona [A|b] przekształca się do postaci Ą# ń# a11 a12 a1n b1 Ą# ń# ó# (1) (1) (1) Ą# a11 a12 a1n b1 ó# m21 a22 a2n b2 Ą# ó# Ą# ó# (1) (1) (1) Ą# . . . . ó# Ą# ó# 0 a22 a2n b2 Ą# . . . . Ł# . . . . Ś# ó# Ą# . . . . ó# Ą# . . . . (1) (1) (1) Ł# . . . . Ś# mn1 an2 ann bn (1) (1) (1) 0 an2 ann bn Uwaga Pierwszy krok eliminacji wymaga wykonania n - 1 dzieleń i (n - 1)n flopów. Pomijając człony rzędu pierwszego (tj. proporcjonalne do n) oraz rzędu zerowego, koszt obliczeniowy pierwszego kroku to ok. n2 flopów. Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 86 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 87 / 111 Drugi krok eliminacji metodą Gaussa Macierz rozszerzona po drugim kroku eliminacji metodą Gaussa Drugi krok eliminacji metodą Gaussa jest identyczny jak pierwszy, z tym, że dotyczy podmacierzy Ą# ń# (1) (1) (1) a22 a2n b2 ó# Ą# . . . Po drugim kroku eliminacji metodą Gaussa macierz rozszerzona [A|b] ó# Ą# . . . . . . Ł# Ś# przyjmuje postać (1) (1) (1) an2 ann bn Ą# ń# a11 a12 a13 a1n b1 ó# (1) (1) (1) (1) (1) ó# m21 a22 a23 a2n b2 Ą# Ą# Zakładamy, że a22 = 0 i obliczamy
ó# Ą# (2) (2) (2) ó# m31 0 a33 a3n b3 Ą# ó# Ą# (1) (1) ó# Ą# mi2 = ai2 /a22 , i = 3, 4, . . . , n . . . . . ó# Ą# . . . . . . . . . . Ł# Ś# (2) (2) (2) Obliczamy też nowe wartości elementów macierzy rozszerzonej mn1 0 an3 ann bn (2) (1) (1) aij = aij - mi2a2j , i, j = 3, 4, . . . , n (2) (1) (1) bi = bi - mi2b2 , i = 3, 4, . . . , n Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 88 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 89 / 111 Macierz rozszerzona po drugim kroku eliminacji metodą Trzeci i dalsze kroki eliminacji metodą Gaussa Gaussa Trzeci i dalsze kroki eliminacji metodą Gaussa (aż do kroku n - 1-szego) wykonuje się analogicznie, wprowadzając stopniowo zera (a właściwie Ściślej macierz rozszerzoną [A|b] po drugim kroku eliminacji metodą współczynniki mij poniżej głównej przekątnej macierzy rozszerzonej [A|b]. Gaussa zapisuje się jako Ą# ń# a11 a12 a13 a14 a1n b1 Ą# ń# a11 a12 a13 a1n b1 ó# Ą# (1) (1) (1) (1) (1) ó# m21 a22 a23 a24 a2n b2 Ą# ó# (1) (1) (1) (1) ó# Ą# ó# m21 a22 a23 a2n b2 Ą# Ą# ó# (2) (2) (2) (2) ó# Ą# ó# m31 m32 a33 a34 a3n b3 Ą# Ą# (2) (2) (2) ó# ó# Ą# m31 m32 a33 a3n b3 Ą# ó# Ą# (3) (3) (3) ó# ó# Ą# m41 m42 0 a44 a4n b4 Ą# ó# Ą# . . . . . ó# Ą# . . . . . ó# Ą# . . . . . . . . . . . Ł# Ś# ó# . . . . . . Ą# . . . . . . (2) (2) (2) Ł# Ś# mn1 mn2 an3 ann bn (3) (3) (3) mn1 mn2 0 an4 ann bn Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 90 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 91 / 111 Trzeci i dalsze kroki eliminacji metodą Gaussa Trzeci i dalsze kroki eliminacji metodą Gaussa Trzeci i dalsze kroki eliminacji metodą Gaussa (aż do kroku n - 1-szego) Trzeci i dalsze kroki eliminacji metodą Gaussa (aż do kroku n - 1-szego) wykonuje się analogicznie, wprowadzając stopniowo zera (a właściwie wykonuje się analogicznie, wprowadzając stopniowo zera (a właściwie współczynniki mij poniżej głównej przekątnej macierzy rozszerzonej [A|b]. współczynniki mij poniżej głównej przekątnej macierzy rozszerzonej [A|b]. Ą# ń# Ą# ń# a11 a12 a13 a14 a1n b1 a11 a12 a13 a14 a1n b1 ó# Ą# ó# Ą# (1) (1) (1) (1) (1) (1) (1) (1) (1) (1) ó# ó# m21 a22 a23 a24 a2n b2 Ą# m21 a22 a23 a24 a2n b2 Ą# ó# Ą# ó# Ą# ó# (2) (2) (2) (2) ó# (2) (2) (2) (2) ó# m31 m32 a33 a34 a3n b3 Ą# ó# m31 m32 a33 a34 a3n b3 Ą# Ą# Ą# ó# Ą# ó# Ą# (3) (3) (3) (3) (3) (3) ó# ó# m41 m42 m43 a44 a4n b4 Ą# m41 m42 m43 a44 a4n b4 Ą# ó# Ą# ó# Ą# ó# Ą# ó# Ą# . . . . . . . . . . . . ó# . . . . . . Ą# ó# . . . . . . Ą# . . . . . . . . . . . . Ł# Ś# Ł# Ś# (3) (3) (3) (4) (4) mn1 mn2 mn3 an4 ann bn mn1 mn2 mn3 0 ann bn Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 92 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 93 / 111 Trzeci i dalsze kroki eliminacji metodą Gaussa Wykonalność eliminacji metodą Gaussa bez permutacji wierszy Zauważmy, że drugi krok rozważanej eliminacji jest wykonalny przy Trzeci i dalsze kroki eliminacji metodą Gaussa (aż do kroku n - 1-szego) (1) założeniu a22 = 0, co, przy wzięciu pod uwagę wykonalności pierwszego
wykonuje się analogicznie, wprowadzając stopniowo zera (a właściwie kroku dzięki założeniu det A1 = a11 = 0, jest równoważne spełnieniu
współczynniki mij poniżej głównej przekątnej macierzy rozszerzonej [A|b]. warunku
a21 a22 0 a22 ó# m21 a22 a23 a24 a2n b2 Ą# ó# Ą# ó# (2) (2) (2) (2) ó# m31 m32 a33 a34 a3n b3 Ą# Ą# ó# Ą# (3) (3) (3) ó# Główne podmacierze prowadzące m41 m42 m43 a44 a4n b4 Ą# ó# Ą# ó# Ą# . . . . . . Macierze Ak o elementach leżących w przecięciu pierwszych k wierszy i k ó# . . . . . . Ą# . . . . . . Ł# Ś# kolumn macierzy A, k = 1, 2, . . . , n, nazywa się głównymi podmacierzami (n-1) (n-1) mn1 mn2 mn3 mn4 ann bn prowadzącymi macierzy A. Warunkiem dostatecznym wykonalności algorytmu eliminacji Gaussa bez permutacji wierszy macierzy rozszerzonej [A|b] jest to, że wszystkie główne podmacierze prowadzące Ak, k = 1, 2, . . . , n, macierzy A są nieosobliwe. Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 94 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 95 / 111 Koszt metody Gaussa eliminacji macierzy do postaci Koszt metody Gaussa eliminacji macierzy do postaci górnotrójkątnej górnotrójkątnej Liczba flopów potrzebna do doprowadzenia macierzy A do postaci Liczba flopów potrzebna do doprowadzenia macierzy A do postaci górnotrójkątnej U, to górnotrójkątnej U, to n
n2 +(n - 1)2 + . . . + 22 n2 +(n - 1)2 + . . . + 22 H" k2 k=1 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 96 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 97 / 111 Koszt metody Gaussa eliminacji macierzy do postaci Koszt metody Gaussa eliminacji macierzy do postaci górnotrójkątnej górnotrójkątnej Liczba flopów potrzebna do doprowadzenia macierzy A do postaci górnotrójkątnej U, to Liczba flopów potrzebna do doprowadzenia macierzy A do postaci n
górnotrójkątnej U, to n2 +(n - 1)2 + . . . + 22 H" k2 k=1 n
n H" k2dk Uwagi 0 Koszt metody podstawiania wstecz n2/2 flopówjest pomijalny. Całkowity koszt metody Gaussa to n3/3, pomijając 1/3 ten wynik zapisujemy ogólnie jako O(n3). Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 98 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 99 / 111 Przykład eliminacji według Gaussa Przykład eliminacji według Gaussa Przykład Przykład Niech Niech Ą# ń# Ą# ń# Ą# ń# Ą# ń# 2 1 1 9 2 1 1 9 ó# Ą# ó# Ą# ó# Ą# ó# Ą# A = 2 2 -1 i b = 9 A = 2 2 -1 i b = 9 Ł# Ś# Ł# Ś# Ł# Ś# Ł# Ś# 4 -1 6 16 4 -1 6 16 Eliminacja metodą Gaussa bez permutacji wierszy jest wykonalna, Eliminacja metodą Gaussa bez permutacji wierszy jest wykonalna, ponieważ det A1 = 2 = 0, det A2 = 2 = 0 i det A3 = -4 = 0. ponieważ det A1 = 2 = 0, det A2 = 2 = 0 i det A3 = -4 = 0.
W wyniku eliminacji otrzymujemy kolejno: W wyniku eliminacji otrzymujemy kolejno: m21 = 1 Ą# ń# Ą# ń#
2 1 1 9 2 1 1 9
ó# Ą# ó# Ą# 2 2 Ś# 0 1 Ś# Ł# -1 9 . Ł# -2 0 .
4 -1 6 16 4 -1 6 16 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 100 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 101 / 111 Przykład eliminacji według Gaussa Przykład eliminacji według Gaussa Przykład Przykład Niech Niech Ą# ń# Ą# ń# Ą# ń# Ą# ń# 2 1 1 9 2 1 1 9 ó# Ą# ó# Ą# ó# Ą# ó# Ą# A = 2 2 -1 i b = 9 A = 2 2 -1 i b = 9 Ł# Ś# Ł# Ś# Ł# Ś# Ł# Ś# 4 -1 6 16 4 -1 6 16 Eliminacja metodą Gaussa bez permutacji wierszy jest wykonalna, Eliminacja metodą Gaussa bez permutacji wierszy jest wykonalna, ponieważ det A1 = 2 = 0, det A2 = 2 = 0 i det A3 = -4 = 0. ponieważ det A1 = 2 = 0, det A2 = 2 = 0 i det A3 = -4 = 0.
W wyniku eliminacji otrzymujemy kolejno: m21 = 1 W wyniku eliminacji otrzymujemy kolejno: m21 = 1, m31 = 2 Ą# ń# Ą# ń#
2 1 1 9 2 1 1 9
ó# Ą# ó# Ą# 1 1 Ś# 1 1 Ś# Ł# -2 0 . Ł# -2 0 .
4 -1 6 16 0 -3 4 -2 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 102 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 103 / 111 Przykład eliminacji według Gaussa Przykład eliminacji według Gaussa Przykład Przykład Niech Niech Ą# ń# Ą# ń# Ą# ń# Ą# ń# 2 1 1 9 2 1 1 9 ó# Ą# ó# Ą# ó# Ą# ó# Ą# A = 2 2 -1 i b = 9 A = 2 2 -1 i b = 9 Ł# Ś# Ł# Ś# Ł# Ś# Ł# Ś# 4 -1 6 16 4 -1 6 16 Eliminacja metodą Gaussa bez permutacji wierszy jest wykonalna, Eliminacja metodą Gaussa bez permutacji wierszy jest wykonalna, ponieważ det A1 = 2 = 0, det A2 = 2 = 0 i det A3 = -4 = 0. ponieważ det A1 = 2 = 0, det A2 = 2 = 0 i det A3 = -4 = 0.
W wyniku eliminacji otrzymujemy kolejno: m21 = 1, m31 = 2 W wyniku eliminacji otrzymujemy kolejno: m21 = 1, m31 = 2, m32 = -3 Ą# ń# Ą# ń#
2 1 1 9 2 1 1 9
ó# Ą# ó# Ą# 1 1 Ś# 1 1 Ś# Ł# -2 0 . Ł# -2 0 .
2 -3 4 -2 2 0 -2 -2 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 104 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 105 / 111 Przykład eliminacji według Gaussa Przykład eliminacji według Gaussa Przykład Przykład Niech Niech Ą# ń# Ą# ń# Ą# ń# Ą# ń# 2 1 1 9 2 1 1 9 ó# Ą# ó# Ą# ó# Ą# ó# Ą# A = 2 2 -1 i b = 9 A = 2 2 -1 i b = 9 Ł# Ś# Ł# Ś# Ł# Ś# Ł# Ś# 4 -1 6 16 4 -1 6 16 Eliminacja metodą Gaussa bez permutacji wierszy jest wykonalna, Eliminacja metodą Gaussa bez permutacji wierszy jest wykonalna, ponieważ det A1 = 2 = 0, det A2 = 2 = 0 i det A3 = -4 = 0. ponieważ det A1 = 2 = 0, det A2 = 2 = 0 i det A3 = -4 = 0.
W wyniku eliminacji otrzymujemy kolejno: m21 = 1, m31 = 2, m32 = -3 Po eliminacji otrzymujemy ostatecznie Ą# ń# Ą# ń#
2 1 1 9 2 1 1 9
ó# Ą# ó# Ą# 1 1 Ś# 1 1 Ś# Ł# -2 0 . Ł# -2 0 .
2 -3 -2 -2 2 -3 -2 -2 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 106 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 107 / 111 Przykład eliminacji według Gaussa Dekompozycja LU dla zaawansowanych Przykład Przykład Niech Ą# ń# Ą# ń# Na podstawie poprzedniego przykładu zauważmy, że 2 1 1 9 Ą# ń# Ą# ń# Ą# ń# ó# Ą# ó# Ą# 1 0 0 2 1 1 2 1 1 A = 2 2 -1 i b = 9 Ł# Ś# Ł# Ś# ó# Ą# ó# Ą# ó# Ą# Ł# 1 1 0 0 1 -2 = 2 2 -1 czyli LU = A . Ś# Ł# Ś# Ł# Ś# 4 -1 6 16 2 -3 1 0 0 -2 4 -1 6 Eliminacja metodą Gaussa bez permutacji wierszy jest wykonalna, ponieważ det A1 = 2 = 0, det A2 = 2 = 0 i det A3 = -4 = 0. Twierdzenie
Po eliminacji otrzymujemy ostatecznie Macierz kwadratowa A, której wszystkie główne podmacierze prowadzące Ą# ń# są nieosobliwe jest w jeden i tylko jeden sposób dekomponowanla na 2 1 1 9
ó# Ą# iloczyn 1 1 Ś# Ł# -2 0 . A = LU
2 -3 -2 -2 przy czym macierz L jest dolnotrójkątna, a macierz U jest górnotrójkątna. Wprowadzamy oznaczenie Macierz U otrzymuje się Gaussa metodą eliminacji macierzy A a macierz L Ą# ń# Ą# ń# 2 1 1 1 0 0 tworzy się ze współczynników metody Gaussa wpisywanych w miejsce ó# Ą# ó# Ą# U = 0 1 -2 oraz L = 1 1 0 . eliminowanych przez nie elementów macierzy A. Główną przekątną Ł# Ś# Ł# Ś# 0 0 -2 2 -3 1 macierzy L wypełnia się jedynkami, a pozostałe jej elementy zerami. Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 108 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 109 / 111 Zastosowanie dekompozycji LU podsumowanie Taneczna wersja (de)kompozycji LU W celu rozwiązania równania (układu równań) Ax = b dokonujemy dekompozycji LU macierzy A A = LU i otrzymujemy równanie LUx = b W celu rozwiązania go najpierw obliczamy pomocniczy wektor y, rozwiązując równanie Ly = b metodą podstawiania w przód, a następnie obliczamy właściwy wektor niewiadomych x, rozwiązując równanie LU Ux = y Maniusiu tańczmy na dwa pas nasze tango andrusowskie! metodą podstawiania wstecz. Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 110 / 111 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 7 listopada 2012 111 / 111