QR分解

Matrix decomposition

線形代数において、QR 分解(QR 分解またはQU 分解とも呼ばれる) は、行列Aを直交行列Qと上三角行列Rの積A  =  QRに分解することです。QR 分解は、線形最小二乗(LLS) 問題を解くためによく使用され、特定の固有値アルゴリズムである QRアルゴリズムの基礎となります。

事例と定義

正方行列

任意の実正方行列 Aは次のように分解できる。

${\displaystyle A=QR,}$

ここで、Qは直交行列（列は直交 単位ベクトル、つまり）であり、Rは上三角行列（直角三角行列とも呼ばれる）である。Aが逆行列 である場合、 Rの対角要素が正であることを条件に、因数分解は一意となる。 ${\displaystyle Q^{\textsf {T}}=Q^{-1}}$

代わりにAが複素正方行列である場合、分解A = QRが存在します。ここで、Qはユニタリ行列です(つまり共役転置です )。 ${\displaystyle Q^{\dagger }=Q^{-1}}$

A がn 個の線形独立な列を持つ場合、 Qの最初のn列はAの列空間の直交基底を形成する。より一般的には、 Qの最初のk列は、任意の1 ≤ k ≤ nに対して、 Aの最初のk列のスパンの直交基底を形成する。^[1] Aの任意のk列がQの最初のk列のみに依存する という事実は、Rの三角形形式に対応する 。^[1]

長方形行列

より一般的には、 m ≥ nの複素m × n行列Aを、m × mユニタリ行列Qとm × n上三角行列Rの積として因数分解することができます。m × n上三角行列の一番下の行（m − n）はすべてゼロで構成されるため、 R、またはRとQの両方を分割することが有用な場合が多くあります。

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

ここで、R ₁はn × n の上三角行列、0 は( m − n )× n の 零行列、Q ₁はm × n、Q ₂はm ×( m − n )であり、Q ₁とQ ₂はどちらも直交列を持ちます。

Golub & Van Loan (1996, §5.2) はQ ₁ R _1をAの薄いQR 分解と呼び、Trefethen と Bau はこれを簡約 QR 分解と呼んでいます。^[1] Aがフルランクnで、 R ₁の対角要素が正であることを要求すると、 R ₁とQ _{1 は}一意ですが、一般にQ _{2 は}一意ではありません。R _1は、 A * A (  Aが実数の場合はA ^T A )のコレスキー分解の上三角因子に等しくなります。

QL、RQ、LQ分解

同様に、 Lを下三角行列として、QL、RQ、LQ 分解を定義することもできます。

QR分解の計算

QR分解を実際に計算する方法はいくつかあります。例えば、グラム・シュミット過程、ハウスホルダー変換、ギブンズ回転などです。それぞれに長所と短所があります。

グラム・シュミット法の使用

内積を持つ（複素数の場合は または ）完全な列ランク行列 の列にグラム・シュミット過程を適用することを考えます。 ${\displaystyle A={\begin{bmatrix}\mathbf {a} _{1}&\cdots &\mathbf {a} _{n}\end{bmatrix}}}$ ${\displaystyle \langle \mathbf {v} ,\mathbf {w} \rangle =\mathbf {v} ^{\textsf {T}}\mathbf {w} }$ ${\displaystyle \langle \mathbf {v} ,\mathbf {w} \rangle =\mathbf {v} ^{\dagger }\mathbf {w} }$

投影を定義します:

${\displaystyle \operatorname {proj} _{\mathbf {u} }\mathbf {a} ={\frac {\left\langle \mathbf {u} ,\mathbf {a} \right\rangle }{\left\langle \mathbf {u} ,\mathbf {u} \right\rangle }}{\mathbf {u} }}$

それから：

