べき乗法

数学 > 数値解析 > 数値線形代数 > 固有値問題の数値解法 > べき乗法 べき乗法（べきじょうほう）とはある n × n {\displaystyle n\times n} 行列の固有値のうち、絶対値最大のものを求める手法の総称であり、いくつかのバリエーションがある。累乗法とも呼ばれる。 典型的には、与えられた n × n {\displaystyle n\times n} 行列 A {\displaystyle \mathbf {A} } に対して、適当な初期ベクトル x ( 0 ) {\displaystyle \mathbf {x} ^{(0)}} から始めて、逐次 x ( k ) = A x ( k − 1 ) {\displaystyle \mathbf {x} ^{(k)}=\mathbf {A} \mathbf {x} ^{(k-1)}} を計算することで、 x ( k ) {\displaystyle \mathbf {x} ^{(k)}} が A {\displaystyle \mathbf {A} } の絶対値最大の固有値 λ 1 {\displaystyle \lambda _{1}} に属する固有ベクトルの方向に漸近していくことを利用し、 lim k → ∞ x ( k ) T x ( k ) x ( k ) T x ( k − 1 ) = λ 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}} により絶対値最大の固有値を得る。ただしベクトル列 { x ( k ) } {\displaystyle \{\mathbf {x} ^{(k)}\}} が定ベクトルに収束していくわけではないことに注意する。 また、べき乗法に類似した、絶対値最小の固有値を求める方法として逆べき乗法がある。 簡単のため、 n × n {\displaystyle n\times n} 行列 A {\displaystyle \mathbf {A} } の固有値 λ i ( i = 1 , 2 , ⋯ , n ) {\displaystyle \lambda _{i}(i=1,2,\cdots ,n)} がすべて互いに異なり ∣ λ 1 ∣>∣ λ 2 ∣> ⋯ >∣ λ n ∣ {\displaystyle \mid \lambda _{1}\mid >\mid \lambda _{2}\mid >\cdots >\mid \lambda _{n}\mid } であるとする。ここで、 λ i {\displaystyle \lambda _{i}} に属する A {\displaystyle \mathbf {A} } の固有ベクトルを u i {\displaystyle \mathbf {u} _{i}} とすると、 u i {\displaystyle \mathbf {u} _{i}} は A u i = λ i u i {\displaystyle \mathbf {A} \mathbf {u} _{i}=\lambda _{i}\mathbf {u} _{i}} をみたす。また、 u i {\displaystyle \mathbf {u} _{i}} は互いに1次独立なので、初期ベクトル x ( 0 ) {\displaystyle \mathbf {x} ^{(0)}} はこれらの1次結合により x ( 0 ) = c 1 u 1 + c 2 u 2 + ⋯ + c n u n {\displaystyle \mathbf {x} ^{(0)}=c_{1}\mathbf {u} _{1}+c_{2}\mathbf {u} _{2}+\cdots +c_{n}\mathbf {u} _{n}} と表すことができる。ここで、 c 1 ≠ 0 {\displaystyle c_{1}\neq 0} とすれば、 x ( k ) {\displaystyle \mathbf {x} ^{(k)}} は以下のように表される。 x ( k ) = A k x ( 0 ) = c 1 λ 1 k u 1 + c 2 λ 2 k u 2 + ⋯ + c n λ n k u n = c 1 λ 1 k { u 1 + c 2 c 1 ( λ 2 λ 1 ) k u 2 + ⋯ + c n c 1 ( λ n λ 1 ) k u n } {\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 \}}} 仮定より ∣ λ l / λ 1 ∣< 1 ( l ≠ 1 ) {\displaystyle \mid \lambda _{l}/\lambda _{1}\mid <1\left(l\neq 1\right)} なので、 k → ∞ {\displaystyle k\rightarrow \infty } のとき x ( k ) {\displaystyle \mathbf {x} ^{(k)}} は絶対値最大の固有値 λ 1 {\displaystyle \lambda _{1}} に属する固有ベクトル u 1 {\displaystyle \mathbf {u} _{1}} と同じ方向 c 1 λ 1 k u 1 {\displaystyle c_{1}{\lambda _{1}}^{k}\mathbf {u} _{1}} に近づいていく。 絶対値最大の固有値 λ 1 {\displaystyle \lambda _{1}} を求めるときは、 x ( k − 1 ) = c 1 λ 1 k − 1 { u 1 + c 2 c 1 ( λ 2 λ 1 ) k − 1 u 2 + ⋯ + c n c 1 ( λ n λ 1 ) k − 1 u n } {\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 \}}} より、 lim k → ∞ x ( k ) T x ( k ) x ( k ) T x ( k − 1 ) = λ 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}} となることを利用する。 行列 A {\displaystyle \mathbf {A} } の固有値が重複を持ち更に対角化可能でない場合も、ジョルダン標準形を考えれば同様の考え方で証明できる。 最大固有値と、その次に大きい固有値の差が小さすぎる場合、収束が極めて遅くなる。 森正武『数値解析』共立出版、2002年2月。ISBN 4-320-01701-3。  固有値問題 逆べき乗法