LU分解

出典: フリー百科事典『ウィキペディア（Wikipedia）』

（行列の）LU 分解（えるゆーぶんかい）とは、行列 A を下三角行列 (lower triangular matrix) L と上三角行列 (upper triangular matrix) U の積、すなわち

A = L U

と分解することを言う。

LU 分解の変種として、下三角行列 L と対角行列 Dと上三角行列 U の積に分解する LDU 分解 や、上三角行列 L と下三角行列 U と置換行列 P の積に分解する LUP 分解 がある。

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

A = L L *

を行うことができる。（L^*の意味については、コレスキー分解の記事を参照のこと）

[編集] LU分解の基本

基本的な解法には ドゥーリトル法 と クラウト法 の2つがある。

以下、n次正方行列の場合で説明する。

これら 2 つの方法とも、A=LU の各成分について書き下した n²個の式を解くことにより、行列 L, U を求める。ただし、このままでは未知の係数の個数が式の個数より多いので解けない。そこで、ドゥーリトル法では、行列 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²個の式を解く。

[編集] 応用

[編集] 連立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は後退代入に対応する。