LU分解
テンプレート:出典の明記 数学における行列のLU分解（エルユーぶんかい）とは、正方行列 A を下三角行列 L と上三角行列 U の積に分解すること。すなわち A = LU が成立するような L と U を求めることをいう。
LU分解の手法
以下、n 次正方行列の場合で説明する。基本的にはA = LU の各成分について書き下した n2 個の式を解くことにより、行列 L , U を求めるのだが、このままでは未知の係数の個数（n (n +1)個）が式の個数（n2個）より多いので解けない。これを解くための解法には ドゥーリトル法 と クラウト法 の2つがある。
- ドゥーリトル法では、行列 L の対角成分の全てを 1 とおき、(1, 1) 成分 , (2, 1) 成分 , (3, 1) 成分 , ... , (1, 2) 成分, (2, 2) 成分, ... の順に n2 個の式を解く。
- クラウト法では、行列 U の対角成分の全てを 1 とおき、(1, 1) 成分 , (1, 2) 成分 , (1, 3) 成分 , ... , (2, 1) 成分, (2, 2) 成分, ... の順に n2 個の式を解く。
- <math>A = LL^*</math>
を行うことができる。ただし、* は行列のエルミート共役を表す。
例
ドゥーリトル法による2次行列のLU分解を行う。与えられた正方行列A の成分をaij とする。
- 下三角行列L の対角成分を全て 1 とおき、残りの成分、(1, 2)を0、(2, 1)を変数l12 とおく。
- <math>L=\begin{pmatrix}1&0\\l_{21}&1\end{pmatrix}</math>
- 上三角行列U の対角成分と対角成分より上の成分を変数におく。
- <math>U=\begin{pmatrix}u_{11}&u_{12}\\0&u_{22}\end{pmatrix}</math>
- A=LU の両辺を係数比較する。
- <math>\begin{align}
a_{11}&=u_{11}\\ a_{12}&=u_{12}\\ a_{21}&=l_{21}u_{11}\\ a_{22}&=l_{21}u_{12}+u_{22} \end{align}</math>
- 上式を上から順に解くことでL , U が求められる。
- <math>\begin{align}
L&=\begin{pmatrix}1&0\\\frac{a_{21}}{a_{11}}&1\end{pmatrix}\\ U&=\begin{pmatrix}a_{11}&a_{12}\\0&a_{22}-\frac{a_{21}a_{12}}{a_{11}}\end{pmatrix} \end{align}</math>
応用
連立1次方程式
- <math>A \boldsymbol{x} = \boldsymbol{b}</math>
の解き方に、行列 A を LU分解する方法がある。L , U は下三角行列、上三角行列であるため、逆行列を求めることなく計算することが可能である。このため、同じA に対しb だけを変えていくつも連立方程式を解く場合、LU分解は有用である[1]。
与えられた方程式
- <math>A \boldsymbol{x} = L U \boldsymbol{x} = \boldsymbol{b}</math>
に対し、変数y を
- <math>U \boldsymbol{x} = \boldsymbol{y}</math>
とおき、これを上式に代入する。
- <math>L \boldsymbol{y} = \boldsymbol{b}</math>
から変数y を求める[2]。求めた解y をUx = y の右辺に代入し、解 x を求めることができる[3]。
Ly = bはガウスの消去法の前進消去、Ux = yは後退代入に対応する。
逆行列
行列 A を LU 分解すると、
- <math>A^{-1} = U^{-1}L^{-1}</math>
により逆行列A-1 を求められる。
また、
- <math>LU\boldsymbol{x_i}=\boldsymbol{e_i}\ (i=1,2,\ldots ,n)</math>
- （ei は単位行列I の第i 列）
の解xi を並べた行列<math>X=[\boldsymbol{x_1},\boldsymbol{x_2},\ldots ,\boldsymbol{x_n}]</math>は AX = I を満たすので、このようにしても逆行列A-1 を求めることができる。
行列式
行列 A を LU 分解できれば、その行列式は簡単に求めることができる。なぜならば、行列 L および U は三角行列であることから、それらの行列式 |L | , |U | は対角成分の積で表され、|A | は、
- <math>|A| = |L||U|</math>
と計算できるからである。
変種
- LDU 分解
- 下三角行列 L と対角行列 D と上三角行列 U の積に分解する。
- <math>A = LDU</math>
- LUP 分解
- 下三角行列 L と上三角行列 U と置換行列 P の積に分解する。
- <math>PA = LU</math>
