Matryca odwracalna - Invertible matrix

W liniowym Algebra An n -by- n macierzą kwadratową nazywany jest odwracalna (również nieosobliwa lub niezdegenerowanych ), o ile istnieje n -by- n kwadratowych macierzy B , tak że

gdzie I n oznacza macierz identyczności n -by- n , a użytym mnożeniem jest zwykłe mnożenie macierzy . Jeżeli tak jest, wtedy macierz B jest jednoznacznie określony przez A i jest nazywany (zwielokrotniony) odwrócony od A , oznaczoną A -1 . Odwracanie macierzy to proces znajdowania macierzy B, która spełnia poprzednie równanie dla danej macierzy odwracalnej A .

Macierz kwadratowa, która nie jest odwracalna, nazywana jest pojedynczą lub zdegenerowaną . Macierz kwadratowa jest osobliwa wtedy i tylko wtedy, gdy jej wyznacznikiem jest zero. Macierze osobliwe są rzadkie w tym sensie, że jeśli wpisy macierzy kwadratowej są losowo wybrane z dowolnego skończonego obszaru na osi liczbowej lub płaszczyźnie zespolonej, prawdopodobieństwo, że macierz jest osobliwa wynosi 0, to znaczy „prawie nigdy” nie będzie osobliwa. Macierze niekwadratowe ( macierze m -by- n dla których mn ) nie mają odwrotności. Jednak w niektórych przypadkach taka macierz może mieć lewą odwrotność lub prawą odwrotność . Jeśli jest m -by- n a stopień z A jest równa n ( nm ), a następnie ma lewą odwrotną wykonania ń -by- m macierzy B, w taki sposób, BA = mi n . Jeśli ma rangę m ( mn ), to jest w prawo odwrotną wykonania ń -by- m macierzy B jest takie, że AB = I m .

Chociaż najczęstszym przypadkiem są macierze nad liczbami rzeczywistymi lub zespolonymi , wszystkie te definicje można podać dla macierzy nad dowolnym pierścieniem . Jednak w przypadku pierścienia przemiennego warunkiem odwracalności macierzy kwadratowej jest to, że jej wyznacznik jest odwracalny w pierścieniu, co na ogół jest bardziej rygorystycznym wymogiem niż bycie niezerowym. W przypadku nieprzemiennego pierścienia zwykły wyznacznik nie jest zdefiniowany. Warunki istnienia lewo-odwrotności lub prawo-odwrotności są bardziej skomplikowane, ponieważ pojęcie rangi nie istnieje nad pierścieniami.

Zbiór n × n macierzy odwracalnych wraz z operacją mnożenia macierzy (i wpisami z pierścienia R ) tworzą grupę , ogólną grupę liniową stopnia n , oznaczoną GL n ( R ) .

Nieruchomości

Twierdzenie o macierzy odwracalnej

Niech być kwadratowy n o n matrycy na polu K (np pole R liczb rzeczywistych). Poniższe stwierdzenia są równoważne (tj. wszystkie są prawdziwe lub wszystkie fałszywe dla dowolnej macierzy):

A jest odwracalne, to znaczy A ma odwrotność, jest niesingularne lub niezdegenerowane.
Jest rzędu równoważne do w a n -by- n macierzy jednostkowej I n .
Jest kolumnie równoważnej do w a n -by- n macierzy jednostkowej I n .
A ma n pozycji obrotu .
det A ≠ 0 . Ogólnie rzecz biorąc, macierz kwadratowa nad pierścieniem przemiennym jest odwracalna wtedy i tylko wtedy, gdy jej wyznacznikiem jest jednostka w tym pierścieniu.
A ma pełną rangę; czyli ranga A = n .
Równanie Ax = 0 ma tylko trywialne rozwiązanie x  =  0 .
Jądro z A jest trywialne, to znaczy, że zawiera tylko pustego wektora jako element KER ( ) = { 0 }.
Równanie Ax = b ma dokładnie jedno rozwiązanie dla każdego b w K n .
Kolumny Aliniowo niezależne .
Kolumny A przęsła K n .
Kol. A = K n .
Kolumny A tworzą podstawę o k n .
Transformacja liniowa odwzorowująca x na Ax jest bijekcją od K n do K n .
Istnieje macierz B n -by- n taka, że AB = I n = BA .
Transpozycji T jest odwracalna matrycy (stąd rzędy Aliniowo niezależne , zakres K n , i stanowią podstawę o K n ).
Liczba 0 nie jest wartością własną od A .
Macierz A może być wyrażona jako iloczyn skończony macierzy elementarnych .
Macierz A ma lewą odwrotność (tj. istnieje B takie, że BA = I ) lub prawą odwrotność (to znaczy istnieje C takie, że AC = I ), w takim przypadku istnieje zarówno lewa, jak i prawa odwrotność i B = C = A -1 .

