LU分解とは？
LU分解（LU decomposition）とは行列を下三角行列と上三角行列に分解してそれらの積で表すことです。つまり下三角行列を\(L\)、上三角行列を\(U\)とすると、
$$A=LU$$ という形で表すことです。
LU分解の方法はいくつかありますが、ここではガウスの消去法とドゥーリトル法について述べます。
その後でLU分解による連立方程式の解法ついても説明します。
なお、「PLU分解」ついては別のページで説明します。
ガウスの消去法
方法
\(A\)に左から基本行列\(E_1,E_2,\cdots E_k\)を掛けて上三角行列\(U\)が得られたとします。
$$E_k\cdots E_2 E_1A=U$$
基本行列の積の逆行列を\(L\)とし、これを両辺に掛けると、
$$A=(E_k\cdots E_2 E_1)^{-1}U=E_1^{-1}E_2^{-1}\cdots E_k^{-1}U$$
以下のように定義すると、
$$L=E_1^{-1}E_2^{-1}\cdots E_k^{-1}$$
\(A\)は\(L\)と\(U\)の積で表すことができます。
$$A=LU$$
この\(L\)は後述の補足3の通り、下三角行列になります。
したがって、各基本行列の逆行列の積が下三角行列です。
基本行列には\(3\)種類ありましたが、ここでは「ある行列を定数倍して別の行に加える」場合の行列のみを使った場合について説明します（補足1）。
この場合の基本行列は、単位行列のある成分に定数を追加しただけなので、逆行列を求めるためには単にその値の符号を反転するだけですみます。
また、それぞれの定数を重ね合わせるだけで積になります（補足2）。
例
\(3\times 3\)の行列についてLU分解を行います。
以下、右をこの行列の変形後、左を基本行列の逆行列とします。
右の行列の\(1\)行目を\(-4\)倍し\(2\)行目に加えます。左の行列は変形前は単位行列であったとし、\((2,1)\)成分を\(-4 \times (-1)=4\)にします。
右の行列の\(1\)行目を\(-5\)倍し\(3\)行目に加えます。左の行列の\((3,1)\)成分を\(-5 \times (-1)=5\)にします。
右の行列の\(2\)行目を\(-3\)倍し\(3\)行目に加えます。左の行列の\((3,2)\)成分を\(-3 \times (-1)=3\)にします。
上三角行列と下三角行列が求められました。
補足1
行基本変形およびこれに対応する基本行列は「1. 2行を入れ替える」「2. ある行を定数倍する」「3. ある行を定数倍して別の行に加える」の3種類がありました。2.は必要があれば容易に行えるはずなので省略します。1.を使う場合については別のページで説明します。
補足2
上の例では基本行列の逆行列の積を計算せず、単位行列に定数を重ね合わせました。このような方法で問題ないのでしょうか。
実は消去の順序によっては正しく積が求められないことがあります。
次の例は第\(2\)列を先に消去し、その後で第\(1\)列を消去しています。
得られた\(LU\)を計算すると元の行列と一致しません。
\(U\)を求めるための消去においては基本行列を左から掛けていましたが、\(L\)を求めるための逆行列は右から掛けています（「方法」の節参照）。右から掛ける場合は行基本変形ではなく、列基本変形と考えるべきです。単に\(U\)を求める際とは逆の行基本変形をしているわけではありません。
にもかかわらずこのような重ね合わせがうまくいくのは第\(1\)列より右に向かって消去を進めるからです（詳細は省略します）。
上三角行列を消去法で求める場合、第\(1\)列より消去するはずです。上の例はあえて説明のために試しただけで、このような順序にする理由はありません。したがって定数を重ね合わせる方法でも問題ないと考えてよいと思います。
なお、どのような順序でも定数を重ね合わせるのではなく、定義に従って積を計算するのであれば問題ありません。気になる場合は積を計算してください。
補足3
\(L=E_1^{-1}E_2^{-1}\cdots E_k^{-1}\)としましたが、この\(L\)は必ず下三角行列になるのでしょうか。
消去のためある行を定数倍しその行より下の行に加えた場合、基本行列においてはその定数は必ず対角成分より下に現れます。
また、その逆行列は定数の符号が変わるだけで位置は変わりません。つまり逆行列においてもその定数は対角成分より下にあります。
さらに、それらの積においても定数の位置は変わりません。
したがって、必ず定数倍した行より下の行に加えることによって消去するのであれば、\(L\)は下三角行列です。
証明
\(U\)と\(L\)が一意に決まらないと仮定するため、
$$A=LDD^{-1}U=(LD)(D^{-1}U)$$
における\(LD\)が下三角行列かつ対角成分が全て\(1\)、\(D^{-1}U\)が上三角行列、\(D\)が単位行列以外であるとする。
\(LD\)が下三角行列であるなら\(D\)は下三角行列、\(D^{-1}U\)が上三角行列であるなら\(D^{-1}\)は上三角行列である。これらを満たすためには\(D\)は対角行列でなければならない。
\(L\)の対角成分が全て\(1\)であるので、
$$(LD)_{ii}=L_{ii}D_{ii}=D_{ii}$$
ただし添え字はこれらが行列の成分であることを示している。
\(D\)が単位行列でないのであれば\((LD)_{ii}\)のうち少なくとも\(1\)つは\(1\)以外でなければならず、仮定に反する。したがって\(U\)と\(L\)は一意に決まる。
■
ドゥーリトル法
方法
\(L\)と\(U\)を以下のように定義します。
$$
\begin{pmatrix}
a_{11}&a_{12}&a_{13}\\
a_{21}&a_{22}&a_{23}\\
a_{31}&a_{32}&a_{33}
\end{pmatrix}
=
\begin{pmatrix}
1&0&0\\
l_{21}&1&0\\
l_{31}&l_{32}&1
\end{pmatrix}
\begin{pmatrix}
u_{11}&u_{12}&u_{13}\\
0&u_{22}&u_{23}\\
0&0&u_{33}
\end{pmatrix}
$$
\(L\)と\(U\)の積を計算すると、
$$
\begin{pmatrix}
a_{11}&a_{12}&a_{13}\\
a_{21}&a_{22}&a_{23}\\
a_{31}&a_{32}&a_{33}
\end{pmatrix}
=
\begin{pmatrix}
u_{11}&u_{12}&u_{13}\\
l_{21}u_{11}&l_{21}u_{12}+u_{22}&l_{21}u_{13}+u_{23}\\
l_{31}u_{11}&l_{31}u_{12}+l_{32}u_{22}&l_{31}u_{13}+l_{32}u_{23}+u_{33}
\end{pmatrix}
$$
以下のように方程式を立てて解きます。複雑なようにみえますが、上から順に代入していくだけです。
\begin{align}
a_{11}&=u_{11}\\
a_{12}&=u_{12}\\
a_{13}&=u_{13}\\
a_{21}&=l_{21}u_{11}\\
a_{22}&=l_{21}u_{12}+u_{22}\\
a_{23}&=l_{21}u_{13}+u_{23}\\
a_{31}&=l_{31}u_{11}\\
a_{32}&=l_{31}u_{12}+l_{32}u_{22}\\
a_{33}&=l_{31}u_{13}+l_{32}u_{23}+u_{33}\\
\end{align}
ドゥーリトル法では\(L\)の対角成分が全て\(1\)となるよう分解しますが、\(L\)ではなく\(U\)の対角成分が全て\(1\)となるようにするのがクラウト法です。
例
以下を分解します。
\begin{align}
A&=
\begin{pmatrix}
6&1&6\\
24&8&4\\
30&17&12
\end{pmatrix}\\
u_{11}&=6\\
u_{12}&=1\\
u_{13}&=6\\
l_{21}&=a_{21}/u_{11}=24/6=4\\
u_{22}&=a_{22}-l_{21}u_{12}=8-4 \times 1=4\\
u_{23}&=a_{23}-l_{21}u_{13}=24-4\times6=0\\
l_{31}&=a_{31}/u_{11}=30/6=5\\
l_{32}&=(a_{32}-l_{31}u_{12})/u_{22}=(17-5\times 1)/4=3\\
u_{33}&=a_{33}-l_{31}u_{13}-l_{32}u_{23}=32-5\times 6 – 3 \times 0 = 2\\
\end{align}
以上より、
\begin{align}
u_{11}&=6\\
u_{12}&=1\\
u_{13}&=6\\
l_{21}&=a_{21}/u_{11}=24/6=4\\
u_{22}&=a_{22}-l_{21}/u_{12}=8-4/1=4\\
u_{23}&=a_{23}-l_{21}u_{13}=24-4\times6=0\\
l_{31}&=a_{31}/u_{11}=30/6=5\\
l_{32}&=(a_{32}-l_{31}u_{12})/u_{22}=(17-5\times 1)/4=3\\
u_{33}&=a_{33}-l_{31}u_{13}-l_{32}u_{23}=32-5\times 6 – 3 \times 0 = 2\\
\end{align}
連立1次方程式の解法
方法
方程式が以下であったとします。
$$A\boldsymbol{x}=\boldsymbol{b} \tag{1}$$
\(\boldsymbol{x}\)が未知数、\(\boldsymbol{b}\)が定数のベクトルです。
以下のようにLU分解できたとします。
$$A=LU$$
\(\boldsymbol {y}\)を
$$U\boldsymbol{x}=\boldsymbol{y}\tag{2}$$
とおくと\( (1) \)は、
$$L\boldsymbol{y}=\boldsymbol{b}\tag{3}$$
と表されます。
そこでまず\( (3) \)の\(\boldsymbol{y}\)を求め、次に\( (2) \)の\(\boldsymbol{x}\)を求めます。
いずれも係数は三角行列であることを利用して方程式を解きます。解き方は次の例を参照ください。
例
\(A\)と\(\boldsymbol{b}\)を
$$
A=
\begin{pmatrix}
30&30&5\\
48&52&18\\
42&44&60
\end{pmatrix}
,
\boldsymbol{b}=
\begin{pmatrix}
110\\
224\\
370\\
\end{pmatrix}
$$
とします。
経過を省略しますが、\(A\)はLU分解により
$$
L=
\begin{pmatrix}
5&0&0\\
8&2&0\\
7&1&6
\end{pmatrix}
,
U=
\begin{pmatrix}
6&6&1\\
0&2&5\\
0&0&8
\end{pmatrix}
$$
となるので、\(L\boldsymbol{y}=\boldsymbol{b}\)は、
$$
\begin{pmatrix}
5&0&0\\
8&2&0\\
7&1&6
\end{pmatrix}
\begin{pmatrix}
y_1\\
y_2\\
y_3
\end{pmatrix}
=
\begin{pmatrix}
110\\
224\\
370
\end{pmatrix}
$$
と表されます。\(1\)行ずつ表すと、
\begin{align}
\hspace{-18pt}5y_1\hspace{48pt}= 110\\
\hspace{-32pt}8y_1+2y_2\hspace{21pt}= 224\\
7y_1+y_2+6y_3= 370\\
\end{align}
上から順に解くと、
\begin{align}
y_1&=\frac{110}{5}=22\\
y_2&=\frac{224-8\times22}{2}=24\\
y_3&=\frac{370-7\times 22-24}{6}=32\\
\end{align}
となります。このように上から下に向かって解くことを前進代入とよびます。
これを\(U\boldsymbol{x}=\boldsymbol{y}\)に代入すると、
$$
\begin{pmatrix}
6&6&1\\
0&2&5\\
0&0&8
\end{pmatrix}
\begin{pmatrix}
x_1\\
x_2\\
x_3\\
\end{pmatrix}
=
\begin{pmatrix}
22\\
24\\
32
\end{pmatrix}
$$
\begin{align}
6x_1 &+6x_2 +\hspace{5pt} x_3 =22\\
&\color{white}{+}2x_2 +5x_3 =24\\
&\hspace{27pt} \color{white}{+}8x_3 =32\\
\end{align}
下から順に解くと、
\begin{align}
x_3&=\frac{32}{8}=4\\
x_2&=\frac{24-5\times 4}{2}=2\\
x_1&=\frac{22-6\times 2-4}{6}=1\\
\end{align}
このように下から上に向かって解くことを後退代入とよびます。
以上、解が求まりました。