行列の分解（Matrix Decomposition） - 大人になってからの再学習

いろいろな場面で、ある行列を複数の行列の積の形に置き換えることが行われる。

これを行列の分解（Matrix Decomposition）と言って、これまでに様々な分解方法が考案されている。

なんのために行列を分解するのか？

行列を分解することで、計算を速く行えるようになる、という実際的なメリットがあったり、その行列の性質がわかったりするから。

では、どのような分解方法があるのかを以下に紹介。

■ LU分解

行列Aを行列Lと行列Uの積の形に分解する。

つまり、

$A=LU$

のかたちにする。
Lは下三角行列 (lower triangularmatrix)で、Uは上三角行列 (upper triangular matrix) で、次のような感じになる。

このような形に分解できれば、

$Ax=b$

の形で表現される連立一次方程式を簡単に（高速に）解くことができる。
$A=LU$ なので、上式は

$LUx=b$

となって、とりあえず

$y = Ux$

と置くと、

$Ly=b$

となるので、「前進代入」という単純な方法で、あっという間に答え（ベクトルyの値）が求まる。

そしたら、 $y=Ux$ と置いたのだから、今度は

$Ux=y$

としてxを求める。これも、「後退代入」という方法で、あっという間に最終的な答え（ベクトルxの値）が求まってしまう。
LU分解するのに、ひと手間かかるけど、一度分解してLとUを記憶しておけば、
$Ax=b$
で、行列Aが同じである方程式を簡単に解くことができる。

■ コレスキー分解（Cholesky Decomposition）

LU分解の発展版。
元となる行列が正定値対称行列のみに有効で、次のように分解する。LU分解よりも高速に分解できる。

$A=LL^T$

Lは下三角行列 (lower triangularmatrix)。
対角行列Dを挟んで、次のように分解することもある（LDL分解）
$A=LDL^T$

LU分解と同様に、解を高速に求める目的で使用される。

■ QR分解（QR Decomposition）

行列を直交行列Qと上三角形行列Rの積に分割する。

$A=QR$

線形最小二乗問題を解く際に多く用いられる。
参考：
数理ファイナンス：QR分解

■ 特異値分解、SVD分解（Singular value decomposition）

直交行列U、対角行列Σ、直交行列Vの積に分割する。

$A=U \Sigma V^T$

対角行列には、元の行列の固有値が並ぶ。
偽逆行列の算出に用いられる。
関連：一般逆行列・ムーア・ペンローズ逆行列 - 大人になってからの再学習
主成分分析（PCA）と関連がある。

参考文献：
・情報数値解析第5回行列の分解と連立1次方程式
http://yebisu.cc.kyushu-u.ac.jp/~watanabe/LECTURE/INA/05.pdf

・第7章連立一次方程式の解法1 ― 直接法
http://na-inet.jp/nasoft/chap07.pdf

・LU分解法（１）：東京大学情報基盤センター特任准教授片桐孝洋
http://www.kata-lab.itc.u-tokyo.ac.jp/OpenLecture/SP20110118.pdf