パワーイテレーション

数学 において、べき乗反復法（べき乗法とも呼ばれる）は固有値アルゴリズムです。対角化可能な 行列 が与えられると、このアルゴリズムはの最大（絶対値で）固有値である数値 と、の対応する固有ベクトルである非ゼロベクトル（つまり ）を生成します。このアルゴリズムはフォン・ミーゼス反復法とも呼ばれます。^[1]${\displaystyle A}$${\displaystyle \lambda}$${\displaystyle A}$${\displaystyle v}$${\displaystyle \lambda}$${\displaystyle Av=\lambda v}$

べき乗反復法は非常に単純なアルゴリズムですが、収束が遅い場合があります。アルゴリズムで最も時間のかかる操作は、行列とベクトルの乗算であるため、適切に実装すれば、非常に大きな疎行列に効果的です。収束の速度は次のようになります(後のセクションを参照)。つまり、収束は、スペクトル ギャップを底とする指数関数です。 ${\displaystyle A}$${\displaystyle (\lambda _{1}/\lambda _{2})^{k}}$

べき乗反復アルゴリズムはベクトルから始まり、それは支配的な固有ベクトルまたはランダムベクトルの近似値である可能性がある。この方法は再帰関係によって記述される。${\displaystyle b_{0}}$

${\displaystyle b_{k+1}={\frac {Ab_{k}}{\|Ab_{k}\|}}}$

したがって、反復ごとに、ベクトルは行列で乗算され、正規化されます。 ${\displaystyle b_{k}}$${\displaystyle A}$

が他の固有値よりも絶対値​​が大きい固有値を持ち、開始ベクトルが優勢な固有値に関連付けられた固有ベクトルの方向に非ゼロの成分を持つと仮定すると、部分列は優勢な固有値に関連付けられた固有ベクトルに収束します。 ${\displaystyle A}$${\displaystyle b_{0}}$${\displaystyle \left(b_{k}\right)}$

上記の2つの仮定がなければ、シーケンスは必ずしも収束しません。このシーケンスでは、 ${\displaystyle \left(b_{k}\right)}$

${\displaystyle b_{k}=e^{i\phi _{k}}v_{1}+r_{k}}$、

ここで、 は支配的な固有値に関連付けられた固有ベクトルであり、 である。 項の存在は、でない限り が収束しないことを意味する。 上記の2つの仮定の下で、によって定義される シーケンスは、${\displaystyle v_{1}}$${\displaystyle \|r_{k}\|\rightarrow 0}$${\displaystyle e^{i\phi _{k}}}$${\displaystyle \left(b_{k}\right)}$${\displaystyle e^{i\phi _{k}}=1}$${\displaystyle \left(\mu _{k}\right)}$

${\displaystyle \mu _{k}={\frac {b_{k}^{*}Ab_{k}}{b_{k}^{*}b_{k}}}}$

支配的な固有値（レイリー商）に収束する。^{[説明が必要]}

これは次のアルゴリズムで計算できます (NumPy を使用した Python で表示)。

#!/usr/bin/env python3

 numpyを npとして インポートする

def  power_iteration ( A ,  num_iterations :  int ): 
    # 理想的にはランダムベクトルを選択します
    # ベクトルが
    固有ベクトルに直交する可能性を減らすため # 
    b_k  =  np . random . rand ( A . shape [ 1 ])

    for  _  in  range ( num_iterations ): 
        # 行列とベクトルの積を計算する Ab 
        b_k1  =  np . dot ( A ,  b_k )

        
        #ノルムを計算するb_k1_norm  =  np.linalg.norm ( b_k1 )

        # ベクトルを再正規化する
        b_k  =  b_k1  /  b_k1_norm

     b_kを返す

べき乗反復( np .配列([[ 0.5 ,  0.5 ],  [ 0.2 ,  0.8 ]]),  10 )

ベクトルは関連する固有ベクトルに収束します。理想的には、関連する固有値を取得するために レイリー商を使用する必要があります。${\displaystyle b_{k}}$

このアルゴリズムは、Google PageRank を計算するために使用されます。

この方法は、レイリー商を計算することによって スペクトル半径（正方行列の場合、最大の大きさを持つ固有値）を計算するためにも使用できる。

${\displaystyle \rho (A)=\max \left\{|\lambda _{1}|,\dotsc ,|\lambda _{n}|\right\}={\frac {b_{k}^{\top }Ab_{k}}{b_{k}^{\top }b_{k}}}.}$

をジョルダン標準形に分解すると、の最初の列は、支配的な固有値 に対応するの固有ベクトルです。一般に の支配的な固有値は一意であるため、 の最初のジョルダン ブロックは、がAの最大固有値である行列です。 開始ベクトルは、Vの列の線形結合として記述できます。 ${\displaystyle A}$${\displaystyle A=VJV^{-1}}$${\displaystyle V}$${\displaystyle A}$${\displaystyle \lambda _{1}}$${\displaystyle A}$${\displaystyle J}$${\displaystyle 1\times 1}$${\displaystyle [\lambda _{1}],}$${\displaystyle \lambda _{1}}$${\displaystyle b_{0}}$

