Ger rotation

I numerisk linjär algebra är en Givens-rotation en rotation i planet som spänns av två koordinataxlar. Givens rotationer är uppkallade efter Wallace Givens , som introducerade dem för numeriska analytiker på 1950-talet medan han arbetade på Argonne National Laboratory .

Matrisrepresentation

En Givens rotation representeras av en matris av formen

$_ (i,j,\theta )={\begin{bmatrix}1&\cdots &0&\cdots &0&\cdots &0\\\vdots &\ddots &\vdots &&\vdots &&\vdots \\0&\cdots &c&\cdots & -s&\cdots &0\\\vdots &&\vdots &\ddots &\vdots &&\vdots \\0&\cdots &s&\cdots &c&\cdots &0\\\vdots &&\vdots &&\vdots &\dots \\ \0&\cdots &0&\cdots &0&\cdots &1\end{bmatrix}},}$

där c = cos θ och s = sin θ visas vid skärningspunkterna i: te och j :te raderna och kolumnerna. Det vill säga, för fix i > j , ges icke-noll-elementen i Givens matris av:

${\begin{aligned}g_{kk}&{}= 1\qquad {\text{för}}\ k\neq i,\,j\\g_{kk}&{}=c\qquad {\text{för}}\ k=i,\,j\\g_ {ji}&{}=-g_{ij}=-s\\\end{aligned}}$

Produkten G ( i , j , θ ) x representerar en moturs rotation av vektorn x i ( i , j ) planet för θ radianer, därav namnet Givens rotation.

Den huvudsakliga användningen av Givens rotationer i numerisk linjär algebra är att introducera nollor i vektorer eller matriser. Denna effekt kan till exempel användas för att beräkna QR-sönderdelningen av en matris. En fördel gentemot hushållartransformationer är att de lätt kan parallelliseras, och en annan är att de ofta för mycket glesa matriser har ett lägre antal operationer.

Stabil beräkning

När en Givens rotationsmatris, G ( i , j , θ ) , multiplicerar en annan matris, A , från vänster, GA , påverkas endast raderna i och j i A. Därför begränsar vi uppmärksamheten till följande motursproblem. Givet a och b , hitta c = cos θ och s = sin θ så att

${\begin{bmatrix}c&-s\\s&c\end{bmatrix}}{\begin{bmatrix}a\\b\end{ bmatrix}}={\begin{bmatrix}r\\0\end{bmatrix}},$

där $r={\sqrt {a^{2}+b^{2}}}$ är längden på vektorn $(a,b)$ . Explicit beräkning av θ är sällan nödvändig eller önskvärd. Istället söker vi direkt c och s . En självklar lösning vore

${\begin{aligned}c&{}\leftarrow a/r\\s&{}\leftarrow -b/r.\end{aligned}}$

kan beräkningen för r flöda över eller underskrida. En alternativ formulering som undviker detta problem ( Golub & Van Loan 1996 , §5.1.8) implementeras som hypotfunktionen i många programmeringsspråk.

Följande Fortran-kod är en minimalistisk implementering av Givens rotation för reella tal. Om ingångsvärdena 'a' eller 'b' ofta är noll, kan koden optimeras för att hantera dessa fall som presenteras här .

    

    
 

  
       
        
        
         
         

      
      
      



 subrutin  givens_rotation  (  a  ,  b  ,  c  ,  s  ,  r  )  real  a  ,  b  ,  c  ,  s  ,  r  real  h  ,  d  if  (  b  .  ne  .  0.0  )  then  h  =  hypot  (  a  ,  b  )  d  =  1.0  /  h  c  =  abs  (  a  )  *  d  s  =  tecken  (  d  ,  a  )  *  b  r  =  tecken  (  1,0  ,  a  )  *  h  annars  c  =  1,0  s  =  0,0  r  =  a  end if  return  end 