Inne właściwości

Co więcej, dla macierzy odwracalnej A obowiązują następujące właściwości :

  • ( A -1 ) -1 = A ;
  • ( k A ) -1 = k -1 A -1 dla niezerowego skalarnego k ;
  • ( Ax ) + = x + A −1 jeśli A ma kolumny ortonormalne, gdzie + oznacza odwrotność Moore'a–Penrose'a, a x jest wektorem;
  • ( T ) -1 = ( -1 ) t ;
  • Dla dowolnych odwracalnych n -by- n macierzy A i B , ( AB ) -1 = B -1 A -1 . Bardziej ogólnie, jeśli A 1 , ..., A k są odwracalnymi macierzami n -by- n , wtedy ( A 1 A 2A k -1 A k ) -1 = A-1
    k
    A-1
    k -1
    -1
    2
    A-1
    1
    ;
  • det A -1 = ( det A ) -1 .

Rzędy macierzy odwrotnej V macierzy Uortonormalne do kolumn U (i odwrotnie, zamieniając wiersze na kolumny). Aby to zobaczyć, załóżmy, że UV = VU = I , gdzie rzędy V są oznaczone jako i kolumny U jak dla . Wtedy wyraźnie, euklidesowy iloczyn skalarny dowolnych dwóch . Ta właściwość może być również użyteczna przy konstruowaniu odwrotności macierzy kwadratowej w niektórych przypadkach, gdy znany jest zbiór wektorów ortogonalnych (ale niekoniecznie wektorów ortonormalnych) do kolumn U. W takim przypadku można zastosować iteracyjny proces Grama-Schmidta do tego początkowego zbioru, aby określić wiersze odwrotności V .

Matrycy, która jest sama w sobie odwrotną (czyli macierzą tak, że = -1 i 2 = I ), jest nazywany involutory matrycy .

W odniesieniu do jego adiugat

Adjugate matrycy mogą być wykorzystywane w celu znalezienia odwrotny sposób następujący:

Jeśli jest macierzą odwracalną, to

W odniesieniu do macierzy tożsamości

Z asocjatywności mnożenia macierzy wynika, że ​​jeśli

dla skończonych macierzy kwadratowych A i B , to także

Gęstość

Powyżej zakresu liczb rzeczywistych, przy czym zestaw pojedynczych n -by- n macierzy, rozpatrywane jako podzbiór R n x n , to zestaw zerowa , to znaczy ma Lebesgue'a miary zero . Dzieje się tak, ponieważ macierze osobliwe są pierwiastkami funkcji wyznacznika . Jest to funkcja ciągła, ponieważ jest wielomianem we wpisach macierzy. Tak więc w języku teorii środka , prawie wszystkie n -by- N matryce są odwracalne.

Co więcej, n -by- n macierze odwracalne są gęstym zbiorem otwartym w przestrzeni topologicznej wszystkich n -by- n macierzy. Równoważnie zbiór macierzy osobliwych jest zamknięty i nigdzie nie gęsty w przestrzeni n -by- n macierzy.

W praktyce jednak można napotkać macierze nieodwracalne. A w obliczeniach numerycznych macierze, które są odwracalne, ale bliskie macierzy nieodwracalnej, nadal mogą być problematyczne; mówi się, że takie macierze są źle uwarunkowane .

Przykłady

Rozważ następującą macierz 2 na 2:

Matryca jest odwracalna. Aby to sprawdzić, można obliczyć to , które jest niezerowe.

Jako przykład macierzy nieodwracalnej lub pojedynczej, rozważ macierz

Wyznacznikiem jest 0, co jest warunkiem koniecznym i wystarczającym, aby macierz była nieodwracalna.

Metody inwersji macierzy

Eliminacja Gaussa

Eliminacja Gaussa-Jordana to algorytm, którego można użyć do określenia, czy dana macierz jest odwracalna i znalezienia odwrotności. Alternatywą jest dekompozycja LU , która generuje górną i dolną trójkątną macierz, które są łatwiejsze do odwrócenia.

Metoda Newtona

Uogólnienie metody Newtona stosowanej do algorytmu odwrotnego multiplikatywnego może być wygodne, jeśli wygodnie jest znaleźć odpowiedni początkowy ziarno:

