Był taki algorytm do odwracania macierz, ale bez używania tej dołączonej macierzy, inicjowanej na I = diagonal(1
), znaczy wyliczamy odwrotną na tej wejściowej - tak w miejscu, in situ.
https://pl.wikipedia.org/wiki/Metoda_eliminacji_Gaussa
chodzi o odwracanie bez używania tego A | I, co podwaja pamięć, jaki i liczbę operacji zapewne.
A | I -> I | A^-1
zamiast tego pajacowania ma być od razu - w miejscu, bez używania I:
A -> A^-1
Zamiast pajacowania in situ:P można zobaczyć artykuł na Wikipedii: https://en.wikipedia.org/wiki/Invertible_matrix#Methods_of_matrix_inversion , coś się powinno nadać.
lion137 napisał(a):
Zamiast pajacowania in situ:P można zobaczyć artykuł na Wikipedii: https://en.wikipedia.org/wiki/Invertible_matrix#Methods_of_matrix_inversion , coś się powinno nadać.
Nie ma tam tej metod.
Takie cos znalazłem: http://file.scirp.org/pdf/AM_2013100413422038.pdf
Pamiętam troszkę inną wersję, w której zamieniano kolumny na końcu, a tu tego nie widzę.
http://file.scirp.org/Html/37474.html
to jest jakaś prymitywna wersja, bo ograniczona do przypadku w którym nie ma zer na przekątnej.
Pełna wersja wymaga wymiany wierszy, jak i kolumn.
np. dla macierzy: A =
0 1
1 1
i ta metoda juŻ wysiada.
A^1 = ?
Pytanie jest po co Ci ten algorytm, odwracanie metoda Gaussa jest 1/3O(n^3), to przeciez te macierze Ci sie zmieszcza w pamieci.
lion137 napisał(a):
Pytanie jest po co Ci ten algorytm, odwracanie metoda Gaussa jest 1/3O(n^3), to przeciez te macierze Ci sie zmieszcza w pamieci.
Niby jakim cudem miałbyś uzyskać Gaussem 1/3 n^3, jeśli rozwiązanie układu wymaga w tej metodzie więcej od 1/2 n^3?
tam jest raczej 3n^3 albo i gorzej, z uwagi na operacje na macierzy: n x 2n;
natomiast metoda in-situ to chyba: n^3, czyli 3 razy szybciej.
Nie kłócmy się o detale, chcę Ci pomóc. Eliminacja Gaussa - Jordana jest 1/3O(n^3): Dla każdej kolumny wykonujemy n^2
działań, mamy n
kolumn, czyli w sumie jest całka z n^2
, czyli n^3/3
. Żeby odwrócić macierz trzeba jeszcze wykonać te obliczenia na dodatkowej macierzy, więc może być nawet 2 * n^3/3
. Ale nawet jak Ci sie uda ograniczyć do n^3/3
, to i tak trzecia potęga tutaj zamiata, nie wiem jaki Masz komputer, ale, powiedzmy, max niech będzie nawet 1000 x 1000, to chyba Będziesz mieć miejsce na dodatkowe milion floatów.
Co to za podejście?
Na papierze też można obliczać, zatem po co nam w ogóle komputer...
a i tak już wiem jak to obliczać w ogólnym przypadku;
niewiele roboty w stosunku do tej uproszczonej wersji, trzeba jedynie pamiętać zamiany wierszy,
więc konieczna będzie pomocnicza tablicy o rozmiarze n, w której zapisujemy pary indeksów tych zamienianych wierszy...
[i,j] x n;