LU分解

数学における行列のLU分解（エルユーぶんかい、英: LU decomposition）とは、正方行列 A を下三角行列 L と上三角行列 U の積に分解すること。すなわち A = LU が成立するような L と U を求めることをいう。正方行列 A のLU分解が存在する必要十分条件はすべての首座小行列式が 0 でないことである。また L の対角成分をすべて 1 とすれば分解はただ一通りに定まる。文献によってはLR分解とも呼ばれる（それはAを左三角(left triangular)と右三角(right triangular)の行列の積に分解するということにちなむ）。

LU分解の手法

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

例

ドゥーリトル法による2次行列のLU分解を行う。与えられた正方行列A の成分をa_ij とする。

下三角行列 L の対角成分を全て 1 とおき、残りの成分、(1, 2)を0、(2, 1)を変数l₂₁ とおく。
$L={\begin{bmatrix}1&0\\l_{21}&1\end{bmatrix}}$
上三角行列 U の対角成分と対角成分より上の成分を変数におく。
$U={\begin{bmatrix}u_{11}&u_{12}\\0&u_{22}\end{bmatrix}}$
A=LU の両辺を係数比較する。
${\begin{aligned}a_{11}&=u_{11}\\a_{12}&=u_{12}\\a_{21}&=l_{21}u_{11}\\a_{22}&=l_{21}u_{12}+u_{22}\end{aligned}}$
上式を上から順に解くことでL , U が求められる。
${\begin{aligned}L&={\begin{bmatrix}1&0\\{\frac {a_{21}}{a_{11}}}&1\end{bmatrix}}\\U&={\begin{bmatrix}a_{11}&a_{12}\\0&a_{22}-{\frac {a_{21}a_{12}}{a_{11}}}\end{bmatrix}}\end{aligned}}$