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 とする。

1. 下しも三角さんかく行列ぎょうれつ L の対たい角かく成分せいぶんを全すべて 1 とおき、残のこりの成分せいぶん、(1, 2)を0、(2, 1)を変数へんすうl₂₁ とおく。

   $L={\begin{bmatrix}1&0\\l_{21}&1\end{bmatrix}}$

2. 上うえ三角さんかく行列ぎょうれつ U の対たい角かく成分せいぶんと対たい角かく成分せいぶんより上うえの成分せいぶんを変数へんすうにおく。

   $U={\begin{bmatrix}u_{11}&u_{12}\\0&u_{22}\end{bmatrix}}$

3. 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}}$

4. 上うえ式しきを上うえから順じゅんに解とくことで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}}$

応用おうよう

連立れんりつ1次じ方程式ほうていしき

連立れんりつ1次じ方程式ほうていしき

$A{\boldsymbol {x}}={\boldsymbol {b}}$

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

与あたえられた方程式ほうていしき

$A{\boldsymbol {x}}=LU{\boldsymbol {x}}={\boldsymbol {b}}$

に対たいし、変数へんすうy を

$U{\boldsymbol {x}}={\boldsymbol {y}}$

とおき、これを上うえ式しきに代入だいにゅうする。

$L{\boldsymbol {y}}={\boldsymbol {b}}$

から変数へんすうy を求もとめる。求もとめた解かいy をUx = y の右辺うへんに代入だいにゅうし、解かい x を求もとめることができる。

Ly = bはガウスの消去しょうきょ法ほうの前進ぜんしん消去しょうきょ、Ux = yは後退こうたい代入だいにゅうに対応たいおうする。

逆ぎゃく行列ぎょうれつ

行列ぎょうれつ A を LU 分解ぶんかいすると、

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

により逆ぎゃく行列ぎょうれつA^-1 を求もとめられる。

また、

$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}}}]$は 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