本記事は数学の徹底解説シリーズに含まれます。
初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
LU分解と連立一次方程式
正方行列$A\in M_{n}(\mK)$に対し，下三角行列$L$と上三角行列$U$を用いた次の$LU$分解を考える。
A &= LU
\end{align}
ただし，$\mK$は複素数空間$\mC$または実数空間$\mR$を表し，$M_{n}(\mK)$は$\mK$上の$n$次正方行列全体の集合を表す。このとき，方程式$A\vx=\vb$は以下の手続きによって解くことができる。
- $A=LU$となる$LU$分解を求める
- $L\vy=\vb$の解$\vy$を求める（前進代入）
- $U\vx=\vy$の解$\vx$を求める（後退代入）
ただし，$\vx=[x_{1},\ldots,x_{n}]^{T}$，$\vy=[y_{1},\ldots,y_{n}]^{T}$とする。
$LU$分解の意義ともいえる定理です。
証明
まず，$A=LU$を代入します。
LU\vx &= \vb
\end{align}
$U\vx=\vy$とおくと，方程式$A\vx=\vb$を解くためには以下の二つの方程式を解けばよいことがわかります。
L\vy &= \vb \label{分解後_1}\\[0.7em]
U\vx &= \vy \label{分解後_2}
\end{align}
ただし，$\vy=[y_{1},\ldots,y_{n}]^{T}$とします。ここで，$L=(l_{i,j})^{n\times n}$，$U=(u_{i,j})^{n\times n}$とおきます。$L$が下三角行列であることに注意すると，式($\ref{分解後_1}$)は以下のように変形されます。
l_{1,1}y_{1} &= b_{1} \\[0.7em]
l_{2,1}y_{1}+l_{2,2}y_{2} &= b_{2}\\[0.7em]
&\vdots \\[0.7em]
\sum_{j=1}^{n}l_{n,j}y_{j} &= b_{n}
\end{align}
したがって，上から順に代入していくことで以下の逐次計算により式($\ref{分解後_1}$)の解を求めることができます。
y_{1} &= b_{1}/l_{1,1} \\[0.7em]
y_{2} &= (b_{2}-l_{2,1}y_{1})/l_{2,2} \\[0.7em]
&\vdots \\[0.7em]
y_{n} &= \left(b_{n}-\sum_{j=1}^{n-1}l_{n,j}y_{j}\right)/l_{n,n}
\end{align}
同様に，$U$が上三角行列であることに注意すると，以下の逐次計算により式($\ref{分解後_2}$)の解を求めることができます。
x_{n} &= y_{n}/u_{nn} \\[0.7em]
x_{n-1} &= (b_{n-1}-u_{n-1,n}y_{n})/u_{n-1,n-1} \\[0.7em]
&\vdots \\[0.7em]
x_{1} &= \left(b_{1}-\sum_{j=2}^{n}u_{1,j}y_{j}\right)/u_{1,1}
\end{align}
これらの逐次計算は，いずれも$O(n(n+1)/2)=O(n^{2})$で計算することができるため，$A$の$LU$分解が既知の場合は逆行列の計算$O(n^{2})$と同等の効率で連立一次方程式を解くことができます。連立方程式の解法の一つとしてよく利用されるGaussの消去法では，$\vb$が変わるたびにアルゴリズムを新しく走らせる必要があります。一方で，$LU$分解では一度$A$の$LU$分解を求めてしまえば，あとは前進消去と後退消去を計算するだけで済むという利点があります。
Gaussの消去法の計算量も$O(n^{3})$であり，$LU$分解の見つけ方は本質的にGaussの消去法と同等であることから，$LU$分解を見つけるための計算量は$O(n^{3})$となります。ゆえに，$LU$分解の旨味は同じ係数行列$A$に対する連立一次方程式を複数回解く場合に発揮されるといえます。
コメント