Dessutom, som Edward Anderson upptäckte när han förbättrade LAPACK , är kontinuitet ett tidigare förbisett numeriskt övervägande. För att uppnå detta kräver vi att r är positiv. Följande MATLAB / GNU Octave -kod illustrerar algoritmen.

 
       0
          
           0
               
        
          0
          
       0
          0
          
          
       
            
                
            
            
            
    
            
                
            
            
            
    
 funktion  [c, s, r] = given_rotation  (  a, b  )  om  b  ==  ;  c  =  tecken  (  a  );  om  (  c  ==  );  c  =  1,0  ;  % Till skillnad från andra språk returnerar MatLabs teckenfunktion 0 vid inmatning 0.  end  ;  s  =  ;  r  =  abs  (  a  );  elseif  a  ==  ;  c  =  ;  s  =  tecken  (  b  );  r  =  abs  (  b  );  elseif  abs  (  a  )  >  abs  (  b  );  t  =  b  /  a  ;  u  =  tecken  (  a  )  *  sqrt  (  1  +  t  *  t  );  c  =  1  /  u  ;  s  =  -  c  *  t  ;  r  =  a  *  u  ;  annars  t  =  a  /  b  ;  u  =  tecken  (  b  )  *  sqrt  (  1  +  t  *  t  );  s  =  -1  /  u  ;  _  c  =  t  /  u  ;  r  =  b  *  u  ;  slutet  slut 

IEEE 754 copysign(x,y) -funktionen ger ett säkert och billigt sätt att kopiera tecknet för y till x . Om det inte är tillgängligt, | x |⋅sgn( y ) , med funktionerna abs och sgn , är ett alternativ som gjorts ovan.

Triangularisering

Givet följande 3 × 3 matris:

$\displaystyle A_{1}={\begin{bmatrix}6&5&0\\5&1&4\\0&4&3\\\end{bmatrix}},}$

utför två iterationer av Givens-rotationen (observera att Givens-rotationsalgoritmen som används här skiljer sig något från ovan) för att ge en övre triangulär matris för att beräkna QR-sönderdelningen .

För att bilda den önskade matrisen måste vi nollställa element (2, 1) och (3, 2) . Vi väljer först element (2, 1) till noll. Använda en rotationsmatris av:

$G_{1}={\begin{bmatrix}c&-s&0\\s&c&0\\0&0&1\\\end{bmatrix}}.$

Vi har följande matrismultiplikation:

${\begin{aligned}G_{1}A_{1}&{}=A_{2 }\\&{}={\begin{bmatrix}c&-s&0\\s&c&0\\0&0&1\\\end{bmatrix}}{\begin{bmatrix}6&5&0\\5&1&4\\0&4&3\\\end{bmatrix} },\end{aligned}}$

var

${\begin{aligned}r&{}={\sqrt {6^{2}+5^{2}}}\approx 7.8102\\c&{}=6/r\approx 0.7682\\s&{} =-5/r\approx -0,6402.\end{aligned}}$

Att plugga in dessa värden för c och s och utföra matrismultiplikationen ovan ger A ₂ :

$A_{2}\approx {\begin{bmatrix}7.8102&4.4813&2.57-23.\32&3.\07\32&3.\32&3. { bmatrix}}$

Vi vill nu nollställa element (3, 2) för att avsluta processen. Med samma idé som tidigare har vi en rotationsmatris av:

$G_{2}={\begin{bmatrix}1&0&0\\0&c&-s\\0&s&c\\\end{bmatrix}}$

Vi presenteras med följande matrismultiplikation:

