Macierz odwrotna: Algorytm obliczania
- Szczegóły
Po zaprezentowaniu podstawowych operacji na macierzach, warto skupić się na bardziej zaawansowanych zagadnieniach, takich jak obliczanie macierzy odwrotnej. Odwracanie macierzy jest uogólnieniem dzielenia liczb. Macierz odwrotna nie istnieje dla macierzy osobliwych.
Czym jest macierz odwrotna?
Macierz odwrotna do macierzy kwadratowej A (ozn. A-1) to taka macierz, która pomnożona przez macierz A (z lewej lub prawej strony) daje macierz jednostkową I. Innymi słowy, gdy pomnożymy macierz A przez macierz do niej odwrotną (lub wykonamy to mnożenie w odwrotnej kolejności, tzn. A-1 * A), to otrzymamy macierz jednostkową.
Macierz odwrotna istnieje tylko dla tzw. macierzy nieosobliwych (czyli takich, których wyznacznik jest różny od zera). Dodatkowe informacje można znaleźć pod hasłami macierz osobliwa, uogólniona macierz odwrotna.
Jak obliczyć macierz odwrotną?
Aby znaleźć wartości niewiadomych, możemy zastosować wzory Cramera, które opierają się na dzieleniu przez siebie wyznaczników macierzy.
A-1=AD⋅1/detA
Przeczytaj także: DBK w medycynie
Od razu widzimy, że do obliczenia potrzebny jest wyznacznik i że nie może być równy 0.
AD=[Aij]T
A w jaki sposób liczymy dopełnienie algebraiczne? Jest to wyznacznik, a zatem obliczamy go za pomocą tego samego wzoru. Jako wiersz rozwinięcia wybierzemy pierwszy wiersz zawierający elementy 1, 2 i 3. Obliczamy wyznaczniki M. Minory macierzy o rozmiarze 2 są macierzami jednoelementowymi. wybieramy dowolny wiersz lub kolumnę (najlepiej taki, w którym jest najwięcej zer). rekurencyjnie tą samą metodą).
Algorytmy obliczania wyznacznika macierzy
Pierwszy sposób to nic innego jak przeniesienie na język programowania opisanego przeze mnie wyżej rozwinięcia Laplace'a. Jak już pisałem wcześniej, rozwinięcie Laplace'a jest bardzo niewydajne obliczeniowo. Jego złożoność to aż O(n!)\Omicron(n!) (nn to stopień macierzy, !! to silnia), czyli jedna z najgorszych złożoności, z jakimi mamy do czynienia w algorytmice.
Oczywiście moglibyśmy kod nieco zoptymalizować - znamy dokładne wzory na wyznaczniki dla macierzy 2×2 i 3×3, więc moglibyśmy szybciej ucinać rekurencję.
Przeczytaj także: Wzór na macierz odwrotną - wyjaśnienie
Zdecydowanie wydajniejszym podejściem jest metoda Bareissa (opublikowana w 1967 r.; znana też jako metoda Montantego), która jednak wymaga nieco więcej wstępu teoretycznego, bo jest to modyfikacja innego sposobu ręcznego obliczania wyznaczników - metody eliminacji Gaussa.
Samej metody gaussowskiej pokazywać jednak nie będę, zachęcam do doczytania na własną rękę. W metodzie Gaussa wyznacznik obliczamy przez wcześniejsze uproszczenie macierzy do macierzy trójkątnej (czyli zawierającej wartości różne od zera tylko na głównej przekątnej i nad nią).
Aby to osiągnąć, wykonuje dzielenia wartości na wierszach, co wprowadza błędy przybliżeń, a jak chcemy patrzeć dogłębniej, jest wolniejszą operacją niż dodawanie czy mnożenie.
Najczęściej spotykana implementacja algorytmu zupełnie porzuca ideę osiągania macierzy trójkątnej, jak to jest w metodzie Gaussa. Zamiast tego wykorzystujemy przekątną, żeby zapisywać minory główne macierzy.
Minory główne to wyznaczniki macierzy powstałych przez usunięcie wierszy i kolumn o tych samych indeksach. Stąd możemy już się domyślić, że skoro przekątna zawiera wyznaczniki fragmentów macierzy, stopniowo coraz większych, to na końcu przekątnej będzie wyznacznik całej macierzy.
Przeczytaj także: Wnioski z obliczania macierzy odwrotnej
Jest to podejście, które nie pozbywa się dzielenia, ale nie doprowadza do wartości ułamkowych, stąd też spotkamy się czasem w literaturze z nazwą FFGE (Fraction Free Gaussian Elimination, po pol. Tworzymy macierz pomocniczą B, która w tym momencie jest kopią macierzy wejściowej.
Otwieramy trzy zagnieżdżone iteracje. Idea jest taka, że mamy okno obliczeniowe, które rozpoczynamy od całości macierzy, a potem odcinamy wiersz z kolumną o tych samych indeksach, idąc od lewego górnego rogu do prawego dolnego.
Jak wspomniałem wcześniej, na przekątnej zostawiamy wówczas wartość minora. Obliczymy nową wartość elementu B[i][j]. Dzielną obliczamy przez pomnożenie aktualnego B[i][j] przez lewy górny róg okna obliczeniowego, odejmując od tego iloczyn elementu najwyżej (w aktualnym oknie) nad B[i][j] i najbardziej na lewo (też w aktualnym oknie) od B[i][j].
Dzielnik to ostatnio obliczony minor, czyli wartość B[k−1][k−1]. Zwracamy wartość w B[n−1][n−1]. Powyższe kroki możemy bardzo łatwo przepisać na kod. Jak widać na pierwszy rzut oka, mamy trzy zagnieżdżone iteracje zawsze iterujące do n. Oznacza to, że złożoność obliczeniowa algorytmu wynosi O(n3)\Omicron(n^3).
Oczywiście nie są to jedyne algorytmy do obliczania wyznacznika macierzy. Wzór Leibnitza - wykorzystuje do obliczeń permutacje elementów macierzy. Algorytm Berkowitza - w przeciwieństwie do algorytmu Bareissa całkowicie eliminuje potrzebę dzielenia, a nie tylko zapewnia brak ułamków. Do tego algorytm można zrównoleglić i ma też inne zastosowania niż tylko obliczanie wyznaczników.
Algorytm Dodgsona - bardzo podobny do metody rozwinięć Laplace'a, aczkolwiek tutaj mimo dzielenia na mniejsze macierze cały czas trzymamy się zapisu wewnątrz jednej macierzy. Złożoność (o ile dobrze znalazłem) wynosi O(22n)\Omicron(2^{2n}).
Zastosowania wyznacznika i macierzy odwrotnej
Jednym z najpowszechniejszych zastosowań wyznaczników macierzy jest obliczanie za ich pomocą układów równań liniowych.
W ogólny sposób można to zapisać jako: AX=B
Wykorzystując wzory Cramera, możesz wyprowadzić sobie uniwersalne wzory do rozwiązywania układów równań. Nawet łatwo znajdziesz takie dla 2 i 3 niewiadomych.
Jak ostatnio pokazywałem mnożenie macierzy, tak nie pokazywałem dzielenia ani tym bardziej wynikającego z niego faktu, że gdy dzielimy liczbę przez samą siebie, to dostajemy 1.
Jak obliczać pola i objętości, to możemy także w ten sposób obliczać iloczyn wektorowy zgodnie z jego geometryczną interpretacją.
Jeśli czytałeś(-aś) wcześniej mojego bloga, możesz kojarzyć to zastosowanie, ponieważ wykorzystałem je do wykrywania lewoskrętów przy wyznaczaniu otoczki wypukłej.
Rozwijając to, możemy w bardzo analogiczny sposób sprawdzić, czy trzy punkty są współliniowe. Przy bardziej zaawansowanych zagadnieniach z analizy matematycznej spotkasz się z hesjanami, jakobianami i wrońskianami. Są to wyznaczniki, kolejno: macierzy Hessego, Jacobiego i Wrońskiego.
Żeby to obliczyć, musielibyśmy najpierw odwrócić macierz A i dopiero potem obliczyć wyznacznik macierzy A-1.
\[\det(A^{-1})=(detA)^{-1}\]
która mówi, że zamiast męczyć się z odwracaniem samej macierzy, możemy najpierw obliczyć wyznacznik...
Wystarczy przypomnieć sobie, że wyznacznik macierzy to nic innego jak zwykła liczba rzeczywista, więc (detA)-1 to po prostu jakaś liczba podniesiona do potęgi "-1", czyli odwrotność, tzn.
tags: #macierz #odwrotna #algorytm #obliczania
