べき乗法

数学 > 数値解析 > 数値線形代数 > 固有値問題の数値解法 > べき乗法

べき乗法（冪乗法、べきじょうほう）とはある${\displaystyle n\times n}$行列の固有値のうち、絶対値最大のものを求める手法の総称であり、いくつかのバリエーションがある。累乗法とも呼ばれる。

典型的には、与えられた${\displaystyle n\times n}$行列${\displaystyle \mathbf {A} }$に対して、適当な初期ベクトル${\displaystyle \mathbf {x} ^{(0)}}$から始めて、逐次

${\displaystyle \mathbf {x} ^{(k)}=\mathbf {A} \mathbf {x} ^{(k-1)}}$

を計算することで、${\displaystyle \mathbf {x} ^{(k)}}$が${\displaystyle \mathbf {A} }$の絶対値最大の固有値${\displaystyle \lambda _{1}}$に属する固有ベクトルの方向に漸近していくことを利用し、

${\displaystyle \lim _{k\to \infty }{\dfrac {\mathbf {x} ^{(k){\rm {T}}}\mathbf {x} ^{(k)}}{\mathbf {x} ^{(k){\rm {T}}}\mathbf {x} ^{(k-1)}}}=\lambda _{1}}$

により絶対値最大の固有値を得る。ただしベクトル列${\displaystyle \{\mathbf {x} ^{(k)}\}}$が定ベクトルに収束していくわけではないことに注意する。

また、べき乗法に類似した、絶対値最小の固有値を求める方法として逆べき乗法がある。

収束の証明

簡単のため、${\displaystyle n\times n}$行列${\displaystyle \mathbf {A} }$の固有値${\displaystyle \lambda _{i}(i=1,2,\cdots ,n)}$がすべて互いに異なり

${\displaystyle \mid \lambda _{1}\mid >\mid \lambda _{2}\mid >\cdots >\mid \lambda _{n}\mid }$

であるとする。ここで、${\displaystyle \lambda _{i}}$に属する${\displaystyle \mathbf {A} }$の固有ベクトルを${\displaystyle \mathbf {u} _{i}}$とすると、${\displaystyle \mathbf {u} _{i}}$は

${\displaystyle \mathbf {A} \mathbf {u} _{i}=\lambda _{i}\mathbf {u} _{i}}$

をみたす。また、${\displaystyle \mathbf {u} _{i}}$は互いに1次独立なので、初期ベクトル${\displaystyle \mathbf {x} ^{(0)}}$はこれらの1次結合により

${\displaystyle \mathbf {x} ^{(0)}=c_{1}\mathbf {u} _{1}+c_{2}\mathbf {u} _{2}+\cdots +c_{n}\mathbf {u} _{n}}$

と表すことができる。ここで、${\displaystyle c_{1}\neq 0}$とすれば、${\displaystyle \mathbf {x} ^{(k)}}$は以下のように表される。

${\displaystyle \mathbf {x} ^{(k)}=\mathbf {A} ^{k}\mathbf {x} ^{(0)}=c_{1}{\lambda _{1}}^{k}\mathbf {u} _{1}+c_{2}{\lambda _{2}}^{k}\mathbf {u} _{2}+\cdots +c_{n}{\lambda _{n}}^{k}\mathbf {u} _{n}=c_{1}{\lambda _{1}}^{k}{\biggl \{}\mathbf {u} _{1}+{\dfrac {c_{2}}{c_{1}}}\left({\dfrac {\lambda _{2}}{\lambda _{1}}}\right)^{k}\mathbf {u} _{2}+\cdots +{\dfrac {c_{n}}{c_{1}}}\left({\dfrac {\lambda _{n}}{\lambda _{1}}}\right)^{k}\mathbf {u} _{n}{\biggr \}}}$

仮定より${\displaystyle \mid \lambda _{l}/\lambda _{1}\mid <1\left(l\neq 1\right)}$なので、${\displaystyle k\rightarrow \infty }$のとき${\displaystyle \mathbf {x} ^{(k)}}$は絶対値最大の固有値${\displaystyle \lambda _{1}}$に属する固有ベクトル${\displaystyle \mathbf {u} _{1}}$と同じ方向${\displaystyle c_{1}{\lambda _{1}}^{k}\mathbf {u} _{1}}$に近づいていく。

絶対値最大の固有値${\displaystyle \lambda _{1}}$を求めるときは、

${\displaystyle \mathbf {x} ^{(k-1)}=c_{1}{\lambda _{1}}^{k-1}{\biggl \{}\mathbf {u} _{1}+{\dfrac {c_{2}}{c_{1}}}\left({\dfrac {\lambda _{2}}{\lambda _{1}}}\right)^{k-1}\mathbf {u} _{2}+\cdots +{\dfrac {c_{n}}{c_{1}}}\left({\dfrac {\lambda _{n}}{\lambda _{1}}}\right)^{k-1}\mathbf {u} _{n}{\biggr \}}}$

より、

${\displaystyle \lim _{k\to \infty }{\dfrac {\mathbf {x} ^{(k){\rm {T}}}\mathbf {x} ^{(k)}}{\mathbf {x} ^{(k){\rm {T}}}\mathbf {x} ^{(k-1)}}}=\lambda _{1}}$

となることを利用する。

行列${\displaystyle \mathbf {A} }$の固有値が重複を持ち更に対角化可能でない場合も、ジョルダン標準形を考えれば同様の考え方で証明できる。

欠点

最大固有値と、その次に大きい固有値の差が小さすぎる場合、収束が極めて遅くなる。

参考文献

• 森正武『数値解析』共立出版、2002年2月。ISBN 4-320-01701-3。 

関連項目

• 固有値問題
• 逆べき乗法