解答例
はじめに、
と置く。右辺を計算すると、
である。1行目から各成分ごとに表すと、
である。
上から順に解いてゆく。
まず、第1式と第2式と第3式からそれぞれ
$u_{11}$ と $u_{12}$ と $u_{13}$ が求まる。
続いて、$u_{11}$ が求まっていることから、
第4式によって $l_{21}$ が
と求まる。
これと既に
$u_{12}$ が求まっていることから、
第5式によって $u_{22}$ が
と求まる。同じように第6式から、
$u_{23}$ が
と求まる。続いて、
$u_{11}$ が求まっていることから、
第7式によって $l_{31}$ が
と求まる。
これと既に
$u_{12}$ と $u_{22}$ が求まっていることから、
第8式によって $l_{32}$ が
と求まる。
最期に $l_{31}$, $u_{13}$, $l_{32}$, $u_{23}$ が既に求まっていることから、
$u_{33}$ が
と求まる。
このように LU 分解された行列の各成分は1行目から(または1列目から)順番に連鎖式に値が求まって行く。
解答例
主座小行列とは?
$n$ 次正方行列を
と表すとき、
主座小行列 $A_{k}$ $(k=1,2, \cdots, n)$ とは、
のように $A$ の左上に位置する部分行列のことである。
英語では、leading principle minor という。
このような行列の
行列式が全て $0$ ではないこと、すなわち、
がLU分解可能なための必要十分条件である。
それを以下のように証明する。
「全ての主座小行列の行列式が $0$ でない」$\hspace{2mm} \Longrightarrow \hspace{2mm}$ 「LU分解可能」$\hspace{1mm}$ の証明
$k$ 成分ベクトル $\mathbf{c}_{k}$ と $\mathbf{b}$ を
$$
\tag{1}
$$
と定義し、
主座小行列 $A_{k}$ を係数行列とする連立一次方程式
$$
\tag{2}
$$
を考える。
$
|A_{k}| \neq 0
$
$(k=1,\cdots, n)$
と仮定すると、
$A_{k}$ は逆行列 $A_{k}^{-1}$ を持つので
(証明は
行列式が0でない行列は逆行列を持つを参考)、
$(2)$ により、
が成り立つ。
これは $(2)$ を満たす $\mathbf{c}_{k}$ が唯一つ存在することを表している。
そこで、
$\mathbf{c}_{k}$ の各成分を用いて、
$n$ 次の上三角行列 $C$ を
と定義する。
$A$ と $C$
の積は、
と表せるが、
この行列の第 $k$ 列は、
$(1)$ と $(2)$ から、
となる。
すなわち、
$0$ から $k-1$ 行の成分が $0$ であり、
$k$ 行の成分が $1$ である列ベクトルである。
これより $AC$ は
$$
\tag{3}
$$
と表される下三角行列になる。
ここで、
積の行列式の性質と
下三角行列の行列式は対角成分の積になること、
および
$(3)$ から
が成り立つ。
これより、$|C| \neq 0$ である。
したがって、$C$ には逆行列 $C^{-1}$ が存在し、
$(3)$ から
が成り立つ。
ここで、
$C$ は上三角行列であり、
上三角行列の逆行列もまた上三角行列であることから、
$C^{-1}$ は上三角行列である。
すなわち、$C^{-1}$ は
と表される行列である。
したがって、$A$ を
$$
\tag{4}
$$
と表すことができる。
このように、行列 $A$ は下三角行列と上三角行列の積に分解される。
最後に、
$(4)$ の右辺の上三角行列 $C^{-1}$ の対角成分が $0$ でないこと証明する。
$C^{-1}$ は逆行列 $C$ を持つので、
$C^{-1}$ の行列式は 0 でない
(
逆行列を持つ行列の行列式は 0 でないを参考)。
すなわち、
が成立する。
一方で、
$C^{-1}$ は上三角行列であるので、
行列式は対角成分の積に等しい。
すなわち、
が成立する。
これより、
$C^{-1}$ の個々の対角成分は 0 にならない。
すなわち、
が成立する。
以上から、
行列 $A$ は
(対角成分が$0$でない)下三角行列と上三角行列の積に分解できることが示された。
「LU分解可能」$\hspace{5mm} \Longrightarrow \hspace{5mm}$「全ての主座小行列の行列式が $0$ でない 」 の証明
行列 $A$ が
$$
\tag{5}
$$
とLU分解できるとする。
ここで、$L$ は
と表される下三角行列であり、
$U$ は
と表される上三角行列である。
また $U$ の対角成分は $0$ ではない。
$L$ と $U$ の各成分をそれぞれ $l_{ij}$, $u_{ij}$ と表すと、
$A$ の 各成分 $a_{st}$ は
$(5)$ から、
$$
\tag{6}
$$
と表せる。
ここで、
$L$ が下三角行列であり、
$U$ が上三角行列であることから、
$$
\tag{7}
$$
が成り立つ。
これを踏まえて
$A$ の $k$ 行 $k$ 列成分よりも左上にある成分に着目する。
すなわち、
を満たす $a_{st}$ に着目する。
このような $s$ と $t$ に対しては、
$(7)$ から
が成立するので、
$(6)$ は第 $k$ 項までの和のみによって表される。
すなわち、
が表される。
この式は
$A$ の $k$ 行 $k$ 列より左上にある各成分は、
$L$ の $k$ 行 $k$ 列より左上にある成分と、
$U$ の $k$ 行 $k$ 列より左上にある成分の積によって表されることを意味している。
すなわち、
$$
\tag{8}
$$
が成り立つことを意味している。
左辺は$A$ の主座小行列であり、
右辺は$L$ の主座小行列と $U$ の主座小行列の積になっている。
そこで、
それぞれの主座小行列を
$$
\tag{9}
$$
と表すことにすると、
$(8)$ は、
と表され、
その行列式は、
である。
ここで、
積の行列式の性質を用いた。
$L_{k}$ と $U_{k}$ がそれぞれ下三角行列と上三角行列であることから、
行列式は対角成分の積に等しい。
よって、
$(9)$ から
である。
これらより、
である。
一方で、
$u_{ii} \neq 0 $ $(i=1,2,\cdots,n)$ であるので、
である。
すなわち、
$A$ の任意の主座小行列の行列式は $0$ ではない。