Rotacja Jacobiego

W numerycznej algebrze liniowej obrót Jacobiego jest obrotem Q k _{ℓ dwuwymiarowej} podprzestrzeni liniowej n - wymiarowej przestrzeni iloczynu wewnętrznego , wybranej do zera symetrycznej pary wpisów poza przekątną n × n rzeczywistej symetryczności macierz , A , zastosowana jako transformacja podobieństwa :

${\ Displaystyle A \ mapsto Q_ {k \ ell} ^ {T} AQ_ {k \ ell} = A '. \, \!}$

${\ Displaystyle {\ rozpocząć {bmatrix} {*}&&&\ cdots &&&*\\&\ddots &&&&&\\&&a_ {kk}&\cdots &a_ {k\ell}&&\\\vdots &&\vdots &\ddots & \vdots &&\vdots \\&&a_{\ell k}&\cdots &a_{\ell \ell }&&\\&&&&&\ddots &\\{*}&&&\cdots &&&*\end{bmatrix}}\to {\ begin{bmatrix}{*}&&&\cdots &&&*\\&\ddots &&&&&\\&&a'_{kk}&\cdots &0&&\\\vdots &&\vdots &\ddots &\vdots &&\vdots \\&&0&\ cdots &a'_{\ell \ell }&&\\&&&&&\ddots &\\{*}&&&\cdots &&&*\end{bmatrix}}.}$

Jest to podstawowa operacja w algorytmie wartości własnej Jacobiego , który jest numerycznie stabilny i dobrze nadaje się do implementacji na procesorach równoległych .

Dotyczy to tylko wierszy k i ℓ oraz kolumn k i ℓ A , a A ′ pozostanie symetryczne. Również rzadko obliczana jest wyraźna macierz dla Q _{k ℓ ;} zamiast tego obliczane są wartości pomocnicze, a A jest aktualizowane w wydajny i numerycznie stabilny sposób. Jednak dla odniesienia możemy zapisać macierz jako

${\ Displaystyle Q_ {k \ ell} = {\ rozpocząć {bmatrix} 1&&&&&&\\&\ ddots &&&&0&\\&&c&\cdots &s&&\\&&\vdots &\ddots &\vdots &&\\&&-s&\cdots &c&&\ \&0&&&&\ddots &\\&&&&&&1\end{bmatryca}}.}$

Oznacza to, że Q _{k ℓ} jest macierzą tożsamości, z wyjątkiem czterech wpisów, dwóch na przekątnej ( q _kk i q _ℓℓ , oba równe c ) i dwóch symetrycznie umieszczonych poza przekątną ( q _{k ℓ} i q _{ℓ k} , równe s i − s , odpowiednio). Tutaj c = cos θ i s = sin θ dla pewnego kąta θ; ale aby zastosować obrót, sam kąt nie jest wymagany. Wykorzystanie delty Kroneckera notacji, wpisy macierzy mogą być zapisane

${\ Displaystyle q_ {ij} = \ delta _ {ij} + (\ delta _ {ik} \ delta _ {jk} + \ delta _ {i \ ell} \ delta _ {j \ ell}) (c-1 )+(\delta _{ik}\delta _{j\ell }-\delta _{i\ell }\delta _{jk})s.\,\!}$

Załóżmy, że h jest indeksem innym niż k lub ℓ (które same muszą być różne). Następnie aktualizacja podobieństwa daje algebraicznie

${\ Displaystyle a'_ {hk} = a'_ {kh} = ca_ {hk} -sa_ {h \ ell} \$

${\ Displaystyle a'_ {h \ ell} = a'_ {\ ell h} = ca_ {h \ ell} + sa_ {hk}\,\!}$

${\ Displaystyle a'_ {k \ ell} = a'_ {\ ell k} =(c^{2}-s^{2})a_{k\ell }+sc(a_{kk}-a_{\ell \ell })=0\,\!}$

$\ Displaystyle a'_ {kk} = c ^ {2} a_ {kk} + s ^ {2} a_ {\ ell \ ell} -2sca_ {k \ ell} \, \!}$

${\ Displaystyle a' _ {\ ell \ ell} = s ^ {2} a_ {kk} + c ^ {2} a _ {\ ell \ ell} + 2sca_ {k \ ell}. \, \!}$

Obliczenia numerycznie stabilne

Aby określić wielkości potrzebne do aktualizacji, musimy rozwiązać równanie pozadiagonalne dla zera ( Golub i Van Loan 1996 , §8.4). To daje do zrozumienia ze

${\ Displaystyle {\ Frac {c ^ {2} -s ^ {2}} {sc}} = {\ Frac {a _ {\ ell \ ell} -a_ {kk}} {a_ {k \ ell}}} .}$

Ustaw β na połowę tej wielkości,

${\ Displaystyle \ beta = {\ Frac {a _ {\ ell \ ell} -a_ {kk}} {2a_ {k \ ell}}}.}$

Jeśli k _{ℓ .} wynosi zero, możemy zatrzymać się bez przeprowadzania aktualizacji, dlatego nigdy nie dzielimy przez zero Niech t będzie tan θ. Następnie za pomocą kilku tożsamości trygonometrycznych redukujemy równanie do

${\ Displaystyle t ^ {2} + 2 \ beta t-1 = 0. \, \!}$

Dla stabilności wybieramy rozwiązanie

${\ Displaystyle t = {\ Frac {\ operatorname {sgn} (\ beta)} {|\ beta | + {\ sqrt {\ beta ^ {2} + 1}}}}.}$

Z tego możemy otrzymać c i s jako

${\ Displaystyle c = {\ Frac {1} {\ sqrt {t ^ {2} + 1}}} \, \!} s$

$\ Displaystyle s = ct \, \ !}$

Chociaż moglibyśmy teraz użyć algebraicznych równań aktualizacji podanych wcześniej, może być lepiej napisać je od nowa. Pozwalać

${\ Displaystyle \ rho = {\ Frac {1-c} {s}}}$

tak, że ρ = tan(θ/2). Następnie poprawione równania aktualizacji są

$\ Displaystyle a'_ {hk} = a'_ {kh} = a_ {hk} -s ($

$\ Displaystyle a'_ {h \ ell} = a' _ {\ ell h} = a _ {h \ ell} + s (a_ {hk} - \ rho a_ {h \ ell}) \, \!}$

${\ Displaystyle a'_ {k \ ell} = a' _ {\ ell k} = 0 \, \!}$

${\ Displaystyle a'_ {kk} = a_ {kk} -ta_ {k \ ell} \, \!}$

${\ Displaystyle a'_ {\ ell \ ell} = a _ {\ ell \ ell} + ta_ {k \ ell} \, \!}$

Jak wcześniej zauważono, nigdy nie musimy jawnie obliczać kąta obrotu θ. W rzeczywistości możemy odtworzyć aktualizację symetryczną określoną przez Q _{kℓ , zachowując} tylko trzy wartości k , ℓ i t , z t ustawionym na zero dla obrotu zerowego.

Zobacz też

• Rotacja Givensa
• Transformacja domowników

•   Golub, Gene H .; Van Loan, Charles F. (1996), Matrix Obliczenia (wyd. 3), Baltimore: Johns Hopkins University Press, ISBN 978-0-8018-5414-9