Odwracanie macierzy 4×4

Do napisania czegokolwiek z dziedziny programowania gier lub grafiki potrzebna jest zawsze chociaż skromna biblioteka, zawierają podstawowe obiekty matematyczne. Jej częścią na pewno muszą być wektory, a nie od rzeczy są także macierze, kwaterniony, obiekty reprezentujące linie i płaszczyzny, i tak dalej. Taką bibliotekę zwykle albo pisze się raz, albo wykorzystuje jedną z już istniejących. Jakikolwiek byłby nasz wybór, mogłoby się wydawać, że sprawę z nią można załatwić raz na zawsze.
Cóż, nic bardziej błędnego :) Możemy być oczywiście bardzo przywiązani do narzędzi, którymi się posługujemy – języka programowania, platformy, itd. – ale kiedyś na pewno przyjdzie nam zmierzyć się z zupełnie innym językiem i innym środowiskiem. A wtedy trzeba jakoś ten problem matematycznej biblioteki rozwiązać choćby na szybko.

Ostatnio przytrafiło mi się właśnie coś takiego. Nie jest to naturalnie nic pasjonującego, bowiem implementowania dodawania, odejmowania czy mnożenia wektorów jest zajęciem raczej nużącym. Jednak okazało się, że istnieje przynajmniej jedna potrzebna, a niezbyt oczywista matematyczna operacja, którą należy koniecznie uwzględnić. To odwracanie macierzy.
Chcąc tego dokonać programowo, możemy wykorzystać na przykład któryś z tych trzech sposobów:

• Metoda bezpośrednia. Jest to prostu zaimplementowanie ręcznego sposobu odwracania macierzy, wykorzystywanego zazwyczaj w połączeniu z kartką i długopisem :) Dla tych, co przysypiali na wykładach z algebry (lub nie mieli jeszcze szczęścia na nie uczęszczać ;)) przypominam, że polega to na wykonaniu określonych operacji (mnożenia przez liczbę oraz dodawania) na wierszach naszej macierzy oraz jednocześnie na wierszach macierzy jednostkowej. W ich wyniku nasza macierz sama ma zmienić się w jednostkową, zaś ta druga będzie wtedy szukaną odwrotnością. Wiadomo skądinąd, że złożoność tego algorytmu to O(n³), gdzie n to wymiar macierzy.

  

• Rozwiązanie układów równań. Ta metoda wymaga posiadania procedury rozwiązującej układy równań, jak na przykład eliminacji Gaussa lub znajdowania rozkładu LU. Posługując się nią, możemy obliczyć kolejne wiersze macierzy odwrotnej i też zajmie nam to czas O(n³). Oczywiście trzeba jeszcze mieć (tj. napisać) rzeczoną procedurę, co już takie proste nie jest :)
• Dopełnienie algebraiczne. Ten sposób charakteryzuje się głównie tym, że wymaga obliczenia sporej liczby wyznaczników – nie tylko tej macierzy, którą odwracamy, ale i każdej z jej podmacierzy. Wiadomo zaś, ze wyliczanie wyznaczników nie należy do operacji tanich. W istocie złożoność tej metody odwracania leży gdzieś w okolicach wykładniczej.

Trzeba jednak zauważyć pewną rzecz. Otóż do celów graficznych potrzebujemy jedynie macierzy o stałym rozmiarze, i to niewielkim – zwykle 4×4. Przy tak małym rozmiarze danych złożoność algorytmu (która niejawnie zakłada, że rozmiar ten jest bardzo duży) nie jest miarodajna. Liczy się bowiem dokładna ilość faktycznie wykonywanych operacji. A przy takim podejściu spotyka nas niespodzianka, jako że najwyraźniej najlepsza okazuje się metoda ostatnia. Jest ona używana na przykład w funkcji D3DXMatrixInverse, zatem posiada całkiem dobrą rekomendację :)
I ma chyba tylko jedną wadę. Po rozpisaniu występującej w niej pętli (co jest możliwe, jeśli znamy z góry rozmiar macierzy) zamienia się ona w dość odstraszającą szpaltę kodu z kilkunastoma długimi, niemal identycznie wyglądającymi wierszami, które różnią się tylko permutacją cyferek oraz plusów i minusów. Ale przecież tak wygląda kod w zasadzie każdego działania na macierzach i właśnie dlatego tak lubimy je implementować ;-)

Be Sociable, Share!

• 
• 

Be Sociable, Share!

• 
• 

• Tweet
•