Metoda eliminacji Gaussa Mikołaj Buda i Filip Wiśniewski 15 grudnia 2012 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 1 / 52 Zakres zagadnień 1 Carl Friedrich Gauss 2 Metoda eliminacji Gaussa 3 Macierze eliminacji 4 Permutacje 5 Macierz odwrotna 6 Zadania Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 2 / 52 Carl Friedrich Gauss Książe matematyków Carl Friedrich Gau (Gauss) urodził się 30 kwietnia 1777 w Brunszwiku, a zmarł 23 lutego 1855 w Getyndze. Był niemieckim matematykiem, fizykiem, astronomem i geodetą. Jako malec nauczył się czytać, a także samodzielnie opanował proste rachunki. Jak sam twierdził, nauczył się rachować, zanim jeszcze zaczął mówić. Jego podobizna widniała na dziesięciomarkowym banknocie. Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 3 / 52 Metoda eliminacji Gaussa Układ równań: ńł a + 2b + c = 2 ł 3a + 8b + c = 12 ół 4b + c = 2 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 4 / 52 Metoda eliminacji Gaussa Układ równań: ńł a + 2b + c = 2 ł 3a + 8b + c = 12 ół 4b + c = 2 Zapiszmy jako: Ax = b Gdzie: Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 4 / 52 Metoda eliminacji Gaussa Układ równań: ńł a + 2b + c = 2 ł 3a + 8b + c = 12 ół 4b + c = 2 Zapiszmy jako: Ax = b Gdzie: A - współczynniki znajdujące się przy niewiadomych, Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 4 / 52 Metoda eliminacji Gaussa Układ równań: ńł a + 2b + c = 2 ł 3a + 8b + c = 12 ół 4b + c = 2 Zapiszmy jako: Ax = b Gdzie: A - współczynniki znajdujące się przy niewiadomych, x - nasze niewiadome, Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 4 / 52 Metoda eliminacji Gaussa Układ równań: ńł a + 2b + c = 2 ł 3a + 8b + c = 12 ół 4b + c = 2 Zapiszmy jako: Ax = b Gdzie: A - współczynniki znajdujące się przy niewiadomych, x - nasze niewiadome, b - rozwiązanie równań znajdujące się po prawej stronie znaku równości. Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 4 / 52 Metoda eliminacji Gaussa Układ równań: ńł a + 2b + c = 2 ł 3a + 8b + c = 12 ół 4b + c = 2 Zapiszmy jako: Ax = b Gdzie: A - współczynniki znajdujące się przy niewiadomych, x - nasze niewiadome, b - rozwiązanie równań znajdujące się po prawej stronie znaku równości. ł łł ł łł ł łł a11 a12 a13 a 2 ł ł ł ł ł a21 a22 a23 ł b = 12 a31 a32 a33 c 2 x A b Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 5 / 52 Metoda eliminacji Gaussa Diagonala W przypadku rozwiązywania układów równań tworzy się macierze kwadratowe, których główna przekątna zawierająca elementy o równych wskaznikach wiersza i kolumny nazywana jest diagonalą, bądz główną przekątną macierzy. ł łł x x x ł ł x x x ! diagonala x x x Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 6 / 52 Metoda eliminacji Gaussa Niech m = wiersz, a n = kolumna, Elementy macierzy numerujemy następująco: ł łł a11 a12 a13 ł a21 a22 a23 ł a31 a32 a33 Tworzymy macierz współczynników A: ł łł 1 2 1 ł ł A = 3 8 1 0 4 1 Element osiowy Pierwszy element w macierzy A w lewym górnym rogu nazywany jest elementem osiowym (ang. pivot). Elementów osiowych szukamy na omówionej wcześniej diagonali. Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 7 / 52 Metoda eliminacji Gaussa ł łł 1 2 1 ł ł A = 3 8 1 0 4 1 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 8 / 52 Metoda eliminacji Gaussa ł łł 1 2 1 ł ł A = 3 8 1 0 4 1 Dokonujemy eliminacji wszystkich elementów niezerowych pod elementem osiowym (A11). Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 9 / 52 Metoda eliminacji Gaussa ł łł 1 2 1 ł ł A = 3 8 1 0 4 1 Dokonujemy eliminacji wszystkich elementów niezerowych pod elementem osiowym (A11). Mnożymy pierwszy wiersz przez -3 i dodajemy do drugiego wiersza. Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 9 / 52 Metoda eliminacji Gaussa ł łł 1 2 1 ł ł A = 3 8 1 0 4 1 Dokonujemy eliminacji wszystkich elementów niezerowych pod elementem osiowym (A11). Mnożymy pierwszy wiersz przez -3 i dodajemy do drugiego wiersza. (A11 -3) + A21 = 0 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 9 / 52 Metoda eliminacji Gaussa ł łł 1 2 1 ł ł A = 3 8 1 0 4 1 Dokonujemy eliminacji wszystkich elementów niezerowych pod elementem osiowym (A11). Mnożymy pierwszy wiersz przez -3 i dodajemy do drugiego wiersza. (A11 -3) + A21 = 0 (A12 -3) + A22 = 2 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 9 / 52 Metoda eliminacji Gaussa ł łł 1 2 1 ł ł A = 3 8 1 0 4 1 Dokonujemy eliminacji wszystkich elementów niezerowych pod elementem osiowym (A11). Mnożymy pierwszy wiersz przez -3 i dodajemy do drugiego wiersza. (A11 -3) + A21 = 0 (A12 -3) + A22 = 2 (A13 -3) + A23 = -2 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 9 / 52 Metoda eliminacji Gaussa Utworzyliśmy nowy drugi wiersz macierzy z wyzerowanymi wartościami pod elementem osiowym: ł łł ł łł 1 2 1 1 2 1 ł ł ł ł A = 3 8 1 0 2 -2 0 4 1 0 4 1 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 10 / 52 Metoda eliminacji Gaussa ł łł ł łł 1 2 1 1 2 1 ł ł ł ł A = 3 8 1 0 2 -2 0 4 1 0 4 1 Kolejny element osiowy na diagonali: 2 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 11 / 52 Metoda eliminacji Gaussa ł łł ł łł 1 2 1 1 2 1 ł ł ł ł A = 3 8 1 0 2 -2 0 4 1 0 4 1 Kolejny element osiowy na diagonali: 2 Musimy pozbyć się 4 pod elementem osiowym. Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 11 / 52 Metoda eliminacji Gaussa ł łł ł łł 1 2 1 1 2 1 ł ł ł ł A = 3 8 1 0 2 -2 0 4 1 0 4 1 Kolejny element osiowy na diagonali: 2 Musimy pozbyć się 4 pod elementem osiowym. Mnożymy drugi wiersz przez -2 i dodajemy do trzeciego wiersza. Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 11 / 52 Metoda eliminacji Gaussa ł łł ł łł 1 2 1 1 2 1 ł ł ł ł A = 3 8 1 0 2 -2 0 4 1 0 4 1 Kolejny element osiowy na diagonali: 2 Musimy pozbyć się 4 pod elementem osiowym. Mnożymy drugi wiersz przez -2 i dodajemy do trzeciego wiersza. (A21 -2) + A31 = 0 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 11 / 52 Metoda eliminacji Gaussa ł łł ł łł 1 2 1 1 2 1 ł ł ł ł A = 3 8 1 0 2 -2 0 4 1 0 4 1 Kolejny element osiowy na diagonali: 2 Musimy pozbyć się 4 pod elementem osiowym. Mnożymy drugi wiersz przez -2 i dodajemy do trzeciego wiersza. (A21 -2) + A31 = 0 (A22 -2) + A32 = 0 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 11 / 52 Metoda eliminacji Gaussa ł łł ł łł 1 2 1 1 2 1 ł ł ł ł A = 3 8 1 0 2 -2 0 4 1 0 4 1 Kolejny element osiowy na diagonali: 2 Musimy pozbyć się 4 pod elementem osiowym. Mnożymy drugi wiersz przez -2 i dodajemy do trzeciego wiersza. (A21 -2) + A31 = 0 (A22 -2) + A32 = 0 (A23 -2) + A33 = 5 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 11 / 52 Metoda eliminacji Gaussa Utworzyliśmy nowy trzeci wiersz macierzy: ł łł ł łł ł łł 1 2 1 1 2 1 1 2 1 ł ł ł ł ł ł A = 3 8 1 0 2 -2 0 2 -2 0 4 1 0 4 1 0 0 5 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 12 / 52 Metoda eliminacji Gaussa Utworzyliśmy nowy trzeci wiersz macierzy: ł łł ł łł ł łł 1 2 1 1 2 1 1 2 1 ł ł ł ł ł ł A = 3 8 1 0 2 -2 0 2 -2 0 4 1 0 4 1 0 0 5 Otrzymaną macierz U nazywamy macierzą górnotrójkątną, która zawiera same 0 pod główną diagonalą macierzy. Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 12 / 52 Metoda eliminacji Gaussa Utworzyliśmy nowy trzeci wiersz macierzy: ł łł ł łł ł łł 1 2 1 1 2 1 1 2 1 ł ł ł ł ł ł A = 3 8 1 0 2 -2 0 2 -2 = U 0 4 1 0 4 1 0 0 5 Otrzymaną macierz U nazywamy macierzą górnotrójkątną, która zawiera same 0 pod główną diagonalą macierzy. Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 13 / 52 Metoda eliminacji Gaussa Utworzyliśmy nowy trzeci wiersz macierzy: ł łł ł łł ł łł 1 2 1 1 2 1 1 2 1 ł ł ł ł ł ł A = 3 8 1 0 2 -2 0 2 -2 = U 0 4 1 0 4 1 0 0 5 Otrzymaną macierz U nazywamy macierzą górnotrójkątną, która zawiera same 0 pod główną diagonalą macierzy. Uwaga! W przypadku, gdy element osiowy drogą eliminacji stanie się zerem, musimy zamienić wiersz z wierszem znajdującym się poniżej i kontynuować proces eliminacji. Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 14 / 52 Metoda eliminacji Gaussa Macierz rozszerzona Macierz A można rozszerzyć o wektor b będący rozwiązaniami układu równań. Powstaje wówczas macierz rozszerzona. Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 15 / 52 Metoda eliminacji Gaussa Macierz rozszerzona Macierz A można rozszerzyć o wektor b będący rozwiązaniami układu równań. Powstaje wówczas macierz rozszerzona ł łł 1 2 1 | 2 ł ł A = 3 8 1 | 12 0 4 1 | 2 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 16 / 52 Metoda eliminacji Gaussa Macierz rozszerzona Macierz A można rozszerzyć o wektor b będący rozwiązaniami układu równań. Powstaje wówczas macierz rozszerzona ł łł 1 2 1 | 2 ł ł A = 3 8 1 | 12 0 4 1 | 2 W momencie stosowania eliminacji Gaussa możemy jednocześnie operować na ostatniej kolumnie znajdując tym samym wartości wektora b. Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 16 / 52 Metoda eliminacji Gaussa Zatem: ł łł 1 2 1 | 2 ł ł A = 3 8 1 | 12 0 4 1 | 2 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 17 / 52 Metoda eliminacji Gaussa Zatem: ł łł ł łł 1 2 1 | 2 1 2 1 | 2 ł ł ł ł A = 3 8 1 | 12 0 2 -2 | 6 0 4 1 | 2 0 4 1 | 2 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 18 / 52 Metoda eliminacji Gaussa Zatem: ł łł ł łł 1 2 1 | 2 1 2 1 | 2 ł ł ł ł A = 3 8 1 | 12 0 2 -2 | 6 0 4 1 | 2 0 4 1 | 2 ł łł 1 2 1 | 2 ł ł 0 2 -2 | 6 0 0 5 | -10 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 19 / 52 Metoda eliminacji Gaussa Ostatecznie znając postać macierzy U, oraz wektora b możemy zapisać uproszczony układ równań: Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 20 / 52 Metoda eliminacji Gaussa Ostatecznie znając postać macierzy U, oraz wektora b możemy zapisać uproszczony układ równań: ńł a + 2b + c = 2 ł 2b - 2c = 6 ół 5c = -10 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 21 / 52 Metoda eliminacji Gaussa Ostatecznie znając postać macierzy U, oraz wektora b możemy zapisać uproszczony układ równań: ńł a + 2b + c = 2 ł 2b - 2c = 6 ół 5c = -10 Rozwiązaniem układu równań są liczby a = 6, b = -1, c = -2 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 22 / 52 Metoda eliminacji Gaussa - ćwiczenie Rozwiąż metodą Gaussa równanie: ńł 2a + 4b + -2c = 2 ł 4a + 9b - 3c = 8 ół -2a - 3b + 7c = 10 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 23 / 52 Metoda eliminacji Gaussa - ćwiczenie Tworzę rozszerzoną macierz A współczynników i wektora b: ł łł 2 4 -2 | 2 ł ł A = 4 9 -3 | 8 -2 -3 7 | 10 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 24 / 52 Metoda eliminacji Gaussa - ćwiczenie Tworzę rozszerzoną macierz A współczynników i wektora b: ł łł 2 4 -2 | 2 ł ł A = 4 9 -3 | 8 -2 -3 7 | 10 Pierwszy element osiowy: 2 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 25 / 52 Metoda eliminacji Gaussa - ćwiczenie Tworzę rozszerzoną macierz A współczynników i wektora b: ł łł 2 4 -2 | 2 ł ł A = 4 9 -3 | 8 -2 -3 7 | 10 Pierwszy element osiowy: 2 Chcąc pozbyć się najpierw 4 mnożymy pierwszy wiersz przez -2 i dodajemy do drugiego: Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 26 / 52 Metoda eliminacji Gaussa - ćwiczenie Tworzę rozszerzoną macierz A współczynników i wektora b: ł łł 2 4 -2 | 2 ł ł A = 4 9 -3 | 8 -2 -3 7 | 10 Pierwszy element osiowy: 2 Chcąc pozbyć się najpierw 4 mnożymy pierwszy wiersz przez -2 i dodajemy do drugiego: (A11 -2) + A21 = 0 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 26 / 52 Metoda eliminacji Gaussa - ćwiczenie Tworzę rozszerzoną macierz A współczynników i wektora b: ł łł 2 4 -2 | 2 ł ł A = 4 9 -3 | 8 -2 -3 7 | 10 Pierwszy element osiowy: 2 Chcąc pozbyć się najpierw 4 mnożymy pierwszy wiersz przez -2 i dodajemy do drugiego: (A11 -2) + A21 = 0 (A12 -2) + A22 = 1 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 26 / 52 Metoda eliminacji Gaussa - ćwiczenie Tworzę rozszerzoną macierz A współczynników i wektora b: ł łł 2 4 -2 | 2 ł ł A = 4 9 -3 | 8 -2 -3 7 | 10 Pierwszy element osiowy: 2 Chcąc pozbyć się najpierw 4 mnożymy pierwszy wiersz przez -2 i dodajemy do drugiego: (A11 -2) + A21 = 0 (A12 -2) + A22 = 1 (A13 -2) + A23 = 1 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 26 / 52 Metoda eliminacji Gaussa - ćwiczenie ł łł ł łł 2 4 -2 | 2 2 4 -2 | 2 ł ł ł ł A = 4 9 -3 | 8 0 1 1 | 4 -2 -3 7 | 10 -2 -3 7 | 10 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 27 / 52 Metoda eliminacji Gaussa - ćwiczenie ł łł ł łł 2 4 -2 | 2 2 4 -2 | 2 ł ł ł ł A = 4 9 -3 | 8 0 1 1 | 4 -2 -3 7 | 10 -2 -3 7 | 10 Pozbywamy się -2 pod pierwszym elementem osiowym. Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 27 / 52 Metoda eliminacji Gaussa - ćwiczenie ł łł ł łł 2 4 -2 | 2 2 4 -2 | 2 ł ł ł ł A = 4 9 -3 | 8 0 1 1 | 4 -2 -3 7 | 10 -2 -3 7 | 10 Pozbywamy się -2 pod pierwszym elementem osiowym. Mnożymy pierwszy wiersz przez 1 i dodajemy do drugiego: Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 27 / 52 Metoda eliminacji Gaussa - ćwiczenie ł łł ł łł 2 4 -2 | 2 2 4 -2 | 2 ł ł ł ł A = 4 9 -3 | 8 0 1 1 | 4 -2 -3 7 | 10 -2 -3 7 | 10 Pozbywamy się -2 pod pierwszym elementem osiowym. Mnożymy pierwszy wiersz przez 1 i dodajemy do drugiego: (A11 1) + A31 = 0 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 27 / 52 Metoda eliminacji Gaussa - ćwiczenie ł łł ł łł 2 4 -2 | 2 2 4 -2 | 2 ł ł ł ł A = 4 9 -3 | 8 0 1 1 | 4 -2 -3 7 | 10 -2 -3 7 | 10 Pozbywamy się -2 pod pierwszym elementem osiowym. Mnożymy pierwszy wiersz przez 1 i dodajemy do drugiego: (A11 1) + A31 = 0 (A12 1) + A32 = 1 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 27 / 52 Metoda eliminacji Gaussa - ćwiczenie ł łł ł łł 2 4 -2 | 2 2 4 -2 | 2 ł ł ł ł A = 4 9 -3 | 8 0 1 1 | 4 -2 -3 7 | 10 -2 -3 7 | 10 Pozbywamy się -2 pod pierwszym elementem osiowym. Mnożymy pierwszy wiersz przez 1 i dodajemy do drugiego: (A11 1) + A31 = 0 (A12 1) + A32 = 1 (A13 1) + A33 = 5 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 27 / 52 Metoda eliminacji Gaussa - ćwiczenie ł łł ł łł 2 4 -2 | 2 2 4 -2 | 2 ł ł ł ł A = 4 9 -3 | 8 0 1 1 | 4 -2 -3 7 | 10 -2 -3 7 | 10 ł łł 2 4 -2 | 2 ł ł 0 1 1 | 4 0 1 5 | 12 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 28 / 52 Metoda eliminacji Gaussa - ćwiczenie ł łł ł łł 2 4 -2 | 2 2 4 -2 | 2 ł ł ł ł A = 4 9 -3 | 8 0 1 1 | 4 -2 -3 7 | 10 -2 -3 7 | 10 ł łł 2 4 -2 | 2 ł ł 0 1 1 | 4 0 1 5 | 12 Drugi element osiowy: 1 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 29 / 52 Metoda eliminacji Gaussa - ćwiczenie ł łł ł łł 2 4 -2 | 2 2 4 -2 | 2 ł ł ł ł A = 4 9 -3 | 8 0 1 1 | 4 -2 -3 7 | 10 -2 -3 7 | 10 ł łł 2 4 -2 | 2 ł ł 0 1 1 | 4 0 1 5 | 12 Drugi element osiowy: 1 Mnożymy drugi wiersz przez -1 i dodajemy do trzeciego: Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 30 / 52 Metoda eliminacji Gaussa - ćwiczenie ł łł ł łł 2 4 -2 | 2 2 4 -2 | 2 ł ł ł ł A = 4 9 -3 | 8 0 1 1 | 4 -2 -3 7 | 10 -2 -3 7 | 10 ł łł 2 4 -2 | 2 ł ł 0 1 1 | 4 0 1 5 | 12 Drugi element osiowy: 1 Mnożymy drugi wiersz przez -1 i dodajemy do trzeciego: (A21 -1) + A31 = 0 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 30 / 52 Metoda eliminacji Gaussa - ćwiczenie ł łł ł łł 2 4 -2 | 2 2 4 -2 | 2 ł ł ł ł A = 4 9 -3 | 8 0 1 1 | 4 -2 -3 7 | 10 -2 -3 7 | 10 ł łł 2 4 -2 | 2 ł ł 0 1 1 | 4 0 1 5 | 12 Drugi element osiowy: 1 Mnożymy drugi wiersz przez -1 i dodajemy do trzeciego: (A21 -1) + A31 = 0 (A22 -1) + A32 = 0 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 30 / 52 Metoda eliminacji Gaussa - ćwiczenie ł łł ł łł 2 4 -2 | 2 2 4 -2 | 2 ł ł ł ł A = 4 9 -3 | 8 0 1 1 | 4 -2 -3 7 | 10 -2 -3 7 | 10 ł łł 2 4 -2 | 2 ł ł 0 1 1 | 4 0 1 5 | 12 Drugi element osiowy: 1 Mnożymy drugi wiersz przez -1 i dodajemy do trzeciego: (A21 -1) + A31 = 0 (A22 -1) + A32 = 0 (A23 -1) + A33 = 4 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 30 / 52 Metoda eliminacji Gaussa - ćwiczenie ł łł ł łł 2 4 -2 | 2 2 4 -2 | 2 ł ł ł ł A = 4 9 -3 | 8 0 1 1 | 4 -2 -3 7 | 10 -2 -3 7 | 10 ł łł ł łł 2 4 -2 | 2 2 4 -2 | 2 ł ł ł ł 0 1 1 | 4 0 1 1 | 4 = U 0 1 5 | 12 0 0 4 | 8 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 31 / 52 Metoda eliminacji Gaussa - ćwiczenie Podstawiając pod układ równań otrzymujemy: ńł 2a + 4b + -2c = 2 ł b + c = 4 ół 4c = 8 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 32 / 52 Metoda eliminacji Gaussa - ćwiczenie Podstawiając pod układ równań otrzymujemy: ńł 2a + 4b + -2c = 2 ł b + c = 4 ół 4c = 8 Zatem: a = -1, b = 2, c = 2 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 32 / 52 Macierze eliminacji Pierwszy przykład: ł łł 1 2 1 ł ł A = 3 8 1 0 4 1 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 33 / 52 Macierze eliminacji Pierwszy przykład: ł łł 1 2 1 ł ł A = 3 8 1 0 4 1 Eliminacja elementu (2, 1) macierzy polegała na przekształceniu macierzy poprzez pomnożenie pierwszego wiersza przez -3 i dodanie go do drugiego wiersza. Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 33 / 52 Macierze eliminacji Pierwszy przykład: ł łł 1 2 1 ł ł A = 3 8 1 0 4 1 Eliminacja elementu (2, 1) macierzy polegała na przekształceniu macierzy poprzez pomnożenie pierwszego wiersza przez -3 i dodanie go do drugiego wiersza. Możemy to krótko zapisać w postaci mnożenia macierzy A przez macierz elementarną E21 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 33 / 52 Macierze eliminacji Pierwszy przykład: ł łł 1 2 1 ł ł A = 3 8 1 0 4 1 Eliminacja elementu (2, 1) macierzy polegała na przekształceniu macierzy poprzez pomnożenie pierwszego wiersza przez -3 i dodanie go do drugiego wiersza. Możemy to krótko zapisać w postaci mnożenia macierzy A przez macierz elementarną E21 ł łł ł łł ł łł 1 0 0 1 2 1 1 2 1 ł ł ł ł ł ł E21A = -3 1 0 3 8 1 = 0 2 -2 0 0 1 0 4 1 0 4 1 E21 A E21A Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 34 / 52 Macierze eliminacji ł łł 1 2 1 ł ł E21A = 0 2 -2 0 4 1 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 35 / 52 Macierze eliminacji ł łł 1 2 1 ł ł E21A = 0 2 -2 0 4 1 Eliminacja elementu (3, 2) macierzy polegała na przekształceniu macierzy poprzez pomnożenie drugiego wiersza przez -2 i dodanie go do trzeciego wiersza. Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 35 / 52 Macierze eliminacji ł łł 1 2 1 ł ł E21A = 0 2 -2 0 4 1 Eliminacja elementu (3, 2) macierzy polegała na przekształceniu macierzy poprzez pomnożenie drugiego wiersza przez -2 i dodanie go do trzeciego wiersza. Możemy to krótko zapisać w postaci mnożenia macierzyE21A przez macierz elementarną E32 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 35 / 52 Macierze eliminacji ł łł 1 2 1 ł ł E21A = 0 2 -2 0 4 1 Eliminacja elementu (3, 2) macierzy polegała na przekształceniu macierzy poprzez pomnożenie drugiego wiersza przez -2 i dodanie go do trzeciego wiersza. Możemy to krótko zapisać w postaci mnożenia macierzyE21A przez macierz elementarną E32 ł łł ł łł ł łł 1 0 0 1 2 1 1 2 1 ł ł ł ł ł ł E32(E21A) = 0 1 0 0 2 -2 = 0 2 -2 = U 0 -2 1 0 4 1 0 0 5 E32 (E21A) E32(E21A) Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 36 / 52 Macierze eliminacji Pamiętając o tym, że mnożenie macierzy jest łączne możemy wywnioskować: E32 E21 A = U Uwaga! Macierze eliminacji zawsze zapisujemy od ostatniej znalezionej ku pierwszej co wynika z tego, że mnożenie macierzy nie jest przemienne. Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 37 / 52 Permutacje Działanie permutacji Macierze permutacji przekształcają macierze względem kolumn lub wierszy w zależności po której stronie równania występują. Uwaga! Należy pamiętać, że macierz permutacji musi mieć ten sam wymiar co macierz, na której działamy. Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 38 / 52 Permutacje Macierz permutacji z prawej strony: a b 0 1 b c = c d 1 0 d a Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 39 / 52 Permutacje Macierz permutacji z prawej strony: a b 0 1 b c = c d 1 0 d a Mnożąc macierz przez macierz permutacji z prawej strony dokonujemy przekształceń kolumnowych. W efekcie w powyższym przypadku pierwszą kolumnę zapisujemy w miejsce drugiej kolumny, a drugą kolumnę w miejsce pierwszej kolumny. Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 39 / 52 Permutacje Macierz permutacji z prawej strony: a b 0 1 b c = c d 1 0 d a Mnożąc macierz przez macierz permutacji z prawej strony dokonujemy przekształceń kolumnowych. W efekcie w powyższym przypadku pierwszą kolumnę zapisujemy w miejsce drugiej kolumny, a drugą kolumnę w miejsce pierwszej kolumny. Macierz permutacji z lewej strony: 0 1 a b c d = 1 0 c d a b Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 39 / 52 Permutacje Macierz permutacji z prawej strony: a b 0 1 b c = c d 1 0 d a Mnożąc macierz przez macierz permutacji z prawej strony dokonujemy przekształceń kolumnowych. W efekcie w powyższym przypadku pierwszą kolumnę zapisujemy w miejsce drugiej kolumny, a drugą kolumnę w miejsce pierwszej kolumny. Macierz permutacji z lewej strony: 0 1 a b c d = 1 0 c d a b Mnożąc macierz przez macierz permutacji z lewej strony dokonujemy przekształceń wierszowych. Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 39 / 52 Permutacje - ćwiczenie Jaka macierz przekształca macierz A w macierz B ? ł łł 4 8 9 ł ł A = 5 2 3 4 9 1 ł łł 4 9 8 ł ł B = 5 3 2 4 1 9 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 40 / 52 Permutacje - ćwiczenie Jaka macierz przekształca macierz A w macierz B ? ł łł 4 8 9 ł ł A = 5 2 3 4 9 1 ł łł 4 9 8 ł ł B = 5 3 2 4 1 9 ł łł 1 0 0 ł ł P = 0 0 1 0 1 0 Jest to macierz permutacji, która występuje z prawej strony macierzy A, gdyż dochodzi do przekształceń kolumnowych. Druga kolumna została zamieniona z trzecią. Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 41 / 52 Macierz odwrotna Powróćmy do jednej z macierzy eliminacji: ł łł 1 0 0 ł ł E21 = -3 1 0 0 0 1 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 42 / 52 Macierz odwrotna Powróćmy do jednej z macierzy eliminacji: ł łł 1 0 0 ł ł E21 = -3 1 0 0 0 1 Była to macierz mnożąca pierwszy wiersz przez -3 i dodająca wynik do drugiego wiersza. Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 42 / 52 Macierz odwrotna Powróćmy do jednej z macierzy eliminacji: ł łł 1 0 0 ł ł E21 = -3 1 0 0 0 1 Była to macierz mnożąca pierwszy wiersz przez -3 i dodająca wynik do drugiego wiersza. Szukając macierzy do niej odwrotnej szukamy macierzy, która cofa tę operację. Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 42 / 52 Macierz odwrotna Powróćmy do jednej z macierzy eliminacji: ł łł 1 0 0 ł ł E21 = -3 1 0 0 0 1 Była to macierz mnożąca pierwszy wiersz przez -3 i dodająca wynik do drugiego wiersza. Szukając macierzy do niej odwrotnej szukamy macierzy, która cofa tę operację. Będzie to macierz, która pomnoży pierwszy wiersz przez 3 i doda do drugiego: Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 42 / 52 Macierz odwrotna Powróćmy do jednej z macierzy eliminacji: ł łł 1 0 0 ł ł E21 = -3 1 0 0 0 1 Była to macierz mnożąca pierwszy wiersz przez -3 i dodająca wynik do drugiego wiersza. Szukając macierzy do niej odwrotnej szukamy macierzy, która cofa tę operację. Będzie to macierz, która pomnoży pierwszy wiersz przez 3 i doda do drugiego: ł łł 1 0 0 -1 ł ł E21 = 3 1 0 0 0 1 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 43 / 52 Macierz odwrotna Macierz identycznościowa Iloczyn macierzy i macierzy do niej odwrotnej daje macierz identycznościową. Zawiera ona jedynki na swojej diagonali, oraz same zera. ł łł ł łł ł łł 1 0 0 1 0 0 1 0 0 ł ł ł ł ł ł -3 1 0 3 1 0 = 0 1 0 = I 0 0 1 0 0 1 0 0 1 -1 E21 E21 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 44 / 52 Zadanie 1 Rozwiąż układ równań metodą eliminacji Gaussa i znajdz macierze eliminacji: ńł a + b + c = 4 ł a + 2b + 4c = 8 ół a + 3b + 9c = 14 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 45 / 52 Zadanie 2 Znajdz macierz permutacji, która przekształca macierz A do macierzy B: ł łł 7 17 2 ł ł A = 1 2 5 7 14 32 ł łł 7 14 32 ł ł B = 7 17 2 1 2 5 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 46 / 52 Zadanie 1 - rozwiązanie ł łł 1 1 1 | 4 ł ł A = 1 2 4 | 8 1 3 9 | 14 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 47 / 52 Zadanie 1 - rozwiązanie ł łł ł łł 1 1 1 | 4 1 1 1 | 4 1Row-1 ł ł ł ł A = 1 2 4 | 8 ----- 0 1 3 | 4 1 3 9 | 14 0 2 8 | 10 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 48 / 52 Zadanie 1 - rozwiązanie ł łł ł łł 1 1 1 | 4 1 1 1 | 4 1Row-1 ł ł ł ł A = 1 2 4 | 8 ----- 0 1 3 | 4 1 3 9 | 14 0 2 8 | 10 ł łł 1 1 1 | 4 2Row-2 ł ł ----- 0 1 3 | 4 0 0 2 | 2 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 49 / 52 Zadanie 1 - rozwiązanie ł łł ł łł 1 1 1 | 4 1 1 1 | 4 1Row-1 ł ł ł ł A = 1 2 4 | 8 ----- 0 1 3 | 4 1 3 9 | 14 0 2 8 | 10 ł łł 1 1 1 | 4 2Row-2 ł ł ----- 0 1 3 | 4 0 0 2 | 2 ńł a + b + c = 4 ł b + 3c = 4 ół 2c = 2 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 50 / 52 Zadanie 1 - rozwiązanie ł łł ł łł 1 1 1 | 4 1 1 1 | 4 1Row-1 ł ł ł ł A = 1 2 4 | 8 ----- 0 1 3 | 4 1 3 9 | 14 0 2 8 | 10 ł łł 1 1 1 | 4 2Row-2 ł ł ----- 0 1 3 | 4 0 0 2 | 2 ńł a + b + c = 4 ł b + 3c = 4 ół 2c = 2 a = 2, b = 1, c = 1 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 51 / 52 Zadanie 2 - rozwiązanie ł łł ł łł ł łł 0 1 0 7 17 2 7 14 32 ł ł ł ł ł ł 0 0 1 1 2 5 = 7 17 2 1 0 0 7 14 32 1 2 5 Mikołaj Buda i Filip Wiśniewski Metoda eliminacji Gaussa 15 grudnia 2012 52 / 52