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

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\times 3$ . W przypadku macierzy $n\times n$ wymaga ona obliczenia wyznacznika samej macierzy i obliczenia $n^2$ wyznaczników macierzy $(n-1)\times(n-1)$ . Zgaduję, że nie jest to przydatne w aplikacjach. Ale chciałbym potwierdzenia.

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

linear-algebra matrix complexity

— Stefan Smith
źródło

Odpowiedzi:

$O(n)$ $O(n^3)$

— Wolfgang Bangerth
źródło

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!)

$O(n!)$

O (n^{3})

$O(n^3)$

— 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!)

$O(n!)$

— JM

@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 (A B) = det (A) det (B)

$\det(\mathbf A\mathbf B)=\det(\mathbf A)\det(\mathbf B)$

O (n^{3})

$O(n^3)$

— JM

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.

L U

$LU$

n

$n$

n!

$n!$

O (n^{5})

$O(n^5)$

— Wolfgang Bangerth

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.

L U

$LU$

A

$A$

U

$U$

L

$L$

— Wolfgang Bangerth,

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