数値解析 第14回 (1)　手計算と同じ方法
戻る / 次へ

手計算のアルゴリズム

　$n$ 次正方行列 $A$ の固有値・固有ベクトル $(\lambda_j,\vvv_j)$ ( $j = 1,2,\cdots,n$ ) を手計算で 求めるアルゴリズムは次の通りでした：
Algorithm 1　
  1. 固有多項式 $\varphi_A(x)=\det(xE-A)$ を求める
  2. 固有方程式 $\varphi_A(x)=0$ の $n$ 個の解 $\lambda_1$, $\lambda_2$, $\cdots$, $\lambda_n$ を求める
  3. 各 $\lambda_j$ に対し $(\lambda_j E-A)\vvv=\ooo$ の非零解 $\vvv_j$ を求める
これをコンピュータで実現しましょう。

1° 固有多項式 $\varphi_A(x)$ の計算

　多項式の計算なので数式処理ソフトを使おう、と思うかもしれませんが、 汎用性とのトレードオフで、行列サイズが大きくなると結構な計算時間が掛かるのが普通です。
　次のアルゴリズムを使うと数式処理ソフトが無くても大丈夫です：
Algorithm 2 ( Frame 法 ) ( Faddeev-Leverrier 法 とも言う )
入力：$n$ 次正方行列 $A$
出力：$A$ の固有多項式 $\varphi_A(x)=x^n+c_1\,x^{n-1}+\cdots+c_n$ の係数

   $X=E$
   for $k=1$ to $n$
     $X=AX$
     $c_k=-$tr$(X)\,/\,k$
     $X=X+c_kE$

ただし、正方行列 $X=(x_{ij})$ に対し $\mbox{tr}(X)$ は対角成分の和 $\dps{\sum_i x_{ii}}$ を表します。
Ex.3　2次行列 $\dps{A=\mat{cc}{a & b \\ c & d}}$ の場合
Ex.4　5次行列 $\dps{ A=\mat{rrrrr}{\ -4 & 6 & -9 & -6 & -8\ \\[-0.2em] 4 & -9 & 5 & 4 & 4\ \\[-0.2em] 4 & -2 & 8 & 3 & -1\ \\[-0.2em] 1 & 0 & 9 & -1 & 2\ \\[-0.2em] -2 & -7 & 1 & 1 & 6\ } }$ の場合
( Alg.2 の証明は例えば Graduate Texts in Mathematics 138, pp.53-54 にあります。)

2° 固有方程式 $\varphi_A(x)=0$ の解の計算

　これはニュートン法でできます。

※　第3回 Rem.12 で述べたように 複素数解もニュートン法で得られますが、 C言語なら complex.h を include するか、自分で複素数ライブラリを作るかしなければなりません。 Python なら complex 型が標準で使えます。

3° $(\lambda_j E-A)\vvv=\ooo$ の非零解の計算

　$(\lambda_j E-A)$ が逆行列を持ちませんので、 この講義で紹介したガウスの消去法などはそのままでは使えません。 ひとつの手としては
  • $i=$ ランダムな番号 ( $1 \leqq i \leqq n$ )
  • $\vvv$ の第 $i$ 成分 $=1$
と仮定して、$\vvv$ の他の $n-1$ 個の成分に関する連立一次方程式を解く、 ということが考えられます。( 固有値 $\lambda_j$ が重解である場合にはさらに工夫が必要です。)

戻る / 次へ