LU分解

LU分解は連立方程式を高速かつ簡単に解くために用いる。ググっても数式ばかりで直感的によくわからないので具体例をつかったメモを残しておく。

前提の考え方

LU分解の目的

$$ A = \left(\begin{array}{ccc}
1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9 \\
\end{array}\right) $$

であったとき、行列LとUを

$$A = LU$$

という形で表現したいわけだが、

$$ L = \left(\begin{array}{ccc}
1 & 0 & 0 \\
? & 1 & 0 \\
? & ? & 1 \\
\end{array}\right) $$

$$ U = \left(\begin{array}{ccc}
? & ? & ? \\
0 & ? & ? \\
0 & 0 & ? \\
\end{array}\right) $$

のように、 ? 以外の数字は決まっているので
LU分解とは ? の数を探るということである。

Lは横3つ、Uは縦3つに分けて考えられるということ

例えば、Lという行列が、

$$ L = \left(\begin{array}{ccc}
1 & 0 & 0 \\
4 & 1 & 0 \\
7 & 8 & 1 \\
\end{array}\right) $$

だとすると縦３つに分け、それぞれを勝手に\(L_1, L_2, L_3\)と置くことで

$$ \begin{eqnarray*}L &=& \left(\begin{array}{ccc}
\left(\begin{array}{c}
1\\
4\\
7\\
\end{array}\right) \left(\begin{array}{c}
0\\
1\\
8\\
\end{array}\right) \left(\begin{array}{c}
0\\
0\\
1\\
\end{array}\right)
\end{array}\right) \\&=& \left(\begin{array}{ccc}
\left(\begin{array}{c}
\\
L_1\\
\\
\end{array}\right) \left(\begin{array}{c}
\\
L_2\\
\\
\end{array}\right) \left(\begin{array}{c}
\\
L_3\\
\\
\end{array}\right)
\end{array}\right)\end{eqnarray*}$$

と考える事ができる。Uは横３つに分けることで、

$$ \begin{eqnarray*}U &=& \left(\begin{array}{ccc}
1 & 2 & 3 \\
0 & 5 & 6 \\
0 & 0 & 9 \\
\end{array}\right) \\
&=&
\left(\begin{array}{ccc}
\left(\begin{array}{ccc}
1&2&3
\end{array}\right)\\\left(\begin{array}{ccc}
0&5&6
\end{array}\right)\\\left(\begin{array}{ccc}
0&0&9
\end{array}\right)\\
\end{array}\right) &=&\left(\begin{array}{ccc}
\left(\begin{array}{ccc}
&U_1&
\end{array}\right)\\\left(\begin{array}{ccc}
&U_2&
\end{array}\right)\\\left(\begin{array}{ccc}
&U_3&
\end{array}\right)\\
\end{array}\right)\end{eqnarray*}$$

と考えることができる。ここで、LとUの積LUは、

\begin{eqnarray*}LU &=& \left(\begin{array}{ccc} \left(\begin{array}{c} \\ L_1\\ \\ \end{array}\right) \left(\begin{array}{c} \\ L_2\\ \\ \end{array}\right) \left(\begin{array}{c} \\ L_3\\ \\ \end{array}\right) \end{array}\right)\left(\begin{array}{ccc} \left(\begin{array}{ccc} &U_1& \end{array}\right)\\\left(\begin{array}{ccc} &U_2& \end{array}\right)\\\left(\begin{array}{ccc} &U_3& \end{array}\right)\\ \end{array}\right) \\ &=& \left( \begin{array}{ccc} L_1 & L_2 & L_3 \end{array}\right) \left( \begin{array}{c} U_1\\ U_2\\ U_3\\ \end{array} \right) \\ &=& L_1 U_1 + L_2 U_2 + L_3 U_3 \end{eqnarray*}

と表記できる。

通常のやり方

ポイント

$$ A = \left(\begin{array}{ccc}
2 & 3 & -1\\
2 & 7 & 3\\
2 & -1 & 1\\
\end{array}\right) $$

として問題を解いていくことにしよう。

前提の考え方で、以下のように表すことができる。

$$LU = L_1 U_1 + L_2 U_2 + L_3 U_3 $$

$$L_1 U_1 = \left( \begin{array}{c}
1\\
?\\
?\\
\end{array} \right) \left( \begin{array}{ccc}
? & ? & ? \end{array} \right ) =\left( \begin{array}{ccc}
? & ? & ?\\
? & ? & ?\\
? & ? & ?\\
\end{array}\right) \\L_2 U_2 = \left( \begin{array}{c}
0\\
1\\
?\\
\end{array} \right) \left( \begin{array}{ccc}
0 & ? & ? \end{array} \right ) =\left( \begin{array}{ccc}
0 & 0 & 0\\
0 & ? & ?\\
0 & ? & ?\\
\end{array}\right) \\
L_3 U_3 = \left( \begin{array}{c}
0\\
0\\
1\\
\end{array} \right) \left( \begin{array}{ccc}
0 & 0 & ? \end{array} \right )= \left( \begin{array}{ccc}
0 & 0 & 0\\
0 & 0 & 0\\
0 & 0 & ?\\
\end{array}\right) $$

Aの1行1列目は、\( L_1 U_1 \)でしか表現できないということがポイントだ。

つまり\( L_1 U_1 \)は自動的に決定することができる。

\(L_1 U_1 \)を求める

$$L_1 U_1 =\left( \begin{array}{ccc}
2 & 3 & -1\\
2 & ? & ?\\
2 & ? & ?\\
\end{array}\right) $$