Victor Pan i John Reif wykonali pracę, która obejmuje sposoby generowania początkowego ziarna. Magazyn Byte podsumował jedno z ich podejść.

Metoda Newtona jest szczególnie użyteczna, gdy mamy do czynienia z rodzinami powiązanych macierzy, które zachowują się wystarczająco jak sekwencja stworzona dla powyższej homotopii: czasami dobrym punktem wyjścia do udoskonalenia aproksymacji nowej odwrotności może być już uzyskana odwrotność poprzedniej macierzy, która prawie pasuje aktualna macierz, na przykład para sekwencji macierzy odwrotnych stosowanych do uzyskania macierzy pierwiastków kwadratowych przez iterację Denmana-Beaversa ; może to wymagać więcej niż jednego przejścia iteracji w każdej nowej macierzy, jeśli nie są one wystarczająco blisko siebie, aby wystarczyło jedno. Metoda Newtona jest również użyteczna do „retuszowania” poprawek do algorytmu Gaussa-Jordana, który został zanieczyszczony małymi błędami z powodu niedoskonałej arytmetyki komputerowej .

Metoda Cayleya-Hamiltona

Twierdzenie Cayleya-Hamiltona pozwala na odwrotność wyrażenia , śladów i potęg :

gdzie jest wymiarem , i jest śladem macierzy podanym przez sumę głównej przekątnej. Suma jest przejmowana i zbiory wszystkich spełniające liniowe równanie diofantyczne

Wzór można przepisać w postaci pełnych wielomianów Bella argumentów jako

Rozkład własny

Jeśli macierz A może być zdekomponowana i jeśli żadna z jej wartości własnych nie wynosi zero, to A jest odwracalna i jej odwrotność jest dana przez

gdzie jest kwadratem ( N x N ) matrycy, której i -tej kolumnie to wektor własny z i jest macierzą diagonalną , której elementy przekątnej są odpowiednie wartości własnych, tj . Jeśli jest symetryczna, to na pewno będzie macierzą ortogonalną , a zatem . Ponadto, ponieważ jest to macierz diagonalna, jej odwrotność jest łatwa do obliczenia:

Rozkład Choleskiego

Jeżeli macierz A jest dodatnio określona , to jej odwrotność można otrzymać jako

gdzie L jest niższy trójkątny Cholesky'ego rozkładu z A i L * oznacza sprzężoną transpozycję L .

Rozwiązanie analityczne

Zapisanie transpozycji macierzy kofaktorów , znanej jako macierz sprzężona , może być również skutecznym sposobem obliczania odwrotności małych macierzy, ale ta metoda rekurencyjna jest nieefektywna w przypadku dużych macierzy. Aby wyznaczyć odwrotność, obliczamy macierz kofaktorów:

aby

gdzie | | jest determinanta na A , C jest macierzą kofaktorów i C T reprezentuje macierz transpozycję .

Odwrócenie macierzy 2 × 2

Równanie kofaktora wymienione powyżej uzyskuje się następujące wyniki dla 2 x 2 matryce. Odwrócenie tych macierzy można wykonać w następujący sposób:

Jest to możliwe, ponieważ 1/( adbc ) jest odwrotnością wyznacznika danej macierzy, a tę samą strategię można zastosować dla innych rozmiarów macierzy.

Metoda Cayleya-Hamiltona daje

Inwersja macierzy 3 × 3

Wydajna obliczeniowo inwersja macierzy 3 × 3 jest dana przez

(gdzie skalara A nie należy mylić z macierzą A ).

Jeśli wyznacznik jest niezerowy, macierz jest odwracalna, a elementy macierzy pośredniej po prawej stronie podane są przez

Wyznacznik A można obliczyć, stosując regułę Sarrusa w następujący sposób:

Rozkład Cayleya-Hamiltona daje

Ogólna odwrotność 3 × 3 może być zwięźle wyrażona w kategoriach iloczynu krzyżowego i iloczynu potrójnego . Jeśli macierz (składająca się z trzech wektorów kolumnowych , , i ) jest odwracalna, jej odwrotność jest dana przez

Wyznacznik A, , jest równy iloczynowi potrójnemu , , i —objętość równoległościanu utworzonego przez rzędy lub kolumny:

Poprawność wzoru można sprawdzić, korzystając z właściwości iloczynów krzyżowych i potrójnych i zauważając, że dla grup odwrotność lewa i prawa zawsze się pokrywają. Intuicyjnie, ze względu na iloczyny krzyżowe, każdy rząd jest prostopadły do ​​nieodpowiednich dwóch kolumn (co powoduje, że warunki poza przekątną wynoszą zero). Dzielenie przez

