ギブンズローテーション

数値線形代数において、ギブンズ回転は2 つの座標軸が張る平面での回転です。ギブンズ回転は、1950 年代にアルゴンヌ国立研究所で働いていたときに数値解析者にこの回転を導入したウォレス ギブンズにちなんで名付けられました。

行列の左から作用するギブンズ回転は行演算であり、行間でデータを移動しますが、常に同じ列内にあります。行加算の基本演算とは異なり、ギブンズ回転は、それによってアドレス指定された両方の行を変更します。回転の仕組みを理解するには、1 つのターゲット行の要素を を通じて で表し、もう 1 つのターゲット行の要素を を通じて で表します。この場合、 ギブンズ回転の効果は、各サブベクトルを同じ角度で回転することです。行加算と同様に、アルゴリズムでは、特定の 1 つの要素が 0 になるようにこの角度を選択することが多く、残りの列で何が起こっても、許容できる副作用と見なされます。 ${\displaystyle x_{1}}$${\displaystyle x_{n}}$${\displaystyle y_{1}}$${\displaystyle y_{n}}$$${\displaystyle {\begin{bmatrix}\vdots &\vdots &\ddots &\vdots \\x_{1}&x_{2}&\dots &x_{n}\\\vdots &\vdots &\ddots &\vdots \\y_{1}&y_{2}&\dots &y_{n}\\\vdots &\vdots &\ddots &\vdots \end{bmatrix}}}$$${\displaystyle (x_{k},y_{k})}$

行列に右から作用するギブンズ回転は、列演算であり、2 つの列間でデータを移動しますが、常に同じ行内にあります。左からの作用と同様に、各サブベクトルを同じ角度で回転させますが、ここでこれらの名前付き要素は、行列内で次のように発生します。 一部のアルゴリズム、特に行列の相似性 を維持するアルゴリズムでは、ギブンズ回転を共役作用として適用します。つまり、2 つの行間で 1 角度回転し、対応する列間で同じ角度回転します。この場合、両方の回転の影響を受ける 4 つの要素への影響はより複雑です。ヤコビ回転は、これらの 4 つのうち 2 つの非対角要素をゼロにする目的で、このような共役作用です。 ${\displaystyle (x_{k},y_{k})}$$${\displaystyle {\begin{bmatrix}\dots &x_{1}&\dots &y_{1}&\dots \\\dots &x_{2}&\dots &y_{2}&\dots \\\ddots &\vdots &\ddots &\vdots &\ddots \\\dots &x_{n}&\dots &y_{n}&\dots \end{bmatrix}}}$$

数値線形代数におけるギブンズ回転の主な用途は、ベクトルまたは行列を、特定の係数がゼロである特殊な形式に変換することです。この効果は、たとえば、行列のQR 分解を計算するために使用できます。ハウスホルダー変換に対する利点の 1 つは、簡単に並列化できることです。もう 1 つの利点は、非常に疎な行列の場合、演算数が少なくなることです。

ギブンズ回転は次のような 行列で表される。

${\displaystyle G(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 &\ddots &\vdots \\0&\cdots &0&\cdots &0&\cdots &1\end{bmatrix}},}$

ここで、c = cos  θおよびs = sin  θ は、 i番目とj番目の行と列の交点に現れます。つまり、i > jが固定されている場合、ギブンズ行列の非ゼロ要素は次のように表されます。

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

積G ( i ,  j ,  θ ) x は、 ( i ,  j )平面におけるベクトル xのθラジアンの反時計回りの回転を表すため、ギブンズ回転と呼ばれます。

ギブンズ回転行列G ( i ,  j ,  θ )を別の行列Aに左から掛け合わせると、G Aとなり、Aのi行目とj行目のみが影響を受ける。したがって、次の反時計回りの問題に注目する。aとb が与えられたとき、c = cos  θとs = -sin  θを求め、

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

ここで はベクトルの長さです。θを明示的に計算する必要も望ましくもありません。代わりにcとs を直接求めます。明らかな解決策は次のようになります。 ${\displaystyle r={\sqrt {a^{2}+b^{2}}}}$${\displaystyle (a,b)}$

${\displaystyle {\begin{aligned}c&{}\leftarrow a/r\\s&{}\leftarrow -b/r.\end{aligned}}}$^[1]

しかし、 rの計算はオーバーフローまたはアンダーフローする可能性があります。この問題を回避する別の定式化 (Golub & Van Loan 1996、§5.1.8) は、多くのプログラミング言語でhypot関数として実装されています。

次の Fortran コードは、実数のギブンズ回転の最小限の実装です。入力値 'a' または 'b' が頻繁にゼロになる場合は、ここに示すように、これらのケースを処理するようにコードを最適化できます。

サブルーチンgivens_rotation ( a 、b 、c 、s 、r )    

実数a 、b 、c 、s 、r実数h 、d    
 

