行列の累乗法

定義

サイズが $n \times n$ の正方行列 $A$ のべき乗を計算することによって $A$ の優勢固有値を求める方法を べき乗法^{the power method}という。

説明

与えられた行列の固有値を計算するには特性多項式を解く必要がある。しかし $5 \ge n$ のときは根の公式が存在しないため、特性多項式の根を代数的に容易に求めることは不可能だ。これは手計算でももちろん難しいが、コンピュータで計算する場合でも同様だ。べき乗法はこのような問題を解決する方法であり、行列のべき乗を計算する過程を通して優勢固有値を近似的に求めることができる。

$n \times n$ 行列 $A$ と ▷eq07◯次元ベクトル ▷eq08◯ に対して、下のような数列を $A$ によって生成される べき乗列^{power sequence generated by $A$}という。

$$ \left\{ \mathbf{x},\quad A\mathbf{x},\quad A^{2}\mathbf{x}, \dots \right\} $$

定理

$n \times n$ 行列 $A$ が ▷eq07◯個の線形独立な固有ベクトルを持つとする。$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} $$

定理によって任意の初期ベクトル $\mathbf{x}_{0}$ に行列 $A$ を繰り返し掛けることで優勢固有値を求めることができる。$\mathbf{x}_{0}$ が優勢固有空間と直交しないという仮定が必要だが、$\mathbf{x}_{0}$ をランダムに抽出した場合にそうなる確率は非常に低い。
定理では優勢固有値が正であると仮定しているが、もし負ならば ▷eq22◯ の列は向きが互いに反対の単位優勢固有ベクトルに近づき振動するだろう。同様に ▷eq23◯ は優勢固有値の絶対値に収束するだろう。
もし $A$ が対角化可能で ▷eq07◯個の独立な固有ベクトルを持つなら、定理の条件を満たす。
$A$ が対称行列であれば ▷eq07◯個の独立な固有ベクトルを持つので、定理の条件を満たす。

証明

$A$ の ▷eq07◯個の線形独立な固有ベクトルを ▷eq30◯ と表記しよう。これらは ▷eq31◯ の基底なので、▷eq18◯ を次のように表すことができる。

$$ \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) $$

ここで ▷eq18◯ が ▷eq15◯ の固有空間と直交しないため ▷eq35◯ は ▷eq36◯ ではない。▷eq37◯ を両辺に掛けて整理すると次を得る。

$$ \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*} $$

▷eq15◯ が優勢固有値であるため、各括弧内の値は ▷eq39◯ のとき ▷eq40◯ に収束する。

補題
▷eq41◯ を初期単位ベクトル ▷eq18◯ に対して ▷eq43◯ のように表すことができる。すなわち ▷eq22◯ の数列は下記のようでもある: $$ \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 $$

上の補題により ▷eq41◯ は優勢単位ベクトルに収束する。この結果から ▷eq46◯ もまた優勢固有値に収束することがわかる。

■

補題の証明

数学的帰納法で証明する。▷eq47◯ のときは成り立つことを知っている。今、▷eq48◯ のとき成り立つと仮定する。すると ▷eq49◯ のときも成り立つことを下記のように示すことができる。

$$ \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\|} $$

■