QR分解
ハウスホルダー変換 (またはハウスホルダー鏡映)はベクトルを取り、平面または超平面に関する鏡映をする変換である。この演算は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.
QR分解はギブンス回転を使用しても計算できる。各回転により行列の亜対角要素がゼロになり、R行列を構成できる。すべてのギブンス回転を結合することで直交行列Qを構成できる。
実際には、行列全体を構成して乗算をするようなギブンス回転は行われない。代わりに、疎な要素を計算するような無駄な計算をしない、疎なギブンス行列乗算と同等なあるギブンス回転の手順が採られる。そのギブンス回転の手順は少しの非対角成分をゼロにするだけで済み、ハウスホルダー変換よりも容易に並列化できる。
QR分解の定義を非正方行列に導入し、固有値を特異値に置き換えることで、上記性質を非正方行列 A {\displaystyle A} に拡張することができる。
非正方行列AのQR分解を
A = Q [ R O ] , Q ∗ Q = I {\displaystyle A=Q{\begin{bmatrix}R\\O\end{bmatrix}},\qquad Q^{*}Q=I}
とする。ただし、 O {\displaystyle O} は零行列、 Q {\displaystyle Q} はユニタリ行列。
特異値分解と行列式の性質から、 σ i {\displaystyle \sigma _{i}} を A {\displaystyle A} の特異値として、
| ∏ i r i i | = ∏ i σ i {\displaystyle \left|\prod _{i}r_{ii}\right|=\prod _{i}\sigma _{i}}
A {\displaystyle A} と R {\displaystyle R} の特異値は同じであるが、複素固有値が異なる場合があることに注意すること。しかしながら、Aが正方ならば、下記は真である。
∏ i σ i = | ∏ i λ i | {\displaystyle {\prod _{i}\sigma _{i}}=\left|{\prod _{i}\lambda _{i}}\right|}
結論として、QR分解を使うことによって行列の固有値や特異値の積を効率よく計算することができる。
64911&-55.97231&16.76007\\6&167&-68\\0&6.64078&-37.6311\end{bmatrix}}}
同様にしてそれぞれ非対角要素 a 21 {\displaystyle a_{21}} ・ a 32 {\displaystyle a_{32}} 要素がゼロであるようなギブンス行列 G 2 {\displaystyle G_{2}} ・ G 3 {\displaystyle G_{3}} を構成し、三角行列 R {\displaystyle R} を構成する。直交行列 Q T {\displaystyle Q^{\textsf {T}}} はすべてのギブンス行列の積 Q T = G 3 G 2 G 1 {\displaystyle Q^{\textsf {T}}=G_{3}G_{2}G_{1}} で表される。したがって、 G 3 G 2 G 1 A = Q T A = R {\displaystyle G_{3}G_{2}G_{1}A=Q^{\textsf {T}}A=R} であり、QR分解は A = Q R {\displaystyle A=QR} である。