行列の累乗法
定義
大きさが $n \times n$ の 正方行列 $A$ の冪乗を計算することによって $A$ の 優勢固有値 を求める方法を べき乗法the power methodという。
説明
与えられた行列の固有値を計算するには 特性多項式 を解かなければならない。しかし $5 \ge n$ のときは解の公式は存在しないため、特性多項式の根を代数的に容易に計算することは不可能である。これは手計算の場合はもちろん困難だが、コンピュータで計算する場合も同様である。べき乗法はこのような問題を解決する方法として、行列の冪乗を計算する過程を通して優勢固有値を近似的に求める方法である。
$n \times n$ 行列 $A$ と $n$次元ベクトル $\mathbf{x} \in \mathbb{R}^{n}$ に対して、以下のような数列を $A$ によって生成される べき乗数列power sequence generated by $A$という。
$$ \left\{ \mathbf{x},\quad A\mathbf{x},\quad A^{2}\mathbf{x},\quad \dots \right\} $$
べき乗計算を繰り返すと、ベクトルの大きさが非常に大きくなったり小さくなったりして計算が困難になる。これを解決するために、以下の定理のように各ステップでベクトルの大きさを正規化する方法や、ベクトルの最大成分の大きさを調整する方法を用いる。
定理
定理によって任意の初期ベクトル $\mathbf{x}_{0}$ に対して行列 $A$ を繰り返し掛けることで優勢固有値を求めることができる。 $\mathbf{x}_{0}$ が優勢 固有空間 と直交しないという仮定が必要だが、 $\mathbf{x}_{0}$ をランダムに抽出したときにそのようになる確率は非常に低い。
定理では優勢固有値が正であることを仮定しているが、もし負であれば $(1)$ の数列は向きが互いに逆の単位優勢固有ベクトルに近づき振動するだろう。類似して ▷eq16◯ は優勢固有値の絶対値に収束する。
もし $A$ が 対角化可能であれば $n$ 個の独立な固有ベクトルを持つので、定理の条件を満たす。
$A$ が 対称行列であれば $n$ 個の独立な固有ベクトルを持つので、定理の条件を満たす。
$\ell^{2}$ 正規化によるべき乗法
$n \times n$ 行列 $A$ が $n$ 個の 線形独立 な固有ベクトルを持つとする。$A$ の 優勢固有値 $\lambda_{1}$ が正であるとする。すると $\lambda_{1}$ に対応する固有空間に直交しない単位ベクトル $\mathbf{x}_{0} \in \mathbb{R}^{n}$ に対して、以下のような正規化されたべき乗数列は優勢単位固有ベクトルに収束する。
$$ \mathbf{x}_{0},\quad \mathbf{x}_{1} = \dfrac{ A \mathbf{x}_{0} }{\| A \mathbf{x}_{0} \|},\quad \mathbf{x}_{2} = \dfrac{ A \mathbf{x}_{1} }{\| A \mathbf{x}_{1} \|},\quad \dots,\quad \mathbf{x}_{k} = \dfrac{ A \mathbf{x}_{k-1} }{\| A \mathbf{x}_{k-1} \|},\quad \dots \tag{1} $$
また以下の数列は優勢固有値に収束する。
$$ A \mathbf{x}_{1} \cdot \mathbf{x}_{1}, \quad A \mathbf{x}_{2} \cdot \mathbf{x}_{2}, \quad \dots, \quad A \mathbf{x}_{k} \cdot \mathbf{x}_{k}, \quad \dots \tag{2} $$
一方 $(1)$ は以下の数列とも等しい。
$$ \mathbf{x}_{0},\quad \mathbf{x}_{1} = \dfrac{ A \mathbf{x}_{0} }{\| A \mathbf{x}_{0} \|},\quad \mathbf{x}_{2} = \dfrac{ A^{k} \mathbf{x}_{0} }{\| A^{k} \mathbf{x}_{0} \|},\quad \dots,\quad \mathbf{x}_{k} = \dfrac{ A^{k} \mathbf{x}_{0} }{\| A^{k} \mathbf{x}_{0} \|},\quad \dots $$
最大成分の大きさによるスケーリングによるべき乗法
$n \times n$ 行列 $A$ が $n$ 個の 線形独立 な固有ベクトルを持つとする。$A$ の 優勢固有値 $\lambda_{1}$ が正であるとする。すると $\lambda_{1}$ に対応する 固有空間 に 直交 しない単位ベクトル $\mathbf{x}_{0} \in \mathbb{R}^{n}$ に対して、以下のような正規化されたべき乗数列は優勢単位固有ベクトルに収束する。
$$ \mathbf{x}_{0},\quad \mathbf{x}_{1} = \dfrac{ A \mathbf{x}_{0} }{\max(A \mathbf{x}_{0})},\quad \mathbf{x}_{2} = \dfrac{ A \mathbf{x}_{1} }{\max(A \mathbf{x}_{1})},\quad \dots,\quad \mathbf{x}_{k} = \dfrac{ A \mathbf{x}_{k-1} }{\max(A \mathbf{x}_{k-1})},\quad \dots \tag{3} $$
このとき $\max (\mathbf{x})$ はベクトル $\mathbf{x}$ の成分の絶対値のうち最大の値を意味する。また以下の数列は優勢固有値に収束する。
$$ \dfrac{A \mathbf{x}_{1} \cdot \mathbf{x}_{1}}{\mathbf{x}_{1} \cdot \mathbf{x}_{1}}, \quad \dfrac{A \mathbf{x}_{2} \cdot \mathbf{x}_{2}}{\mathbf{x}_{2} \cdot \mathbf{x}_{2}}, \quad \dots, \quad \dfrac{A \mathbf{x}_{k} \cdot \mathbf{x}_{k}}{\mathbf{x}_{k} \cdot \mathbf{x}_{k}}, \quad \dots $$
一方 $(3)$ は以下の数列と等しい。
$$ \mathbf{x}_{0},\quad \mathbf{x}_{1} = \dfrac{ A \mathbf{x}_{0} }{\max(A \mathbf{x}_{0})},\quad \mathbf{x}_{2} = \dfrac{ A^{2} \mathbf{x}_{0} }{\max(A^{2} \mathbf{x}_{0})},\quad \dots,\quad \mathbf{x}_{k} = \dfrac{ A^{k} \mathbf{x}_{0} }{\max(A^{k} \mathbf{x}_{0})},\quad \dots $$
証明
$\ell^{2}$ 正規化によるべき乗法について証明する。$A$ の $n$ 個の線形独立な固有ベクトルを $\mathbf{v}_{i}$ と表記する。これらは $\mathbb{R}^{n}$ の 基底 であるから、 $\mathbf{x}_{0}$ を次のように表現できる。
$$ \mathbf{x}_{0} = c_{1}\mathbf{v}_{1} + \cdots c_{2}\mathbf{v}_{2} + \cdots + c_{n} \mathbf{v}_{n} \quad (c_{1} \ne 0) $$
ここで $\mathbf{x}_{0}$ が $\lambda_{1}$ の固有空間と直交しないので $c_{1}$ は $0$ ではない。$A^{k}$ を両辺に掛けて整理すると次を得る。
$$ \begin{align*} A^{k}\mathbf{x}_{0} &= c_{1}A^{k}\mathbf{v}_{1} + \cdots c_{2}A^{k}\mathbf{v}_{2} + \cdots + c_{n}A^{k}\mathbf{v}_{n} \\ &= c_{1}\lambda_{1}^{k}\mathbf{v}_{1} + \cdots c_{2}\lambda_{2}^{k}\mathbf{v}_{2} + \cdots + c_{n}\lambda_{n}^{k}\mathbf{v}_{n} \\ &= \lambda_{1}^{k} \left[ c_{1}\mathbf{v}_{1} + \cdots c_{2}\left( \dfrac{\lambda_{2}}{\lambda_{1}} \right)^{k}\mathbf{v}_{2} + \cdots + c_{n}\left( \dfrac{\lambda_{n}}{\lambda_{1}} \right)^{k}\mathbf{v}_{n} \right] \\ \end{align*} $$
$\lambda_{1}$ が優勢固有値であるため、各括弧内の値は $k \to \infty$ のとき $c_{1}\mathbf{v}_{1}$ に収束する。
補助定理
$\mathbf{x}_{k}$ を初期単位ベクトル $\mathbf{x}_{0}$ に対して $\mathbf{x}_{k} = A^{k} \mathbf{x}_{0} / \left\| A^{k} \mathbf{x}_{0} \right\|$ のように表すことができる。すなわち $(1)$ の数列は以下とも等しい。 $$ \mathbf{x}_{0},\quad \mathbf{x}_{1} = \dfrac{ A \mathbf{x}_{0} }{\| A \mathbf{x}_{0} \|},\quad \mathbf{x}_{2} = \dfrac{ A^{k} \mathbf{x}_{0} }{\| A^{k} \mathbf{x}_{0} \|},\quad \dots,\quad \mathbf{x}_{k} = \dfrac{ A^{k} \mathbf{x}_{0} }{\| A^{k} \mathbf{x}_{0} \|},\quad \dots $$
上の補助定理により $\mathbf{x}_{k}$ は優勢単位ベクトルに収束する。この結果から $A \mathbf{x}_{k} \cdot \mathbf{x}_{k}$ もまた優勢固有値に収束することがわかる。
■
補助定理の証明
数学的帰納法で証明する。$k=1$ のときは成り立つことを確認してある。今 $k=m$ のとき成り立つと仮定する。すると $k=m+1$ のときも成り立つことを以下のように示せる。
$$ \mathbf{x}_{m+1} = \dfrac{ A \mathbf{x}_{m} }{ \left\| A \mathbf{x}_{m} \right\| } = \dfrac{1}{\left\| A^{m}\mathbf{x}_{0} \right\|}\dfrac{ A (A^{m}\mathbf{x}_{0}) }{ \left\| \dfrac{A (A^{m}\mathbf{x}_{0})}{ \left\| A^{m}\mathbf{x}_{0} \right\|} \right\| } = \dfrac{A^{m+1} \mathbf{x}_{0}}{\left\| A^{m+1} \mathbf{x}_{0} \right\|} $$
■