Macierz ortogonalna

KorzyściEdit

Analiza numeryczna korzysta z wielu właściwości macierzy ortogonalnych w numerycznej algebrze liniowej, i pojawiają się one w sposób naturalny. Na przykład, często pożądane jest obliczenie ortonormalnej podstawy dla przestrzeni lub ortogonalnej zmiany podstaw; oba te przypadki przyjmują postać macierzy ortogonalnych. Posiadanie wyznacznika ±1 i wszystkich wartości własnych o wielkości 1 jest bardzo korzystne z punktu widzenia stabilności numerycznej. Jedną z implikacji jest to, że liczba stanu wynosi 1 (co jest minimum), więc błędy nie są powiększane podczas mnożenia z macierzą ortogonalną. Z tego powodu wiele algorytmów używa macierzy ortogonalnych, takich jak odbicia Householdera i rotacje Givensa. Pomocne jest również to, że nie tylko macierz ortogonalna jest odwracalna, ale jej odwrotność jest dostępna w zasadzie za darmo, poprzez wymianę indeksów.

Permutacje są niezbędne do sukcesu wielu algorytmów, w tym metody Gaussian elimination with partial pivoting (gdzie permutacje wykonują pivoting). Jednakże, rzadko pojawiają się one jawnie jako macierze; ich specjalna forma pozwala na bardziej efektywną reprezentację, taką jak lista n indeksów.

Podobnie, algorytmy używające macierzy Householdera i Givensa zazwyczaj używają wyspecjalizowanych metod mnożenia i przechowywania. Na przykład, rotacja Givensa wpływa tylko na dwa rzędy macierzy, którą mnoży, zmieniając pełne mnożenie rzędu n3 na znacznie bardziej wydajne rzędu n. Kiedy użycie tych odbić i rotacji wprowadza zera do macierzy, zwolniona przestrzeń jest wystarczająca do przechowywania wystarczającej ilości danych do odtworzenia transformacji, i to w sposób solidny. (Idąc za Stewartem (1976), nie przechowujemy kąta obrotu, co jest zarówno kosztowne, jak i źle się zachowuje.)

DekompozycjeEdit

Wiele ważnych dekompozycji macierzy (Golub & Van Loan 1996) obejmuje macierze ortogonalne, w tym w szczególności:

Dekompozycja QR M = QR, Q ortogonalne, R górny trójkąt Dekompozycja wartości pojedynczej M = UΣVT, U i V ortogonalne, Σ diagonalna macierzy Eigendekompozycja macierzy symetrycznej (rozkład zgodny z twierdzeniem spektralnym) S = QΛQT, S symetryczna, Q ortogonalna, Λ diagonalna Rozkład biegunowy M = QS, Q ortogonalna, S symetryczna dodatnio-półskończona

PrzykładyEdytuj

Rozważmy naddeterminowany układ równań liniowych, jaki może wystąpić przy wielokrotnych pomiarach zjawiska fizycznego w celu kompensacji błędów eksperymentalnych. Napisz Ax = b, gdzie A jest m × n, m > n.Dekompozycja QR redukuje A do trójkąta górnego R. Na przykład, jeśli A jest 5 × 3 to R ma postać

R = . {{displaystyle R={{begin{bmatrix}}} &&&&&&&\cdot \\0&&&&0\end{bmatrix}}.}

W przypadku układu liniowego, który jest niedeterministyczny, lub w inny sposób nieodwracalnej macierzy, rozkład wartości pojedynczych (SVD) jest równie użyteczny. Z A przedstawionym jako UΣVT, zadowalające rozwiązanie wykorzystuje pseudoinwersję Moore’a-Penrose’a, VΣ+UT, gdzie Σ+ jedynie zastępuje każdy niezerowy wpis na przekątnej jego odwrotnością. Ustaw x na VΣ+UTb.

