Jacobi rotation

I numerisk linjär algebra är en Jacobi-rotation en rotation , Qkℓ , av ett 2-dimensionellt linjärt delrum av ett n- dimensionellt inre produktrum , valt att nollställa ett symmetriskt par off- _{en diagonala} ingångar av n × n reell symmetri matris , A , när den tillämpas som en likhetstransformation :

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

${\begin{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 {\ börja{bmatrix}{*}&&&\cdots &&&*\\&\ddots &&&&&\\&&a'_{kk}&\cdots &0&&\\\vdots &&\vdots &\ddots &\vdots &&\vdots \\&&0&\ cdots &a'_{\ell \ell }&&\\&&&&&\ddots &\\{*}&&&\cdots &&&*\end{bmatrix}}.$

Det är kärnoperationen i Jacobis egenvärdealgoritm , som är numeriskt stabil och väl lämpad för implementering på parallella processorer .

Endast raderna k och ℓ och kolumnerna k och ℓ i A kommer att påverkas, och den A ′ kommer att förbli symmetrisk. Dessutom beräknas en explicit matris för Qkℓ _{sällan ;} istället beräknas hjälpvärden och A uppdateras på ett effektivt och numeriskt stabilt sätt. Men som referens kan vi skriva matrisen som

$Q_{k\ell }={\begin{bmatrix}1&&&&&&\\&\ddots &&&&0&\\&&c&\cdots &s&&\\\&&\vdots &\ddots &\vdots &&\\&&-s&\cdots &c&&\ \&0&&&&\ddots &\\&&&&&&1\end{bmatrix}}.$

Det vill säga, Q _{k ℓ} är en identitetsmatris förutom fyra poster, två på diagonalen ( q _kk och q _ℓℓ , båda lika med c ) och två symmetriskt placerade utanför diagonalen ( q _{k ℓ} och q _{ℓ k} , lika med s och − s , respektive). Här är c ​​= cos θ och s = sin θ för någon vinkel θ; men för att applicera rotationen krävs inte själva vinkeln. Med hjälp av Kronecker deltanotation kan matrisposterna skrivas

$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.\,\!$

Antag att h är ett annat index än k eller ℓ (som i sig måste vara distinkt). Sedan producerar likhetsuppdateringen, algebraiskt,

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

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

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

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

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

Numeriskt stabil beräkning

För att bestämma de kvantiteter som behövs för uppdateringen måste vi lösa ekvationen utanför diagonalen för noll ( Golub & Van Loan 1996, §8.4). Detta betyder att

${\frac {c^{2}-s^{2}}{sc}}={\frac {a_{\ell \ell }-a_{kk}}{a_{k\ell }}} .$

Sätt β till hälften av denna kvantitet,

$\beta ={\frac {a_{\ell \ell }-a_{kk}}{2a_{k\ell }}}.$

Om en _{k ℓ} är noll kan vi stoppa utan att utföra en uppdatering, så vi dividerar aldrig med noll. Låt t vara tan θ. Sedan med några trigonometriska identiteter reducerar vi ekvationen till

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

För stabilitet väljer vi lösningen

$t={\frac {\operatörsnamn {sgn}(\beta )}{|\beta |+{\sqrt {\beta ^{2}+1}}}}.$

Från detta kan vi få c och s as

${\displaystyle c={\frac {1}{\sqrt {t^{2}+1}}}\,\!} s$

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

Även om vi nu skulle kunna använda de algebraiska uppdateringsekvationerna som gavs tidigare, kan det vara bättre att skriva om dem. Låta

$\rho ={\frac {1-c}{s}},$

så att ρ = tan(θ/2). Då är de reviderade uppdateringsekvationerna

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

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

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

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

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

Som tidigare påpekats behöver vi aldrig explicit beräkna rotationsvinkeln θ. Faktum är att vi kan reproducera den symmetriska uppdateringen som bestäms av Qkℓ genom att endast behålla de tre värdena k , ℓ och t _{, till} med t satt noll för en nollrotation.

Se även

• Ger rotation
• Hushållarförvandling

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