2.7.0.1 記号の約束

以下、行列 $A$ に対して、$A^{(j)}$ で、$j$ 次の主座小行列を表す:

$$A^{(j)} = \begin{pmatrix} a_{11} & \cdots & a_{1j} \\ \vdots & &\vdots\\ a_{j1} & \cdots & a_{jj} \end{pmatrix}.$$

蛇足ながら、数値計算言語の MATLAB では、 a という行列に対して、 a(1:j,1:j) という式で $j$ 次の主座小行列を表せる。

証明. 行列を $k$ 行, $k$ 列のところで線を引いてブロックわけする:

$$A= \left( \begin{array}{c\vert c} A^{(k)} & \mbox{\large$\ast$... ...st$} \\ \hline \mbox{\large$O$} & \mbox{\large$\ast$} \end{array} \right).$$

(${\cal L}$ の右上のブロック、 $U$ の左下のブロックは零行列ということを主張している。)

$${\cal L}A= \left( \begin{array}{c\vert c} {\cal L}^{(k)} & \mb... ...$} \\ \hline \mbox{\large$\ast$} & \mbox{\large$\ast$} \end{array} \right)$$

であるから、

$${\cal L}^{(k)}A^{(k)}=U^{(k)},\quad \det {\cal L}^{(k)}\det A^{(k)}=\det U^{(k)}.$$

正則 $A$ が LU 分解 $A=LU$ を持つとする。 $0\ne \det A=\det L\det U$ より、$L$ と $U$ も正則である。 $\det U=\dsp\prod_{i=1}^n u_{ii}$ より、 $u_{ii}\ne 0$ ( $i=1,\dots,n$). $L$ の逆行列を ${\cal L}$ とすると、 ${\cal L}$ は下三角で、 ${\cal L}A=U$ が成り立つから、前半を用いて、

$$\forall k\in\{1,\dots,n\}\quad \det {\cal L}^{(k)}\det A^{(k)}=\det U^{(k)} =\prod_{i=1}^k u_{ii}\ne 0.$$

これから $\det A^{(k)}\ne 0$. $\qedsymbol$ $\qedsymbol$

逆に $\det A^{(k)}\ne 0$ ( $k=1,\dots,n$) ならば $A$ は LU 分解できる ことを示すには、Gauss の消去法によって具体的に LU 分解を構成してみせる。

証明. $k$ についての帰納法による。 $k=1$ のとき、 $0\ne \det A^{(1)}=a_{11}$ より、 第 1 列の対角線より下を掃き出すことができる。実際

$${\cal L}:= \left( \begin{array}{cccc} 1 & & & \bigzerou \\ -... ...array} \right),\quad q_{j1}:=\frac{a_{j1}}{a_{11}}\quad\mbox{($2\le j\le n$)}$$

とおくと、

$${\cal L}A= \left( \begin{array}{c\vert cc} a_{11} & & \\ 0 & & \\ \vdots & \bigast & \\ 0 & & \end{array} \right).$$

ゆえに $k=1$ のとき確かに成り立つ。

$k=\ell$ のとき成り立つと仮定して、$k=\ell+1$ とする。 $A$ が $\det A^{(j)}\ne 0$ ( $1\le \forall j\le k$) を満たすと仮定する。 特に $\det A^{(j)}\ne 0$ ( $1\le\forall j\le \ell$) であり、 帰納法の仮定より Gauss の消去法の前進消去過程は $\ell$ 段まで実行できる。 すなわち行に関する基本変形を表す下三角の基本行列の積である 下三角行列 ${\cal L}$ が存在して、

$${\cal L}A= \left( \begin{array}{ccc\vert ccc} u_1 & & \bigast ... ...e & & & & & \\ & \bigzerol & & & A' & \\ & & & & & \end{array} \right).$$

これから

$${\cal L}^{(\ell+1)} A^{(\ell+1)} =\left({\cal L}A\right)^{(\ell+... ...l+1} \end{array} \right),\quad u_{\ell+1}:=\mbox{$A'$\ の $(1,1)$\ 成分}.$$

このとき

$$u_1 \cdots u_{\ell} u_{\ell+1} =\det\left({\cal L}^{(\ell+1)} A^... ... L}^{(\ell+1)}\det A^{(\ell+1)} =1\cdot\det A^{(\ell+1)} =\det A^{(\ell+1)}.$$

仮定より $\det A^{(\ell+1)}\ne 0$ であるから、 $u_{\ell+1}\ne 0$. ゆえに第 $(\ell+1)$ 列の対角線より下も掃き出すことができる。 すなわち Gauss の消去法の前進消去過程は $(\ell+1)$ 段まで実行できる。$\qedsymbol$ $\qedsymbol$

証明. 前半は補題 2.5 から明らか。 $A$ が正則であるならば、${\cal L}$ も正則であることに注意して、 $L:={\cal L}^{-1}$ とおけば $A=LU$. ${\cal L}$ は 単位下三角であるから $\det L^{(k)}=1$ であるので、 $\det A^{(k)}=\det U^{(k)}=\prod_{i=1}^k u_{ii}$. $\qedsymbol$ $\qedsymbol$

以上をまとめると、次の定理が得られる。

この定理の、簡単だが応用上重要な系として、次のものがある。

証明. よく知られているように、対称行列 $A$ が正値であるためには

$$\det A^{(k)}>0$$   $$\mbox{($k=1,\dots,n$)}$$

が成り立つことが必要十分である。これを思い出せば明らか。 $\qedsymbol$ $\qedsymbol$

なお、正値対称行列の LU 分解としては、 Cholesky 分解が重要である。 これについては、桂田 [1] などを見よ。

LU 分解の一意性についても片付けておこう。

証明. $A$ が正則であることから $U_1$ も正則である。 したがって

$$L_2^{-1} L_1=U_2 U_1^{-1}.$$

左辺は単位下三角行列の積であるから単位下三角行列であり、 右辺は上三角行列の積であるから上三角行列である。 ゆえにこの等式の両辺は、単位下三角行列かつ上三角行列であるので、 実は単位行列 $I$ に等しい。これから

$$L_1=L_2,\quad U_1=U_2$$

が得られる。 $\qedsymbol$ $\qedsymbol$

$$A= \left( \begin{array}{cc} A' & B' \\ C' & D' \end{array} ... ...1 & I \end{array} \right) \quad\mbox{($A'$, $L'$\ は $k$\ 次正方行列)}$$

とブロック分けすると

$${\cal L}_k\cdots{\cal L}_1 A= \left( \begin{array}{cc} L' A' & L' B' \\ \bigast_2 & \bigast_3 \end{array} \right).$$

これから

$$L' A'= \left( \begin{array}{ccc} u_{1} & & \bigast \\ &\ddots& \\ & & u_{k} \end{array} \right).$$

これは $A'$ の LU 分解となっているので

$$\det A'=u_1\cdots u_k. \qed$$

やり残し「任意の正則行列 $A$ に対して、 ある置換行列 $P$ が存在して、 $P A$ は LU 分解できる」を証明したい。