QR分解のソースを表示

{{参照方法|date=2020年8月}}
{{ページ番号|date=2020年8月}}
{{翻訳直後|1=[http://en.wikipedia.org/w/index.php?title=QR_decomposition&oldid=983984255 英語版 "QR decomposition" 13:16, 17 October 2020 (UTC)]|date=2020年11月 }}
'''QR分解'''（キューアールぶんかい、{{lang-en-short|QR decomposition, QR factorization}}）とは、''m'' × ''n'' 実行列 ''A''を、 ''m'' 次[[直交行列]] ''Q'' と ''m'' × ''n'' [[三角行列|上三角行列]] ''R'' との積への分解により表すこと、またはそう表した表現をいう{{sfn|Golub|Van Loan|2013|loc={{google books quote|id=X5YfsuCWpxMC|page=246|5.2 The QR Factorization}}}}。このような分解は常に存在する{{sfn|Golub|Van Loan|2013|loc={{google books quote|id=X5YfsuCWpxMC|page=246|Theorem 5.2.1 (QR Factorization)}}}}。

QR分解は[[最小二乗法|線型最小二乗問題]]を解くために使用される。また、[[固有値問題の数値解法]]の1つである[[QR法]]の基礎となっている。

==定義==

===正方行列===
すべての実[[正方行列]] ''A''は[[直交行列]]''Q''と上[[三角行列]](別名右三角行列)''R''を用いて
: <math> A = QR</math>
と分解できる。もし''A''が[[正則行列|正則]]ならば、''R''の対角成分が正になるような因数分解は一意に定まる。

もし''A''が複素正方行列ならば、''Q''が[[ユニタリ行列]] (つまり<math>Q^* Q = QQ^* = I</math>)となるような分解''A'' = ''QR''が存在する。

もし''A''が''n''個の[[線形独立]]な列を持つなら、''Q''の最初の''n''列は''A''の[[列空間]]の[[正規直交基底]]をなす。より一般的に、1&nbsp;≤&nbsp;''k''&nbsp;≤&nbsp;''n''の任意の''k''について、''Q''の最初の''k''列は''A''の最初の''k''列の[[線型包]]をなす<ref name=Trefethen>L. N. Trefethen and D. Bau, ''Numerical Linear Algebra'' (SIAM, 1997).</ref>''。A''の任意の列''k''が''Q''の最初の''k''列にのみ依存するということは、''R''が三角行列であることから明らかである<ref name=Trefethen/>。

===矩形行列===
より一般的に、''m''&nbsp;≥&nbsp;''n''である複素''m''×''n''行列''A''を、''m''×''m''[[ユニタリ行列]]''Q''と''m''×''n''上三角行列''R''に分解することができる。''m''×''n''上三角行列の下から(''m''−''n'')行はすべてゼロであるため、''R''や、''R''と''Q''両方の分割を簡単に行うことができる。
:<math>
  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 
</math>

ここで、''R''<sub>1</sub>は''n''×''n''上三角行列、''0''は(''m''&nbsp;−&nbsp;''n'')×''n''零行列、''Q''<sub>1</sub>は''m''×''n''行列、''Q''<sub>2</sub>は''m''×(''m''&nbsp;−&nbsp;''n'')行列で、''Q''<sub>1</sub>と''Q''<sub>2</sub>は両方直交する列を持つ。

''Q''<sub>1</sub>''R''<sub>1</sub>を{{harvtxt|Golub|Van Loan|1996|loc=§5.2}}はAの薄い(''thin'')QR分解と呼び、 Trefethen & Bauは軽減(''reduced'')QR分解と呼んでいる<ref name=Trefethen/>。もし''A''が最大[[行列の階数|階数]]''n''であり、''R''<sub>1</sub>の対角成分を正にするならば、''R''<sub>1</sub>と''Q''<sub>1</sub>は一意に定まる。しかし一般的に''Q''<sub>2</sub>はそうではない。''R''<sub>1</sub>は''A''<sup>*</sup> ''A'' (''A''が実行列の場合''A''<sup>T</sup>''A''に等しい)の[[コレスキー分解]]の上三角部分に等しい。

===QL・RQ・LQ分解===
同様に、''L''を下(''lower'')三角行列として、QL、RQ、LQ分解を定義することができる。

==QR分解の計算==
QR分解を計算する手法として、[[グラム・シュミットの正規直交化法|グラム・シュミット分解]]、[[ハウスホルダー変換]]、[[ギブンス回転]]などがある。それぞれ利点と欠点がある。

===グラム・シュミットの正規直交化法の使用===
{{details|グラム・シュミットの正規直交化法}}
[[グラム・シュミットの正規直交化法]]を最大階数行列の列<math>A = \left[\boldsymbol{a}_1, \ldots, \boldsymbol{a}_n\right]</math>に適用することを考える。[[内積]]<math>\langle\boldsymbol{v}, \boldsymbol{w}\rangle = \boldsymbol{v}^\textsf{T} \boldsymbol{w}</math> (複素ベクトルの場合 <math>\langle\boldsymbol{v}, \boldsymbol{w}\rangle = \boldsymbol{v}^* \boldsymbol{w}</math>)とする。

[[ベクトルの成分分解|射影]]の定義より、
:<math>\operatorname{proj}_{\boldsymbol{u}}\boldsymbol{a} =
  \frac{\left\langle\boldsymbol{u}, \boldsymbol{a}\right\rangle}{\left\langle\boldsymbol{u}, \boldsymbol{u}\right\rangle}{\boldsymbol{u}} 
</math>

したがって、
:<math>\begin{align}
  \boldsymbol{u}_1 &= \boldsymbol{a}_1, &
    \boldsymbol{e}_1 &= {\boldsymbol{u}_1 \over \|\boldsymbol{u}_1\|} \\
  \boldsymbol{u}_2 &= \boldsymbol{a}_2 - \operatorname{proj}_{\boldsymbol{u}_1}\,\boldsymbol{a}_2, &
    \boldsymbol{e}_2 &= {\boldsymbol{u}_2 \over \|\boldsymbol{u}_2\|} \\
  \boldsymbol{u}_3 &= \boldsymbol{a}_3 - \operatorname{proj}_{\boldsymbol{u}_1}\,\boldsymbol{a}_3 - \operatorname{proj}_{\boldsymbol{u}_2}\,\boldsymbol{a}_3, &
    \boldsymbol{e}_3 &= {\boldsymbol{u}_3 \over \|\boldsymbol{u}_3\|} \\
                 & \vdots &
                   & \vdots \\
  \boldsymbol{u}_k &= \boldsymbol{a}_k - \sum_{j=1}^{k-1}\operatorname{proj}_{\boldsymbol{u}_j}\,\boldsymbol{a}_k,&
    \boldsymbol{e}_k &= {\boldsymbol{u}_k \over \|\boldsymbol{u}_k\|}
\end{align} </math>

ここで<math>\boldsymbol{a}_i</math>を新しく計算された正規直交基底上に表すことができ、<math>\left\langle\boldsymbol{e}_i, \boldsymbol{a}_i\right\rangle = \left\|\boldsymbol{u}_i\right\|</math>であるから、
:<math>\begin{align}
   \boldsymbol{a}_1 &= \langle\boldsymbol{e}_1, \boldsymbol{a}_1\rangle \boldsymbol{e}_1 \\
   \boldsymbol{a}_2 &= \langle\boldsymbol{e}_1, \boldsymbol{a}_2\rangle \boldsymbol{e}_1
                 + \langle\boldsymbol{e}_2, \boldsymbol{a}_2\rangle \boldsymbol{e}_2 \\
   \boldsymbol{a}_3 &= \langle\boldsymbol{e}_1, \boldsymbol{a}_3\rangle \boldsymbol{e}_1
                 + \langle\boldsymbol{e}_2, \boldsymbol{a}_3\rangle \boldsymbol{e}_2
                 + \langle\boldsymbol{e}_3, \boldsymbol{a}_3\rangle \boldsymbol{e}_3 \\
                &\vdots \\
   \boldsymbol{a}_k &= \sum_{j=1}^k \langle \boldsymbol{e}_j, \boldsymbol{a}_k \rangle \boldsymbol{e}_j
\end{align} </math>

これは行列の形に書くことができ、
:<math>A = QR</math>

ただし、
:<math>Q = \left[\boldsymbol{e}_1, \ldots, \boldsymbol{e}_n\right],</math>

:<math>R = \begin{bmatrix}
  \langle\boldsymbol{e}_1, \boldsymbol{a}_1\rangle &
  \langle\boldsymbol{e}_1, \boldsymbol{a}_2\rangle &
  \langle\boldsymbol{e}_1, \boldsymbol{a}_3\rangle & \ldots \\
                                         0 &
  \langle\boldsymbol{e}_2, \boldsymbol{a}_2\rangle &
  \langle\boldsymbol{e}_2, \boldsymbol{a}_3\rangle & \ldots \\
                                         0 &
                                         0 &
  \langle\boldsymbol{e}_3, \boldsymbol{a}_3\rangle & \ldots \\
                                    \vdots &
                                    \vdots &
                                    \vdots &
                                    \ddots
\end{bmatrix} </math>

====例====
: <math>A = \begin{bmatrix}
  12 & -51 &   4 \\
   6 & 167 & -68 \\
  -4 &  24 & -41
\end{bmatrix}</math>
の分解を考える。

正規直交行列<math>Q</math>に対して、
: <math>Q^\textsf{T} \,Q = I</math>

が常に成り立つから、グラム・シュミット法により以下の手順で<math>Q</math>を計算できる。
: <math>\begin{align}
  U = \begin{bmatrix}
        \boldsymbol u_1 & \boldsymbol u_2 & \boldsymbol u_3
      \end{bmatrix} &=
      \begin{bmatrix}
        12 & -69 & -58/5 \\
         6 & 158 &   6/5 \\
        -4 &  30 & -33
      \end{bmatrix}; \\
  Q = \begin{bmatrix}
        \dfrac{\boldsymbol u_1}{\|\boldsymbol u_1\|} &
        \dfrac{\boldsymbol u_2}{\|\boldsymbol u_2\|} &
        \dfrac{\boldsymbol u_3}{\|\boldsymbol u_3\|}
      \end{bmatrix} &=
      \begin{bmatrix}
         6/7 & -69/175 & -58/175 \\
         3/7 & 158/175 &   6/175 \\
        -2/7 &   6/35  & -33/35
      \end{bmatrix} 
\end{align}</math>

したがって、
: <math>\begin{align}
  Q^\textsf{T} A &= Q^\textsf{T}Q\,R = R; \\
               R &= Q^\textsf{T}A =
    \begin{bmatrix}
      14 &  21 & -14 \\
       0 & 175 & -70 \\
       0 &   0 &  35
    \end{bmatrix} 
\end{align}</math>

====RQ分解との関係====
RQ分解は行列''A''を上三角行列''R''(別名右三角)と直交行列''Q''に変換する。QR分解との違いはこれらの行列の順番だけである。

QR分解はグラム・シュミットの正規直交化法を''A''の''最初の列''から''最後の列''の順に適用する。

RQ分解はグラム・シュミットの正規直交化法を''A''の''最後の行''から''最初の行''の順に適用する。

====利点と欠点====

グラム・シュミットの正規直交化法は本来、数値的に不安定である。射影の応用として直交化との幾何学的な類似性があるが、直交化自体は数値的な差異が生じやすい。しかしながら、実装が簡単という大きな利点があり、外部線形代数ライブラリが利用できない場合のプロトタイピングに便利なアルゴリズムである。

===ハウスホルダー変換の使用===
[[File:Householder.svg|thumb|QR分解のためのハウスホルダー変換: 目標はベクトル<math>x</math>を同じ長さかつ<math>e_1</math>の共線であるベクトルに変換する線形変換を見つけることである。直交射影(グラム・シュミット法)を使うこともできるが、ベクトル<math>x</math>と<math>e_1</math>が直交に近い場合、数値的に不安定である。代わりに、ハウスホルダー変換により点線を通して鏡映する(点線は<math>x</math>と<math>e_1</math>のなす角の二等分線)。この変換による最大角は45度である。]]

[[ハウスホルダー変換]] (または''ハウスホルダー鏡映'')はベクトルを取り、[[平面]]または[[超平面]]に関する鏡映をする変換である。この演算は''m''×''n''行列<math>A</math> (''m''&nbsp;≥&nbsp;''n'')の''QR''変換の計算に使うことができる。

''Q''は一つの座標を除いたすべての座標が未知でもベクトルを鏡映するために使用できる。

スカラ''α''に対して<math>\|\boldsymbol{x}\| = |\alpha|</math>を満たすような<math>A</math>の任意の実''m''次元列ベクトル<math>\boldsymbol{x}</math>を考える。もしこのアルゴリズムが[[浮動小数点数|浮動小数点演算]]を用いて実装されている場合、[[誤差#桁落ち|桁落ち]]（による誤差の拡大）を防ぐため、行列''A''の最終的な上三角部分においてすべての要素が0である後のピボット座標<math>x_k</math>に対し、''α''を<math>\boldsymbol{x}</math>の''k''番目の座標の逆符号とする。複素行列の場合には、
:<math>\alpha = -\exp(i \arg x_k) \|\boldsymbol{x}\|</math>
{{harv|Stoer|Bulirsch|2002|p=225}}として、さらに以下の''Q''の導出において転置を共役転置に読み替えること。

ここで、<math>\boldsymbol{e}_1</math>をベクトル(1 0 … 0)<sup>T</sup>、||·||を[[ユークリッド空間#ユークリッド空間の計量|ユークリッド距離]]、<math>I</math>を''m''×''m''単位行列とし、
: <math>\begin{align}
  \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{align}</math>

あるいは、<math>A</math>が複素行列ならば、
: <math>Q = I - 2\boldsymbol{v}\boldsymbol{v}^*</math>
とおく。

<math>Q</math>は''m''×''m''ハウスホルダー行列であり、
: <math>Q\boldsymbol{x} = \begin{bmatrix} \alpha & 0 & \cdots & 0 \end{bmatrix}^\textsf{T} \ </math>

これにより''m''×''n''行列''A''を上[[三角行列|三角]]の形に漸次変換できる。まず、'''x'''の最初の列を選んで得られるハウスホルダー行列''Q''<sub>1</sub>に''A''を乗算する。この結果、行列''Q''<sub>1</sub>''A''は左の列が(最初の行を除き)ゼロになる。
: <math>Q_1A = \begin{bmatrix}
  \alpha_1 & \star & \dots & \star \\
         0 &       &       &       \\
    \vdots &       &    A' &       \\
         0 &       &       &
\end{bmatrix}</math>

この操作を''A''′ (''Q''<sub>1</sub>''A''から最初の列と最初の行を除いたもの)に繰り返すと、ハウスホルダー行列''Q''′<sub>2</sub>が得られる。''Q''′<sub>2</sub>は''Q''<sub>1</sub>より小さいということに注意すること。''A''′の代わりに''Q''<sub>1</sub>''A''で計算したいため、''A''′を左上に拡張し、ひとつの1を埋める必要がある。つまり、一般的には
:<math>Q_k = \begin{bmatrix}
  I_{k-1} & 0    \\
       0  & Q_k'
\end{bmatrix}</math>
とする。
<math>t</math>回このプロセスを繰り返すと、<math>t = \min(m - 1, n)</math>のとき、
:<math>R = Q_t \cdots Q_2 Q_1 A</math>

は上三角行列である。そこで、
:<math>Q = Q_1^\textsf{T} Q_2^\textsf{T} \cdots Q_t^\textsf{T}</math>
とすると、
<math>A = QR</math>は<math>A</math>のQR分解である。

この鏡映変換を用いた計算方法は先述のグラム・シュミット法よりも[[数値的安定性]]がある。<!--下記例を参照、上記と比較せよ-->

下表にサイズ''n''の正方行列を仮定したときの、ハウスホルダー変換によるQR分解の''k''番目のステップにおける計算量を示す。
{| class="wikitable"
|-
! 演算
! ''k''番目のステップにおける計算量
|-
| 乗算
| <math>2(n - k + 1)^2</math>
|-
| 加算
| <math>(n - k + 1)^2 + (n - k + 1)(n - k) + 2 </math>
|-
| 除算
| <math>1</math>
|-
| 平方根
| <math>1</math>
|}

これらの数を''n''&nbsp;−&nbsp;1ステップ(サイズ''n''の正方行列であるため)まで合計して、このアルゴリズムの(浮動小数点演算の観点からの)複雑さは
:<math>\frac{2}{3}n^3 + n^2 + \frac{1}{3}n - 2 = O\left(n^3\right)</math>
と表せる。

====例====
: <math>A = \begin{bmatrix}
  12 & -51 &   4 \\
   6 & 167 & -68 \\
  -4 &  24 & -41
\end{bmatrix} </math>
の分解を考える。

まず、行列''A''の最初の列、ベクトル<math>\boldsymbol{a}_1 = \begin{bmatrix} 12 & 6 & -4 \end{bmatrix}^\textsf{T}</math>を、<math>\left\|\boldsymbol{a}_1\right\| \;\boldsymbol{e}_1 = \begin{bmatrix} 1 & 0 & 0\end{bmatrix}^\textsf{T} </math>に変換する鏡映を見つける必要がある。 

今、
: <math>\begin{align}
\boldsymbol{u} &= \boldsymbol{x} - \alpha\boldsymbol{e}_1, \\
\boldsymbol{v} &= \frac{\boldsymbol{u}}{\|\boldsymbol{u}\|}
\end{align}</math>
とする。

ここで、
: <math>\alpha = 14</math>であり、<math>\boldsymbol{x} = \boldsymbol{a}_1 = \begin{bmatrix} 12 & 6 & -4 \end{bmatrix}^\textsf{T} </math>

であるから、
: <math>\boldsymbol{u} = \begin{bmatrix} -2 & 6 & -4 \end{bmatrix}^\textsf{T} = \begin{bmatrix} 2 \end{bmatrix}\begin{bmatrix} -1 & 3 & -2 \end{bmatrix}^\textsf{T}</math> and <math>\boldsymbol{v} = {1 \over \sqrt{14}}\begin{bmatrix} -1 & 3 & -2 \end{bmatrix}^\textsf{T} </math>であり、
: <math>\begin{align}
      Q_1
  ={} &I - {2 \over \sqrt{14}\sqrt{14}}
         \begin{bmatrix} -1 \\ 3 \\ -2 \end{bmatrix}
         \begin{bmatrix} -1 &  3 &  -2 \end{bmatrix} \\
  ={} &I - {1 \over 7}\begin{bmatrix}
          1 & -3 &  2 \\
         -3 &  9 & -6 \\
          2 & -6 &  4
       \end{bmatrix} \\
  ={} &\begin{bmatrix}
          6/7 &  3/7 & -2/7 \\
          3/7 & -2/7 &  6/7 \\
         -2/7 &  6/7 &  3/7 \\
       \end{bmatrix}
\end{align} </math>
である。

今、
:<math>Q_1A = \begin{bmatrix}
  14 &  21 & -14 \\
   0 & -49 & -14 \\
   0 & 168 & -77
\end{bmatrix} </math>

を見てみると、すでにほぼ三角行列である。あとは(3, 2)要素を零にするだけでよい。

(1, 1)における[[小行列式|小行列]]を取り、同じプロセスを
:<math>A' = M_{11} = \begin{bmatrix}
  -49 & -14 \\
  168 & -77
\end{bmatrix} </math>
に再び適用する。

先述のメソッドと同様にして、このプロセスの次のステップが正しく動作するために、1で直和を取ることにより、ハウスホルダー変換
:<math>Q_2 = \begin{bmatrix}
  1 &     0 &  0 \\
  0 & -7/25 & 24/25 \\
  0 & 24/25 &  7/25
\end{bmatrix} </math>

を得る。

今、
:<math>Q = Q_1^\textsf{T} Q_2^\textsf{T} = \begin{bmatrix}
   6/7 & -69/175 & 58/175 \\
   3/7 & 158/175 & -6/175 \\
  -2/7 &   6/35  & 33/35
\end{bmatrix} </math>

または、有効数字四桁で、
:<math>\begin{align}
  Q &= Q_1^\textsf{T} Q_2^\textsf{T} = \begin{bmatrix}
     0.8571 & -0.3943 &  0.3314 \\
     0.4286 &  0.9029 & -0.0343 \\
    -0.2857 &  0.1714 &  0.9429
  \end{bmatrix} \\
  R &= Q_2 Q_1 A = Q^\textsf{T} A = \begin{bmatrix}
    14 &  21 & -14 \\
     0 & 175 & -70 \\
     0 &   0 & -35
  \end{bmatrix}
\end{align} </math>
を得た。

行列''Q''は直交行列であり、''R''は上三角行列であるため、''A'' = ''QR''は求めるべきQR分解である。

====利点と欠点====

ハウスホルダー変換の使用は、''R''行列のゼロを生成するメカニズムに鏡映を利用しているため、最もシンプルでかつ数値的に安定したQR分解アルゴリズムである。しかしながら、新しい零要素を生成する毎回の鏡映変化において行列''Q''と''R''両方の行列全体を書き換えるため、ハウスホルダー変換は必要とするメモリ帯域幅が多く、並列化できない。（ただし鏡映変換のブロック化に基づくブロック化ハウスホルダ変換を使えばメモリ帯域幅への要求を低減することができる）

===ギブンス回転の使用===
''QR''分解は[[ギブンス回転]]を使用しても計算できる。各回転により行列の亜対角要素がゼロになり、''R''行列を構成できる。すべてのギブンス回転を結合することで直交行列''Q''を構成できる。

実際には、行列全体を構成して乗算をするようなギブンス回転は行われない。代わりに、疎な要素を計算するような無駄な計算をしない、疎なギブンス行列乗算と同等なあるギブンス回転の手順が採られる。そのギブンス回転の手順は少しの非対角成分をゼロにするだけで済み、[[ハウスホルダー変換]]よりも容易に並列化できる。

====例====
: <math>A = \begin{bmatrix}
  12 & -51 &   4 \\
   6 & 167 & -68 \\
  -4 &  24 & -41
\end{bmatrix} </math>
の分解を考える。

まず、左下隅の要素、<math>\boldsymbol{a}_{31} = -4</math>をゼロにする回転行列を構成する必要がある。この行列<math>G_1</math>はギブンス回転で求めることができる。まずベクトル<math>\begin{bmatrix} 12 & -4 \end{bmatrix}</math>を、''X''軸に沿って回転させる。このベクトルは角度<math>\theta = \arctan\left[ {-(-4) \over 12}\right] </math>を持つ。直交ギブンス回転行列<math>G_1</math>を次のように作る。

:<math>\begin{align}
  G_1 &= \begin{bmatrix}
    \cos(\theta) & 0 & -\sin(\theta) \\
               0 & 1 &             0 \\
    \sin(\theta) & 0 &  \cos(\theta)
  \end{bmatrix} \\
      &\approx \begin{bmatrix}
    0.94868 & 0 & -0.31622 \\
    0       & 1 &  0       \\
    0.31622 & 0 &  0.94868 
  \end{bmatrix}
\end{align} </math>

ここで<math>G_1A</math>の結果は<math>\boldsymbol{a}_{31}</math>要素がゼロである。
:<math>G_1A \approx \begin{bmatrix}
  12.64911 & -55.97231 &  16.76007 \\
   6       & 167       & -68       \\
   0       &   6.64078 & -37.6311 
\end{bmatrix} </math>

同様にしてそれぞれ非対角要素<math>a_{21}</math>・<math>a_{32}</math>要素がゼロであるようなギブンス行列<math>G_2</math>・<math>G_3</math>を構成し、三角行列<math>R</math>を構成する。直交行列<math>Q^\textsf{T}</math>はすべてのギブンス行列の積<math>Q^\textsf{T} = G_3 G_2 G_1</math>で表される。したがって、<math>G_3 G_2 G_1 A = Q^\textsf{T} A = R</math>であり、''QR''分解は<math>A = QR</math>である。

====利点と欠点====

ギブンス回転によるQR分解は、アルゴリズムを完全に動かすのに必要な行の順序を決定するのが簡単ではないため、実装に最も手間がかかる。しかしながら、新しいゼロ要素<math>a_{ij}</math>がゼロになる予定の要素の行(i)とその上の行(j)にしか影響しないという特筆すべき利点がある。これにより、ギブンス回転アルゴリズムはハウスホルダー変換手法よりも帯域幅効率が良く、容易に並列化できる。

==行列式や固有値の積との関係==
QR分解を正方行列の[[行列式]]の絶対値を求めるのに利用できる。ある行列が<math>A = QR</math>と分解できるとする。このとき
:<math>\det(A) = \det(Q) \cdot \det(R)</math>
である。

''Q''はユニタリであるため、<math>|\det(Q)| = 1</math>である。したがって、<math>r_{ii}</math>を''R''の対角要素とすると、
:<math>\left|\det(A)\right| = \left|\det(R)\right| = \left|\prod_{i} r_{ii}\right|</math>

となる。

さらに、行列式は固有値の積に等しいため、<math>\lambda_i</math>を<math>A</math>の固有値とすると、
: <math>\left|\prod_{i} r_{ii}\right| = \left|\prod_{i} \lambda_{i}\right|</math>

となる。

QR分解の定義を非正方行列に導入し、固有値を特異値に置き換えることで、上記性質を非正方行列<math>A</math>に拡張することができる。

非正方行列''A''のQR分解を
: <math>A = Q \begin{bmatrix} R \\ O \end{bmatrix}, \qquad Q^* Q = I </math>

とする。ただし、<math>O</math>は零行列、<math>Q</math>はユニタリ行列。

[[特異値分解]]と行列式の性質から、<math>\sigma_i</math>を<math>A</math>の特異値として、
:<math>\left|\prod_i r_{ii}\right| = \prod_i\sigma_{i} </math>

<math>A</math>と<math>R</math>の特異値は同じであるが、複素固有値が異なる場合があることに注意すること。しかしながら、''A''が正方ならば、下記は真である。
:<math>{\prod_i \sigma_i} = \left|{\prod_i \lambda_i}\right|</math>

結論として、QR分解を使うことによって行列の固有値や特異値の積を効率よく計算することができる。

==列のピボット==
ピボットQRは列のピボット<ref>{{cite book |last1=Strang |first1=Gilbert |title=Linear Algebra and Learning from Data |date=2019 |publisher=Wellesley Cambridge Press |location=Wellesley |isbn=978-0-692-19638-0 |page=143 |edition=1}}</ref>の新しいステップにおいて、それぞれ初めに残りの列で最も大きいものを取るという点で、通常のグラム・シュミット法とは異なっている。したがって、[[置換行列]]''P''を次のように導入する。
:<math>AP = QR\quad \iff\quad A = QRP^\textsf{T}</math>

列のピボットは''A''が(ほぼ)[[行列の階数#性質|階数落ち]]である、またはその疑いがある場合に便利である。また、数値的精度を向上させることもできる。通常、''R''の対角成分が非増加、つまり<math>\left|r_{11}\right| \ge \left|r_{22}\right| \ge \ldots \ge \left|r_{nn}\right|</math>となるように''P''を選ぶ。この手段により[[特異値分解]]よりも低い計算コストで''A''の(数値的な)階数を求めることができ、いわゆる{{仮リンク|Rank Revealing QR分解|en|rank-revealing QR algorithm}}の基礎となっている。

==線形逆問題への利用==
行列の逆行列を直接求めるのに比べ、QR分解を利用した逆問題の解法は、[[条件数]]が減少していることからも分かるように、数値的に安定している<ref>Parker, Geophysical Inverse Theory, Ch1.13.</ref>。

次元が<math>m \times n</math>で階数が<math>m</math>であるような行列<math>A</math>に対して、劣決定(<math>m < n</math>)線形問題<math>Ax = b</math>を解くためには、まず<math>A</math>の転置行列のQR分解<math>A^\textsf{T} = QR</math>を求める。ただし、Qは直交行列(つまり、<math>Q^\textsf{T} = Q^{-1}</math>)であり、Rは<math>R = \begin{bmatrix} R_1 \\ 0 \end{bmatrix}</math>という特殊な形である。ここで、<math>R_1</math>は<math>m \times m</math>正方右三角行列、零行列は<math>(n-m) \times m</math>次元である。計算すると、この逆問題の解を次のように表すことができる。<math>
x = Q \begin{bmatrix}
    \left(R_1^\textsf{T}\right)^{-1}b \\
                           0
  \end{bmatrix}
</math>

ここで、<math>R_1^{-1}</math>は[[ガウスの消去法]]で計算でき、<math>\left(R_1^\textsf{T}\right)^{-1} b</math>は{{仮リンク|前方置換法|en|triangular matrix#Forward and back substitution}}を用いることで直接計算できる。後者の手法の方が数値的精度が高く、計算量も少ないという利点がある。

ノルム<math>\|A \hat{x} - b\|</math>を最小にするような過決定(<math>m \geq n</math>)問題<math>Ax = b</math>の解<math>\hat{x}</math>を求めるためには、まず<math>A</math>のQR分解<math>A = QR</math>を求める。<math>Q_1</math>を直交行列<math>Q</math>全体のうち最初の<math>n</math>列を含む<math>m \times n</math>行列、<math>R_1</math>を先述の通りに置くと、この問題の解は<math>\hat{x} = R_1^{-1} \left(Q_1^\textsf{T} b\right) </math>と表せる。劣決定の場合と同様に、<math>R_1</math>の逆行列を直接計算しなくても、{{仮リンク|後方置換法|en|triangular matrix#Forward and back substitution}}を用いることで早く正確に<math>\hat x</math>を求めることができる。(<math>Q_1</math>と<math>R_1</math>は数値ライブラリによっては高速な(''economic'')QR分解として実装されている。)

==一般化==
{{仮リンク|岩澤分解|en|Iwasawa decomposition}}はQR分解を半単純リー群に一般化している。

== 脚注 ==
{{脚注ヘルプ}}
{{reflist}}

== 参考文献 ==
===和文===
{{Refbegin}}
* {{Cite book|和書|editor1-first=真|editor1-last=長尾|editor1-link=長尾真|editor2-first=晴久|editor2-last=石田|editor2-link=石田晴久|editor3-first=康善他|editor3-last=稲垣|editor3-link=稲垣康善|title=岩波情報科学辞典|edition=初版|publisher=[[岩波書店]]|year=1990|page=163|isbn=9784000800747|ref={{SfnRef|長尾|石田|他編|1990}}}}
* {{Cite book|和書|author=森正武|authorlink=森正武|year=2002|title=数値解析|edition=第2版|publisher=[[共立出版]]|series=共立数学講座, 12|isbn=4320017013|ref={{SfnRef|森|2002}}}}
* {{Cite book|和書|author=山本哲朗|title=数値解析入門|publisher=[[サイエンス社]]|series=サイエンスライブラリ 現代数学への入門 14|date=2003-06|edition=増訂版|isbn=4-7819-1038-6|ref={{SfnRef|山本}}}}
{{Refend}}
===英文===
{{Refbegin}}
* {{Cite book
|last1      = Golub
|first1     = Gene H. |authorlink1=ジーン・ゴラブ
|last2      = Van Loan
|first2     = Charles F. |authorlink2=:en:Charles F. Van Loan
|year       = 2013
|title      = Matrix computations
|edition    = Fourth
|url        = {{google books|X5YfsuCWpxMC|plainurl=yes}}
|publisher  = Johns Hopkins University Press
|isbn       =978-1421407944
|mr         = 3024913
|ref        = harv
|language=en}}
* {{Cite book|first1=Lloyd N.|last1=Trefethen|authorlink1=ニック・トレフェセン|first2=David |last2=Bau III |title=Numerical Linear Algebra|isbn=9780898713619|publisher=Society for Industrial and Applied Mathematics|year=1997|ref= harv|language=en}}
* {{Cite book|last1=Horn|first1=Roger A.|authorlink1=:en:Roger Horn|last2=Johnson|first2=Charles R.|authorlink2=:en:Johnson Charles|year=1985|title=Matrix Analysis|publisher=Cambridge University Press|isbn=0-521-38632-2|chapter=Section 2.8.|ref= harv|language=en}}
* {{Cite book|last1=Press|first1=William H.|authorlink1=:en:William H. Press|last2=Teukolsky|first2=Saul A.|authorlink2=:en:Saul Teukolsky
|last3=Vetterling|first3=William T.|authorlink3=:en:William T. Vetterling|coauthor=Flannery, Brian P.|year=2007|chapter=Section 2.10. QR Decomposition|title=[[:en:Numerical Recipes|Numerical Recipes]]: The Art of Scientific Computing|edition=3rd|location=New York|publisher=[[:en:Cambridge University Press|Cambridge University Press]]|isbn=978-0-521-88068-8|ref= harv|language=en}}
* {{Cite book|last1=Stoer|first1=Josef|authorlink1=:en:Josef Stoer|last2=Bulirsch|first2=Roland |authorlink2=:en:Roland Bulirsch|year=2002|title=Introduction to Numerical Analysis|edition=3rd|publisher=Springer|isbn=0-387-95452-X|ref= harv|language=en|series=Texts in applied mathematics, 12}}
* {{Citation | last1=Golub | first1=Gene H. | author1-link=ジーン・ゴラブ | last2=Van Loan | first2=Charles F. | author2-link=:en:Charles F. Van Loan | title=Matrix Computations | publisher=Johns Hopkins | edition=3rd | isbn=978-0-8018-5414-9 | year=1996}}.
{{Refend}}

== 関連項目 ==
* [[QR法]]
* {{仮リンク|極分解|en|Polar decomposition}}
* [[固有値分解]]
* [[LU分解]]
* [[特異値分解]]

==外部リンク==
*[https://web.archive.org/web/20081212221215/http://www.bluebit.gr/matrix-calculator/ Online Matrix Calculator] 行列のQR分解の実行
*[http://netlib.org/lapack/lug/node39.html LAPACK users manual] QR分解の計算のサブルーチンの詳細
*[https://web.archive.org/web/20061122183956/http://documents.wolfram.com/mathematica/functions/QRDecomposition Mathematica users manual] QR分解の計算のルーチンの詳細と例
*[http://www.alglib.net/ ALGLIB] LAPACKのC++、C#、Delphiなどへの移植
*[http://eigen.tuxfamily.org/dox-devel/group__QR__Module.html Eigen::QR] QR分解のC++での実装
{{linear algebra}}
{{DEFAULTSORT:QRきゆうああるふんかい}}
[[Category:数値線形代数]]
[[Category:行列]]
[[Category:行列の分解]]
[[Category:数学に関する記事]]