Zakres zagadnień Algebra Choleskiego metoda dekompozycji i Gaussa metoda eliminacji 1 Macierze dodatnio określone Adam Dąbrowski 2 Choleskiego metoda dekompozycji Politechnika Poznańska Wydział Informatyki i Zarządzania Katedra Sterowania i Inżynierii Systemów 3 Pracownia Układów Elektronicznych i Przetwarzania Sygnałów Operacje elementarne 31 stycznia 2009 4 Koncepcja Gaussa metody eliminacji 5 Dekompozycja LU Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 1 / 74 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 2 / 74 Macierz dodatnio określona Fizyczne znaczenie wyrażenia xtAx > 0 Definicja Przykład Kwadratowa, rzeczywista i symetryczna macierz A o wymiarze n n jest Rozważmy obwód elektryczny o n zaciskach zewnętrznych, zbudowany nazywana macierzą dodatnio określoną, jeśli nierówność z rezystorów. Niech w chwili t zaciski te mają względem masy potencjały v1(t), v2(t), . . . , vn(t) i niech do obwodu dopływają przez nie prądy xtAx > 0 i1(t), i2(t), . . . , in(t), z obwodu odpływa więc do masy suma tych prądów i1(t) +i2(t) + + in(t). Zdefiniujmy wektory jest spełniona dla dowolnego niezerowego wektora x "Rn. Ą# ń# Ą# ń# v1(t) i1(t) Przykład ó# Ą# ó# Ą# v2(t) i2(t) ó# Ą# ó# Ą# Macierze dodatnio określone są częste w opisach zjawisk przyrodniczych ó# Ą# ó# Ą# v = oraz i = . . ó# Ą# ó# Ą# . . i systemów technicznych. Na przykład macierz admitancyjna Ł# . Ś# Ł# . Ś# Ą# ń# vn(t) in(t) 1 1 1 1 + + - 0 R1 R2 R3 R3 ó# Ą# 1 1 1 1 1 dla uproszczenia pominięto oznaczenie chwili t. Przez Y oznaczmy macierz Y = - + + - Ś# , Ł# R3 R3 R4 R6 R6 1 1 1 konduktancyjną (admitancyjną) tego obwodu. Zatem i = Yv . Dodatnia 0 - + R6 R5 R6 (zamieniana na ciepło) moc dostarczana do tego obwodu jest więc równa która opisuje obwód elektryczny, analizowany na poprzednim wykładzie vti = vtYv > 0 metodą potencjałów węzłowych, jest dodatnio określona. Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 3 / 74 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 4 / 74 Pasywne systemy fizyczne Macierze dodatnio określone Twierdzenie Zjawiska fizyczne polegają zazwyczaj na przemianach różnych form energii Jeśli macierz A jest dodatnio określona, to jest nieosobliwa. wyrażanych jako iloczyny pewnych wielkości, np.: siłaprzesunięcie, napięcieładunek itd. Systemy fizyczne zawierają zazwyczaj wiele Dowód elementów pobierających, przetwarzających i magazynujących energię. Aatwo pokazać, że jeśli macierz A jest osobliwa, to nie jest dodatnio Zatem energia pobrana przez system jest sumą iloczynów wielokości określona. Istotnie w tym przypadku istnieje niezerowy wektor x "Rn taki, określających energie pobrane przez poszczególne elementy i w rezultacie że Ax = 0. Wówczas jednak xtAx = 0, a zatem macierz A nie jest jest iloczynem skalarnym pewnych wektorów. W systemach liniowych te dodatnio określona. wektory są powiązane zależnością macierzową. Jeśli system jest pasywny, tzn. nie zawiera zródeł energii, to dostarczona do niego energia jest zawsze Wniosek nieujemna, a w praktyce jest dodatnia ze względu na rozpraszanie energii. Jeśli macierz A jest dodatnio określona, to równanie Na przykład rozważany obwód elektryczny złożony z rezystorów zamienia energię elektryczną na ciepło w sposób nieodwracalny. Ax = b Zatem macierze opisujące systemy pasywne są dodatnio określone. ma dokładnie jedno rozwiązanie. Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 5 / 74 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 6 / 74 Konstrukcja macierzy dodatnio określonej Przykłady macierzy dodatnio określonych Twierdzenie Niech rzeczywista kwadratowa macierz M o wymiarze n n będzie nieosobliwa. Wówczas macierz Przykład Niech
A = MMt 1 2 M = . 3 4 jest dodatnio określona. Macierz M jest nieosobliwa, ponieważ det(M) =-2. Dlatego macierz Dowód
5 11 Zauważmy najpierw, że At =(MMt)t =(Mt)tMt = MMt = A, czyli A = MMt = 11 25 macierz A jest symetryczna. Niech x będzie dowolnym niezerowym wektorem x "Rn. Wprowadzmy oznaczenie y = Mtx = 0. Wówczas
2 2 2 2 2 2 g44 = a44 - g41 - g42 - g43 = 7 - 12 - (-2)2 - 12 = 1 g44 = a44 - g41 - g42 - g43 = 7 - 12 - (-2)2 - 12 = 1 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 33 / 74 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 34 / 74 Koszt obliczeniowy metody Choleskiego Zastosowanie metody Choleskiego Obliczenie elementów gjj, j = 1, 2, . . . , n, wymaga wykonania Rozwiążmy układ równań j-1 n n
n(n - 1) n2 Ax = b 1 = (j - 1) = H" 2 2 j=1 k=1 j=1 w przypadku, gdy macierz A jest dodatnio określona. Stosując metodę flopów, zaś obliczenie elementów gij, przy czym i = j + 1, j + 2, . . . , n oraz Choleskiego otrzymujemy j = 1, 2, . . . , n wymaga wykonania GGtx = b n n j-1 n n n
Rozwiązujemy najpierw dolnotrójkątny układ równań 1 = (j - 1) = (n - j)(j - 1) j=1 i=j+1 k=1 j=1 i=j+1 j=1 Gy = b n n n
nn(n - 1) n(n + 1/2)(n + 1) n(n + 1) = n (j - 1) - j2 + j = - + metodą podstawiania w przód, a następnie górnotrójątny układ równań 2 3 2 j=1 j=1 j=1 Gtx = y n3 n3 n3 H" - = 2 3 6 metodą podstawiania wstecz. flopów. Zatem taki jest też całkowity przybliżony koszt obliczeniowy metody Choleskiego w przypadku dużych liczb n. Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 35 / 74 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 36 / 74 Gaussa metoda eliminacji Przekształcanie układu równań w układ równoważny Strategia postępowania Operacje elementarne Rozważamy problem rozwiązywania układu n równań z n niewiadomymi Transformacji układu równań Ax = b Ax = b nie czyniąc żadnych dodatkowych założeń o macierzy A. wukład równań Nasza strategia polega na przekształceniu tego układu w układ Ux = y , równoważny dokonamy za pomocą tzw. operacji elementarnych, wśród których Ux = y wyróżniamy trzy rodzaje operacji: (tzn. mający te same rozwiązania), ale w którym macierz U jest pomnożenie równania przez niezerową stałą, górnotrójkątna. dodanie jednego równania do drugiego równania, Jeśli macierz U jest nieosobliwa, to (jak już wiemy) ten układ może być w prosty sposób rozwiązany przez podstawianie wstecz. zmianę kolejności równań. Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 37 / 74 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 38 / 74 Przekształcanie układu równań w układ równoważny Pomnożenie wiersza macierzy rozszerzonej przez stałą m Pomóżmy j-ty wiersz macierzy rozszerzonej [A|b] przez stałą m = 0.
Operacje elementarne Wówczas Jeśli układ równań Macierz M Ax = b przekształcenia Ć [|b] =M[A|b] . będziemy reprezentować za pomocą macierzy rozszerzonej [A|b], to operacje elementarne możemy sformułować jako: wyraża się wzorem pomnożenie wiersza macierzy rozszerzonej przez niezerową stałą, j dodanie jednego wiersza do drugiego wiersza macierzy rozszerzonej, Ą# ń# 1 zmianę kolejności wierszy macierzy rozszerzonej. ó# Ą# . . ó# Ą# . ó# Ą# ó# Ą# 1 ó# Ą# Macierz przekształcenia M ó# Ą# ó# m Ą# M = j Macierz rozszerzoną układu równań po przekształceniu możemy wyrazić ó# Ą# ó# Ą# 1 ó# Ą# jako ó# Ą# . . Ć Ł# Ś# . [|b] =M[A|b] . 1 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 39 / 74 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 40 / 74 Dodanie jednego wiersza do drugiego Dodanie m-krotności jednego wiersza do drugiego
Dodajmy j-ty wiersz do i-tego wiersza macierzy rozszerzonej [A|b]. Dodajmy j-ty wiersz pomnożony przez stałą m = 0 do i-tego wiersza Wówczas macierzy rozszerzonej [A|b]. Wówczas Macierz M Macierz M przekształcenia przekształcenia Ć Ć [|b] =M[A|b] . [|b] =M[A|b] . wyraża się wzorem wyraża się wzorem j j Ą# ń# Ą# ń# 1 1 ó# Ą# . ó# Ą# . . ó# Ą# . . ó# Ą# . ó# Ą# ó# Ą# ó# Ą# ó# Ą# 1 ó# Ą# 1 ó# Ą# ó# Ą# ó# Ą# . ó# Ą# . . ó# Ą# . M = . M = ó# Ą# . ó# Ą# ó# Ą# ó# Ą# ó# Ą# i 1 1 ó# Ą# i m 1 ó# Ą# ó# Ą# ó# Ą# . ó# Ą# . . . Ł# . Ś# Ł# . Ś# 1 1 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 41 / 74 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 42 / 74 Zmiana kolejności wierszy Gaussa metoda eliminacji Zamieńmy miejscami i-ty oraz j-ty wiersz macierzy rozszerzonej [A|b]. Wówczas Przekształcanie układu równań Macierz M Ax = b przekształcenia Ć [|b] =M[A|b] . w układ równoważny Ux = y wyraża się wzorem j i Ą# ń# z górnotrójkątną macierzą U polega na sukcesywnym eliminowaniu 1 pewnych niezerowych elementów macierzy A za pomocą odpowiednich ó# Ą# . . ó# Ą# . ó# Ą# kolejnych operacji elementarnych. Procedura ta jest nazywana ó# Ą# j 0 1 ó# Ą# ó# Ą# . Gaussa metodą eliminacji ó# Ą# . M = . ó# Ą# ó# Ą# ó# Ą# i 1 0 lub eliminacją metodą Gaussa nie zaś jak mówi wielu metodą ó# Ą# ó# Ą# . . eliminacji Gaussa lub jeszcze gorzej eliminacją Gaussa . Ł# . Ś# 1 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 43 / 74 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 44 / 74 Eliminacja Gaussa Zmiana nastroju osób przedstawionych na banknotach Smutna Królowa Elżbieta II Wesoła Królowa Elżbieta II (opuściła wykład z Algebry) (po wykładzie z Algebry) Eliminacja Gaussa odyła się za sprawą zastąpienia marek niemieckich przez Euro. Wówczas banknot dziesięciomarkowy z podobizną Gaussa został wyeliminowany przez monetę 5 Euro. To smutne nie tylko dla samego Gaussa, ale i dla wszystkich osób Bardziej zaawansowane metody przetwarzania obrazów (w tym zmiany zafascynowanych Algebrą! min) poznają Ci z Państwa, którzy wybiorą specjalność MULTIMEDIA! Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 45 / 74 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 46 / 74 Królowa Elżbieta II na poważnie Carl Friedrich Gauss Sławny syn murarza Carl Friedrich Gauss urodził się w biednej rodzinie pomocnika murarskiego 30. kwietnia 1777 r. w Brunszwiku (Braunschweig). W 1807 r. został profesorem Uniwersytetu w Getyndze (Gttingen) i funkcję tę pełnił aż do śmierci 23. lutego 1855 r. Uważany jest za jednego z największych matematyków wszechczasów. Dla porządku na serio Królowa Elżbieta II tak wygląda na banknocie Przez sobie współczesnych był nazywany księciem matematyków . 20-tu dolarów kanadyjskich z lat 1986-91 z serii z ptakami na odwrocie. Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 47 / 74 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 48 / 74 Carl Friedrich Gauss Gaussa metoda eliminacji bez zmiany kolejności wierszy Książę matematyków Pierwszy (podstawowy) krok eliminacji metodą Gaussa Rozpatrujemy element a11 macierzy A i (na razie, aby uniknąć permutacji wierszy macierzy A) zakładamy, że a11 = 0. Na tej podstawie obliczamy
współczynniki mi1 = ai1/a11 , i = 2, 3, . . . , n przez które kolejno mnożymy pierwsze równanie (pierwszy rząd macierzy Talent matematyczny Gaussa ujawnił się bardzo wcześnie. W szkole jako rozszerzonej) i kolejno odejmujemy od pozostałych wierszy. W ten sposób karę za złe zachowanie otrzymał zadanie obliczenia sumy wszystkich liczb eliminujemy elementy ai1, i = 2, 3, . . . , n pierwszej kolumny macierzy całkowitych od 1 do 100. Nauczyciel sądził, że zabierze mu to sporo czasu, rozszerzonej, sprowadzając je do zera. Obliczamy przy tym nowe wartości zanim otrzyma prawidłowy wynik. Gauss rozwiązał jednak to zadanie w pozostałych elementów macierzy rozszerzonej mgnieniu oka. Dodał dwa razy te liczby, przy czym ich drugi zestaw (1) dodawał odwracając kolejność składników, tj. otrzymując 1 + 100 = 101, aij = aij - mi1a1j , i, j = 2, 3, . . . , n 2 + 99 = 101, 3 + 98 = 101,. . . , 50 + 51 = 101, czyli następujący (1) wynik końcowy (1/2) 100 101 = 5050. bi = bi - mi1b1 , i = 2, 3, . . . , n Korzystając z tego rozumowania oblicza się pole powierzchni trójkąta. Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 49 / 74 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 50 / 74 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 31 stycznia 2009 51 / 74 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 52 / 74 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 31 stycznia 2009 53 / 74 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 54 / 74 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 31 stycznia 2009 55 / 74 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 56 / 74 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 31 stycznia 2009 57 / 74 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 58 / 74 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 31 stycznia 2009 59 / 74 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 60 / 74 Koszt metody Gaussa eliminacji macierzy do postaci Koszt metody Gaussa eliminacji macierzy do postaci trójkątnej trójkątnej Liczba flopów potrzebna do doprowadzenia macierzy A do postaci górnotrójkątnej U, to n
Liczba flopów potrzebna do doprowadzenia macierzy A do postaci n2 +(n - 1)2 + . . . + 22 H" k2 górnotrójkątnej U, to k=1
n n3 n2 +(n - 1)2 + . . . + 22 H" k2dk = 3 0 Uwagi Koszt metody podstawiania wstecz n2/2 flopówjest pomijalny. Koszt dekompozycji Choleskiego n3/6 jest dwukrotnie mniejszy, ale ta dekompozycja wymaga, aby macierz układu równań była dodatnio określona. Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 61 / 74 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 62 / 74 Gaussa metoda eliminacji Gaussa metoda eliminacji 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 31 stycznia 2009 63 / 74 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 64 / 74 Gaussa metoda eliminacji Gaussa metoda eliminacji 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 31 stycznia 2009 65 / 74 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 66 / 74 Gaussa metoda eliminacji Gaussa metoda eliminacji 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 31 stycznia 2009 67 / 74 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 68 / 74 Gaussa metoda eliminacji Gaussa metoda eliminacji 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 31 stycznia 2009 69 / 74 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 70 / 74 Gaussa metoda eliminacji Dekompozycja LU 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 31 stycznia 2009 71 / 74 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 72 / 74 Zastosowanie dekompozycji LU Karnawałowa 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 pa nasze tango andrusowskie! metodą podstawiania wstecz. Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 73 / 74 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 74 / 74