2003/09/30

夏休み明け

# 一番ややっこしい話を 3 回ほど行う。=> 固有値問題

固有値問題

	固有値問題の意味とは.. ? ( 数学的な定式としては )
		A x = \lambda x
	となる、( 固有ベクトル x と.. ) \lambda ( 固有値 ) を求める問題

	# しかし、物理的な意味を考えると...

	天井から、糸を吊してやる
		動きは自由

	# しかし..

	二箇所固定すると... ( 楽器のげんのようなものを考える )
		動きがかなり限定される
			=> 長さの n 倍の振動しかできない ( 波長は 1/n となる )

	固有値問題の意味とは.. ? ( 物理的な定式としては )
		限定された状態 (制約条件が与えられた)で、限られた動きを調べること

	例
		(上記のげんの例で、)固有値が \labmda_1,  \labmda_2,  \labmda_3, ... の時
			振動数が最も低い ( 音 ) .. 最小の固有値 \labmda_1

	# 「固有値問題の意味」は、物理的な特性を考えないとイメージがわかない..

	地震によって、建物がたおれるかどうか ?
		建物の固有振動数 ( 固有値 ) によって決る。
			# 固有振動数が地震の最多振動数と一致すると、共振してしまい、倒れてしまう。


==

固有値問題の解法 ( text p.71 )

	問題
		A x = \lambda x	

		a11 a12 a13 x1           x1
		a21 a22 a23 x2 = \labmda x2
		a31 a32 a33 x3           x3

	から、

		a11' 0   0
		 0  a22' 0
		 0  0   a33'

	# この対角要素が固有値.. ( この時、固有ベクトルは、単位ベクトルになる.. )

	の形にすることが「解く」こと
		この行列の変形が、固有値を変えなければよい。
			相似変換 P が、そのような変換

	「相似変換」の例
		=> 座標回転 ( ゲーム機で、多用されている... )

		2 x 2 の場合
			原点を中心とした円を潰して変形してできた楕円を考える
				=> 長軸と単軸が固有ベクトルで、その長さが固有値
					これを x, y 軸と合せる作業 ( 回転 ) をすれば、
					x, y との交点が固有値となる。
					   => 「回転」は、固有値は変っていない。


==

固有値問題の種類

	行列 A は、実対称行列 を考えることが多い
		# 「対称性」は、「保存則」を意味する。
		# 問題は、実世界のものを考えており、その世界では、
		# 現象が変化しない ( 保存される.. ) ものを扱うことが多いから..

		=> (この場合..) 固有ベクトルは、互いに直交している
			# 答が正しいかどうかを判定することに利用できる。


==

相似変換による固有値問題の解法 ( p.71 )
	# 相似変換は、固有値は変えないが、固有ベクトルはかえる.. ( 変
        # えかたが回転になっている.. )

	相似変換
		A -> A' = P^{-1}AP

	二次元の場合

		A = app apq
                    aqp aqq

			# 称行行列を考えているので、apq = aqp

		回転行列 P は、
			\cos{\thita}	-\sin{\thita}
			\sin{\thita}	\cos{\thita}
		となり、P^{-1} は、実は、P^{t} ( 転置行列 ) になる。
		後は、
			

		P^{-1}AP = A = app' apq'
		               aqp' aqq'

		の対角要素以外の要素 ( apq' = aqp' ) が 0 になるように、
		P すなわち、\thita を選択すればよい。

		要素を比較して、

			apq' = apq ( c^2 - s^2 ) + ( app - aqq )sc = 0
				where
					c = \cos{\thita)
					s = \sin{\thita)
		 更に
			t = \tan{\thita} = s/c
		とおくと、
			-apq t^2 + ( app - aqq ) t + apq = 0
		という二次方程式がえられる。

		この t を求める ( 答は、二つある [ 回転して、軸を合せる方法は 二つあるので.. ]
		が、数値計算的には、絶対値の小さい方が良いことがわかっているのでそちらを取る )

		t = \frac{aqq-app)\pm \sqrt{ (aqq-app)^2+4apq }}{2apq}

		ここで、
			\phi = \frac{aqq-app}{2apq}
		とすれば、
			t = \frac{sign(\phi)}{|\pha|+\sqrt{\phi^2+1}

	n x n でも、同様な操作で、任意の要素を 0 とすることができるが...
		一つの要素を 0 にした状態で、他の要素を操作すると、折角 0 にした
		要素が、0 じゃなくなってしまう (fill in) という現象がおきる
			# このままだと、アルゴリズムが停止しない.. !!
		しかし、
			fill-in が生じても、対角要素に対して、ひ対角要素の
			絶対値が小くなる
				十分にちいさくなったらおしまい (  O(4n) )
					ヤコビ法
				n 回ではおわならい

			反復回数を減らすには..
				もっとも、大きな要素から処理すればよいが...
					最大要素を探すのは、O(n^2) なので...
						かえって損かも..

					閾値法
						最大値ではなく、ある閾
						値より大きな要素を見付
						けたら御仕舞いとする。

			# 反復回数がへっても、結果的に、計算量がふえるかも...
			
	# 小さな n ( 例えば 4x4 .. ) では、fill-in が生れないことが多い.. (??)
	# 固有値は、代数方程式と関係がある。
	#	4 次方程式までなら、公式がある関係上、fill-in がおきない (??)
	#		=> しかし、偶然 !!
	# 一般の n では、かならず、fill-in がしょうじる !!

	固有ベクトルは、P を累積すればよい。

==

今週の課題 ( 例は、p.80 )
	実対称行列の固有値問題を解く ( ヤコビ法  )
		二週間でやる。

==

固有ベクトル
	絶対値はきらない
		=> v が固有ベクトルなら、a v ( a \ne 0 ) も固有ベクトル

	(固有ベクトルを求める..) ライブラリィによって、固有ベクトルの
	正規化の方法は異なる
		=> 見掛け上、結果が異なるように見える。

==

固有値が重複していたら ?
	図形的には、「円」になる
		=> 固有ベクトルがきらない
			# だから、なんでもよいのですが...
				=> やはり、結果が異なるように見えることに注意

	# ヤコビ法を利用する場合に、操作順序によって、違う結果となる。

==

次回、ヤコビ法以外の、解法を行う。