b . ne . 0.0の場合h = hypot ( a , b ) d = 1.0 / h c = abs ( a ) * d s = sign ( d , a ) * b r = sign ( 1.0 , a ) * hそれ以外の場合c = 1.0 s = 0.0 r = a終了    
       
        
        
         
         

      
      
      


戻る
終了

さらに、エドワード・アンダーソンがLAPACKの 改良で発見したように、これまで見落とされていた数値的考慮は連続性です。これを実現するには、rが正である必要があります。^[2]次のMATLAB / GNU Octaveコードはアルゴリズムを示しています。

function [c, s, r] = givens_rotation ( a, b ) if b == 0 ; c = sign ( a ); if ( c == 0 ); c = 1.0 ; % 他の言語とは異なり、MatLab の sign 関数は入力 0 に対して 0 を返します。end ; s = 0 ; r = abs ( a ); elseif a == 0 ; c = 0 ; s = - sign ( b ); r = abs ( b ); elseif abs ( a ) > abs ( b ); t = b / a ; u = sign ( a ) * sqrt ( 1 + t * t ); c = 1 / u ; s = - c * t ; r = a * u ; else t = a / b ; u = sign ( b ) * sqrt ( 1 + t * t ); s = - 1 / u ; c = t / u ; r = b * u ;終了終了 
       
          
           
               
        
          
          
       
          
          
          
       
            
                
            
            
            
    
            
                
            
            
            
    

IEEE 754 copysign(x,y)関数は、 の符号yを にコピーする安全で安価な方法を提供しますx。これが利用できない場合は、上記と同様に、 abs関数とsgn関数を使用して| x |⋅sgn( y )を実行することもできます。

次の3 × 3行列があるとします。

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

ギブンズ回転を2回反復すると（ここで使用されるギブンズ回転アルゴリズムは上記と若干異なることに注意）、QR分解を計算するための上三角行列が生成されます。

目的の行列を形成するには、要素(2, 1)と(3, 2)をゼロにする必要があります。要素(2, 1)は、次の回転行列を使用して最初にゼロにされます。

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

行列の乗算の結果は次のようになります。

${\displaystyle {\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}}}$

どこ

${\displaystyle {\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}}}$

cとsにこれらの値を使用し、上記の行列乗算を実行すると、A ₂が生成されます。

${\displaystyle A_{2}\approx {\begin{bmatrix}7.8102&4.4813&2.5607\\0&-2.4327&3.0729\\0&4&3\\\end{bmatrix}}}$

要素(3, 2)をゼロにするとプロセスは終了します。前と同じ考え方を使用すると、回転行列は次のようになります。

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

その後、行列の乗算は次のようになります。

${\displaystyle {\begin{aligned}G_{2}A_{2}&{}=A_{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}}}$

どこ

${\displaystyle {\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}}}$

cとsにこれらの値を使用して乗算を実行すると、結果はA ₃になります。

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

この新しい行列A ₃は、 QR 分解の反復を実行するために必要な上三角行列です。Q は、回転行列の転置を使用して次のように形成されます。

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

この行列乗算を実行すると次のようになります。

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

これにより、ギブンズ回転の 2 回の反復が完了し、QR 分解の計算が実行できるようになります。

上記の計算を、行列の固有値を求めるQR アルゴリズムのステップとして実行する場合、次に行列 を計算しますが、最初に と を掛けてを形成するのではなく、それぞれ(右側)を掛けます。その理由は、右側のギブンズ行列を掛けるたびに の 2 つの列のみが変化するため、必要なのは単なる算術演算であり、ギブンズ回転の場合、合計すると算術演算になるからです。一般行列を掛けるには算術演算が必要になります。同様に、行列全体を格納すると個の要素になりますが、各ギブンズ行列はそのペアと によって完全に指定されるため、それらの 個は 個の要素に格納できます。 ${\displaystyle RQ}$${\displaystyle G_{1}^{T}}$${\displaystyle G_{2}^{T}}$${\displaystyle Q}$${\displaystyle G_{k}^{T}}$${\displaystyle RG_{1}^{T}\dots G_{k-1}^{T}}$${\displaystyle R}$${\displaystyle O(n)}$${\displaystyle n-1}$${\displaystyle O(n^{2})}$${\displaystyle n\times n}$${\displaystyle Q}$${\displaystyle O(n^{3})}$${\displaystyle Q}$${\displaystyle n^{2}}$${\displaystyle (c,s)}$${\displaystyle n-1}$${\displaystyle 2n-2}$

この例では、 $${\displaystyle {\begin{aligned}RQ=A_{3}(G_{1}^{T}G_{2}^{T})={}&(A_{3}G_{1}^{T})G_{2}^{T}\\\approx {}&{\begin{bmatrix}8.8687&-1.5575&2.5607\\2.9972&3.5965&0.9665\\0&0&-4.1843\end{bmatrix}}G_{2}^{T}\approx {\begin{bmatrix}8.8687&2.9972&0.0\\2.9972&-1.0430&-3.5750\\0&-3.5750&2.1742\end{bmatrix}}\end{aligned}}}$$