${\displaystyle {\begin{aligned}\mathbf {u} _{1}&=\mathbf {a} _{1},&\mathbf {e} _{1}&={\frac {\mathbf {u} _{1}}{\|\mathbf {u} _{1}\|}}\\\mathbf {u} _{2}&=\mathbf {a} _{2}-\operatorname {proj} _{\mathbf {u} _{1}}\mathbf {a} _{2},&\mathbf {e} _{2}&={\frac {\mathbf {u} _{2}}{\|\mathbf {u} _{2}\|}}\\\mathbf {u} _{3}&=\mathbf {a} _{3}-\operatorname {proj} _{\mathbf {u} _{1}}\mathbf {a} _{3}-\operatorname {proj} _{\mathbf {u} _{2}}\mathbf {a} _{3},&\mathbf {e} _{3}&={\frac {\mathbf {u} _{3}}{\|\mathbf {u} _{3}\|}}\\&\;\;\vdots &&\;\;\vdots \\\mathbf {u} _{k}&=\mathbf {a} _{k}-\sum _{j=1}^{k-1}\operatorname {proj} _{\mathbf {u} _{j}}\mathbf {a} _{k},&\mathbf {e} _{k}&={\frac {\mathbf {u} _{k}}{\|\mathbf {u} _{k}\|}}\end{aligned}}}$

新しく計算された直交基底上の s を次のように表すことができます。 ${\displaystyle \mathbf {a} _{i}}$

${\displaystyle {\begin{aligned}\mathbf {a} _{1}&=\left\langle \mathbf {e} _{1},\mathbf {a} _{1}\right\rangle \mathbf {e} _{1}\\\mathbf {a} _{2}&=\left\langle \mathbf {e} _{1},\mathbf {a} _{2}\right\rangle \mathbf {e} _{1}+\left\langle \mathbf {e} _{2},\mathbf {a} _{2}\right\rangle \mathbf {e} _{2}\\\mathbf {a} _{3}&=\left\langle \mathbf {e} _{1},\mathbf {a} _{3}\right\rangle \mathbf {e} _{1}+\left\langle \mathbf {e} _{2},\mathbf {a} _{3}\right\rangle \mathbf {e} _{2}+\left\langle \mathbf {e} _{3},\mathbf {a} _{3}\right\rangle \mathbf {e} _{3}\\&\;\;\vdots \\\mathbf {a} _{k}&=\sum _{j=1}^{k}\left\langle \mathbf {e} _{j},\mathbf {a} _{k}\right\rangle \mathbf {e} _{j}\end{aligned}}}$

ここで、これは行列形式で書くことができます。 ${\displaystyle \left\langle \mathbf {e} _{i},\mathbf {a} _{i}\right\rangle =\left\|\mathbf {u} _{i}\right\|}$

${\displaystyle A=QR}$

どこ：

${\displaystyle Q={\begin{bmatrix}\mathbf {e} _{1}&\cdots &\mathbf {e} _{n}\end{bmatrix}}}$

そして

${\displaystyle R={\begin{bmatrix}\langle \mathbf {e} _{1},\mathbf {a} _{1}\rangle &\langle \mathbf {e} _{1},\mathbf {a} _{2}\rangle &\langle \mathbf {e} _{1},\mathbf {a} _{3}\rangle &\cdots &\langle \mathbf {e} _{1},\mathbf {a} _{n}\rangle \\0&\langle \mathbf {e} _{2},\mathbf {a} _{2}\rangle &\langle \mathbf {e} _{2},\mathbf {a} _{3}\rangle &\cdots &\langle \mathbf {e} _{2},\mathbf {a} _{n}\rangle \\0&0&\langle \mathbf {e} _{3},\mathbf {a} _{3}\rangle &\cdots &\langle \mathbf {e} _{3},\mathbf {a} _{n}\rangle \\\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&0&\cdots &\langle \mathbf {e} _{n},\mathbf {a} _{n}\rangle \\\end{bmatrix}}.}$

例

次の分解を考えてみましょう

