LU分解のソースを表示

{{出典の明記|date=2013年4月24日 (水) 04:30 (UTC)}}
[[数学]]における行列の'''LU分解'''（エルユーぶんかい、{{lang-en-short|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''<sup>2</sup> 個の式を解くことにより、行列 ''L'' , ''U'' を求めるのだが、このままでは未知の係数の個数（''n'' (''n'' + 1) 個）が式の個数（''n''<sup>2</sup>個）より多いので解けない。これを解くための解法には '''ドゥーリトル法''' と '''クラウト法''' の2つがある。

* ドゥーリトル法では、行列 ''L'' の対角成分の全てを 1 とおき、(1, 1) 成分 , (2, 1) 成分 , (3, 1) 成分 , ... , (1, 2) 成分, (2, 2) 成分, ... の順に ''n''<sup>2</sup> 個の式を解く。
* クラウト法では、行列 ''U'' の対角成分の全てを 1 とおき、(1, 1) 成分 , (1, 2) 成分 , (1, 3) 成分 , ... , (2, 1) 成分, (2, 2) 成分, ... の順に ''n''<sup>2</sup> 個の式を解く。

=== 例 ===
ドゥーリトル法による2次行列のLU分解を行う。与えられた正方行列''A'' の成分を''a<sub>ij</sub>'' とする。

# 下三角行列 ''L'' の対角成分を全て 1 とおき、残りの成分、(1, 2)を0、(2, 1)を変数''l''<sub>21</sub> とおく。
#:<math>L=\begin{bmatrix}1&0\\l_{21}&1\end{bmatrix}</math>
# 上三角行列 ''U'' の対角成分と対角成分より上の成分を変数におく。
#:<math>U=\begin{bmatrix}u_{11}&u_{12}\\0&u_{22}\end{bmatrix}</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{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{align}</math>

== 応用 ==
=== 連立1次方程式 ===
[[線型方程式系|連立1次方程式]]
:<math>A \boldsymbol{x} = \boldsymbol{b}</math>
の解き方に、行列 ''A'' を LU分解する方法がある。''L'' , ''U'' は下三角行列、上三角行列であるため、逆行列を求めることなく計算することが可能である。このため、同じ''A'' に対し'''''b''''' だけを変えていくつも連立方程式を解く場合、LU分解は有用である<ref>{{cite|和書 |title=コンピュータによる流体力学 |author=Joel H. Ferziger |author2=Milovan Peri&#x107; |translator=小林敏雄、谷口伸行、坪倉誠 |publisher=シュプリンガー・フェアラーク東京 |year=2003 |isbn=4-431-70842-1 |page=90}}</ref>。

与えられた方程式
:<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''''' を求める<ref group="注釈">左辺''L'''y''''' を計算し、左辺と右辺を係数比較すれば、'''''y''''' が求まる。</ref>。求めた解'''''y''''' を''U'''x''''' = '''''y''''' の右辺に代入し、解 '''''x''''' を求めることができる<ref group="注釈">左辺''U'''x'''''を計算し、左辺と右辺を係数比較すれば、'''''x''''' が求まる。</ref>。

''L'''y''''' = '''''b'''''は[[ガウスの消去法]]の前進消去、''U'''x''''' = '''''y'''''は後退代入に対応する。

=== 逆行列 ===
行列 ''A'' を LU 分解すると、
:<math>A^{-1} = U^{-1}L^{-1}</math>
により[[正則行列|逆行列]]''A''<sup>-1</sup> を求められる。

また、
:<math>LU\boldsymbol{x_i}=\boldsymbol{e_i} \quad (i=1,2,\dots ,n)</math>
: （'''''e'''<sub>i</sub>'' は[[単位行列]]''I'' の第''i'' 列）
の解'''''x'''<sub>i</sub>'' を並べた行列<math>X=[\boldsymbol{x_1},\boldsymbol{x_2},\dots ,\boldsymbol{x_n}]</math>は ''AX'' = ''I'' を満たすので、このようにしても逆行列''A''<sup>-1</sup> を求めることができる。

=== 行列式 ===
行列 ''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>

== 脚注 ==
{{脚注ヘルプ}}
=== 注釈 ===
{{Notelist}}
=== 出典 ===
{{reflist}}

== 関連項目 ==
*[[:en:Crout matrix decomposition]]

{{Linear algebra}}

{{DEFAULTSORT:LUふんかい}}
[[Category:数値線形代数]]
[[Category:行列の分解]]
[[Category:数学に関する記事]]

[[de:Gaußsches Eliminationsverfahren#LR-Zerlegung]]