powoduje, że elementy diagonalne są jednością. Na przykład pierwsza przekątna to:

Inwersja macierzy 4 × 4

Wraz ze wzrostem wymiaru wyrażenia na odwrotność A stają się skomplikowane. Dla n = 4 , metoda Cayleya-Hamiltona prowadzi do wyrażenia, które jest nadal możliwe do wykonania:

Inwersja blokowa

Macierze można również odwracać blokowo przy użyciu następującego analitycznego wzoru inwersji:

 

 

 

 

( 1 )

gdzie A , B , C i Dpodblokami macierzy o dowolnej wielkości. ( Musi być kwadratowy, tak, że może być odwrócony Ponadto, i D - CA -1 B musi być nieosobliwa). Strategia ta jest szczególnie korzystne, gdy jest przekątnej D - CA -1 B (The dopełniacza Schur z A ) jest małą macierzą, ponieważ są to jedyne macierze wymagające inwersji.

Technika ta była kilkakrotnie wymyślana na nowo i jest zasługą Hansa Boltza (1923), który użył jej do inwersji osnowy geodezyjnej , oraz Tadeusza Banachiewicza (1937), który ją uogólnił i udowodnił jej poprawność.

Twierdzenie nieważności mówi, że unieważnienie A wynosi nieważności podbloku w dolnej prawej stronie odwrotnej macierzy, a unieważnienie B wynosi nieważności podbloku w prawej górnej części matrycy odwrotnej.

Procedura inwersji, która doprowadziła do Equation ( 1 ), wykonywała operacje blokowe na macierzach, które najpierw działały na C i D. Zamiast tego, jeśli A i B są operowane jako pierwsze i pod warunkiem, że D i A - BD -1 C są nieosobliwe, wynik jest

 

 

 

 

( 2 )

Zrównanie równań ( 1 ) i ( 2 ) prowadzi do

 

 

 

 

( 3 )

gdzie Równanie ( 3 ) jest tożsamością macierzy Woodbury'ego , która jest równoważna dwumianowemu twierdzeniu odwrotnemu .

Jeśli A i D są odwracalne, to powyższe dwie odwrotności macierzy blokowej można połączyć, aby zapewnić prostą faktoryzację

 

 

 

 

( 2 )

Zgodnie z tożsamością Weinsteina-Aronszajna , jedna z dwóch macierzy w macierzy przekątnej blokowej jest odwracalna dokładnie wtedy, gdy druga jest.

Ponieważ blokowe odwrócenie macierzy n × n wymaga odwrócenia dwóch macierzy połówkowych i 6 mnożenia między dwiema macierzami połówkowymi, można wykazać, że algorytm dziel i zwyciężaj, który używa odwracania blokowego do odwrócenia macierzy działa z tym samym złożoność czasowa jako algorytm mnożenia macierzy, który jest używany wewnętrznie. Badania nad złożonością mnożenia macierzy pokazują, że istnieją algorytmy mnożenia macierzy o złożoności operacji O ( n 2,3727 ) , podczas gdy najlepiej udowodnionym dolnym ograniczeniem jest Ω ( n 2 log n ) .

