Juliaと遊ぶ線形代数(6) LU分解とガウス消去法

LU分解は、正方行列を下三角行列と上三角行列の積に分解する方法です。

LU分解を利用すれば、連立一次方程式の計算をさらに効率化できます。

この記事は「LU分解」についてまとめます。

この記事がカバーする内容

LU分解とは何か
なぜLU分解が計算を効率化するのか
LU分解とガウス消去法にどんな違いがあるのか

LU分解

LU分解(LU decomposition)は

$$A=LU$$

に分解する方法です。

$A$は正方行列(Square matrix)、$L$は下三角行列(Lower triangular matrix)、$U$は上三角行列(Upper triangular matrix)です。

$A$がn元連立一次方程式の係数行列とすると、それぞれの行列は

$A = \begin{bmatrix}
a_{11} & a_{12} & a_{13} & \cdots & a_{1n} \\
a_{21} & a_{22} & a_{23} & \cdots & a_{2n} \\
a_{31} & a_{32} & a_{33}&\cdots & a_{3n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n1} & a_{n2} & a_{n3} &\cdots & a_{nn}
\end{bmatrix}$

$L = \begin{bmatrix}
1 & 0 & 0 &\cdots & 0 \\
l_{21} & 1 & 0 &\cdots & 0 \\
l_{31} & l_{32} & 1 &\cdots & 0 \\
\vdots & \vdots & \vdots &\ddots & \vdots \\
l_{n1} & l_{n2} & l_{n3} & \cdots & 1
\end{bmatrix}$

$U = \begin{bmatrix}
u_{11} & u_{12} & u_{13} &\cdots & u_{1n} \\
0 & u_{22} & u_{23} &\cdots & u_{2n} \\
0 & 0 & u_{33} &\cdots & u_{3n} \\
\vdots & \vdots & \vdots &\ddots & \vdots \\
0 & 0 & 0 & \cdots & u_{nn}
\end{bmatrix}$

です。$L$の対角要素を１とおきます。

LU分解は1948年にアラン・マシスン・チューリング(Alan Mathison Turing)に考案されました。アラン・チューリングは、コンピュータの基礎・原理を築いた方です。アラン・チューリングがどんな人か興味があれば「映画: イミテーションゲーム」がオススメです。

LU分解を使った計算

$A\boldsymbol{x}=\boldsymbol{b}$を計算するために、LU分解をどのように利用するんでしょうか？

LU分解を使ったステップを書き出してみます。

ステップ

$A$をLU分解する
$$A\boldsymbol{x}=LU\boldsymbol{x}$$
$U\boldsymbol{x}=\boldsymbol{y}$とおく
$$\begin{eqnarray}L(U\boldsymbol{x})&=&L\boldsymbol{y}\\
&=&\boldsymbol{b}\end{eqnarray}$$
$L\boldsymbol{y}=\boldsymbol{b}$を使って$\boldsymbol{y}$を解く
$U\boldsymbol{x}=\boldsymbol{y}$を使って$\boldsymbol{x}$を解く

$\boldsymbol{x} =\begin{bmatrix}x_1\\x_2\\x_3\\\vdots\\x_n\end{bmatrix} \quad
\boldsymbol{y} =\begin{bmatrix}y_1\\y_2\\y_3\\\vdots\\y_n\end{bmatrix} \quad
\boldsymbol{b} =\begin{bmatrix}b_1\\b_2\\b_3\\\vdots\\b_n\end{bmatrix} \quad$とおきます。

まず、$L\boldsymbol{y} = \boldsymbol{b}$は、

$$\begin{bmatrix}
1 & 0 & 0 &\cdots & 0 \\
l_{21} & 1 & 0 &\cdots & 0 \\
l_{31} & l_{32} & 1 &\cdots & 0 \\
\vdots & \vdots & \vdots &\ddots & \vdots \\
l_{n1} & l_{n2} & l_{n3} & \cdots & 1
\end{bmatrix}
\begin{bmatrix}y_1\\y_2\\y_3\\\vdots\\y_n\end{bmatrix}=\begin{bmatrix}b_1\\b_2\\b_3\\\vdots\\b_n\end{bmatrix}$$

です。これを$y_1$から$y_n$の順に解きます。

この操作を前進代入と呼びます。

その後、$U\boldsymbol{x}=\boldsymbol{y}$より

$$\begin{bmatrix}
u_{11} & u_{12} & u_{13} &\cdots & u_{1n} \\
0 & u_{22} & u_{23} &\cdots & u_{2n} \\
0 & 0 & u_{33} &\cdots & u_{3n} \\
\vdots & \vdots & \vdots &\ddots & \vdots \\
0 & 0 & 0 & \cdots & u_{nn}
\end{bmatrix}
\begin{bmatrix}x_1\\x_2\\x_3\\\vdots\\x_n\end{bmatrix}=
\begin{bmatrix}y_1\\y_2\\y_3\\\vdots\\y_n\end{bmatrix}$$

です。$x_n$から$x_1$の順に解きます。

この操作を後退代入と呼びます。

この操作によって、$\boldsymbol{x}$が求められました。