これを表現するためには、

$$ L_1 U_1 =\left( \begin{array}{c}
1\\
1\\
1\\
\end{array} \right) \left( \begin{array}{ccc}
2 & 3 & -1 \end{array} \right ) =\left( \begin{array}{ccc}
2 & 3 & -1\\
2 & 3 & -1\\
2 & 3 & -1\\
\end{array}\right)\\$$

ここまでをまとめると以下になる。

$$A =\left( \begin{array}{ccc}
2 & 3 & -1\\
2 & 3 & -1\\
2 & 3 & -1\\
\end{array}\right) + L_2 U_2 + L_3 U_3$$

\( L_2 U_2\)を求める

移項して右辺を\(L_2 U_2 + L_3 U_3\)の形にする。

$$A -\left( \begin{array}{ccc}
2 & 3 & -1\\
2 & 3 & -1\\
2 & 3 & -1\\
\end{array}\right) = L_2 U_2 + L_3 U_3$$

$$\left( \begin{array}{ccc}
0 & 0 & 0\\
0 & 4 & 4\\
0 & -4 & 2\\
\end{array}\right) = L_2 U_2 + L_3 U_3$$

さっきと同様に

$$L_2 U_2 =\left( \begin{array}{ccc}
0 & 0 & 0\\
0 & 4 & 4\\
0 & -4 & ?\\
\end{array}\right)$$

である必要があるから

$$\begin{eqnarray*} L_2 U_2 &=&\left( \begin{array}{ccc}
0 & 0 & 0\\
0 & 4 & 4\\
0 & -4 & ?\\
\end{array}\right) =\left( \begin{array}{c}
0\\
1\\
-1\\
\end{array} \right) \left( \begin{array}{ccc}
0 & 4 & 4 \end{array} \right )\\
&=&\left( \begin{array}{ccc}
0 & 0 & 0\\
0 & 4 & 4\\
0 & -4 & -4\\
\end{array}\right) \end{eqnarray*}$$

\(L_3 U_3\)を求める

再度移行して右辺を\(L_3 U_3\)にする。

$$A – L_1 U_1 – L_2 U_2 = L_3 U_3$$

$$左辺 = \left( \begin{array}{ccc}
0 & 0 & 0\\
0 & 4 & 4\\
0 & -4 & 2\\
\end{array}\right) – \left( \begin{array}{ccc}
0 & 0 & 0\\
0 & 4 & 4\\
0 & -4 & -4\\
\end{array}\right) = \left( \begin{array}{ccc}
0 & 0 & 0\\
0 & 0 & 0\\
0 & 0 & 6\\
\end{array}\right)$$

$$L_2 U_2 =\left( \begin{array}{ccc}
0 & 0 & 0\\
0 & 0 & 0\\
0 & 0 & 6\\
\end{array}\right)$$

である必要があるから、

$$\begin{eqnarray*} L_2 U_2 &=&\left( \begin{array}{ccc}
0 & 0 & 0\\
0 & 0 & 0\\
0 & 0 & 6\\
\end{array}\right) =\left( \begin{array}{c}
0\\
0\\
1\\
\end{array} \right) \left( \begin{array}{ccc}
0 & 0 & 6 \end{array} \right )\\
&=&\left( \begin{array}{ccc}
0 & 0 & 0\\
0 & 0 & 0\\
0 & 0 & 6\\
\end{array}\right) \end{eqnarray*}$$

\(LU\)を求める

一連の作業により

$$ \begin{eqnarray*} L_1 U_1 &=&\left( \begin{array}{c}
1\\
1\\
1\\
\end{array} \right) \left( \begin{array}{ccc}
2 & 3 & -1 \end{array} \right ) \\ L_2 U_2
&=&\left( \begin{array}{c}
0\\
1\\
-1\\
\end{array} \right) \left( \begin{array}{ccc}
0 & 4 & 4 \end{array} \right ) \\ L_3 U_3&=&
\left( \begin{array}{c}
0\\
0\\
1\\
\end{array} \right) \left( \begin{array}{ccc}
0 & 0 & 6 \end{array} \right ) \end{eqnarray*} $$

が求められているので、

$$\begin{eqnarray*}LU &=& L_1 U_1 + L_2 U_2 + L_3 U_3 \\ &=&\left( \begin{array}{ccc} L_1 & L_2 & L_3 \end{array}\right) \left( \begin{array}{c} U_1\\ U_2\\ U_3\\ \end{array} \right) \\&=&\left(\begin{array}{ccc} \left(\begin{array}{c} \\ L_1\\ \\ \end{array}\right) \left(\begin{array}{c} \\ L_2\\ \\ \end{array}\right) \left(\begin{array}{c} \\ L_3\\ \\ \end{array}\right) \end{array}\right)\left(\begin{array}{ccc} \left(\begin{array}{ccc} &U_1& \end{array}\right)\\\left(\begin{array}{ccc} &U_2& \end{array}\right)\\\left(\begin{array}{ccc} &U_3& \end{array}\right)\\ \end{array}\right) \end{eqnarray*}$$

を思い出して復元すると、

$$ LU = \left( \begin{array}{ccc}
1 & 0 & 0\\
1 & 1 & 0\\
1 & -1 & 1\\
\end{array}\right)\left( \begin{array}{ccc}
2 & 3 & -1\\
0 & 4 & 4\\
0 & 0 & 6\\
\end{array}\right)$$