QR分解
RQ分解は行列Aを上三角行列R(別名右三角)と直交行列Qに変換する。QR分解との違いはこれらの行列の順番だけである。
QR分解はグラム・シュミットの正規直交化法をAの最初の列から最後の列の順に適用する。
RQ分解はグラム・シュミットの正規直交化法をAの最後の行から最初の行の順に適用する。
より一般的に、m ≥ nである複素m×n行列Aを、m×mユニタリ行列Qとm×n上三角行列Rに分解することができる。m×n上三角行列の下から(m−n)行はすべてゼロであるため、Rや、RとQ両方の分割を簡単に行うことができる。
A = Q R = Q [ R 1 0 ] = [ Q 1 , Q 2 ] [ R 1 0 ] = Q 1 R 1 {\displaystyle A=QR=Q{\begin{bmatrix}R_{1}\\0\end{bmatrix}}={\begin{bmatrix}Q_{1},Q_{2}\end{bmatrix}}{\begin{bmatrix}R_{1}\\0\end{bmatrix}}=Q_{1}R_{1}}
ここで、R1はn×n上三角行列、0は(m − n)×n零行列、Q1はm×n行列、Q2はm×(m − n)行列で、Q1とQ2は両方直交する列を持つ。
Q1R1をGolub & Van Loan (1996, §5.2)はAの薄い(thin)QR分解と呼び、 Trefethen & Bauは軽減(reduced)QR分解と呼んでいる。もしAが最大階数nであり、R1の対角成分を正にするならば、R1とQ1は一意に定まる。しかし一般的にQ2はそうではない。R1はA A (Aが実行列の場合AAに等しい)のコレスキー分解の上三角部分に等しい。
QR分解を計算する手法として、グラム・シュミット分解、ハウスホルダー変換、ギブンス回転などがある。それぞれ利点と欠点がある。
225)とし、以下のQの導出において転置を共役転置に読み替えること。
ここで、 e 1 {\displaystyle {\boldsymbol {e}}_{1}} をベクトル(1 0 ... 0)、||·||をユークリッド距離、 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ハウスホルダー行列であり、
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番目のステップにおける計算量を示す。
これらの数を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は列のピボットの新しいステップにおいて、それぞれ初めに残りの列で最も大きいものを取るという点で、通常のグラム・シュミット法とは異なっている。したがって、置換行列Pを次のように導入する。
A P = Q R ⟺ A = Q R P T {\displaystyle AP=QR\quad \iff \quad A=QRP^{\textsf {T}}}
列のピボットはAが(ほぼ)階数落ちである、またはその疑いがある場合に便利である。また、数値的精度を向上させることもできる。通常、Rの対角成分が非増加、つまり | r 11 | ≥ | r 22 | ≥ ... ≥ | r n n | {\displaystyle \left|r_{11}\right|\geq \left|r_{22}\right|\geq \ldots \geq \left|r_{nn}\right|} となるようにPを選ぶ。この手段により特異値分解よりも低い計算コストでAの(数値的な)階数を求めることができ、いわゆるRank Revealing QR分解(英語版)の基礎となっている。