LU分解の幾何的解釈

はじめに

本記事では、LU分解の幾何的な解釈を紹介する。また、LU分解後の行列 $L$ の対角成分についての性質を幾何的に証明する。

LU分解の定義

行列 $A \in R^{n \times n}$ のLU分解とは、 $A = L U$ となる下三角行列 $L \in R^{n \times n}$ と上三角行列 $U \in R^{n \times n}$ を求めることである。

$\begin{array}{r} (\begin{array}{c} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array}) = (\begin{array}{c} l_{11} & 0 & 0 \\ l_{21} & l_{22} & 0 \\ l_{31} & l_{32} & l_{33} \end{array}) (\begin{array}{c} u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \end{array}) \end{array}$

このような行列 $L, U$ は無数に存在するが、行列 $L, U$ のどちらか一方の対角成分を $1$ に固定すると、このような行列は一意になる。本記事では、行列 $U$ の対角成分を $1$ に固定する。

$\begin{array}{r} (\begin{array}{c} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array}) = (\begin{array}{c} l_{11} & 0 & 0 \\ l_{21} & l_{22} & 0 \\ l_{31} & l_{32} & l_{33} \end{array}) (\begin{array}{c} 1 & u_{12} & u_{13} \\ 0 & 1 & u_{23} \\ 0 & 0 & 1 \end{array}) \end{array}$

LU分解の幾何的解釈

行列 $A$ の列ベクトル $a_{1}, . . ., a_{n}$ と行列 $L$ の列ベクトル $l_{1}, . . ., l_{n}$ を考える。

$\begin{array}{r} (\begin{array}{c} a_{1} & a_{2} & a_{3} \end{array}) = (\begin{array}{c} l_{1} & l_{2} & l_{3} \end{array}) (\begin{array}{c} 1 & u_{12} & u_{13} \\ 0 & 1 & u_{23} \\ 0 & 0 & 1 \end{array}) \end{array}$

このとき、ベクトル $a_{i}$ はベクトル $l_{1}, . . ., l_{n}$ の線形結合で表せる。ただし、すべてのベクトル $l_{1}, . . ., l_{n}$ を使えるわけではなく、添え字 $i$ のベクトル $a_{i}$ では、ベクトル $l_{1}, . . ., l_{i}$ しか使えない。添え字 $i$ が大きくなるにしたがって、使えるベクトルが一つずつ増えていく。

$\begin{aligned} a_{1} & = l_{1} \\ a_{2} & = u_{12} l_{1} + l_{2} \\ a_{3} & = u_{13} l_{1} + u_{23} l_{2} + l_{3} \end{aligned}$

また、線形結合に使うベクトル $l_{i}$ は、 $i = 1$ では $R^{n}$ 空間から選べるが、添え字 $i$ が大きくなるにしたがって、存在範囲が狭まっていく。例えば、 $n = 3$ では、ベクトル $l_{1}$ はxyz空間、ベクトル $l_{2}$ はyz平面、ベクトル $l_{3}$ はz直線から選ぶ。

一般に、 $n$ 次元空間に線形独立な $n$ 本のベクトルがあるとき、任意のベクトルはそれらの線形結合で表せる。LU分解とは、使用できるベクトルが制限されている下で、すべてのベクトル $a_{1}, . . ., a_{n}$ を線形結合で表せるベクトル $l_{1}, . . ., l_{n}$ とその係数 $U$ を求めることであると言える。

では、LU分解の流れを幾何的に解釈していく。以下では、 $n = 3$ での例を示す。図1に説明に使用するベクトル $a_{1}, . . ., a_{n}$ を示す。ここで、青色がx軸、緑色がy軸、赤色がz軸である。

ベクトル!FORMULA[40][-1334035532][0] ベクトル $a_{1}, a_{2}, a_{3}$

まず、ベクトル $a_{1}$ を線形結合で表せるように、ベクトル $l_{1}$ を選ぶ。 $l_{1} = a_{1}$ であり、ベクトル $l_{1}$ はxyz空間上にあるため、ベクトル $a_{1}$ をベクトル $l_{1}$ （青色）として選べばよい（図2）。

ベクトル!FORMULA[47][36557034][0] ベクトル $l_{1}$

次に、ベクトル $a_{2}$ を線形結合で表せるように、ベクトル $l_{2}$ を選ぶ。 $l_{2} = a_{2} - u_{12} l_{1}$ であり、ベクトル $l_{2}$ はyz平面上にあるため、ベクトル $a_{2}$ からベクトル $l_{1}$ をyz平面と交差するように伸ばすと、交点がベクトル $l_{2}$ （緑色）となる（図3）。

