行列のLU分解

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

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

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

より係数行列は

$${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}$を行うと

$${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}$を行うと

$${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)}$に行列

$$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の第２変換行列$M^{(2)}$は

$$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)$$

となる.

つまり，

$$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$より，

$$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)$$

$$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)$$

となる.よって

$$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$の対角成分は全て１であることに気付きます. これを一般化すると

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

$$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)$$

$$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)$