${\begin{aligned}G_{2}A_={A_{2}&{ 3}\\&{}\approx {\begin{bmatrix}1&0&0\\0&c&-s\\0&s&c\\\end{bmatrix}}{\begin{bmatrix}7.8102&4.4813&2.5607\\0&-2.4327&3 .0729\\0&4&3\\\end{bmatrix}},\end{aligned}}$

var

${\begin{aligned}r&{}\approx {\sqrt {(-2.4327)^{2}+4^{2}}}\approx 4.6817\\c&{}\approx -2.4327/r\approx -0,5196\\s&{}\approx -4/r\approx -0,8544.\end{aligned}}$

Att plugga in dessa värden för c och s och utföra multiplikationerna ger oss A ₃ :

$A_{3}\approx {\begin{bmatrix}7.8102&4.4813&2.5607\\0&4.6817&0.9665\\0&0&-4.1843\\\end{bmatrix}}.$

Denna nya matris A3 _QR är den övre triangulära matrisen som behövs för att utföra en iteration av -sönderdelningen . Q bildas nu med hjälp av transponeringen av rotationsmatriserna på följande sätt:

$Q=G_{1}^{T}\,G_{2}^{T}.$

Att utföra denna matrismultiplikation ger:

$Q\approx {\begin{bmatrix}0.7682&0.3327&0.5470\\0.6402&-0.3992&-0.6564\\0&0.8544&-0.5196\\\end{bmatrix}}.$

Detta slutför två iterationer av Givens Rotation och beräkning av QR-nedbrytningen kan nu göras.

I Clifford algebras

I Clifford representeras algebror och dess underordnade strukturer som geometriska algebrarotationer av bivectors . Givna rotationer representeras av den yttre produkten av basvektorerna. Givet valfritt par av basvektorer $\mathbf {e} _{i},\mathbf {e} _{j}$ Givna rotationer är bivectors:

$B_{ij}=\mathbf {e} _{i}\wedge \mathbf {e} _{j}.$

Deras åtgärd på vilken vektor som helst skrivs:

$v=e^{-(\theta /2)(\mathbf { e} _{i}\wedge \mathbf {e} _{j})}ue^{(\theta /2)(\mathbf {e} _{i}\wedge \mathbf {e} _{j}) },$

var

$e^{(\theta /2)(\mathbf {e} _{i}\wedge \mathbf {e} _{j})}=\cos(\theta /2)+\sin(\theta /2)\mathbf {e} _{i}\wedge \mathbf {e} _{j}.$

Dimension 3

Se även: Euler-vinklar och Davenport-rotationer

Det finns tre Givens-rotationer i dimension 3:

$R_{X}(\theta )={\begin{bmatrix}1&0&0\\0&\cos \theta &-\sin \theta \\0&\sin \theta &\cos \theta \end{bmatrix}} .$

${\begin{aligned}\\R_{Y}(\theta )={\begin{bmatrix} \cos \theta &0&-\sin \theta \\0&1&0\\\sin \theta &0&\cos \theta \end{bmatrix}}\end{aligned}}$

${\begin{aligned}\\R_{Z}(\theta )={\begin{bmatrix}\cos \theta &-\sin \theta &0\\\sin \theta &\cos \theta &0\\0&0&1\end{bmatrix}}\end{aligned}}$

Med tanke på att de är endomorfismer kan de komponeras med varandra så många gånger som önskas, med tanke på att g ∘ f ≠ f ∘ g .

Dessa tre sammansatta Givens-rotationer kan generera vilken rotationsmatris som helst enligt Davenports chained rotation theorem . Detta innebär att de kan förvandla utrymmets standardbas till vilken annan ram som helst i utrymmet .

När rotationer utförs i rätt ordning kommer värdena på den slutliga ramens rotationsvinklar att vara lika med Euler-vinklarna för den slutliga ramen i motsvarande konvention. Till exempel, en operator $R=R_{Y}(\theta _{3}).R_{X}(\theta _{2}).R_{Z}(\theta _{1})$ transforms the basis of the space into a frame with angles roll, pitch and yaw $YPR=(\theta _{3},\theta _{2},\theta _{1})$ in the Tait–Bryan convention z-x-y (convention in which the line of nodes is perpendicular to z and Y axes, also named Y-X′-Z″).

Av samma anledning kan vilken rotationsmatris som helst i 3D brytas upp i en produkt av tre av dessa rotationsoperatorer .

Betydelsen av sammansättningen av två Givens-rotationer g ∘ f är en operator som transformerar vektorer först med f och sedan med g , vilket är f- och g -rotationer kring en basaxel i rummet. Detta liknar den yttre rotationsekvivalensen för Euler-vinklar.

Tabell över sammansatta rotationer

Följande tabell visar de tre Givens-rotationerna ekvivalenta med de olika Euler-vinklarkonventionerna med hjälp av yttre sammansättning (sammansättning av rotationer kring basaxlarna) av aktiva rotationer och den högerhänta regeln för vinklarnas positiva tecken.

Notationen har förenklats på så sätt att c ₁ betyder cos θ ₁ och s ₂ betyder sin θ ₂ ) . Vinklarnas underindex är den ordning i vilken de appliceras med hjälp av yttre sammansättning (1 för inre rotation, 2 för nutation, 3 för precession)

