べき乗法 - ishikawashの学習ノート

線形代数に関連した数値計算の手法として、べき乗法があります。べき乗法とは、固有値と固有ベクトルの性質から、ベクトルに行列を繰り返しかけることで絶対値最大の固有値とそれに属する固有ベクトルを求める方法です。計算手順が行列の次数に依らないので、任意の次数の行列に適用可能です。べき乗法の証明は、既に幾つものウェブサイトで説明されているので、そちらを参照にしていただければ良いと思いますが、今回私が参照したのは次のサイトです。

相異なる固有値に属する固有ベクトルは互いに一次独立なので、任意のベクトルは固有ベクトルを基底にして表すことができます。このベクトルに行列をかけ続けると、絶対値最大の固有値と固有ベクトルの積に収束する、というわけですね。
以下、個人的な補足。固有値を推定する式ですが、
$\vec{v_{n+1}} = A\vec{v_n} = \lambda\vec{v_n}$
から、 $\vec{v_{n+1}}$ と $\vec{v_{n}}$ の内積を求めると
$\vec{v_{n+1}}\cdot\vec{v_n} = A\vec{v_n}\cdot\vec{v_n} = \lambda\vec{v_n}\cdot\vec{v_n}$
となりますが、この時 $\vec{v_{n}}$ は単位ベクトルなので、その結果
$\lambda\vec{v_{n}}\cdot\vec{v_{n}} = \lambda$
となって固有値が得られます。

最後に、せっかくなのでべき乗法をC++で実装し検証してみました*1。ソースコードは次のURLから取得可能です。
http://homepage.mac.com/radio_nights/files/power_method.tar.gz
3次正方行列の各成分を指定すると、固有値と固有ベクトルを計算して表示する単純なプログラムです。あくまで習作ですのでエラーチェックは行っていませんが、厳密さを求めるならば、与えられた行列の特性方程式が実数解を持つかどうか事前に判定すべきかもしれません。

*1:ベクトル行列ライブラリとして、Java3D javax.vecmathパッケージのC++実装を利用しています。