行列のUL分解

Gaussの消去法は連立1次方程式を解くための主要な道具です.ここでは，拡大係数行列 $[A : {\bf b}]$ のピボットの乗数から，行列 $A$

を下三角行列

と上三角行列

の積

で表す方法を学びます.

では，どうやって $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の第２変換行列 $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$ の対角成分は全て１であることに気付きます. これを一般化すると

定理 2..12 行の入れ替えを行わずに，行列が上三角行列に変形できるならば，行列は下三角行列を用いてに分解できます. ここで， $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)$