ハウスホルダー変換の使用
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/28 14:18 UTC 版)
「QR分解」の記事における「ハウスホルダー変換の使用」の解説
QR分解のためのハウスホルダー変換: 目標はベクトル x {\displaystyle x} を同じ長さかつ e 1 {\displaystyle e_{1}} の共線であるベクトルに変換する線形変換を見つけることである。直交射影(グラム・シュミット法)を使うこともできるが、ベクトル x {\displaystyle x} と e 1 {\displaystyle e_{1}} が直交に近い場合、数値的に不安定である。代わりに、ハウスホルダー変換により点線を通して鏡映する(点線は x {\displaystyle x} と e 1 {\displaystyle e_{1}} のなす角の二等分線)。この変換による最大角は45度である。 ハウスホルダー変換 (またはハウスホルダー鏡映)はベクトルを取り、平面または超平面に関する鏡映をする変換である。この演算はm×n行列 A {\displaystyle A} (m ≥ n)のQR変換の計算に使うことができる。 Qは一つの座標を除いたすべての座標が未知でもベクトルを鏡映するために使用できる。 スカラαに対して ‖ x ‖ = | α | {\displaystyle \|{\boldsymbol {x}}\|=|\alpha |} を満たすような A {\displaystyle A} の任意の実m次元列ベクトル x {\displaystyle {\boldsymbol {x}}} を考える。もしこのアルゴリズムが浮動小数点演算を用いて実装されている場合、桁落ちを防ぐため、行列Aの最終的な上三角部分においてすべての要素が0である後のピボット座標 x k {\displaystyle x_{k}} に対し、αを x {\displaystyle {\boldsymbol {x}}} のk番目の座標の逆符号とする。複素行列の場合、 α = − exp ( i arg x k ) ‖ x ‖ {\displaystyle \alpha =-\exp(i\arg x_{k})\|{\boldsymbol {x}}\|} (Stoer & Bulirsch 2002, p. 225)とし、以下のQの導出において転置を共役転置に読み替えること。 ここで、 e 1 {\displaystyle {\boldsymbol {e}}_{1}} をベクトル(1 0 … 0)T、||·||をユークリッド距離、 I {\displaystyle I} をm×m単位行列とし、 u = x − α e 1 , v = u ‖ u ‖ , Q = I − 2 v v T {\displaystyle {\begin{aligned}{\boldsymbol {u}}&={\boldsymbol {x}}-\alpha {\boldsymbol {e}}_{1},\\{\boldsymbol {v}}&={{\boldsymbol {u}} \over \|{\boldsymbol {u}}\|},\\Q&=I-2{\boldsymbol {v}}{\boldsymbol {v}}^{\textsf {T}}\end{aligned}}} あるいは、 A {\displaystyle A} が複素行列ならば、 Q = I − 2 v v ∗ {\displaystyle Q=I-2{\boldsymbol {v}}{\boldsymbol {v}}^{*}} とおく。 Q {\displaystyle Q} はm×mハウスホルダー行列であり、 Q x = [ α 0 ⋯ 0 ] T {\displaystyle Q{\boldsymbol {x}}={\begin{bmatrix}\alpha &0&\cdots &0\end{bmatrix}}^{\textsf {T}}\ } これによりm×n行列Aを上三角の形に漸次変換できる。まず、xの最初の列を選んで得られるハウスホルダー行列Q1にAを乗算する。この結果、行列Q1Aは左の列が(最初の行を除き)ゼロになる。 Q 1 A = [ α 1 ⋆ … ⋆ 0 ⋮ A ′ 0 ] {\displaystyle Q_{1}A={\begin{bmatrix}\alpha _{1}&\star &\dots &\star \\0&&&\\\vdots &&A'&\\0&&&\end{bmatrix}}} この操作をA′ (Q1Aから最初の列と最初の行を除いたもの)に繰り返すと、ハウスホルダー行列Q′2が得られる。Q′2はQ1より小さいということに注意すること。A′の代わりにQ1Aで計算したいため、A′を左上に拡張し、ひとつの1を埋める必要がある。つまり、一般的には Q k = [ I k − 1 0 0 Q k ′ ] {\displaystyle Q_{k}={\begin{bmatrix}I_{k-1}&0\\0&Q_{k}'\end{bmatrix}}} とする。 t {\displaystyle t} 回このプロセスを繰り返すと、 t = min ( m − 1 , n ) {\displaystyle t=\min(m-1,n)} のとき、 R = Q t ⋯ Q 2 Q 1 A {\displaystyle R=Q_{t}\cdots Q_{2}Q_{1}A} は上三角行列である。であるからして、 Q = Q 1 T Q 2 T ⋯ Q t T {\displaystyle Q=Q_{1}^{\textsf {T}}Q_{2}^{\textsf {T}}\cdots Q_{t}^{\textsf {T}}} とすると、 A = Q R {\displaystyle A=QR} は A {\displaystyle A} のQR分解である。 このメソッドは先述のグラム・シュミット法よりも数値的安定性がある。 下表にサイズnの正方行列を仮定したときの、ハウスホルダー変換によるQR分解のk番目のステップにおける計算量を示す。 演算k番目のステップにおける計算量乗算 2 ( n − k + 1 ) 2 {\displaystyle 2(n-k+1)^{2}} 加算 ( n − k + 1 ) 2 + ( n − k + 1 ) ( n − k ) + 2 {\displaystyle (n-k+1)^{2}+(n-k+1)(n-k)+2} 除算 1 {\displaystyle 1} 平方根 1 {\displaystyle 1} これらの数をn − 1ステップ(サイズnの正方行列であるため)まで合計して、このアルゴリズムの(浮動小数点演算の観点からの)複雑さは 2 3 n 3 + n 2 + 1 3 n − 2 = O ( n 3 ) {\displaystyle {\frac {2}{3}}n^{3}+n^{2}+{\frac {1}{3}}n-2=O\left(n^{3}\right)} と表せる。
※この「ハウスホルダー変換の使用」の解説は、「QR分解」の解説の一部です。
「ハウスホルダー変換の使用」を含む「QR分解」の記事については、「QR分解」の概要を参照ください。
- ハウスホルダー変換の使用のページへのリンク
