行列の分解

線型代数学という数学の分野において、行列の分解とは、行列の行列の積への因数分解である．多くの異なった行列の分解があり、それぞれがある問題のために利用される。リー群の分解はこれらのより本質的な視点を与える。

1. 例
----

数値解析において、異なる分解が効率的な行列アルゴリズムを実装するために用いられる。

例えば、線型方程式系1=//Ax// = //b//}} を解くとき、行列 A}} はLU分解により分解できる。LU分解は行列を下三角行列 L}} と上三角行列 U}} の積に分解する。系 1=//L// = //b//}} と 1=//Ux// = //L//sup は、もとの系 1=//Ax// = //b//}} と比べて解くのに必要な加法や乗法が少ないが、浮動小数点のような不正確な計算ではかなりの桁数を必要とし得る。

同様に、QR分解は A}} を直交行列 Q}} と上三角行列 R}} の積 QR}} として表す。系 1=//Q// = //b//}} は 1=//Rx// = sup によって解かれ、系 1=//Rx// = //c//}} は '後退代入' によって解かれる。必要な加法と乗法の回数はLU分解のときの約2倍だが、QR分解は数値的に安定なため不正確な計算においてより多くの桁数が必要とならない。

2. 線型方程式系を解くことと関係する分解
---------------------

2.1. LU分解
---------

適用：正方行列
分解：1=//A// = //LU//}},、ただし L}} は下三角行列で U}} は上三角行列
関連：//LDU//分解は 1=//A// = //LDU//}} である、ただし L}} は下三角行列で対角線に 1 が並び、U}} は上三角行列で対角線に 1 が並び、D}} は対角行列である．
関連：LUP分解は 1=//A// = //LUP//}} である、ただし L}} は下三角行列で、U}} は上三角行列で、P}} は置換行列である．
存在： LUP 分解は任意の正方行列 A}} に対して存在する。P}} が単位行列のとき、LUP分解はLU分解となる。LU分解が存在すればLDU分解も存在するSimon。
コメント：LUP 分解と LU 分解は //n// × //n//}} の線型方程式系 1=//Ax// = //b//}} を解く際に有用である。これらの分解はガウスの消去法の過程を行列の形にまとめたものである。行列 P}} はガウスの消去法の過程で行われる任意の行の交換を表す。ガウスの消去法で行の交換なしに行階段形になれば 1=//P// = //I//}} であり、したがって LU 分解は存在する。

2.2. LUリダクション
-------------

2.3. ブロックLU分解
-------------

2.4. 階数因数分解
-----------

適用：階数 r}} の //m// × //n//}} 行列
分解：1=//A// = //CF//}}、ただし C}} は //m// × //r//}} の full column rank matrix であり、F}} は //r// × //n//}} の full row rank matrix である。
コメント：階数因数分解は A}} のムーア・ペンローズ擬逆行列を計算するのに使え、適用して線型系 1=//Ax// = //b//}} のムーア・ペンローズ擬逆行列ことができる。

2.5. コレスキー分解
------------

適用：正方，対称，正定値行列
分解：1=//A// = //sup,、ただし U}} は上三角行列で対角成分は正//
コメント：実対称正定値行列のコレスキー分解は一意にできる。
コメント：実対称と複素対称にも一応適用ができるが、行列が正則でも分解が存在しない可能性がある。
コメント：コレスキー分解は複素エルミート行列にも適用できる。必ずしも分解が存在しないが、行列が正定値なら必ず分解できる。
コメント：代替はLDL分解であり，平方根を引き出すことを避けられる．

2.6. QR分解
---------

適用：//m// × //n//}} 行列
分解：1=//A// = //QR//}},、ただし Q}} は m}} 次直交行列であり，R}} は //m// × //n//}} の上三角行列である。
コメント：QR分解は方程式系 1=//Ax// = //b//}} を A}} の逆行列を求めずに解く別の方法を提供する。Q}} が直交行列であることは 1=//sup を意味するので、1=//Ax// = //b//}} は 1=//Rx// = //sup と同値であり、後者は R}} が三角行列だから解きやすい。

2.7. RRQR分解
-----------

2.8. 補間分解
---------

3. 固有値や関連概念に基づく分解
-----------------

3.1. 固有値分解
----------

スペクトル分解 とも呼ばれる。
適用：相異なる固有ベクトルを持つ正方行列 A}}。
分解：1=//A// = //VDV//sup、 ただし D}} は A}} の固有値からなる対角行列で，V}} の行は対応する A}} の固有ベクトル。
存在：//n// × //n//}} 行列 A}} はつねに n}} 個の固有値を持ち、それらを並べて //n// × //n//}} の対角行列 D}} と対応する零でない行の行列 V}} を作ることができ、固有値方程式 1=//AV// = //VD//}} を満たす。n}} 個の固有ベクトルが相異なるとき、V}} は可逆であり、分解 1=//A// = //VDV//sup ができる。
コメント：固有ベクトルの長さが 1}} であるように正規化することがいつでもできる。A}} が実対称行列であれば、V}} はいつでも可逆であり正規化された列を持つようにできる。すると等式 1=//Vsup が成り立つ、なぜならば各固有ベクトルは互いに直交するからである。したがって、分解は 1=//A// = //VDsup となる。
コメント：n}} 個の相異なる固有値をもつという条件は十分ではあるが必要ではない。必要十分条件は各固有値の幾何学的重複度がその代数的重複度に等しいことである。
コメント：固有分解は線型常微分方程式系あるいは線型差分方程式系の解の理解に有用である。例えば，初期条件 1=//x//sub から始まる差分方程式 1=//x//sub は 1=//xsub によって解かれ、これは 1=//xsub に同値であり、ここで V}} と D}} は A}} の固有ベクトルと固有値から作られる行列である。D}} は対角行列だから、冪 Dsup は単に各対角成分を k}} 乗するだけである。A}} は普通対角でないから A}} を k}} 乗するよりもはるかに容易である。

