数値解析（塩田）2022年度

数値解析第14回 (2)　累乗法

前へ / 戻る / 次へ

累乗法のアルゴリズム

　上述の通り、手計算どおりの計算を実現するためにはたくさんの処理が必要です。そこで、シンプルな反復法で固有値・固有ベクトルを計算する方法を紹介しましょう。

Th.5　対角化可能な

$n$ 次行列

$A$ の固有値が条件

$\dps{|\,\lambda_1\,| \gt \max(|\,\lambda_2\,|,\cdots, |\,\lambda_n\,|)}$

$\cdots\cdots$

$(\ast)$ を満たすとする　このとき、次のアルゴリズムによって

$(\lambda_1, \vvv_1)$ を求めることができる。

$\lambda_1$ は、絶対値が他の固有値よりも真に大きいので「最大固有値」と呼びます。

Algorithm 6
入力：

$n$ 次正方行列

$A$
出力：

$A$ の最大固有値

$\lambda$ と、

$\lambda$ に対する固有ベクトル

$\vvv$

$\vvv=$ ( ランダムな単位ベクトル )
while True
新 $\,\vvv=$ ( $A\vvv$ 方向の単位ベクトル )
if ( $\vvv$ ≒ 旧 $\,\vvv$ ) or ( $\vvv$ ≒ $-$ 旧 $\,\vvv$ )
break
$\dps{\lambda=\frac{(\vvv,A\vvv)}{(\vvv,\vvv)}}$
$(\lambda,\vvv)$ を出力

ただし

$(\xxx,\yyy)$ は標準内積

$\dps{(\xxx,\yyy)=\sum_{i=1}^n\,x_i\,y_i}$ を表します。

実行例

Ex.7　3次行列

$\dps{ A=\mat{rrrrr}{\ -6 & -4 & -7 \ \\[-0.2em] -4 & -3 & -3 \ \\[-0.2em] -7 & -3 & -8 \ \\[-0.2em] } }$ の場合

実行例を見る

実行例を折りたたむ

 v  = [ 0.4984323604,  0.80980835590,  0.3094763461]
 v  = [-0.6447177816, -0.41093312268, -0.6445719128]
 v  = [ 0.6310132733,  0.36167194503,  0.6863058014]
 v  = [-0.6301415521, -0.35584999826, -0.6901394084]
 v  = [ 0.6300168634,  0.35524585187,  0.6905643609]
 v  = [-0.6300047155, -0.35518066806, -0.6906089715]
 v  = [ 0.6300033728,  0.35517374127,  0.6906137588]
 v  = [-0.6300032313, -0.35517300111, -0.6906142685]
 v  = [ 0.6300032162,  0.35517292218,  0.6906143229]
 v  = [-0.6300032145, -0.35517291376, -0.6906143287]
 v  = [ 0.6300032144,  0.35517291286,  0.6906143293]
 v  = [-0.6300032144, -0.35517291276, -0.6906143294]
 v  = [ 0.6300032144,  0.35517291275,  0.6906143294]

λ1 = -15.928508004
 v1 = [ 0.6300032144,  0.35517291275,  0.6906143294]

ただし縦ベクトルを横に表示しています。

Th.5 の証明

$A$ は対角化可能と仮定していますので、固有ベクトルたち

$\vvv_1$ ,

$\cdots$ ,

$\vvv_n$ は一次独立であり、

$\vvv$ の初期値

$\vvv_0$ は

$\dps{\vvv_0=\sum_{i=1}^n c_i\,\vvv_i=c_1\,\vvv_1+\cdots+c_n\,\vvv_n}$ と書くことができます。すると

$\dps{A\vvv_j=\lambda_j\,\vvv_j}$ ゆえ、

$k=1,2,\cdots$ に対して

$\begin{align} A^k\vvv_0 &=c_1A^k\vvv_1+\cdots+c_nA^k\vvv_n \\ &=c_1\lambda_1^k\vvv_1+\cdots+c_n\lambda_n^k\vvv_n \\ &=\lambda_1^k\left(c_1\vvv_1+c_2\left(\frac{\lambda_2}{\lambda_1}\right)^k\vvv_2+\cdots+c_n\left(\frac{\lambda_n}{\lambda_1}\right)^k\vvv_n\right) \\ \end{align}$ が成り立ちます。仮定

$(\ast)$ より

$\dps{\lim_{k\rightarrow\infty}\left(\frac{\lambda_j}{\lambda_1}\right)^k=0}$ (

$\forall\,j \geqq 2$ ) が成り立ちますので、

$A^k\vvv_0$ の方向は

$k\rightarrow\infty$ のとき

$\vvv_1$ 方向へ収束してゆきます。 Alg.6 の

$\vvv$ は

$A^k\vvv_0$ 方向の単位ベクトルですので、 (

$\pm 1$ 倍を除いて )

$\vvv_1$ 方向の単位ベクトルに収束します。
　あとは

$A\vvv=\lambda\vvv$ から

$\dps{\frac{(\vvv,A\vvv)}{(\vvv,\vvv)}=\frac{(\vvv,\lambda\vvv)}{(\vvv,\vvv)}=\frac{\lambda(\vvv,\vvv)}{(\vvv,\vvv)}=\lambda}$ が得られます。

前へ / 戻る / 次へ