LU 分解(前編) - Red cat の数学よもやま話

正則行列の LU 分解(その 1)

$A=(a_{ij})$ を n 次正則行列とする。このとき、 $a_{1j}$ の中で 0 でないものが少なくとも一つ存在するので、A に右から置換行列 $P_1$ を掛けて、一般性を失うことなく $a_{11}\neq 0$ として良い。そこで
$M_1=\left(\begin{array}1&0&0&\dots&0\\-m_{21}&1&0&\dots&0\\-m_{31}&0&1$\ddots&\ddots&\vdots\\\vdots&\vdots&\ddots&1&0\\-m_{n1}&0&\dots&0&1\end{array}\right)$
とおく。ただし $m_{i1}=\frac{a_{i1}}{a_{11}}$ である。すると
$M_1AP_1=\left(\begin{array}a_{11}&*&\dots&*\\0&*&\dots&*\\\vdots&\vdots&&\vdots\\0&*&\dots&*\end{array}\right)$
となるので、この行列から 1 行目と 1 列目を除いた (n - 1) 次行列に対して、帰納的に同じ手順を繰り返すと、対角成分が 1 のある下三角行列 M と置換行列 P があって
$MAP=U$
と出来る。ただし U は対角成分が 0 でない上三角行列。 $L=M^{-1}$ はやはり対角成分が 1 の下三角行列だから、結局
$AP=LU$
と下三角行列と上三角行列の積に分解できたことになる。これを正則行列の LU 分解という。P を固定すれば、この分解は一意であることは簡単に証明できる。実際
$AP=LU=L_1U_1$
とすれば $L_1^{-1}L = U_1U^{-1}$ であり、左辺は下三角行列、右辺は上三角行列だから、両辺は対角行列でなければならない。特に左辺は対角成分が 1 だから単位行列でなければならず、このことから $U_1=U$ を得る。したがって $L_1=L$ も成り立つ。

正則行列の LU 分解(その 2)

$A=(a_{ij})$ を n 次正則行列とする。このとき、 $a_{i1}$ の中で 0 でないものが少なくとも一つ存在するので、A に左から置換行列 $P_1$ を掛けて、一般性を失うことなく $a_{11}\neq 0$ として良い。そこで
$V_1=\left(\begin{array}1&-m_{12}&-m_{13}&\dots&-m_{1n}\\0&1&0&\dots&0\\0&0&1$\ddots&\ddots&\vdots\\\vdots&\vdots&\ddots&1&0\\0&0&\dots&0&1\end{array}\right)$
とおく。ただし $m_{1j}=\frac{a_{1j}}{a_{11}}$ である。すると
$P_1AV_1=\left(\begin{array}a_{11}&0&\dots&0\\*&*&\dots&*\\\vdots&\vdots&&\vdots\\*&*&\dots&*\end{array}\right)$
となるので、この行列から 1 行目と 1 列目を除いた (n - 1) 次行列に対して、帰納的に同じ手順を繰り返すと、対角成分が 1 のある上三角行列 V と置換行列 P があって
$PAV=L$
と出来る。ただし L は対角成分が 0 でない下三角行列。 $U=V^{-1}$ はやはり対角成分が 1 の下三角行列だから、結局
$PA=LU$
と下三角行列と上三角行列の積に分解できたことになる。これも正則行列の LU 分解という。P を固定すれば、この分解もやはり一意であることが上記と同様、簡単に証明できる。

正則行列の LDU 分解

以上の手順において、U ないし L の対角成分を対角成分とする対角行列 D を考えると、適当な置換行列 $P_1,P_2$ があって
$AP_1=LDU$
ないし
$P_2 A=LDU$
と出来ることが分かる。ただし L , U は各々下三角行列、上三角行列で、その対角成分は 1 である。これを正則行列の LDU 分解という。これもまた $P_1$ ないし $P_2$ を固定すると一意性が示せる。