D..5.1 LU 分解

最初に二つの言葉を定義する。

行列 $ L=(\ell_{ij})$ 下三角行列 (lower triangluar matrix) であるとは、対角線の上にある成分がすべて 0 である、つまり

$\displaystyle i>j\quad\Then\quad \ell_{ij}=0
$

が成り立つことと定義する。

同様に、 $ U=(u_{ij})$ 上三角行列 (upper triangular matrix) であるとは、 対角線の下にある成分がすべて 0 である、つまり

$\displaystyle i<j\quad\Then\quad u_{ij}=0
$

が成り立つことと定義する。

目で見えるように書くと

$\displaystyle L=
\left(
\begin{array}{ccccc}
\ell_{11} & 0 & \cdots&\cdots &...
... & u_{2n}\\
\vdots & 0 & \ddots & \\
0 & 0 & & u_{nn}
\end{array} \right)
$

ということである。

LU 分解
行列 $ A$ に対して、

$\displaystyle A = L U
$

を満たす下三角行列 $ L$ と上三角行列 $ U$ を求めることを (これはいつもできるとは限らない -- 後述)、 $ A$ LU 分解すると呼ぶ。

Gauss の消去法の前進消去段階では、 係数行列に行に関する基本変形を施して上三角行列 (それを $ U$ とおく) に 変形したが、 行に関する基本変形は、基本行列を左からかけることで表現できる。 Gauss の消去法では、これら基本行列はすべて正則な下三角行列である。 そこで、この変形は

$\displaystyle L_k \cdots L_2 L_1 A = U$   $\displaystyle \mbox{($L_j$ は正則な下三角行列, $U$ は上三角行列)}$

とかける。これから

$\displaystyle A={L_1}^{-1}{L_2}^{-1}\cdots {L_k}^{-1}U
$

となるが、 $ L:={L_1}^{-1}{L_2}^{-1}\cdots {L_k}^{-1}$ は実は下三角行列である。 これは次の補題から分かる。

\begin{jlemma}\upshape
\begin{enumerate}[(1)]
\item
下三角行列全体は...
...行列全体
は乗法について群をなす)。
\end{enumerate}\end{jlemma}

さて、それでは Gauss の消去法はいつでも出来るかというと、 (掃き出し法との類推ですぐ分かるように) 対角成分に 0 が現われたらダメになるわけである。 この場合は、行を適当に交換することで消去が出来るようになる。

\begin{jproposition}\upshape
$A$ を $n$ 次正則行列とする。
\begin{e...
...}
P A=L U
\end{displaymath}が成り立つ。
\end{enumerate}\end{jproposition}

正則行列 $ A$ の LU 分解はたとえ存在しても一意ではないが、 $ A$

$\displaystyle A = L D U\quad
($$\displaystyle \mbox{$L$ は対角成分が $1$ の下三角行列、
$U$ は対角成分が $1$ の上三角行列、
$D$ は対角行列}$$\displaystyle )
$

の形に分解する LDU 分解は一意である。

桂田 祐史
2017-06-19