Eftersom rotationer tillämpas precis i motsatt ordning av Euler-vinklartabellen för rotationer , är denna tabell densamma men byter index 1 och 3 i vinklarna som är associerade med motsvarande post. En post som zxy betyder att först tillämpa y -rotationen, sedan x , och slutligen z , i basaxlarna.

Alla kompositionerna antar högerhandskonventionen för de matriser som multipliceras, vilket ger följande resultat.

xzx	${\begin{bmatrix}c_{2}&-c_{1}s_{2}&s_{1}s_{2}\\c_ {3}s_{2}&c_{3}c_{2}c_{1}-s_{3}s_{1}&-c_{2}c_{3}s_{1}-c_{1}s_{3 }\\s_{2}s_{3}&c_{3}s_{1}+c_{1}c_{2}s_{3}&c_{3}c_{1}-c_{2}s_{3}s_ {1}\end{bmatrix}}$	xzy	${\begin{bmatrix}c_{2}c_{3}&-c_{3}s_{2}c_{1}+ s_{3}s_{1}&c_{3}s_{2}s_{1}+s_{3}c_{1}\\s_{2}&c_{1}c_{2}&-c_{2}s_ {1}\\-s_{3}c_{2}&s_{3}s_{2}c_{1}+c_{3}s_{1}&-s_{3}s_{2}s_{1}+ c_{3}c_{1}\end{bmatrix}}$
xyx	${\begin{bmatrix}c_{2}&s_{1}s_{2}&c_{1}s_{2}\\s_{2 }s_{3}&c_{3}c_{1}-c_{2}s_{3}s_{1}&-c_{3}s_{1}-c_{1}c_{2}s_{3}\ \-c_{3}s_{2}&c_{3}c_{2}s_{1}+c_{1}s_{3}&c_{3}c_{2}c_{1}-s_{3}s_{ 1}\end{bmatrix}}$	xyz	${\begin{bmatrix}c_{3}c_{2}&-s_{3}c_{1}+c_{3}s_ {2}s_{1}&s_{3}s_{1}+c_{3}s_{2}c_{1}\\s_{3}c_{2}&c_{3}c_{1}+s_{3 }s_{2}s_{1}&-c_{3}s_{1}+s_{3}s_{2}c_{1}\\-s_{2}&c_{2}s_{1}&c_{2 }c_{1}\end{bmatrix}}$
yxy	${\begin{bmatrix}c_{3}c_{1}-c_{2}s_{3}s_{1}&s_{2} s_{3}&c_{3}s_{1}+s_{3}c_{2}c_{1}\\s_{1}s_{2}&c_{2}&-c_{1}s_{2}\ \-c_{2}c_{3}s_{1}-c_{1}s_{3}&c_{3}s_{2}&c_{3}c_{2}c_{1}-s_{3}s_{ 1}\end{bmatrix}}$	yxz	${\begin{bmatrix}c_{3}c_{1}-s_{3}s_{2}s_{1}&-s_{ 3}c_{2}&c_{3}s_{1}+s_{3}s_{2}c_{1}\\s_{3}c_{1}+c_{3}s_{2}s_{1} &c_{3}c_{2}&s_{3}s_{1}-c_{3}s_{2}c_{1}\\-c_{2}s_{1}&s_{2}&c_{2}c_{ 1}\end{bmatrix}}$
yzy	${\begin{bmatrix}c_{3}c_{2}c_{1}-s_{3}s_{1}&-c_{ 3}s_{2}&c_{2}c_{3}s_{1}+c_{1}s_{3}\\c_{1}s_{2}&c_{2}&s_{1}s_{2}\ \-c_{3}s_{1}-c_{1}c_{2}s_{3}&s_{2}s_{3}&c_{3}c_{1}-c_{2}s_{3}s_{ 1}\end{bmatrix}}$	yzx	${\begin{bmatrix}c_{2}c_{1}&-s_{2}&c_{2}s_{1}\\c_{ 3}s_{2}c_{1}+s_{3}s_{1}&c_{3}c_{2}&c_{3}s_{2}s_{1}-s_{3}c_{1}\\ s_{3}s_{2}c_{1}-c_{3}s_{1}&s_{3}c_{2}&s_{3}s_{2}s_{1}+c_{3}c_{1} \end{bmatrix}}$
zyz	${\begin{bmatrix}c_{3}c_{2}c_{1}-s_{3}s_{1}&-c_{ 2}s_{1}c_{3}-c_{1}s_{3}&c_{3}s_{2}\\c_{3}s_{1}+c_{1}c_{2}s_{3} &c_{3}c_{1}-c_{2}s_{3}s_{1}&s_{2}s_{3}\\-c_{1}s_{2}&s_{1}s_{2}&c_{ 2}\end{bmatrix}}$	zyx	${\begin{bmatrix}c_{2}c_{1}&-c_{2}s_{1}&s_{2}\ \s_{3}s_{2}c_{1}+c_{3}s_{1}&-s_{3}s_{2}s_{1}+c_{3}c_{1}&-s_{3 }c_{2}\\-c_{3}s_{2}c_{1}+s_{3}s_{1}&c_{3}s_{2}s_{1}+s_{3}c_{1} &c_{3}c_{2}\end{bmatrix}}$
zxz	${\begin{bmatrix}c_{3}c_{1}-c_{2}s_{1}s_{3}&-c_{ 3}s_{1}-c_{1}c_{2}s_{3}&s_{2}s_{3}\\c_{2}c_{3}s_{1}+c_{1}s_{3} &c_{3}c_{2}c_{1}-s_{3}s_{1}&-c_{3}s_{2}\\s_{1}s_{2}&c_{1}s_{2}&c_ {2}\end{bmatrix}}$	zxy	${\begin{bmatrix}c_{3}c_{1}+s_{3}s_{2}s_{1}&-c_ {3}s_{1}+s_{3}s_{2}c_{1}&s_{3}c_{2}\\c_{2}s_{1}&c_{2}c_{1}&-s_{ 2}\\-s_{3}c_{1}+c_{3}s_{2}s_{1}&s_{3}s_{1}+c_{3}s_{2}c_{1}&c_{3 }c_{2}\end{bmatrix}}$

Se även

• Jacobi rotation
• Rotationsplan
• Hushållarförvandling
• Davenport rotationer

Citat

• Bindel, D.; Demmel, J.; Kahan, W.; Marques, O. (2000), On Computing ger rotationer tillförlitligt och effektivt . LAPACK Working Note 148, University of Tennessee, UT-CS-00-449, 31 januari 2001.
• Cybenko, George (mars–april 2001), "Reducing Quantum Computations to Elementary Unitary Operations" (PDF) , Computing in Science and Engineering , 3 (2): 27–32, doi : 10.1109/5992.908999
•   Golub, Gene H .; Van Loan, Charles F. (1996), Matrix Computations (3:e upplagan), Johns Hopkins, ISBN 978-0-8018-5414-9 .
•   Tryck, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Avsnitt 11.3.1. Givens Method" , Numeriska recept: The Art of Scientific Computing (3:e upplagan), New York: Cambridge University Press, ISBN 978-0-521-88068-8