LU分解とは?   ~具体例と必要十分条件 ~

LU分解とは?
  正方行列 $A$ を下三角行列
上三角行列
との積によって、
LU分解
と表わすことをLU分解 (lower–upper (LU) decomposition) という。
具体例と補足
  $3 \times 3$ の行列
をLU分解すると、
LU分解の例
となる (導出方法は こちらを参考) 。
補足1:
  当サイトでは、 下三角行列の対角成分が $1$ である LU 分解を紹介しているが、 そうではなく、 上三角行列の対角成分を $1$ とする流儀や、 対角成分を $1$ に固定しない流儀もある。 どれを選んだとしても、本質的な議論に変わりはない。
補足2:
  どんな正方行列でも LU 分解できるわけではない。 「LU 分解の必要十分条件」を参考

計算方法:
  行列
LU 分解せよ。
解答例
  はじめに、
と置く。右辺を計算すると、
である。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列目から)順番に連鎖式に値が求まって行く。

具体例
  $3 \times 3$ の行列
をLU分解せよ。
解答例
 
と置く。 右辺の積を実行すると、
である。1行目から各成分ごとに表すと、
である。 第1式と第2式と第3式からそれぞれ
である。これらと第4式から $l_{21}$ が
と求まる。 続いて第5式から $u_{22}$ が
と求まる。 同じように第6式から $u_{23}$ が
と求まる。 続いて、 第7式から $l_{31}$ が
と求まり、 第8式から $l_{32}$ が
と求まる。 最期に 第9式から $u_{33}$ が
と求まる。 以上から、
を得る。

必要十分条件
  行列が LU分解可能であるための必要十分条件は、 全ての主座小行列の行列式が0でないことである (主座小行列については証明で定義を述べる)。
解答例
 
主座小行列とは?
  $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$ ではない。