LU分解

テンプレート:出典の明記 数学における行列のLU分解（エルユーぶんかい、テンプレート:Lang-en-short）とは、正方行列 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 とする。

1. 下三角行列 L の対角成分を全て 1 とおき、残りの成分、(1, 2)を0、(2, 1)を変数l₂₁ とおく。

   $L=\left[\begin{array}{cc}1& 0\\ l_{21}& 1\end{array}\right]$

2. 上三角行列 U の対角成分と対角成分より上の成分を変数におく。

   $U=\left[\begin{array}{cc}{u}_{11}& u_{12}\\ 0& u_{22}\end{array}\right]$

3. A=LU の両辺を係数比較する。

   $\begin{array}{cc}{a}_{11}& =u_{11}\\ a_{12}& =u_{12}\\ a_{21}& =l_{21}{u}_{11}\\ a_{22}& =l_{21}{u}_{12}+u_{22}\end{array}$

4. 上式を上から順に解くことでL , U が求められる。

   $\begin{array}{cc}L& =\left[\begin{array}{cc}1& 0\\ \frac{a_{21}}{a_{11}}& 1\end{array}\right]\\ U& =\left[\begin{array}{cc}{a}_{11}& a_{12}\\ 0& a_{22}-\frac{a_{21}{a}_{12}}{a_{11}}\end{array}\right]\end{array}$

応用

連立1次方程式

連立1次方程式

$A𝒙=𝒃$

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

与えられた方程式

$A𝒙=LU𝒙=𝒃$

に対し、変数y を

$U𝒙=𝒚$

とおき、これを上式に代入する。

$L𝒚=𝒃$

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

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

逆行列

行列 A を LU 分解すると、

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

により逆行列A^-1 を求められる。

また、

$LU{𝒙}_{𝒊}={𝒆}_{𝒊}(i=1,2,\dots ,n)$

（e_i は単位行列I の第i 列）

の解x_i を並べた行列$X=[{𝒙}_1,{𝒙}_2,\dots ,{𝒙}_{𝒏}]$は AX = I を満たすので、このようにしても逆行列A^-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