ベクトル!FORMULA[55][36557065][0] ベクトル $l_{2}$

最後に、ベクトル $a_{3}$ を線形結合で表せるように、ベクトル $l_{3}$ を選ぶ。 $l_{3} = a_{3} - u_{13} l_{1} - u_{23} l_{2}$ であり、ベクトル $l_{3}$ はz直線上にあるため、ベクトル $a_{3}$ からベクトル $l_{1}, l_{2}$ をz直線と交差するように伸ばすと、交点がベクトル $l_{3}$ （赤色）となる（図4）。

ベクトル!FORMULA[63][36557096][0] ベクトル $l_{3}$

行列 $L$ の対角成分の性質

行列 $L$ の対角成分 $l_{i i} \in R$ について、以下の性質が成り立つ。ただし、行列 $A_{i} \in R^{i \times i}$ は、行列 $A$ から $1, . . ., i$ 行と $1, . . ., i$ 列を抜き出した行列である。

$\begin{array}{r} l_{i i} = \frac{\det (A_{i})}{\det (A_{i - 1})} \end{array}$

$n = 3, i = 3$ の場合で証明するが、一般の $n, i$ にも拡張できる。なお、以下の図は前節と同じ数値であるが、見やすいように見方を変えている。

まず、ベクトル $a_{1}, . . ., a_{i - 1}, a_{i}$ が作る平行体 $P_{1}$ を考える（図5）。

平行体!FORMULA[76][35722886][0] 平行体 $P_{1}$

次に、ベクトル $a_{1}, . . ., a_{i - 1}, l_{i}$ が作る平行体 $P_{2}$ を考える（図6）。

平行体!FORMULA[79][35722917][0] 平行体 $P_{2}$

そして、ベクトル $a_{1}, . . ., a_{i - 1}, e_{i}$ が作る平行体 $P_{3}$ 考える。ここで、ベクトル $e_{i}$ は、第 $i$ 成分が $1$ で、それ以外の成分が $0$ のベクトルである（図7）。

平行体!FORMULA[86][35722948][0] 平行体 $P_{3}$

ここで、平行体 $P_{2}$ は平行体 $P_{1}$ のベクトル $a_{i}$ を平行に移動したものであるため、平行体 $P_{1}$ の体積は平行体 $P_{2}$ の体積と等しい（図8）。

平行体!FORMULA[92][-1454011693][0]の体積平行体 $P_{1}, P_{2}$ の体積

また、平行体 $P_{2}$ は平行体 $P_{3}$ のベクトル $e_{i}$ を $l_{i i}$ 倍に伸ばしたものであるため、平行体 $P_{2}$ の体積は平行体 $P_{3}$ の体積の $l_{i i}$ 倍である（図9）。

平行体!FORMULA[100][-566507981][0]の体積平行体 $P_{2}, P_{3}$ の体積

以上より、

平行体 $P_{1}$ の体積＝平行体 $P_{2}$ の体積＝ $l_{i i} \times$ 平行体 $P_{3}$ の体積、

である（図10）。

平行体!FORMULA[105][-668025147][0]の体積平行体 $P_{1}, P_{2}, P_{3}$ の体積

平行体の体積は、それを作るベクトルを並べた行列の行列式に等しい。ここで、ベクトル $a_{1}, . . ., a_{n - 1}, e_{n}$ を並べた行列の行列式（平行体 $P_{3}$ の体積）は、行列 $A_{n - 1}$ の行列式に等しいことに注意する。 $\det (A_{n}) = l_{i i} \det (A_{n - 1})$ であり、 $l_{i i} = \det (A_{n}) / \det (A_{n - 1})$ が成り立つ。

付録

定理1を代数的に証明する。

$\begin{array}{r} A_{i} = L_{i} U_{i} \end{array}$

$\begin{aligned} \det (L_{i}) & = l_{11} \times \dots \times l_{i i} \\ \det (U_{i}) & = 1 \end{aligned}$

$\begin{aligned} \det (A_{i}) & = \det (L_{i} U_{i}) \\ = \det (L_{i}) \det (U_{i}) \\ = l_{11} \times \dots \times l_{(i - 1) (i - 1)} \times l_{i i} \\ = \det (A_{i - 1}) \times l_{i i} \end{aligned}$