LU分解

行列A,L,U

* Lは対角要素が全て1、対角要素より上の要素が全て0の下三角行列
* Uは対角要素は1とは限らない、対角要素より下の要素が全て0の上三角行列

A = LU

Ax=b という方程式があれば、 LUx=b

すなわちL(Ux)=b

Ux=yとおくと、Ly=b

LU分解は消去法を用いて行う。

P,,ij,,(α) = I + αe,,i,,e,,j,,^T^

Aの第j行にαをかけて第i行に加える操作:

P,,ij,,(α)A = A + αe,,i,,e,,j,,^T^A

P,,ij,,(α) について次の性質がある:

* P,,ij,,^-1^(α) = P,,ij,,(-α) = I - αe,,i,,e,,j,,^T^
* P,,i'j,,(α')P,,ij,,(α) = I + (αe,,i,, + α'e,,i',,)e,,j,,^T^

実際にLU分解を行うときには、行列P,,ij,,(α)をAにかけるような計算は計算が遅いためしない。代わりに、行どうしの消去の計算を行う。

参考文献:
http://www.math.meiji.ac.jp/~mk/lecture/suurikaisekitokuron/gauss-elimination.pdf