線形代数のキソ ... 三角化とLU分解

線形代数 ... 要するに行列計算についての簡単なメモ。

三角化

$ n $次正方行列の $ X $ があるとする。これに適当な正則行列$ P $を使って、

\[ P^{-1}  A  P  = \begin{pmatrix} a'_{11} & a'_{12} & \cdots & a'_{1n} \\ 0 & a_{22} & \cdots & a'_{2n} \\ \vdots & \vdots & & \vdots \\ 0 & 0 & \cdots & a'_{nn}  \end{pmatrix} \]

と、三角行列(上の場合は上三角行列)にすることを、三角化(上三角化)という。

これは、いわゆる固有値問題

\[ A \mathbf{x} = \lambda \mathbf{x}  \]

の解である、固有値と固有ベクトルを解くことで得ることができる。すなわち、$P$が固有ベクトルを(正規化して)並べたもので、三角化された行列の対角成分が、

\[ P^{-1}  A  P  = A' = \begin{pmatrix} \lambda_1 & a'_{12} & \cdots & a'_{1n} \\ 0 & \lambda_2 & \cdots & a'_{2n} \\ \vdots & \vdots & & \vdots \\ 0 & 0 & \cdots & \lambda_n  \end{pmatrix} \]

と、固有値によって三角化される。

三角化された行列$A'$が対角行列(上側も下側も0)になる場合を対角化という。

\[ P^{-1}  A  P  = A' = \begin{pmatrix} \lambda_1 & 0 & \cdots & 0 \\ 0 & \lambda_2 & \cdots & 0 \\ \vdots & \vdots & & \vdots \\ 0 & 0 & \cdots & \lambda_n  \end{pmatrix} \]

この方が、固有値問題からの帰結はイメージしやすい。両辺に左から$ P $をかけてやれば、

\[ A P = P A' = \begin{pmatrix} x_{11} & x_{12} & \cdots & x_{1n} \\ x_{21} & x_{22} & \cdots & x_{2n} \\ \vdots & \vdots & & \vdots \\ x_{n1} & x_{n2} & \cdots & x_{nn}  \end{pmatrix} \begin{pmatrix} \lambda_1 & 0 & \cdots & 0 \\ 0 & \lambda_2 & \cdots & 0 \\ \vdots & \vdots & & \vdots \\ 0 & 0 & \cdots & \lambda_n  \end{pmatrix}  \]

各固有値$ \lambda_i $ に対して、固有ベクトル $ \mathbf{x}_i = ( x_{i1},x_{i2},\cdots,x_{in} )^t $ を割り当てると、それぞれの列で成り立つことがわかる。

 ただし、"場合もある"といったように、任意の行列$ A $は必ずしも対角化できない。それは、$ P $が正則でなくなる場合である。すなわち、固有ベクトルが一次従属であり、多重固有値による固有ベクトルを考えて、その一次独立性を検討すればこれを確認できる。

固有値問題

 固有値問題は、以下を満たす$ \lambda $ と $ \mathbf{x} $ を求める問題あった。

\[ A \mathbf{x} = \lambda \mathbf{x}  \]

 これを解くのに、行列式を使って解くのであった。

\[\det( A - \lambda  I)  = 0  \]

n次$ \lambda $係数の代数方程式になるのであるが、代数学の基本定理より「n次方程式は，複素数の中にn個の解を持つ」ので、$\lambda$の解は$\mathbb{C}$ の中に$n$個見つかるはずである。逆に言うと、$n$次の正方行列$A$が、そもそも体$\mathbb{C}$上の行列であれば、$ n $個の$ \lambda $ を使って、三角化が必ず可能だけれども、複素数$\mathbb{C}$体上の行列でないのであれば、そもそも三角化もできない場合もありうる、ということに注意が必要である。

ここでは$\mathbb{C}$体上の行列として話を続ける。

固有値の解を$ \lambda_1,\lambda_2,\cdots,\lambda_n $とすると、同じ値を固有値が複数表れる場合もある。これを多重固有値と呼ぶ。それぞれ固有値の多重度を$ \textrm{r}( \lambda_i ) $ とすると、

\[ \sum_{i=1}^n \textrm{r} ( \lambda_i ) = \textrm{rank}(A) = n \]

 と、行列の階数に等しくなる。これに対し、固有値$\lambda_i$の固有ベクトル$ \mathbf{x}_i $の自由度を$ f_i $とすると、

\[ 1 \le f_i  \le \textrm{r}(\lambda_i) \]

が成り立つ。

もともとの固有値問題 $ A \mathbf{x} = \lambda \mathbf{x} $は、両辺スカラー倍しても成り立つから、固有ベクトル $ \mathbf{x} $ は、少なくとも1の自由度(スカラー倍)をもつ。

さらに、固有ベクトル $ \mathbf{x} $ は、$ (A-\lambda_i I)\mathbf{x}=0 $が成り立つ。$ ( A-\lambda_i I) $の階数は、 $\lambda_i $の重複度 $ \textrm{r}(\lambda_i) $ により、$ n - \textrm{r}(\lambda_i) \le \textrm{rank}(A-\lambda_i I)  \le  n $ であることから、上記の不等式が成り立つのである。

 直感的には、固有値の重複度と固有ベクトルの自由度は一致しそうなのだが、そうではない。そして、そうではない場合が、対角化不可能となる。たとえば、

\[ \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 &-1 \\ 0 & 1 & 3 \end{pmatrix} と \begin{pmatrix} 2 & 0 & 0 \\ 0 &-1 &-3 \\ 0 & 2 & 4 \end{pmatrix} \]

左は対角化不可能だが、右は対角化可能である。これらはどちらも特性方程式が、

\[ \det(A - \lambda I ) = (\lambda-2)^2(\lambda-1) \]

である。固有値$ \lambda=1,2,2 $となり、固有値2の場合の固有ベクトルの自由度で確認できる。※特性方程式は行列のすべてを表してはいないのである。

ちなみに、左側の行列の2行目以降の2行2列の行列

\[ \begin{pmatrix} 1 &-1 \\ 1 & 3 \end{pmatrix} \]

は、固有値2が重複して対角化できないのに対し、右側の行列の同じ部分は

\[ \begin{pmatrix}-1 &-3 \\ 2 & 4 \end{pmatrix} \]

は、別々の固有値$\lambda=1,2$で対角化できる。固有値2は、1行1列の対角成分”2"と重複しているからで、これと分離しているから対角化が可能なのである。

もう一つ、

\[ \begin{pmatrix} 2 & 1 & 0 \\ 0 &-1 &-3 \\ 0 & 2 & 4 \end{pmatrix} \]

の場合は、対角化ができない。上三角側に追加した成分"1"が影響するからだ。

まとめると、

• 複素数体$\mathbb{C}$上の任意の行列であれば、適当な変換行列を用いて三角化が可能。これは固有値問題を解くことで得られる。
• このうち対角化が可能なのは、特別な場合で、固有値問題の解の固有ベクトルがすべて一次独立の場合に対角化可能となる。
• 固有値問題の解自体、複素数体$\mathbb{C}$上でないと解けない場合がある。固有値が得られなければ三角化もできない。

LU分解

最後に、LU分解について少し。 "三角化"という言葉とLU分解の仕組みのせいでごっちゃになってしまうことがある。

LU分解は、任意の行列$ A $ を、下三角行列 $ L $ と上三角行列 $ U $ の分解することである。

\[ A = LU \]

 シンプルである。これは、今までの"三角化"とは若干スジメが異なっていて、固有値問題ではなく、

\[ A \mathbf{x} = \mathbf{b}  \]

 いわゆる連立方程式を解くときに現れる手法である。

\[ A \mathbf{x} = L U \mathbf{x} = \mathbf{b}  \]

として、$ U \mathbf{x}=\mathbf{y} $ と新たにおいて、

\[ L U \mathbf{x} = L \mathbf{y} = \mathbf{b}  \]

を解く。これが連立方程式を解くときの有名なガウスの消去法である。Aが正則であれば、LU分解できる。