Czy „technika kofaktora” do odwracania macierzy ma jakieś praktyczne znaczenie?

13

Tytuł jest pytaniem. Technika ta polega na użyciu „macierzy kofaktorów” lub „macierzy przylegającej” i daje wyraźne wzory na składniki odwrotności macierzy kwadratowej. Nie jest łatwo zrobić to ręcznie dla matrycy większej niż, powiedzmy, 3×3 . W przypadku macierzy n×n wymaga ona obliczenia wyznacznika samej macierzy i obliczenia n2 wyznaczników macierzy (n1)×(n1) . Zgaduję, że nie jest to przydatne w aplikacjach. Ale chciałbym potwierdzenia.

Nie pytam o teoretyczne znaczenie techniki w dowodzeniu twierdzeń o macierzach.

Stefan Smith
źródło

Odpowiedzi:

11

O(n)O(n3)

Wolfgang Bangerth
źródło
4
Dwie rzeczy, które chcę dodać: złożoność reguły Cramera (użycie wyznaczników do obliczenia odwrotności) to Która jest znacznie znacznie większa niż eliminacja Gaussa . Ponadto, ogólnie rzecz biorąc, nie chcesz obliczać odwrotności, chyba że absolutnie musisz. O ( n 3 )O(n!)O(n3)
Paweł
OTOH, mogą istnieć pewne okoliczności, w których preferowane może być rozszerzenie Laplace'a, np. Pasmowe macierze. Ale rzeczywiście, ogólnie rzecz biorąc, ekspansja Laplace'a ma złożoność . O(n!)
JM
3
@Stefan, tak, eliminacja Gaussa może być wykorzystana do obliczenia determinant. Ponieważ , a eliminacja Gaussa wytwarza czynniki (trójkątne), których wyznaczniki można łatwo obliczyć, to rzeczywiście przyjmie wysiłek. det(AB)=det(A)det(B)O(n3)
JM
1
Tak, masz rację - wyznacznik można obliczyć kosztem dekompozycji . (Naiwny sposób pokazany w podręcznikach z wykorzystaniem rekurencyjnego rozszerzenia jest wykładniczy w - złożoności Wspomnianej przez Pawła). Ale to wciąż daje ogólną złożoność dla proponowanego algorytmu - znacznie więcej niż eliminacja Gaussa, jeśli się go użyje, a nawet więcej niż iteracyjne solwery. LUnn!O(n5)
Wolfgang Bangerth
1
Poprawny. Redukcja wierszy stanowi połowę obliczania rozkładu . Zmniejsza do współczynnikaDruga połowa pracy wykonuje te same operacje, zaczynając od macierzy tożsamości, uzyskując macierzTo prawda, że ​​możesz tego uniknąć, jeśli wszystko, co cię obchodzi, to wyznacznik. LUAUL
Wolfgang Bangerth,
9

Idę przeciwko tłumowi - przylegająca matryca jest w rzeczywistości bardzo przydatna do niektórych zastosowań specjalnych o małych wymiarach (jak cztery lub mniej), w szczególności, gdy potrzebujesz odwrotności macierzy, ale nie dbasz o skalę.

Dwa przykłady obejmują obliczenie odwrotnej homografii i iterację ilorazu Rayleigha dla bardzo małych problemów (które oprócz uproszczenia za pomocą dopasowania są lepsze numerycznie).

bez kosza
źródło
W pełni się zgadzam, są pewne przypadki (ogólnie z małymi matrycami), w których to bardzo pomaga! (na przykład do obliczania współrzędnych barycentrycznych w małym simpleksie)
BrunoLevy