3.2. ジョルダン分解
------------

ジョルダン標準形と

適用：正方行列
コメント：ジョルダン標準形は固有分解を固有値に重複があり対角化できない場合に一般化し、ジョルダン・シュヴァレー分解はこれを基底を選ばずに行う。

3.3. シューア分解
-----------

適用：正方行列
コメント：この分解には2つのバージョンがある．複素シューア分解と実シューア分解である．複素行列は必ず複素シューア分解を持つ．
分解：1=//A// = //UTU//sup、 ただし U}} がユニタリ行列で、//U//sup は U}} の共役転置で、T}} は A}} の固有値を対角線に持つ複素シューア標準形と呼ばれる上三角行列である。
分解：1=//A// = //VSsup、ただし A}}, V}}, S}} は実数のみからなる行列である。V}} は直交行列で，sup は V}} の転置で、S}} は実シューア標準形と呼ばれるブロック上三角行列である。S}} の対角にあるブロックのサイズは 1 × 1}}かまたは 2 × 2}}である。//

3.4. QZ分解
---------

別名：//一般シューア分解//
適用：正方行列 A}} と
コメント：この分解には2つのバージョンがある：複素と実．
分解： および , ただし Q}} と Z}} はユニタリ行列で，sup は共役転置を表し，S}} と T}} は上三角行列である．
コメント：複素QZ分解において，A}} の対角成分と対応する T}} の対角成分の比 1=//λsub は一般化固有値問題 1=//Av// = //λBv//}}を解く一般化固有値である．//
分解：1=//A// = //QSsup および 1=//B// = //QTsup, ただし A}}, B}}, Q}}, Z}}, S}}, T}} は実数のみを成分とする行列である．この場合 Q}} と Z}} は直交行列であり．sup は転置を表し，S}} と T}} はブロック上三角行列である． S}} と T}} の対角ブロックのサイズは 1 × 1}} か 2 × 2}} である．

3.5. 高木分解
---------

適用：正方，複素，対称行列 A}}.
分解：1=//A// = //VDsup, ただし D}} は実非負対角行列で，V}} はユニタリ行列である．sup は V}} の転置を表す．//
コメント：D}} の対角成分は //AA//sup の固有値の非負の平方根である．
コメント：V}} は A}} が実のときでさえ複素かもしれない．
コメント：これは固有分解の特別な場合ではない．

3.6. 特異値分解
----------

適用：//m// × //n//}} 行列 A}}.
分解：1=//A// = //UDV//sup, ただし D}} は非負対角行列で，U}} と V}} はユニタリ行列で，//V//sup は V}} の共役転置を表す．
コメント：D}} の対角成分は A}} の特異値と呼ばれる．
コメント：上の固有分解と同様，特異値分解は行列の乗法がスカラー乗法と同じになる基底の方向を見つけることと関わるが，考える行列が正方行列でなくてもよいからより広い一般性を持つ．

4. 他の分解
-------

4.1. 極分解
--------

適用：正方，複素，行列 A}}．
分解：1=//A// = //UP//}}, ただし U}} はユニタリ行列で P}} は半正定値エルミート行列である．

4.2. 代数的極分解
-----------

適用：正方，複素，非特異行列 A}}.
分解：1=//A// = //QS//}}, ただし Q}} は複素直交行列で S}} は複素対称行列．
コメント：この分解の存在は Asup が sup に相似であることと同値である．

4.3. Sinkhorn 標準形
-----------------

適用：正方実行列 A}} で真に正の成分からなるもの．
分解：1=//A// = //D//sub, ただし S}} は 二重確率行列で //D//sub と //D//sub は真に正の成分からなる実対角行列である．

4.4. 扇形分解
---------

適用：正方，複素行列 A}} で 数値域 が扇形 に含まれるもの．
分解：1=//A// = //CZC//sup, ただし C}} は可逆複素行列で，1=//Z// = diag(//e//sup ですべての ．

5. 一般化
------

quasimatrixおよび cmatrix あるいは continuous matrixに対して SVD, QR, LU, コレスキー分解の類似がある。‘quasimatrix’は，行列のように、長方形の体系で、元は添え字付けられているが、1つの離散的な添え字が連続的な添え字に置き換えられる。同様に，‘cmatrix’は両方の添え字が連続である。cmatrix の例として，積分作用素の核を考えることができる。

これらの分解は Fredholm, Hilbert, Schmidt による初期の研究に基づいている。これら独創的な論文の説明と英訳は Stewart を参照

6. 関連項目
-------

7. 脚注
-----

8. 参考文献
-------

9. 外部リンク
--------

[1]
[2]
[3]
[4] :en:GraphLab collaborative filtering library, large scale parallel implementation of matrix decomposition methods  for multicore.