2.4 LU分解の計算法

実は、Gauss の消去法は LU 分解を計算していることに相当する。 このことを理解すれば、LU 分解の計算法を知っていることになる。 Gauss の消去法が最後まで実行できるためには、 消去の過程で現れる対角成分が 0 にならないことが必要十分であるが、 この項では、それが常に満たされるとして議論する (その条件を吟味することは後の 2.7 で行う)。

Gauss の消去法では、 「行に関する基本変形」で係数行列を上三角行列に変形したが、 「行に関する基本変形」は基本行列を左からかけることに相当する (このことは基本変形を説明してある線形代数の教科書ならば、 必ず解説してあるはずであるが、 桂田 [4] の第4章にも書いておいた)。

$n$ 次正方行列 $A=(a_{ij})$ の $(k,k)$ 成分 $a_{kk}$ で $(i, k)$ 成分 ($i>k$) を掃き出すには、 第 $i$ 行から、 第 $k$ 行の $q_{ik}:=a_{ik}/a_{kk}$ 倍を引く、という操作をするわけだが、 これは

$${\cal L}_{ik}:= I-q_{ik}E_{ik} = \left( \begin{array}{ccccccc... ...{$k$行目} \\ \\ \longleftarrow\mbox{$i$行目} \\ \\ \\ \end{array}$$

を左からかけることで実現される (ここで $I$ は $n$ 次の単位行列, $E_{ik}$ は第 $(i, k)$ 成分のみ$1$ で、 他の成分は 0 であるような $n$ 次正方行列)。 すると、$(k,k)$ 成分 $a_{kk}$ で、 第 $k$ 列の $k$ 行目以降 ($(k+1,k)$, $(k+2,k)$, $\cdots$, $(n,k)$ 成分) を掃き出す操作は、

$${\cal L}_k:= {\cal L}_{n,k} \cdots {\cal L}_{k+2,k} {\cal L}_{k+1,k}$$

を左からかけることで実現されることが分かる。

後で逆行列が必要になるので調べておこう。 まず

$${\cal L}_{ik}^{-1} =I+q_{ik}E_{ik} = \left( \begin{array}{ccc... ...{$k$行目} \\ \\ \longleftarrow\mbox{$i$行目} \\ \\ \\ \end{array}$$

である。 これは計算で示すことも出来るし⁸、 行列の表す基本変形の意味から考えても明らかである。

次に

$${\cal L}_k^{-1} = {\cal L}_{k+1,k}^{-1} {\cal L}_{k+2,k}^{-1} \cd... ...} & & 1 \ & & \vdots & & & \ddots \ & & q_{n,k} & & & & 1 \end{array} \right)$$ (1)

である。これも基本変形の意味から明らかである。

上の操作 ( ${\cal L}_{k}$ を左からかける) を $k=1,2,\cdots,n-1$ の順に行うと、 $A$ の対角線よりも下の部分は掃き出されて、上三角行列になる:

$${\cal L}_{n-1}{\cal L}_{n-2}\cdots {\cal L}_2 {\cal L}_1 A=$$上三角行列$$=:U.$$

簡単のため

$${\cal L}:={\cal L}_{n-1}{\cal L}_{n-2}\cdots {\cal L}_2 {\cal L}_1$$

とおけば、

$${\cal L}A=U.$$ (2)

各 ${\cal L}_k$ が単位下三角行列であるから、${\cal L}$ も単位下三角行列である。 ゆえに ${\cal L}$ は正則で、 逆行列 $L:={\cal L}^{-1}$ ( $={\cal L}^{-1}_1{\cal L}^{-1}_2 \cdots{\cal L}^{-1}_{n-1}$) も単位下三角行列である。 ゆえに (2) に左から $L$ をかけると、

$$A=L U$$

となり、$A$ の LU 分解が得られた。

実はより具体的に

$$L= \left( \begin{array}{cccccc} 1 & &&&\bigzerou \ q_{21} & 1 & ... ...&\ddots &\ddots \ q_{n1} & q_{n2} & \cdots & q_{n,n-1} & 1 \end{array} \right)$$ (3)

であることが分かる (これをもっと前に持って来るのが良いと思うが、はてどうやろうか…)。

(3) (1) の証明と同様に基本変形の意味を考えても分かるが、 ここでは地道な計算で示してみよう。

各 $k$ に対して

$${\cal L}_1^{-1}\cdots{\cal L}_k^{-1} = \left( \begin{array... ...q_{n1} & \cdots & q_{n,k} & \bigzerol & & 1 \end{array}\right)$$

となることを帰納法で示す。

$k=1$ のとき成り立つことは明らかである (式 (1) から、 ${\cal L}_1^{-1}$ がこの形をしていることがすぐ分かる)。

次に $k$ のとき成立すると仮定する。

$${\cal L}_1^{-1}\cdots{\cal L}_k^{-1}{\cal L}_{k+1}^{-1} = \left( \begin{array}{ccc\vert cccc} 1 & & \bigzerou \ q_{21} &... ...rol & & \vdots & &\ddots \ & & & q_{n,k+1}&\bigzerol & & 1 \end{array} \right)$$

$$= \left( \begin{array}{cc} A & O \ C & I \end{array} \right) \le... ...nd{array} \right) = \left( \begin{array}{cc} A & O \ C & D \end{array} \right)$$

$$= \left( \begin{array}{ccc\vert cccc} 1 & & \bigzerou \ q_{21} &... ...\ q_{n1} & \cdots & q_{n,k} & q_{n,k+1} & \bigzerol & & 1 \end{array} \right).$$

これは $k+1$ のときも成立することを示している。 $\qedsymbol$