Przypadek kwadratowej macierzy odwracalnej również jest interesujący. Załóżmy na przykład, że A jest macierzą rotacji 3 × 3, która została obliczona jako kompozycja wielu skrętów i obrotów. Liczba zmiennoprzecinkowa nie odpowiada matematycznemu ideałowi liczb rzeczywistych, więc A stopniowo straciła swoją prawdziwą ortogonalność. Proces Grama-Schmidta mógłby zortogonalizować kolumny, ale nie jest to najbardziej niezawodna, ani najbardziej wydajna, ani najbardziej niezmiennicza metoda. Dekompozycja biegunowa dzieli macierz na parę, z których jedna jest unikalną najbliższą macierzą ortogonalną do danej macierzy, lub jedną z najbliższych, jeśli dana macierz jest pojedyncza. (Bliskość można zmierzyć za pomocą dowolnej normy macierzy niezmiennej przy ortogonalnej zmianie bazy, takiej jak norma spektralna lub norma Frobeniusa). W przypadku macierzy prawie ortogonalnej, szybką zbieżność do czynnika ortogonalnego można osiągnąć dzięki podejściu „metody Newtona”, opracowanej przez Highama (1986) (1990), polegającej na wielokrotnym uśrednianiu macierzy z jej odwrotną transpozycją. Dubrulle (1994) harvtxt błąd: brak celu: CITEREFDubrulle1994 (help) opublikował przyspieszoną metodę z wygodnym testem zbieżności.

Na przykład, rozważmy macierz nieortogonalną, dla której prosty algorytm uśredniania wymaga siedmiu kroków

→ → ⋯ → {{displaystyle {{begin{bmatrix}3&&5}end{bmatrix}} {{rightarrow {{begin{bmatrix}1.8125&&&&&&&&0.8\end{bmatrix}}}

i które przyspieszenie przycina do dwóch kroków (z γ = 0.353553, 0.565685).

→ → → { {{begin{bmatrix}3&&5}}rightarrow {{begin{bmatrix}1.41421&&1.41421\end{bmatrix}}\rightarrow {\begin{bmatrix}0.8&&0.8\end{bmatrix}}}

Gram-Schmidt daje gorsze rozwiązanie, na co wskazuje odległość Frobeniusa wynosząca 8.28659 zamiast minimalnej 8.12404.

→ {{displaystyle {{begin{bmatrix}}3&&5}end{bmatrix}}

Wiersz {{begin{bmatrix}}0.393919&&0.393919\end{bmatrix}}}

RandomizationEdit

Niektóre zastosowania numeryczne, takie jak metody Monte Carlo i eksploracja wielowymiarowych przestrzeni danych, wymagają generowania równomiernie rozłożonych losowych macierzy ortogonalnych. W tym kontekście, „równomierny” jest definiowany w kategoriach miary Haara, która zasadniczo wymaga, aby rozkład nie zmienił się po przemnożeniu przez dowolnie wybraną macierz ortogonalną. Ortogonalizacja macierzy z niezależnymi równomiernie rozłożonymi przypadkowymi wpisami nie daje macierzy ortogonalnych o równomiernym rozłożeniu, ale dekompozycja QR niezależnych normalnie rozłożonych przypadkowych wpisów daje, tak długo jak przekątna R zawiera tylko wpisy dodatnie (Mezzadri 2006). Stewart (1980) zastąpił to bardziej wydajnym pomysłem, który Diaconis & Shahshahani (1987) później uogólnił jako „algorytm podgrupy” (w której to formie działa równie dobrze dla permutacji i rotacji). Aby wygenerować macierz (n + 1) × (n + 1) ortogonalną, należy wziąć macierz n × n oraz równomiernie rozłożony wektor jednostkowy o wymiarze n + 1. Skonstruuj odbicie Householdera z wektora, a następnie zastosuj je do mniejszej macierzy (osadzonej w większym wymiarze z 1 w prawym dolnym rogu).

Najbliższa macierz ortogonalnaEdit

Problem znalezienia macierzy ortogonalnej Q najbliższej danej macierzy M jest związany z problemem ortogonalnym Procrustesa. Istnieje kilka różnych sposobów na uzyskanie unikalnego rozwiązania, z których najprostszy polega na wykonaniu rozkładu wartości singularnych macierzy M i zastąpieniu wartości singularnych jedynkami. Inna metoda wyraża R wprost, ale wymaga użycia pierwiastka kwadratowego z macierzy:

Q = M ( M T M ) – 1 2 {displaystyle Q=Mleft(M^{mathrm {T}} }M}right)^{-{frac {1}{2}}}}

Można to połączyć z babilońską metodą wyodrębniania pierwiastka kwadratowego z macierzy, aby uzyskać rekurencję, która zbiega do macierzy ortogonalnej w sposób kwadratowy:

Q n + 1 = 2 M ( Q n – 1 M + M T Q n ) – 1 {{displaystyle Q_{n+1}}=2M}left(Q_{n}^{-1}}M+M^{mathrm {T} }Q_{n}}}}.