行列のUL分解

Gaussの消去法は連立1次方程式を解くための主要な道具です.ここでは,拡大係数行列 $[A : {\bf b}]$のピボットの乗数から,行列$A$を下三角行列$L$と上三角行列$U$の積$A = LU$で表す方法を学びます.

では,どうやって$A = LU$と分解するのか.

\begin{displaymath}\begin{array}{rrrrrr}
x_{1}& + x_{2}& & + 3x_{4}& =& 4\\
2x_...
... =& -3\\
-x_{1}& + 2x_{2}& + 3x_{3}& - x_{4}& =& 4
\end{array}\end{displaymath}

より係数行列は

$\displaystyle {A}^{(1)} = \left(\begin{array}{rrrr}
1 & 1 & 0 & 3\\
2 & 1 & -1 & 1\\
3 & -1 & -1 & 2\\
-1 & 2 & 3 & -1
\end{array}\right)$

となる. ピボット $a_{11}^{(1)} = 1 \neq 0$より,乗数 $m_{2,1} = 2, m_{3,1} = 3, m_{4,1} = -1$.ここで,行基本変形 $-2R_{1} + R_{2} \to R_{2}$, $-3R_{1}+R_{3} \to R{3}$, $R_{1} + R_{4} \to R_{4}$を行うと

$\displaystyle {A}^{(2)} = \left(\begin{array}{rrrr}
1 & 1 & 0 & 3\\
0 & -1 & -1 & -5\\
0 & -4 & -1 & -7\\
0 & 3 & 3 & 2
\end{array}\right)$

となる.次にピボット $a_{22}^{(2)} = -1 \neq 0$より,乗数 $m_{3,2} = 4, m_{4,2} = -3$.ここで,行基本変形 $-4R_{2} + R_{3} \to R_{3}$, $3R_{2}+R_{4} \to R_{4}$を行うと

$\displaystyle {A}^{(3)} = \left(\begin{array}{rrrr}
1 & 1 & 0 & 3\\
0 & -1 & -1 & -5\\
0 & 0 & 3 & 13\\
0 & 0 & 0 & -13
\end{array}\right)$

となる.$A^{(3)}$は上三角行列より $A^{(3)} = U$とすれば$U$が求まります.では,$L$はどうなっているのでしょうか.ここで行った操作を行列になおして考えると, まず, $-2R_{1} + R_{2} \to R_{2}$, $-3R_{1}+R_{3} \to R_{3}$, $R_{1} + R_{4} \to R_{4}$を行うことは,行列${A}^{(1)}$に行列

$\displaystyle M^{(1)} = \left(\begin{array}{rrrr}
1 & 0 & 0 & 0\\
-m_{2,1} & 1 & 0 & 0\\
-m_{3,1} & 0 & 1 & 0\\
-m_{4,1} & 0 & 0 & 1
\end{array}\right)$

をかけることと同じです.この行列のことをGaussの第1変換行列(first Gaussian transformation matrix)という.次に行った行基本変形 $-4R_{2} + R_{3} \to R_{3}$, $3R_{2}+R_{4} \to R_{4}$$A^{(2)}$に対してであり,Gaussの第2変換行列$M^{(2)}$

$\displaystyle M^{(2)} = \left(\begin{array}{rrrr}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & -m_{3,2} & 1 & 0\\
0 & -m_{4,2} & 0 & 1
\end{array}\right)$

となる.

つまり,

$\displaystyle U = A^{(3)} = M^{(2)}A^{(2)} = M^{(2)}M^{(1)}A^{(1)} = M^{(2)}M^{(1)}A$

より, $L = (M^{(1)})^{-1} (M^{(2)})^{-1}$となります.ここで, $(M^{(1)})^{-1} = L^{(1)},(M^{(2)})^{-1} = L^{(2)}$とおくと, $L = L^{(1)}L^{(2)}$と表せます. $\det M^{(1)} = \det M^{(2)} = 1$より,

$\displaystyle L^{(1)} = (M^{(1)})^{-1} = \left(\begin{array}{rrrr}
1 & 0 & 0 & ...
...1} & 1 & 0 & 0\\
m_{3,1} & 0 & 1 & 0\\
m_{4,1} & 0 & 0 & 1
\end{array}\right)$

$\displaystyle L^{(2)} = (M^{(2)})^{-1} = \left(\begin{array}{rrrr}
1 & 0 & 0 & ...
...
0 & 1 & 0 & 0\\
0 & m_{3,2} & 1 & 0\\
0 & m_{4,2} & 0 & 1
\end{array}\right)$

となる.よって

$\displaystyle L = L^{(1)}L^{(2)} = \left(\begin{array}{rrrr}
1 & 0 & 0 & 0\\
m...
...& 0 & 0\\
2 & 1 & 0 & 0\\
3 & 4 & 1 & 0\\
-1 & -3 & 0 & 1
\end{array}\right)$

となる.$LU$分解の行列$L$の対角成分は全て1であることに気付きます. これを一般化すると

定理 2..12   行の入れ替えを行わずに,行列$A$が上三角行列$U$に変形できるならば,行列$A$は下三角行列$L$を用いて$A = LU$に分解できます. ここで, $m_{ji} = a_{ji}^{(i)}/a_{ii}^{(i)}$,

$\displaystyle U = \left(\begin{array}{cccccc}
a_{11}^{(1)} & a_{12}^{(1)} & \cd...
...n}^{(n-1)}\\
0 & \cdots & \cdot & \cdots & 0 & a_{nn}^{(n)}
\end{array}\right)$

$\displaystyle L = \left(\begin{array}{cccccc}
1 & 0 & \cdots & \cdots & \cdots ...
... & & \ddots & 0\\
m_{n,1} & \cdots & \cdot & \cdots & 0 & 1
\end{array}\right)$

演習問題2-7

1. 次の連立1次方程式を解け.

$\left(\begin{array}{rrr}
1 &0&0\\
2&1&0\\
-1&0&1
\end{array}\right)\left(...
...\end{array}\right) = \left(\begin{array}{r}
2\\
-1\\
1
\end{array}\right)$

2. 次の行列を$LU$分解せよ.

(a) $\left(\begin{array}{rrr}
2&-1&1\\
3&3&9\\
3&3&5
\end{array}\right)$

(b) $\left(\begin{array}{rrrr}
2&0&0&0\\
1&1.5&0&0\\
0&-3&0.5&0\\
2&-2&1&1
\end{array}\right)$