本記事は数学の徹底解説シリーズに含まれます。
初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
LU分解の求め方
正方行列$A\in M_{n}(\mK)$に対し，下三角行列$L$と上三角行列$U$を用いた次の$LU$分解を考える。
A &= LU
\end{align}
ただし，$\mK$は複素数空間$\mC$または実数空間$\mR$を表し，$M_{n}(\mK)$は$\mK$上の$n$次行列全体の集合を表す。このとき，具体的な$L$と$U$は以下の二つの方法によって計算することができる。
- 基本変形行列の逆行列
- 愚直に計算
ただし，$LU$分解の一意性より下三角行列$L$の対角成分は$1$とする。
$U$の対角成分を$1$としても一意に解を求めることが可能です。
証明
以下では，二つの方法それぞれに関して具体的な例を用いて$LU$分解の求め方を説明していきます。
基本変形行列の逆行列
$LU$分解はGaussの消去法を行列を用いて表現した概念と捉えられます。実際に，LU分解と連立一次方程式で説明した上三角行列$L$の逐次計算は前進消去に，下三角行列$U$の逐次計算は後進消去に対応しています。
逆にいえば，Gaussの消去法が$LU$分解の具体的な形を求めるための一つのアルゴリズムとなっているということです。Gaussの消去法とは，分解対象の行列$A$に対して行基本変形を施すことで三角行列となるように掃き出すアルゴリズムのことを指します。行基本変形は基本行列を左から掛けることに相当しますので，Gaussの消去法により$p$回の行基本変形で$A$が上三角行列$U$になったとき，$i$回目の行基本変形を表す行列を$L_{p}$とおくと，
L_{p}\cdots L_{1}A &= U\label{Lのタネ}
\end{align}
となります。行基本変形を表す行列$E_{i}$はすべて正則ですので，その積も正則になります。ここで，各行基本変形を表す行列$L_{i}$の逆行列は，基本操作の方向を反転させたものであるため，簡単に求めることができます。これは，ある基本変形と逆の変形を二回連続で行うと恒等変換になることに起因しています。したがって，$L_{p}\cdots L_{1}$の逆行列を$L$とおくと，$L$はつぎのように簡単に求められます。
L &= \left(L_{p}\cdots L_{1}\right)^{-1} = L_{1}^{-1}\cdots L_{p}^{-1}
\end{align}
この$L$を式($\ref{Lのタネ}$)の左から掛けることにより，$A=LU$が導かれます。同様に，列基本変形は基本行列を右から掛けることに相当しますので，Gaussの消去法により$q$回の行基本変形で$A$が対角成分が先ほど求めた下三角行列$L$になったとき，$j$回目の列基本変形を表す行列を$U_{j}$とおくと，
AU_{1}\cdots U_{q} &= L\label{Uのタネ}
\end{align}
となります。列基本変形を表す行列$U_{i}$はすべて正則ですので，その積も正則になります。ここで，各列基本変形を表す行列$U_{j}$の逆行列は，基本操作の方向を反転させたものであるため，簡単に求めることができます。これは，ある基本変形と逆の変形を二回連続で行うと恒等変換になることに起因しています。したがって，$U_{1}\cdots U_{q}$の逆行列を$U$とおくと，$U$はつぎのように簡単に求められます。
U &= \left(U_{1}\cdots U_{q}\right)^{-1} = U_{q}^{-1}\cdots U_{1}^{-1}
\end{align}
この$U$を式($\ref{Uのタネ}$)の左から掛けることにより，$A=LU$が導かれます。以上をまとめると，$L$と$U$は以下のように求められます。
L &= L_{1}^{-1}\cdots L_{p}^{-1} \label{L}\\[0.7em]
U &= U_{q}^{-1}\cdots U_{1}^{-1} \label{U}
\end{align}
実際には，$L_{1},\ldots,L_{p}$を求める過程で$U$が，$U_{1},\ldots,U_{q}$を求める過程で$L$が求められていますので，掃き出しを行うのはどちらか一方だけで十分です。しかし，どちらを掃き出し法で求めるべきなのかは，どちらの三角行列が対角成分が$1$の単三角行列として指定されているかに依存します。
というのも，$LU$分解には$L$の対角成分を$1$にするケースと$U$の対角成分を$1$にするケースが混在します。式($\ref{L}$)に従って$L$を計算すると，$L$は対角成分が$1$とは制限しない基本変形行列を用いた積として表されます。対角成分を基本変形でいじらないということは，$L_{1},\ldots,L_{q}$の対角成分は常に$1$となりますので，その逆操作に相当する逆行列の対角成分も常に$1$となります。したがって，式($\ref{L}$)に基づいて$L$を計算すると$L$の対角成分は$1$になります。同様に，式($\ref{U}$)に基づいて$U$を計算すると$U$の対角成分は$1$になります。このことから，$L$の対角要素が$1$であると指定されているケースでは，式($\ref{L}$)に基づいて$L$を計算した後に，式($\ref{Uのタネ}$)で求めた$L$と一致するように$U_{1},\ldots,U_{q}$を定め，その上で式($\ref{U}$)に基づいて$U$を計算します。逆に，$U$の対角要素が$1$であると指定されているケースでは，式($\ref{U}$)に基づいて$U$を計算した後に，式($\ref{Lのタネ}$)で求めた$U$と一致するように$L_{1},\ldots,L_{q}$を定め，その上で式($\ref{L}$)に基づいて$L$を計算します。
具体例を用いて確認してみましょう。次の行列$A$を$LU$分解したいとします。
A &=
\begin{bmatrix}
2 & 3 & -1 \\
4 & 4 & -3 \\
-2 & 3 & -1
\end{bmatrix}
\end{align}
行基本変形を用いて$A$が上三角行列になるように掃き出します。
\begin{bmatrix}
2 & 3 & -1 \\
4 & 4 & -3 \\
-2 & 3 & -1
\end{bmatrix}
&\longrarr
\begin{bmatrix}
2 & 3 & -1 \\
0 & -2 & -1 \\
0 & 6 & -2
\end{bmatrix}\\[0.7em]
&\longrarr
\begin{bmatrix}
2 & 3 & -1 \\
0 & -2 & -1 \\
0 & 0 & -5
\end{bmatrix}
\end{align}
したがって，$U$は以下のように求められました。
U &=
\begin{bmatrix}
2 & 3 & -1 \\
0 & -2 & -1 \\
0 & 0 & -5
\end{bmatrix}
\end{align}
同時に，$L_{1},L_{2}$は以下のようになります。
L_{1} &=
\begin{bmatrix}
1 & 0 & 0 \\
-2 & 1 & 0 \\
1 & 0 & 1
\end{bmatrix},\quad
L_{2} =
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 3 & 1
\end{bmatrix}
\end{align}
ここで，$L_{1},L_{2}$の逆の操作を表す逆行列を求めておきます。
L_{1}^{-1} &=
\begin{bmatrix}
1 & 0 & 0 \\
2 & 1 & 0 \\
-1 & 0 & 1
\end{bmatrix},\quad
L_{2}^{-1} =
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & -3 & 1
\end{bmatrix}
\end{align}
したがって，$L$は以下のように求められます。
L &= L_{1}^{-1}L_{2}^{-1}\\[0.7em]
&=
\begin{bmatrix}
1 & 0 & 0 \\
2 & 1 & 0 \\
-1 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & -3 & 1
\end{bmatrix}\\[0.7em]
&=
\begin{bmatrix}
1 & 0 & 0 \\
2 & 1 & 0 \\
-1 & -3 & 1
\end{bmatrix}
\end{align}
実際に，$LU$を計算すると$A$に戻ることが分かります。
LU &=
\begin{bmatrix}
1 & 0 & 0 \\
2 & 1 & 0 \\
-1 & -3 & 1
\end{bmatrix}
\begin{bmatrix}
2 & 3 & -1 \\
0 & -2 & -1 \\
0 & 0 & -5
\end{bmatrix}
=
\begin{bmatrix}
2 & 3 & -1 \\
4 & 4 & -3 \\
-2 & 3 & -1
\end{bmatrix}
= A
\end{align}
愚直に計算
$LU$分解を見つけるためのアルゴリズムとしては，愚直に計算する方法も考えられます。素朴に考えるのであれば，二つの$n\times n$行列の要素分だけ変数が存在しますので，$2n^{2}$次連立方程式となることが見込まれるのですが，実際には上三角行列や下三角行列であり要素の半分程度が$0$となるため，そこまで複雑ではありません。さらに，規則正しく$A$の一行目，一列目，二行目，二列目，…を基準に要素に関する連立方程式を解いていけば，要領よく解を求めることが可能です。
先ほど扱った行列$A$に対してこの方法を試してみましょう。ただし，$LU$分解の一意性を担保するため，下三角行列$L$の対角要素は$1$とします。
\begin{bmatrix}
2 & 3 & -1 \\
4 & 4 & -3 \\
-2 & 3 & -1
\end{bmatrix}
&=
\begin{bmatrix}
1 & 0 & 0 \\
l_{2,1} & 1 & 0 \\
l_{3,1} & l_{3,2} & 1
\end{bmatrix}
\begin{bmatrix}
u_{1,1} & u_{1,2} & u_{1,3} \\
0 & u_{2,2} & u_{2,3} \\
0 & 0 & u_{3,3}
\end{bmatrix}
\end{align}
$A$の一行目に着目すると，
u_{1,1} = 2,\quad u_{1,2} = 3,\quad u_{1,3} = -1
\end{align}
が分かります。次に，$A$の一列目に着目すると，
l_{2,1} = 2,\quad l_{3,1} = -1
\end{align}
が分かります。ここまでを可視化すると，
\begin{bmatrix}
2 & 3 & -1 \\
4 & 4 & -3 \\
-2 & 3 & -1
\end{bmatrix}
&=
\begin{bmatrix}
1 & 0 & 0 \\
2 & 1 & 0 \\
-1 & l_{3,2} & 1
\end{bmatrix}
\begin{bmatrix}
2 & 3 & -1 \\
0 & u_{2,2} & u_{2,3} \\
0 & 0 & u_{3,3}
\end{bmatrix}
\end{align}
となります。次に，$A$の二行目に着目すると，
u_{2,2} = -2,\quad u_{2,3} = -1
\end{align}
が分かります。次に，$A$の二列目に着目すると，
l_{3,2} = -3
\end{align}
が分かります。ここまでを可視化すると，
\begin{bmatrix}
2 & 3 & -1 \\
4 & 4 & -3 \\
-2 & 3 & -1
\end{bmatrix}
&=
\begin{bmatrix}
1 & 0 & 0 \\
2 & 1 & 0 \\
-1 & -3 & 1
\end{bmatrix}
\begin{bmatrix}
2 & 3 & -1 \\
0 & -2 & -1 \\
0 & 0 & u_{3,3}
\end{bmatrix}
\end{align}
となります。最後に，$A$の三行目に着目すると，
u_{3,3} = -5
\end{align}
が分かります。以上より，$A$の$LU$分解が求められました。
\begin{bmatrix}
2 & 3 & -1 \\
4 & 4 & -3 \\
-2 & 3 & -1
\end{bmatrix}
&=
\begin{bmatrix}
1 & 0 & 0 \\
2 & 1 & 0 \\
-1 & -3 & 1
\end{bmatrix}
\begin{bmatrix}
2 & 3 & -1 \\
0 & -2 & -1 \\
0 & 0 & -5
\end{bmatrix}
\end{align}
コメント