LU分解の幾何的解釈

はじめに

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

LU分解の定義

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

\begin{align} \begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix} = \begin{pmatrix} l_{11} & 0 & 0 \\ l_{21} & l_{22} & 0 \\ l_{31} & l_{32} & l_{33} \end{pmatrix} \begin{pmatrix} u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \end{pmatrix} \end{align}

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

\begin{align} \begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix} = \begin{pmatrix} l_{11} & 0 & 0 \\ l_{21} & l_{22} & 0 \\ l_{31} & l_{32} & l_{33} \end{pmatrix} \begin{pmatrix} 1 & u_{12} & u_{13} \\ 0 & 1 & u_{23} \\ 0 & 0 & 1 \end{pmatrix} \end{align}

LU分解の幾何的解釈

行列$A$の列ベクトル$a_1, ..., a_n$と行列$L$の列ベクトル$l_1, ..., l_n$を考える。

\begin{align} \begin{pmatrix} a_1 & a_2 & a_3 \end{pmatrix} = \begin{pmatrix} l_1 & l_2 & l_3 \end{pmatrix} \begin{pmatrix} 1 & u_{12} & u_{13} \\ 0 & 1 & u_{23} \\ 0 & 0 & 1 \end{pmatrix} \end{align}

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

\begin{align} 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{align}

また、線形結合に使うベクトル$l_i$は、$i=1$では$\mathbb{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軸である。

ベクトル$a_1, a_2, a_3$

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

ベクトル$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）。

ベクトル$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）。

ベクトル$l_3$

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

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

付録

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