${\displaystyle b_{0}=c_{1}v_{1}+c_{2}v_{2}+\cdots +c_{n}v_{n}.}$

仮定により、は支配的な固有値の方向に非ゼロの成分を持つため、 となります。 ${\displaystyle b_{0}}$${\displaystyle c_{1}\neq 0}$

の計算上有用な再帰関係は次のように書き直すことができます。 ${\displaystyle b_{k+1}}$

${\displaystyle b_{k+1}={\frac {Ab_{k}}{\|Ab_{k}\|}}={\frac {A^{k+1}b_{0}}{\|A^{k+1}b_{0}\|}},}$

ここで、表現:は次の分析に適しています。 ${\displaystyle {\frac {A^{k+1}b_{0}}{\|A^{k+1}b_{0}\|}}}$

${\displaystyle {\begin{aligned}b_{k}&={\frac {A^{k}b_{0}}{\|A^{k}b_{0}\|}}\\&={\frac {\left(VJV^{-1}\right)^{k}b_{0}}{\|\left(VJV^{-1}\right)^{k}b_{0}\|}}\\&={\frac {VJ^{k}V^{-1}b_{0}}{\|VJ^{k}V^{-1}b_{0}\|}}\\&={\frac {VJ^{k}V^{-1}\left(c_{1}v_{1}+c_{2}v_{2}+\cdots +c_{n}v_{n}\right)}{\|VJ^{k}V^{-1}\left(c_{1}v_{1}+c_{2}v_{2}+\cdots +c_{n}v_{n}\right)\|}}\\&={\frac {VJ^{k}\left(c_{1}e_{1}+c_{2}e_{2}+\cdots +c_{n}e_{n}\right)}{\|VJ^{k}\left(c_{1}e_{1}+c_{2}e_{2}+\cdots +c_{n}e_{n}\right)\|}}\\&=\left({\frac {\lambda _{1}}{|\lambda _{1}|}}\right)^{k}{\frac {c_{1}}{|c_{1}|}}{\frac {v_{1}+{\frac {1}{c_{1}}}V\left({\frac {1}{\lambda _{1}}}J\right)^{k}\left(c_{2}e_{2}+\cdots +c_{n}e_{n}\right)}{\left\|v_{1}+{\frac {1}{c_{1}}}V\left({\frac {1}{\lambda _{1}}}J\right)^{k}\left(c_{2}e_{2}+\cdots +c_{n}e_{n}\right)\right\|}}\end{aligned}}}$

上記の式は次のように簡略化される。${\displaystyle k\to \infty }$

${\displaystyle \left({\frac {1}{\lambda _{1}}}J\right)^{k}={\begin{bmatrix}[1]&&&&\\&\left({\frac {1}{\lambda _{1}}}J_{2}\right)^{k}&&&\\&&\ddots &\\&&&\left({\frac {1}{\lambda _{1}}}J_{m}\right)^{k}\\\end{bmatrix}}\rightarrow {\begin{bmatrix}1&&&&\\&0&&&\\&&\ddots &\\&&&0\\\end{bmatrix}}\quad {\text{as}}\quad k\to \infty .}$

この極限は、の固有値の大きさが1未満である という事実から導かれるので、${\displaystyle {\frac {1}{\lambda _{1}}}J_{i}}$

${\displaystyle \left({\frac {1}{\lambda _{1}}}J_{i}\right)^{k}\to 0\quad {\text{as}}\quad k\to \infty .}$

結果は次のようになります。

${\displaystyle {\frac {1}{c_{1}}}V\left({\frac {1}{\lambda _{1}}}J\right)^{k}\left(c_{2}e_{2}+\cdots +c_{n}e_{n}\right)\to 0\quad {\text{as}}\quad k\to \infty }$

この事実を利用すると、kが大きい場合との関係を強調する形式で記述できます。 ${\displaystyle b_{k}}$${\displaystyle v_{1}}$

${\displaystyle {\begin{aligned}b_{k}&=\left({\frac {\lambda _{1}}{|\lambda _{1}|}}\right)^{k}{\frac {c_{1}}{|c_{1}|}}{\frac {v_{1}+{\frac {1}{c_{1}}}V\left({\frac {1}{\lambda _{1}}}J\right)^{k}\left(c_{2}e_{2}+\cdots +c_{n}e_{n}\right)}{\left\|v_{1}+{\frac {1}{c_{1}}}V\left({\frac {1}{\lambda _{1}}}J\right)^{k}\left(c_{2}e_{2}+\cdots +c_{n}e_{n}\right)\right\|}}\\[6pt]&=e^{i\phi _{k}}{\frac {c_{1}}{|c_{1}|}}{\frac {v_{1}}{\|v_{1}\|}}+r_{k}\end{aligned}}}$

