Lemur zaprasza
Rozwiązywanie układów równań liniowych AX=B Macierz A n x n macierz X n x 1 - macierz niewiadomych macierz B n x 1 - macierz wyrazów wolnych Warunek istnienia rozwiązania jednoznacznego - det A jest różne od 0 Metody dokładne rozwiązywania układów równań liniowych I. proste rozwiązanie X = A-1 B, ale dla n<=4 II. wzory Kramera (Kramer contra Kramer), ale też dla n<=4 III. metoda eliminacji Gaussa, o której teraz: najpierw weźmy szczególne przypadki - kiedy macierz A jest dolno- lub górnotrójkątna Od razu da się wyznaczyć xn: A teraz samo sedno - metoda eliminacji Gaussa. Chodzi o to, żeby układ AX=B doprowadzić do postaci CX=R, gdzie C byłoby macierzą trójkątną. Algorytm doprowadzania macierzy zwykłej do trójkątnej. 1. krok: do i-tego wiersza dodajemy pierwszy pomnożony przez (-ai1 / a11), w ten sposób zerując całą kolumnę w dół. 2. krok: do i-tego wiersza dodajemy drugi pomnożony przez (-ai2 / a22) (już bez pierwszego), zerując kolejną kolumnę. I tak dalej, and so on, et caetera, ... Można to wyrazić wzorami rekurencyjnymi (ble ...) Dostajemy macierz trójkątną i mamy wzory Metoda eliminacji Gaussa z wyborem elementu prostego Szukamy (r - wiersz, s - kolumna) Zamieniamy r-ty wiersz z pierwszym (bez troski o cokolwiek) Zamieniamy s-tą kolumnę z pierwszą (pamiętając, że zmienia to kolejność rozwiązań). Na powyższej metodzie bazuje metoda Choleskiego. Zamieniamy AX=B na LUX=B, gdzie UX=Y. L jest macierzą dolnotrójkątną z jedynkami na przekątnej, U jest macierzą górnotrójkątną. Liczymy najpierw LY = B -> Y, potem UX = Y -> X. Ponieważ L ma na przekątnej '1' bez żadnych dzieleń ! Teraz wyznaczamy X Twierdzenie: Jeśli , ( Ai to macierz utworzona z i pierwszych kolum i wierszy macierzy A), to rozkład A na LU jest jednoznaczny. Pierwszy algorytm wyznaczania macierzy L. Elementy macierzy L: aij wyznaczamy z Gaussa. Metoda Doolittle'a L * U = A no i "na żywca" mamy n2 równań. - schemat obliczeń. No i już widać: Końcowe wzory: Przykład na rozkład macierzy A na iloczyn LU Metody iteracyjne Metoda Jacobiego iteracji prostej Powstaje układ postaci Będziemy iterować (jak fajnie !) Twierdzenie: Jeżeli ciąg uzyskany z przekształcenia jest zbieżny (), to xr jest rozwiązaniem. Dowód: Warunkiem koniecznym zbieżności ciągu jest by norma macierzy alfa była mniejsza od 1 (). Definicja normy macierzy Przykładowe normy: Pierwsza norma bazuje na największym wierszu, druga na największej kolumnie, a trzecia jest normą Euklidesową. Jedna z tych pierwszych dwóch norm nazywa się też normą taksówkową, podobno od tego, w jaki sposób jeżdżą taksówkarze w Nowym Jorku (sic!). Macierz A można rozpisać jako A = AL + D + AP. Teraz równanie AX=B wygląda tak: Metoda iteracyjna Seidela Rozwiązanie istnieje (ciąg jest zbieżny), gdy - macierz małych elementów tak dobrana, żeby po wymnożeniu były małe wartości. Metoda relaksacji Z równania wcześniej otrzymanego Piszemy RESIDUUM (miarę błędu) Logiczne jest, że chodzi nam o to, by r = 0. Np. dla trzech zmiennych Najlepiej pokaże to przykład liczenia z relaksacji Macierz trójwstęgowa a1 = 0, cn = 0 aixi-1 + bixi + cixi+1 = di Tu jakieś dziwne wzory (CUT) Kiedy stosujemy jakie metody: - metody dokładne dla n<30 i macierzy gęstej (???) - metody iterayjne - macierz rzadka, n > 100 Kiedy należy przerwać obliczenia według wzoru iteracyjnego ? Najlepiej, gdy . Niestety trzeba znać dokładną wartość x. Dlatego lepiej na bieżąco porównywać kolejne iteracje i przerwać, gdy różnice będą coraz mniejsze: - ogólnie norma różnicy. Przykłady kilku norm: Problemy mogą wystąpić, gdy ciąg różnic nie jest zbieżny. Szacowanie błędu obliczeń iteracyjnych Problem złego uwarunkowania macierzy np. Jeśli , to macierz jest źle uwarunkowana. Gdy mamy układ równań AX = B i a) macierz B jest obarczona błędem , to układ równań wygląda tak b) macierz A jest obarczona błędem . |