4 絶対値最大の固有値を求める -- 冪乗法

簡単のため $n$ 次正方行列 $A$ が対角化可能で、 その固有値を $\lambda_1$, $\cdots$, $\lambda_n$, それらに属する固有ベクトルを $u_1$, $\cdots$, $u_n$ とする。 さらに $\vert\lambda_1\vert$ は他の固有値の絶対値よりも大きいとする。

$$\vert\lambda_1\vert>\vert\lambda_i\vert\quad\mbox{($i=2,3,\cdots,n$)}$$

任意のベクトル $x\in\C^n$ は

$$x=c_1 u_1+c_2 u_2+\cdots c_n u_n$$

と展開できるが、$A^k$ を作用させると

$$A^k x=c_1 A^k u_1+c_2 A^k u_2+\cdots C_n A^k u_n =c_1 \lambda_1^k u_1+c_2 \lambda_2^k u_2+\cdots C_n \lambda_n^k u_n.$$

$k$ が大きいとき、右辺第 $1$ 項は右辺の他の項と比べて大きくなることが 分かる (ただし $c_1\ne 0$ とする)。$k$ を十分大きくすると、 右辺第2項以下は第1項と比べて無視できるほど小さくなるだろう。 すると $A^k x$ は $u_1$ の定数倍、すなわち $\lambda_1$ に属する固有ベク トルに近くなるはずである。

以上のことを Octave による計算で確かめるためには、 $A^k x$ がオーバーフローすることを防ぐため、 代りにその長さで割った $\dsp\frac{A^k x}{\Vert A^k x\Vert}$ を作ればよい。

以下では素朴に $A$ をかけていくことで $\dsp\frac{A^k x}{\Vert A^k x\Vert}$ を 求めている。

octave:5> x=ones(n,1)
octave:5> for i=1:100
> y=a*x
> x=y/norm(y)
> end
octave:5> a*x ./ x	← a*x の各成分を対応する x の成分で割ってみる
octave:5> eig(a)	← 念のため eig() で a の固有値を調べて比較

線形代数では、固有値を固有多項式の根として特徴づけるが、 普通固有多項式を数値計算で解くのは難しいので、 行列の問題のまま各種の反復法を用いることになる。 上で見た方法は『冪乗法』と呼ばれ、多くの方法の基礎となっている。