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}}$$L={\begin{bmatrix}1&0\\l_{21}&1\end{bmatrix}}$
(二)上三角行列 Uの対角成分と対角成分より上の成分を変数におく。
$U={\begin{bmatrix}u_{11}&u_{12}\\0&u_{22}\end{bmatrix}}$$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}}$${\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}}$${\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}}$

応用

連立1次方程式

連立1次方程式

$A{\boldsymbol {x}}={\boldsymbol {b}}$$A{\boldsymbol {x}}={\boldsymbol {b}}$
の解き方に、行列 AをLU分解する方法がある。L , Uは下三角行列、上三角行列であるため、逆行列を求めることなく計算することが可能である。このため、同じA に対しb だけを変えていくつも連立方程式を解く場合、LU分解は有用である。

与えられた方程式

$A{\boldsymbol {x}}=LU{\boldsymbol {x}}={\boldsymbol {b}}$$A{\boldsymbol {x}}=LU{\boldsymbol {x}}={\boldsymbol {b}}$
に対し、変数y を

$U{\boldsymbol {x}}={\boldsymbol {y}}$$U{\boldsymbol {x}}={\boldsymbol {y}}$
とおき、これを上式に代入する。

$L{\boldsymbol {y}}={\boldsymbol {b}}$$L{\boldsymbol {y}}={\boldsymbol {b}}$
から変数y を求める。求めた解y をUx = yの右辺に代入し、解 xを求めることができる。

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

逆行列

行列 AをLU分解すると、

$A^{-1}=U^{-1}L^{-1}$$A^{-1}=U^{-1}L^{-1}$
により逆行列A^-1 を求められる。

また、

$LU{\boldsymbol {x_{i}}}={\boldsymbol {e_{i}}}\quad (i=1,2,\dots ,n)$$LU{\boldsymbol {x_{i}}}={\boldsymbol {e_{i}}}\quad (i=1,2,\dots ,n)$
︵e_i は単位行列I の第i 列︶

の解x_i を並べた行列$X=[{\boldsymbol {x_{1}}},{\boldsymbol {x_{2}}},\dots ,{\boldsymbol {x_{n}}}]$$X=[{\boldsymbol {x_{1}}},{\boldsymbol {x_{2}}},\dots ,{\boldsymbol {x_{n}}}]$は AX= Iを満たすので、このようにしても逆行列A^-1 を求めることができる。

行列式

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

$|A|=|L||U|$$|A|=|L||U|$
と計算できるからである。

変種

LDU 分解

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

$A=LDU$

LUP 分解

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

$PA=LU$

関連項目

• en:Crout matrix decomposition