別の方法では、ギブンズ回転を複素行列に拡張できます。対角要素が単位絶対値を持ち、位相が任意の対角行列はユニタリです。A を、i および j>i の行と列を使用して ji 要素を 0 にしたい行列とします。D を、同じく単位絶対値を持ち、位相を決定する必要がある ii および jj 対角要素を除いて対角要素が 1 である対角行列とします。D の ii および jj 要素の位相は、積行列 DA の ii および ji 要素が実数になるように選択できます。次に、i および j>i の行と列を使用して、積行列 GDA の ji 要素が 0 になるようにギブンズ回転 G を選択できます。ユニタリ行列の積はユニタリなので、積行列 GD はユニタリであり、そのような行列ペアの積の積もユニタリです。

クリフォード代数と幾何代数などのその子構造では、回転はバイベクトルによって表されます。ギブンズ回転は基底ベクトルの外積によって表されます。任意の基底ベクトルのペアが与えられた場合、ギブンズ回転バイベクトルは次のようになります。 ${\displaystyle \mathbf {e} _{i},\mathbf {e} _{j}}$

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

任意のベクトルに対するそれらの動作は次のように記述されます。

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

どこ

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

次元 3 には 3 つのギブンズ回転があります。

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

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

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

これらは自己準同型なので、g  ∘  f ≠ f  ∘  gであることを念頭に置いて、必要な回数だけ互いに合成することができます。

これら 3 つのギブンズ回転を組み合わせると、ダベンポートの連鎖回転定理に従って任意の回転行列を生成できます。つまり、空間の標準基底を空間内の他の任意のフレームに変換できます。 [説明^が必要]

回転が正しい順序で実行されると、最終フレームの回転角度の値は、対応する規則における最終フレームのオイラー角と等しくなります。たとえば、演算子は、空間の基底を、Tait-Bryan 規則z - x - y (ノードのラインがz軸とY軸に垂直になる規則。Y - X′ - Z″とも呼ばれる) の角度ロール、ピッチ、ヨーを持つフレームに変換します。 ${\displaystyle R=R_{Y}(\theta _{3})\cdot R_{X}(\theta _{2})\cdot R_{Z}(\theta _{1})}$${\displaystyle YPR=(\theta _{3},\theta _{2},\theta _{1})}$

同じ理由で、3D の任意の回転行列は、これらの回転演算子3 つの積に分解できます。

2 つのギブンズ回転g  ∘  fの合成の意味は、ベクトルを最初にfで変換し、次にgで変換する演算子であり、空間の基底の 1 つの軸の周りのfとgの回転です。これは、オイラー角の外部回転の等価性に似ています。

次の表は、アクティブ回転の外在的合成 (基底軸を中心とした回転の合成)と角度の正の符号に対する右手規則 を使用して、さまざまなオイラー角規則に相当する 3 つのギブンズ回転を示しています。

表記は簡略化されており、c _{1 は}cos θ  1 _、 s 2_はsin  θ ₂を意味します。角度のサブインデックスは、外在的合成を使用して適用される順序です（1 は内在的回転、2 は章動、3 は歳差運動）。

回転はオイラー角の回転表とちょうど逆の順序で適用されるため、この表は対応するエントリに関連付けられた角度のインデックス 1 と 3 を入れ替えた以外は同じです。zxy のようなエントリは、最初にy回転を適用し、次にx 回転、最後にz 回転を基準軸に 適用することを意味します。

すべての合成では、乗算される行列に対して右手の規則が想定されており、次の結果が得られます。

• ヤコビ回転
• 回転面
• 世帯主の変革
• ダベンポートローテーション

• Bindel, D.; Demmel, J.; Kahan, W.; Marques, O. (2000)、ギブンズ回転の信頼性と効率のよい計算についてLAPACKワーキングノート148、テネシー大学、UT-CS-00-449、2001年1月31日。
• Cybenko, George (2001 年 3 月～4 月)、「量子計算を基本的なユニタリ演算に縮小する」(PDF)、Computing in Science and Engineering、3 (2): 27–32、doi :10.1109/5992.908999、2016年 3 月 3 日にオリジナル(PDF)からアーカイブ、 2009 年2 月 26 日に取得
• ゴルブ、ジーン H. ;ヴァン・ローン、チャールズ F. (1996)、マトリックス計算(第 3 版)、ジョンズ・ホプキンス、ISBN 978-0-8018-5414-9。
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007)、「セクション 11.3.1. ギブンズ法」、Numerical Recipes: The Art of Scientific Computing (第 3 版)、ニューヨーク: Cambridge University Press、ISBN 978-0-521-88068-8、2011年8月11日にオリジナルからアーカイブされ、2011年8月13日に取得