${\displaystyle A={\begin{bmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{bmatrix}}.}$

直交行列には という性質があることを思い出してください。 ${\displaystyle Q}$ ${\displaystyle Q^{\textsf {T}}Q=I}$

次に、グラム・シュミットの法則を使って次のように計算します。 ${\displaystyle Q}$

${\displaystyle {\begin{aligned}U={\begin{bmatrix}\mathbf {u} _{1}&\mathbf {u} _{2}&\mathbf {u} _{3}\end{bmatrix}}&={\begin{bmatrix}12&-69&-58/5\\6&158&6/5\\-4&30&-33\end{bmatrix}};\\Q={\begin{bmatrix}{\frac {\mathbf {u} _{1}}{\|\mathbf {u} _{1}\|}}&{\frac {\mathbf {u} _{2}}{\|\mathbf {u} _{2}\|}}&{\frac {\mathbf {u} _{3}}{\|\mathbf {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{aligned}}}$

したがって、

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

RQ分解との関係

RQ分解は、行列Aを上三角行列R（直角三角行列とも呼ばれる）と直交行列Qの積に変換します。QR分解との唯一の違いは、これらの行列の順序です。

QR 分解は、 Aの最初の列から始まる列のグラム・シュミット直交化です。

RQ分解は、 Aの最後の行から始まる行のグラム・シュミット直交化です。

メリットとデメリット

グラム・シュミット過程は本質的に数値的に不安定です。投影法の適用は直交化と幾何学的に類似しているように見えますが、直交化自体は数値誤差が生じやすい傾向があります。大きな利点は実装の容易さです。

世帯主の反射を利用する

QR分解におけるハウスホルダー反射：目標は、ベクトル を と同じ長さで と共線的なベクトルに変換する線形変換を見つけることです。直交射影（グラム・シュミット射影）を使用することもできますが、ベクトルと が直交に近い場合、数値的に不安定になります。代わりに、ハウスホルダー反射は点線（との間の角度を二等分するように選択）を通ります。この変換の最大角度は45度です。 ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {e} _{1}}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {e} _{1}}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {e} _{1}}$

ハウスホルダー反射（またはハウスホルダー変換）は、ベクトルを平面または超平面に反射させる変換です。この演算を用いて、 m ≥ nのm行n列行列のQR分解を計算できます。 ${\displaystyle A}$

Q は、1 つの座標以外のすべての座標が消えるようにベクトルを反射するために使用できます。

を任意の実数m次元列ベクトルとし、スカラーαに対してとなるものとする。アルゴリズムが浮動小数点演算を用いて実装される場合、αはのk番目の座標と逆の符号を取るべきである。ここで、 αは行列Aの最終的な上三角形式において、それより後のすべての要素が0となるピボット座標となるべきであり、これにより有意性の低下が避けられる。複素数の場合、^{[2]と設定する。} ${\displaystyle \mathbf {x} }$ ${\displaystyle A}$ ${\displaystyle \|\mathbf {x} \|=|\alpha |}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle x_{k}}$

${\displaystyle \alpha =-e^{i\arg x_{k}}\|\mathbf {x} \|}$

そして、以下のQの構築では、転置を共役転置に置き換えます。

そして、ベクトル[1 0 ⋯ 0] ^T、|| · ||はユークリッドノルム、m × mの単位行列であり、 ${\displaystyle \mathbf {e} _{1}}$ ${\displaystyle I}$

${\displaystyle {\begin{aligned}\mathbf {u} &=\mathbf {x} -\alpha \mathbf {e} _{1},\\\mathbf {v} &={\frac {\mathbf {u} }{\|\mathbf {u} \|}},\\Q&=I-2\mathbf {v} \mathbf {v} ^{\textsf {T}}.\end{aligned}}}$

または、複雑な 場合 ${\displaystyle A}$

${\displaystyle Q=I-2\mathbf {v} \mathbf {v} ^{\dagger }.}$

${\displaystyle Q}$はm行m列のハウスホルダー行列であり、対称かつ直交行列（複素数の場合はエルミートかつユニタリ行列）である。

${\displaystyle Q\mathbf {x} ={\begin{bmatrix}\alpha \\0\\\vdots \\0\end{bmatrix}}.}$

これは、 m行n列の行列Aを上三角形式に段階的に変換するのに使用できます。まず、行列Aに、行列の最初の列xを選択した際に得られるハウスホルダー行列Q ₁を乗じます。これにより、左列（最初の行を除く）がゼロとなる行列Q ₁ Aが得られます。

${\displaystyle Q_{1}A={\begin{bmatrix}\alpha _{1}&\star &\cdots &\star \\0&&&\\\vdots &&A'&\\0&&&\end{bmatrix}}}$

これをA ′ （Q ₁ Aから最初の行と最初の列を削除したもの）に対して繰り返すと、ハウスホルダー行列Q ′ ₂が得られます。Q ′ 2 は Q 1 よりも小さいことに注意してください。_実際には_A ′ではなくQ ₁ Aに作用させたいので、左上に拡張して 1 を埋める必要があります。つまり、一般的には次のように表すことができます。

${\displaystyle Q_{k}={\begin{bmatrix}I_{k-1}&0\\0&Q_{k}'\end{bmatrix}}.}$

このプロセスを繰り返すと、 ${\displaystyle t}$ ${\displaystyle t=\min(m-1,n)}$

${\displaystyle R=Q_{t}\cdots Q_{2}Q_{1}A}$

は上三角行列である。したがって、

${\displaystyle {\begin{aligned}Q^{\textsf {T}}&=Q_{t}\cdots Q_{2}Q_{1},\\Q&=Q_{1}^{\textsf {T}}Q_{2}^{\textsf {T}}\cdots Q_{t}^{\textsf {T}}\end{aligned}}}$

${\displaystyle A=QR}$は の QR 分解です。 ${\displaystyle A}$

この方法は、上記のグラム・シュミット法よりも数値的に安定しています。

数値テストでは、計算された因子とが機械精度でを満たす 。また、直交性は維持される： 。しかし、 と の精度は条件数とともに低下する： ${\displaystyle Q_{c}}$ ${\displaystyle R_{c}}$ ${\displaystyle {\frac {\|QR-Q_{c}R_{c}\|_{\infty }}{\|A\|_{\infty }}}=O(\varepsilon )}$ ${\displaystyle \|Q_{c}^{\mathsf {T}}Q_{c}-I\|_{\infty }=O(\varepsilon )}$ ${\displaystyle Q_{c}}$ ${\displaystyle R_{c}}$ ${\displaystyle \|Q-Q_{c}\|_{\infty }=O(\varepsilon \,\kappa _{\infty }(A)),\quad {\frac {\|R-R_{c}\|_{\infty }}{\|R\|_{\infty }}}=O(\varepsilon \,\kappa _{\infty }(A)).}$

条件付きの例（、）の場合： ${\displaystyle n=4000}$ ${\displaystyle \kappa _{\infty }(A)\approx 3\times 10^{3}}$ ${\displaystyle {\frac {\|QR-Q_{c}R_{c}\|_{\infty }}{\|A\|_{\infty }}}\approx 1.6\times 10^{-15},}$ ${\displaystyle \|Q-Q_{c}\|_{\infty }\approx 1.6\times 10^{-15},}$ ${\displaystyle {\frac {\|R-R_{c}\|_{\infty }}{\|R\|_{\infty }}}\approx 4.3\times 10^{-14},}$ ${\displaystyle \|Q_{c}^{\mathsf {T}}Q_{c}-I\|_{\infty }\approx 1.1\times 10^{-13}.}$

悪条件テスト（、）では： ^[3] ${\displaystyle n=4000}$ ${\displaystyle \kappa _{\infty }(A)\approx 4\times 10^{18}}$ ${\displaystyle {\frac {\|QR-Q_{c}R_{c}\|_{\infty }}{\|A\|_{\infty }}}\approx 1.3\times 10^{-15},}$ ${\displaystyle \|Q-Q_{c}\|_{\infty }\approx 5.2\times 10^{-4},}$ ${\displaystyle {\frac {\|R-R_{c}\|_{\infty }}{\|R\|_{\infty }}}\approx 1.2\times 10^{-4},}$ ${\displaystyle \|Q_{c}^{\mathsf {T}}Q_{c}-I\|_{\infty }\approx 1.1\times 10^{-13}.}$

次の表は、サイズがnの正方行列であると仮定して、ハウスホルダー変換による QR 分解のk番目のステップでの演算数を示しています。

手術	k番目のステップにおける操作の数
掛け算	${\displaystyle 2(n-k+1)^{2}}$
追加事項	${\displaystyle (n-k+1)^{2}+(n-k+1)(n-k)+2}$
分割	${\displaystyle 1}$
平方根	${\displaystyle 1}$

これらの数値をn − 1ステップ（サイズnの正方行列の場合）にわたって合計すると、アルゴリズムの複雑さ（浮動小数点乗算の観点から）は次のように表される。

${\displaystyle {\frac {2}{3}}n^{3}+n^{2}+{\frac {1}{3}}n-2=O\left(n^{3}\right).}$

例

分解を計算してみましょう

${\displaystyle A={\begin{bmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{bmatrix}}.}$

まず、行列Aの最初の列であるベクトルをに変換する反射を見つける必要があります。 ${\displaystyle \mathbf {a} _{1}={\begin{bmatrix}12&6&-4\end{bmatrix}}^{\textsf {T}}}$ ${\displaystyle \left\|\mathbf {a} _{1}\right\|\mathbf {e} _{1}={\begin{bmatrix}\alpha &0&0\end{bmatrix}}^{\textsf {T}}}$

今、

${\displaystyle \mathbf {u} =\mathbf {x} -\alpha \mathbf {e} _{1},}$

そして

${\displaystyle \mathbf {v} ={\frac {\mathbf {u} }{\|\mathbf {u} \|}}.}$

ここ、

${\displaystyle \alpha =14}$そして ${\displaystyle \mathbf {x} =\mathbf {a} _{1}={\begin{bmatrix}12&6&-4\end{bmatrix}}^{\textsf {T}}}$

したがって

${\displaystyle \mathbf {u} ={\begin{bmatrix}-2&6&-4\end{bmatrix}}^{\textsf {T}}=2{\begin{bmatrix}-1&3&-2\end{bmatrix}}^{\textsf {T}}}$そして、そして ${\displaystyle \mathbf {v} ={\frac {1}{\sqrt {14}}}{\begin{bmatrix}-1&3&-2\end{bmatrix}}^{\textsf {T}}}$

${\displaystyle {\begin{aligned}Q_{1}={}&I-{\frac {2}{{\sqrt {14}}{\sqrt {14}}}}{\begin{bmatrix}-1\\3\\-2\end{bmatrix}}{\begin{bmatrix}-1&3&-2\end{bmatrix}}\\={}&I-{\frac {1}{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{aligned}}}$

次に観察します:

${\displaystyle Q_{1}A={\begin{bmatrix}14&21&-14\\0&-49&-14\\0&168&-77\end{bmatrix}},}$

つまり、ほぼ三角行列が出来上がっていることになります。(3, 2)の要素をゼロにするだけで済みます。

(1, 1)マイナーを取り、このプロセスを再度適用して

${\displaystyle A'=M_{11}={\begin{bmatrix}-49&-14\\168&-77\end{bmatrix}}.}$

上記と同じ方法で、ハウスホルダー変換の行列を得る。

${\displaystyle Q_{2}={\begin{bmatrix}1&0&0\\0&-7/25&24/25\\0&24/25&7/25\end{bmatrix}}}$

1 との直和を実行して、プロセスの次のステップが適切に機能することを確認します。

さて、私たちは

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

あるいは、小数点4桁で、

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

行列Qは直交行列であり、Rは上三角行列であるため、必要な QR 分解はA = QRです。

メリットとデメリット

ハウスホルダー変換は、R行列に零点を生成するメカニズムとして反射を利用するため、数値的に安定したQR分解アルゴリズムの中で本質的に最も単純なものです。しかし、ハウスホルダー反射アルゴリズムは帯域幅を大量に消費し、並列化が困難です。これは、新しい零点を生成する反射ごとに、 Q行列とR行列の両方の行列全体が変化するためです。

世帯主QRの並列実装

ハウスホルダーQR法は、TSQRアルゴリズム（ Tall Skinny QRの略）などのアルゴリズムと並列に実装できます。このアルゴリズムは、行列Aがm >> nの場合に適用できます。^[4]このアルゴリズムは、バイナリ縮小木を用いて、フォワードパスの各ノードにおけるローカルハウスホルダーQR分解を計算し、バックワードパスでQ行列を再構成します。バイナリ木構造は、プロセッサ間の通信量を削減することで性能を向上させることを目的としています。

ギブンズ回転の使用

QR分解は、一連のギブンズ回転によっても計算できます。各回転は行列の下対角成分をゼロにし、R行列を形成します。すべてのギブンズ回転を連結すると、直交Q行列が形成されます。

実際には、ギブンズ回転は、行列全体を構築して行列乗算を行うことによって実行されるわけではありません。代わりに、スパース要素の処理という余分な作業なしに、スパースギブンズ行列乗算と同等の処理を実行するギブンズ回転手順が使用されます。ギブンズ回転手順は、比較的少数の非対角要素をゼロにする必要がある状況で有用であり、ハウスホルダー変換よりも簡単に並列化できます。

例

分解を計算してみましょう

${\displaystyle A={\begin{bmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{bmatrix}}.}$

まず、左下要素 をゼロにする回転行列を作成する必要があります。 この行列はギブンズ回転法を用いて作成し、行列 と呼びます。まず、ベクトル を回転させてX軸に沿うようにします。このベクトルの角度は です。 直交ギブンズ回転行列 を作成します。 ${\displaystyle a_{31}=-4}$ ${\displaystyle G_{1}}$ ${\displaystyle {\begin{bmatrix}12&-4\end{bmatrix}}}$ ${\textstyle \theta =\arctan \left({\frac {-(-4)}{12}}\right)}$ ${\displaystyle G_{1}}$

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

そして、今の結果では、要素にゼロが存在します。 ${\displaystyle G_{1}A}$ ${\displaystyle a_{31}}$

${\displaystyle G_{1}A\approx {\begin{bmatrix}12.64911&-55.97231&16.76007\\6&167&-68\\0&6.64078&-37.6311\end{bmatrix}}}$

同様にギブンズ行列とを形成することができ、これらの行列は下対角要素と をゼロにして三角行列 を形成します。 直交行列 は、すべてのギブンズ行列 の積から形成されます。 したがって となり、 QR分解は となります。 ${\displaystyle G_{2}}$ ${\displaystyle G_{3}}$ ${\displaystyle a_{21}}$ ${\displaystyle a_{32}}$ ${\displaystyle R}$ ${\displaystyle Q^{\textsf {T}}}$ ${\displaystyle Q^{\textsf {T}}=G_{3}G_{2}G_{1}}$ ${\displaystyle G_{3}G_{2}G_{1}A=Q^{\textsf {T}}A=R}$ ${\displaystyle A=QR}$

メリットとデメリット

ギブンズ回転によるQR分解は、実装が最も複雑です。アルゴリズムを最大限に活用するために必要な行の順序を決定するのは容易ではないためです。しかし、この方法には大きな利点があります。新しいゼロ要素は、ゼロにする要素がある行 ( i ) とその上の行 ( j ) にのみ影響します。これにより、ギブンズ回転アルゴリズムは、ハウスホルダー反射法よりも帯域幅効率が高く、並列化が容易です。 ${\displaystyle a_{ij}}$

行列式または固有値の積との関連

QR分解を用いて正方行列の行列式を求めることができます。行列を次のように分解するとします。 ${\displaystyle A=QR}$ $${\displaystyle \det A=\det Q\det R.}$$

${\displaystyle Q}$となるように選ぶことができる。したがって、 ${\displaystyle \det Q=1}$ $${\displaystyle \det A=\det R=\prod _{i}r_{ii}}$$

ここで、は の対角要素である。さらに、行列式は固有値の積に等しいので、 ${\displaystyle r_{ii}}$ ${\displaystyle R}$ $${\displaystyle \prod _{i}r_{ii}=\prod _{i}\lambda _{i}}$$

ここでは の固有値です。 ${\displaystyle \lambda _{i}}$ ${\displaystyle A}$

非正方複素行列の QR 分解の定義を導入し、固有値を特異値に置き換えることで、上記の性質を非正方複素行列に拡張できます。 ${\displaystyle A}$

非正方行列Aの QR 分解から始めます。

${\displaystyle A=Q{\begin{bmatrix}R\\0\end{bmatrix}},\qquad Q^{\dagger }Q=I}$

ここで、 は零行列、はユニタリ行列です。 ${\displaystyle 0}$ ${\displaystyle Q}$

特異値分解（SVD）と行列の行列式の性質から、

${\displaystyle {\Big |}\prod _{i}r_{ii}{\Big |}=\prod _{i}\sigma _{i},}$

ここで、は の特異値です。 ${\displaystyle \sigma _{i}}$ ${\displaystyle A}$

との特異値は同じであるが、複素固有値は異なる場合があることに注意する。しかし、Aが正方行列の場合、 ${\displaystyle A}$ ${\displaystyle R}$

${\displaystyle {\prod _{i}\sigma _{i}}={\Big |}\prod _{i}\lambda _{i}{\Big |}.}$

したがって、QR 分解は、行列の固有値または特異値の積を効率的に計算するために使用できます。

列ピボット

ピボットQR法は、通常のグラム・シュミット法とは異なり、各ステップの開始時に残っている最大の列（列ピボット）を取り、それによって置換行列Pを導入する。 ^[5]

${\displaystyle AP=QR\quad \iff \quad A=QRP^{\textsf {T}}}$

列ピボットは、 Aが（ほぼ）ランク落ちである、またはランク落ちの疑いがある場合に有用です。また、数値精度を向上させることもできます。Pは通常、 Rの対角要素が非増加となるように選択されます： 。これは、特異値分解よりも低い計算コストでAの（数値的）ランクを求めるために使用でき、いわゆるランク開示QRアルゴリズムの基礎となります。 ${\displaystyle \left|r_{11}\right|\geq \left|r_{22}\right|\geq \cdots \geq \left|r_{nn}\right|}$

線形逆問題の解法に用いる

直接行列逆行列解と比較すると、QR分解を用いた逆行列解は条件数が減少することからもわかるように数値的に安定している。^[6]

行列が次元、階数である劣決定( ) ${\displaystyle m<n}$線型問題を解くには、まず の転置行列 の QR 分解を求めます。ここでQは直交行列 (つまり) であり、 Rは特殊な形式 です。ここではは正方三角行列で、零行列の次元は です。代数計算を行うと、逆問題の解は次のように表せることが示されます。ここで、 はガウスの消去法で求めるか、前方代入によって直接計算することができます。後者の手法の方が数値精度が高く、計算量が少なくて済みます。 ${\displaystyle A\mathbf {x} =\mathbf {b} }$ ${\displaystyle A}$ ${\displaystyle m\times n}$ ${\displaystyle m}$ ${\displaystyle A}$ ${\displaystyle A^{\textsf {T}}=QR}$ ${\displaystyle Q^{\textsf {T}}=Q^{-1}}$ ${\displaystyle R=\left[{\begin{smallmatrix}R_{1}\\0\end{smallmatrix}}\right]}$ ${\displaystyle R_{1}}$ ${\displaystyle m\times m}$ ${\displaystyle (n-m)\times m}$ ${\displaystyle \mathbf {x} =Q\left[{\begin{smallmatrix}\left(R_{1}^{\textsf {T}}\right)^{-1}\mathbf {b} \\0\end{smallmatrix}}\right]}$ ${\displaystyle R_{1}^{-1}}$ ${\displaystyle \left(R_{1}^{\textsf {T}}\right)^{-1}\mathbf {b} }$

ノルム を最小化する過剰決定問題( )の解を求めるには、まず のQR分解を求めます。この解はと表すことができます。ここでは完全な直交基底の最初の列を含む行列であり、は前述と同じです。劣決定問題と同様に、を明示的に逆行列化することなく、後退代入法を使用してこれを迅速かつ正確に求めることができます。 (は数値計算ライブラリによって「経済的な」QR分解として提供されることがよくあります。) ${\displaystyle {\hat {\mathbf {x} }}}$ ${\displaystyle m\geq n}$ ${\displaystyle A\mathbf {x} =\mathbf {b} }$ ${\displaystyle \left\|A{\hat {\mathbf {x} }}-\mathbf {b} \right\|}$ ${\displaystyle A}$ ${\displaystyle A=QR}$ ${\displaystyle {\hat {\mathbf {x} }}=R_{1}^{-1}\left(Q_{1}^{\textsf {T}}\mathbf {b} \right)}$ ${\displaystyle Q_{1}}$ ${\displaystyle m\times n}$ ${\displaystyle n}$ ${\displaystyle Q}$ ${\displaystyle R_{1}}$ ${\displaystyle {\hat {\mathbf {x} }}}$ ${\displaystyle R_{1}}$ ${\displaystyle Q_{1}}$ ${\displaystyle R_{1}}$

一般化

岩澤分解は、 QR 分解を半単純リー群に一般化します。

参照

• 極性分解
• 固有分解（スペクトル分解）
• LU分解
• 特異値分解

参考文献

1. Trefethen, Lloyd N. ; Bau, David III (1997).数値線形代数. フィラデルフィア, PA: Society for Industrial and Applied Mathematics . ISBN 978-0-898713-61-9。
2. Stoer, Josef ; Bulirsch, Roland (2002) 『数値解析入門』（第3版）、Springer、p. 225、ISBN 0-387-95452-X
3. Holmes, Mark H. (2023). 『科学計算とデータ分析入門』第2版. Springer. ISBN 978-3-031-22429-4。
4. デメル、ジェームズ；グリゴリ、ローラ（2008年6月12日）「通信最適化並列および逐次QRおよびLU因数分解：理論と実践」arXiv：0806.2159 [cs.NA]。
5. ストラング、ギルバート(2019). 『線形代数とデータからの学習』（第1版）. ウェルズリー: ウェルズリー・ケンブリッジ・プレス. p. 143. ISBN 978-0-692-19638-0。
6. パーカー、ロバート・L. (1994).地球物理学的逆理論. プリンストン、ニュージャージー州: プリンストン大学出版局. セクション1.13. ISBN 978-0-691-20683-7. OCLC  1134769155.

さらに読む

• ゴルブ、ジーン・H. ;ヴァン・ローン、チャールズ・F. (1996) 『行列計算』（第3版）、ジョンズ・ホプキンス、ISBN 978-0-8018-5414-9。
• ホーン、ロジャー A. ; ジョンソン、チャールズ R. (1985)、『マトリックス分析』、ケンブリッジ大学出版局、第2.8節、ISBN 0-521-38632-2
• Press, William H. ; Teukolsky, Saul A. ; Vetterling, William T. ; Flannery, Brian P. (2007)「Section 2.10. QR Decomposition」、Numerical Recipes : The Art of Scientific Computing (第3版)、ニューヨーク: Cambridge University Press、ISBN 978-0-521-88068-8

外部リンク

• オンライン行列計算機は行列の QR 分解を実行します。
• LAPACKユーザーマニュアルには、QR分解を計算するためのサブルーチンの詳細が記載されています。
• Mathematicaのユーザーマニュアルには、QR分解を計算するルーチンの詳細と例が記載されています。
• ALGLIB には、LAPACK の C++、C#、Delphi などへの部分的な移植が含まれています。
• Eigen::QR には、QR 分解の C++ 実装が含まれています。

Retrieved from "https://en.wikipedia.org/w/index.php?title=QR_decomposition&oldid=1319759113"