Ta formuła upraszcza się znacznie, gdy górna prawa macierz blokowa jest macierzą zerową. Preparat ten jest użyteczny, gdy macierze i stosunkowo prostych wzorów odwrotnej (lub odwrotności pseudo w przypadku, w którym bloki nie wszystkie są kwadratowe. W tym szczególnym przypadku, wzór inwersja macierzy blok podano w pełni ogólności powyżej staje

Seria Neumann

Jeśli macierz A ma właściwość, że

wtedy A jest nieosobliwe i jego odwrotność może być wyrażona szeregiem Neumanna :

Obcięcie sumy daje w wyniku odwrotność „przybliżoną”, która może być przydatna jako warunek wstępny . Zauważ, że szereg obcięty można przyspieszyć wykładniczo, zauważając, że szereg Neumanna jest sumą geometryczną . Jako taki spełnia

.

Dlatego do obliczenia składników sumy potrzebne są tylko mnożenia macierzy .

Bardziej ogólnie, jeśli A jest "blisko" macierzy odwracalnej X w takim sensie, że

wtedy A jest niesinglowe, a jego odwrotnością jest

Jeżeli jest również tak, że AX ma rangę 1, to upraszcza się do

p -adyczne przybliżenie

Jeśli A jest macierzą ze współczynnikami całkowitymi lub wymiernymi i szukamy rozwiązania w wymiernych arbitralnej precyzji , to metoda aproksymacji p- adycznej zbiega się do dokładnego rozwiązania w , zakładając, że zastosowano standardowe mnożenie macierzy. Metoda polega na rozwiązywaniu n układów liniowych metodą Dixona aproksymacji p- adycznej (każdy w ) i jest dostępna jako taka w oprogramowaniu wyspecjalizowanym w operacjach na macierzach arbitralnej precyzji, na przykład w IML.

Metoda odwrotnych wektorów bazowych

Biorąc pod uwagę macierz kwadratowa , z rzędami interpretowane jako wektory ( Einstein podsumowanie zakłada), gdzie są standardową podstawą ortonormalna z przestrzeni euklidesowej ( ), a następnie za pomocą Clifford algebra (lub Geometryczne Algebra ) możemy obliczyć odwrotność (czasami nazywane także podwójny ) wektorów kolumnowych jak kolumny macierzy odwrotnej . Zauważ, że miejsce " " wskazuje, że " " zostało usunięte z tego miejsca w powyższym wyrażeniu dla . Mamy wtedy , gdzie jest delta Kroneckera . Posiadamy również , zgodnie z wymaganiami. Jeśli wektory nie są liniowo niezależne, to macierz nie jest odwracalna (nie ma odwrotności).

Pochodna macierzy odwrotnej

Załóżmy, że macierz odwracalna A zależy od parametru t . Wtedy pochodna odwrotności A względem t jest dana przez

Aby wyprowadzić powyższe wyrażenie na pochodną odwrotności A , można zróżnicować definicję macierzy odwrotności, a następnie znaleźć odwrotność A :

Odjęcie od obu stron powyższego i pomnożenie z prawej strony przez daje poprawne wyrażenie na pochodną odwrotności:

Podobnie, jeśli jest małą liczbą, to

Bardziej ogólnie, jeśli

następnie,

Biorąc pod uwagę dodatnią liczbę całkowitą ,

W związku z tym,

Uogólnione odwrotność

Niektóre właściwości macierzy odwrotnych są wspólne dla uogólnionych odwrotności (na przykład odwrotność Moore'a-Penrose'a ), którą można zdefiniować dla dowolnej macierzy m -by- n .

Aplikacje

W przypadku większości praktycznych zastosowań, jest nie konieczne odwracanie macierzy w celu rozwiązania układu równań liniowych ; jednak dla unikalnego rozwiązania konieczne jest, aby zaangażowana macierz była odwracalna.

Techniki dekompozycji, takie jak dekompozycja LU, są znacznie szybsze niż inwersja, a także opracowano różne szybkie algorytmy dla specjalnych klas systemów liniowych.

Regresja/najmniejsze kwadraty

Chociaż jawna odwrotność nie jest konieczna do oszacowania wektora niewiadomych, jest to najłatwiejszy sposób oszacowania ich dokładności, znalezionej na przekątnej macierzy odwrotności (macierz kowariancji a posteriori wektora niewiadomych). Jednak w wielu przypadkach znane są szybsze algorytmy do obliczania tylko przekątnych wpisów macierzy odwrotnej.

Odwrotność macierzy w symulacjach w czasie rzeczywistym

Inwersja macierzy odgrywa istotną rolę w grafice komputerowej , szczególnie w renderowaniu grafiki 3D i symulacjach 3D. Przykłady obejmują rzutowanie z ekranu na świat , transformacje obiektów ze świata na podprzestrzeń do świata oraz symulacje fizyczne.

Odwrócenie macierzy w komunikacji bezprzewodowej MIMO

Inwersja macierzy odgrywa również istotną rolę w technologii MIMO (Multiple-Input, Multiple-Output) w komunikacji bezprzewodowej. System MIMO składa się z N anten nadawczych i M anten odbiorczych. Unikalne sygnały, zajmujące to samo pasmo częstotliwości, są wysyłane przez N anten nadawczych i odbierane przez M anten odbiorczych. Sygnał docierający do każdej anteny odbiorczej będzie liniową kombinacją N nadawanych sygnałów tworzącą macierz transmisyjną H N  ×  M . Bardzo ważne jest, aby macierz H była odwracalna, aby odbiorca mógł odczytać przesyłane informacje.

Zobacz też

Bibliografia

Dalsza lektura

Zewnętrzne linki