LU分解

行列のLU 分解（エルユーぶんかい）とは、行列 A を下三角行列 L と上三角行列 U の積、すなわち

$A = LU$

に分解することを言う。

LU分解の手法

以下、n 次正方行列の場合で説明する。基本的にはA = LU の各成分について書き下した n² 個の式を解くことにより、行列 L , U を求めるのだが、このままでは未知の係数の個数が式の個数より多いので解けない。これを解くための解法には ドゥーリトル法 と クラウト法 の2つがある。

• ドゥーリトル法では、行列 L の対角成分の全てを 1 とおき、(1, 1) 成分 , (2, 1) 成分 , (3, 1) 成分 , ... , (1, 2) 成分, (2, 2) 成分, ... の順に n² 個の式を解く。
• クラウト法では、行列 U の対角成分の全てを 1 とおき、(1, 1) 成分 , (1, 2) 成分 , (1, 3) 成分 , ... , (2, 1) 成分, (2, 2) 成分, ... の順に n² 個の式を解く。

行列 A が正定値対称行列のときには、コレスキー分解

$A = LL^*$

を行うことができる。ただし、^* は行列のエルミート共役を表す。

応用

連立1次方程式

まず、連立1次方程式

$A \mathbf{x} = \mathbf{b}$

の行列 A を LU 分解すると、

$L U \mathbf{x} = \mathbf{b}$

となる。そこで変数y を

$U \mathbf{x} = \mathbf{y}$

のように定めて、上の式に代入すると、

$L \mathbf{y} = \mathbf{b}$

となる。

まずLy = b によって、変数y を求め、その解を用いてUx = y により、解 x を求める。Ly = b やUx = y はL ,U がそれぞれ下三角行列、上三角行列であるため、逆行列を求めることなく容易に計算することが可能である。このため、b だけを変えていくつも連立方程式を解く場合、LU 分解は有用である。

Ly = bはガウスの消去法の前進消去、Ux = yは後退代入に対応する。

逆行列

行列 A を LU 分解した後、

$A^{-1} = U^{-1}L^{-1}$

により逆行列を求めることができる。

行列式

行列 A を LU 分解できれば、その行列式は簡単に求めることができる。なぜならば、行列 L および U は三角行列であることから、それらの行列式$|L|$、$|U|$は対角成分の積で表され、$|A|$は、

$|A| = |L||U|$

と計算できるからである。

変種

LDU 分解

下三角行列 L と対角行列 D と上三角行列 U の積に分解する。

$A = LDU$

LUP 分解

下三角行列 L と上三角行列 U と置換行列 P の積に分解する。

$PA = LU$

関連項目

• en:Crout matrix decomposition