LU分解を解説   ～具体例と必要十分条件 ～

具体例と補足
  $3 \times 3$ の行列 をLU分解すると、 となる (導出方法は こちらを参考) 。   当サイトでは、 下三角行列の対角成分が $1$ である LU 分解を紹介しているが、 そうではなく、 上三角行列の対角成分を $1$ とする流儀や、 対角成分を $1$ に固定しない流儀もある。 どれを選んだとしても、本質的な議論に変わりはない。   どんな正方行列でも 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列目から)順番に連鎖式に値が求まって行く。

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

解答例
 
主座小行列とは？
  $n$ 次正方行列を と表すとき、 主座小行列 $A_{k}$ $(k=1,2, \cdots, n)$ とは、 のように $A$ の左上に位置する部分行列のことである。 英語では、leading principle minor という。
  このような行列の行列式が全て $0$ ではないこと、すなわち、 がLU分解可能なための必要十分条件である。 それを以下のように証明する。
  $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$でない)下三角行列と上三角行列の積に分解できることが示された。
  行列 $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$ ではない。