どこで、どのように${\displaystyle e^{i\phi _{k}}=\left(\lambda _{1}/|\lambda _{1}|\right)^{k}}$${\displaystyle \|r_{k}\|\to 0}$${\displaystyle k\to \infty }$

シーケンスは有界であるため、収束する部分シーケンスが含まれます。優勢な固有値に対応する固有ベクトルはスカラーまでしか一意ではないため、シーケンスが収束しない場合でも、 kが大きい場合はほぼAの固有ベクトルになります。 ${\displaystyle \left(b_{k}\right)}$${\displaystyle \left(b_{k}\right)}$${\displaystyle b_{k}}$

あるいは、Aが対角化可能であれば、次の証明は同じ結果をもたらす。

λ ₁、λ ₂、...、λ _{m を}Aのm個の固有値（重複度付き）とし、v ₁、v ₂、...、v _mを対応する固有ベクトルとします。 が優勢な固有値であると仮定すると、 に対して となります。 ${\displaystyle \lambda _{1}}$${\displaystyle |\lambda _{1}|>|\lambda _{j}|}$${\displaystyle j>1}$

初期ベクトルは次のように記述できます。 ${\displaystyle b_{0}}$

${\displaystyle b_{0}=c_{1}v_{1}+c_{2}v_{2}+\cdots +c_{m}v_{m}.}$

がランダムに（一様確率で）選択される場合、c ₁ ≠ 0 となる確率は 1です。 ${\displaystyle b_{0}}$

${\displaystyle {\begin{aligned}A^{k}b_{0}&=c_{1}A^{k}v_{1}+c_{2}A^{k}v_{2}+\cdots +c_{m}A^{k}v_{m}\\&=c_{1}\lambda _{1}^{k}v_{1}+c_{2}\lambda _{2}^{k}v_{2}+\cdots +c_{m}\lambda _{m}^{k}v_{m}\\&=c_{1}\lambda _{1}^{k}\left(v_{1}+{\frac {c_{2}}{c_{1}}}\left({\frac {\lambda _{2}}{\lambda _{1}}}\right)^{k}v_{2}+\cdots +{\frac {c_{m}}{c_{1}}}\left({\frac {\lambda _{m}}{\lambda _{1}}}\right)^{k}v_{m}\right)\\&\to c_{1}\lambda _{1}^{k}v_{1}&&\left|{\frac {\lambda _{j}}{\lambda _{1}}}\right|<1{\text{ for }}j>1\end{aligned}}}$

一方で：

${\displaystyle b_{k}={\frac {A^{k}b_{0}}{\|A^{k}b_{0}\|}}.}$

したがって、は固有ベクトル （の倍数）に収束します。収束は幾何収束であり、比は ${\displaystyle b_{k}}$${\displaystyle v_{1}}$

${\displaystyle \left|{\frac {\lambda _{2}}{\lambda _{1}}}\right|,}$

ここで、 は2 番目の支配的な固有値を表します。したがって、支配的な固有値と大きさが近い固有値がある場合、この方法はゆっくりと収束します。 ${\displaystyle \lambda _{2}}$

べき乗反復法は行列の 1 つの固有値のみを近似しますが、特定の計算問題には依然として有用です。たとえば、Google は検索エンジンでドキュメントのPageRank を計算するために使用しています^[2] 。また、Twitter はフォローすべき人物の推奨をユーザーに表示するために使用しています^[3] 。べき乗反復法は、Web 行列などの疎行列に特に適しています。また、係数行列を明示的に保存する必要がなく、代わりに行列ベクトル積を評価する関数にアクセスできる行列フリー法としても使用できます。条件が整えられた非対称行列の場合、べき乗反復法はより複雑なアーノルディ反復法よりも優れたパフォーマンスを発揮します。対称行列の場合、べき乗反復法はめったに使用されません。これは、反復あたりのコストが小さいことを犠牲にすることなく収束速度を簡単に上げることができるためです。たとえば、Lanczos 反復法やLOBPCG を参照してください。 ${\displaystyle A}$${\displaystyle Ax}$

より高度な固有値アルゴリズムのいくつかは、べき乗反復のバリエーションとして理解することができます。たとえば、逆反復法は、行列にべき乗反復を適用します。他のアルゴリズムは、ベクトルによって生成されたサブスペース全体を調べます。このサブスペースはクリロフサブスペースとして知られています。これは、アーノルディ反復法またはランチョス反復法によって計算できます。グラム反復法^[4]は、最大固有値対を計算するための超線形かつ決定論的な方法です。 ${\displaystyle A^{-1}}$${\displaystyle b_{k}}$

• レイリー商反復
• 逆反復