2004/09/28 これから、三回、「固有値問題」を行う 対称行列 二回 9/28 演習なし 10/5 ヤコビ法 ( 二週間でやる ) 非対称行列 一回 10/12 ベキ乗方法 # 「固有値問題」は、この講義の中で、一番ややっこしい。 == 固有値問題とは、 行列 A に対して A x = \lambda x となる x, \lambda ( 共に 非 0 ) を求めること !! 物理学上、どのような意味があるか ? 地震がおきると、倒壊する建物とそうでない建物ができるのはなぜか ? 振動現象があるときに、「共振」という現象がみられる 共振する場合は、倒壊する 共振しない場合は、倒壊しない 共振する周波数を求めること 固有値 振動に於ける固有値 片側が固定されている紐の振動 色々な周波数が生れる可能性がある 両端が固定されている紐の振動 振動数に限りがある 基本周波数 \omega の定数倍しかでて来ない この基本周波数を求めることが固有値を求めること 固有値の応用には、振動にかぎらず、様々な物理現象で必要となる # 核物理とか.. 振動は、固有値問題に還元できる典型的なもの。 # この講義では、問題を解くことが中心なので、内容的には、この程度で.. 具体的に、固有値を解くということは ? 行列 a_11 a_12 a_13 A = ( a_21 a_22 a_23 ) a_31 a_32 a_33 に対して a_11 a_12 a_13 x_1 x_1 ( a_21 a_22 a_23 ) ( x_2 ) = \lambda ( x_2 ) a_31 a_32 a_33 x_3 x_3 となる x ( 固有ベクトル ) x_1 x = ( x_2 ) x_3 と、\lambda ( 固有値 ) が欲しい。 上手く変換を繰り返して、 \lambda_1 0 0 ( 0 \lambda_2 0 ) ( x_1 x_2 x_3 ) = A ( x_1 x_2 x_3 ) 0 \lambda_1 の形にできればよい。 # 前期に、連立方程式を解くこと形によくにている # [ポイント] 答が変らない式変換を繰り返して、問題を単純化すれば良い # 「連立方程式」の場合は、「連立方程式」の解を変えない式変形をした # 固有値の場合も、固有値を変えない式変形 ( 相似変換 ) をすればよい !! == 相似変換 A に対して、P^{-1}AP を求めること # 当然のことながら、P は正則 ( P^{-1} があるので.. ) 問題は、どのような P を掛ければ、単純になるか ? 相似変換の例 座標の回転 ゲームをしているときに利用される計算が実は、相似変換 二次元の固有値問題 楕円の軸の長さを計算することと同じ 一般の行列は、斜めに楕円 回転して、横にした楕円にできれば、固有値を求めることになる。 個々の軸が、固有ベクトルになっている 固有ベクトルは、互いに直交する # 斜めの絵がでてくる => 固有値問題が与えらえる # 真っ直の絵にする => 固有値問題を解く # Pentium の SSE は座標変換を行うための仕組 # 相似変換 ( ゲーム / グラフィックス ) に向いている ## 実際問題として、確かに計算は、はやくなるが、データの取り出しの方が問題なので、それほど簡単ではない.. ジャンボジェット機の固有値問題 => 19 万元 == 対称行列の固有値問題 二次元の対称行列 A = ( a_pp a_pq ) a_qp a_qq (where a_pq = a_qp とする ) これの固有値を求めるには、回転の行列 P ( \thita だけ回転 ) P = ( \cos{\thita} \sin{\thita} ) - \sin{\thita} \cos{\thita} を利用して、 P^{-1}AP = ( b_pp b_pq ) b_qp b_qq ( where b_pq = b_qp = 0 ) を計算すればよい。 # この P の決定性には任意性 ( ニ通りの解 ) がある。 # 楕円を縦にするか横にするか ? ## 問題を考えるときに、解の存在と一意性が必要になることに注意 # 普通は、回転の確度の小さいものをとる。 二次元の回転ができれば、n 次元の場合でも、一次元ずつ二次元の回転を 利用することによって、n - 1 回の回転で、n 次元の問題も解ける 二次元の問題が解ければ、n 次元も Okey 実際の計算では.. # s = \sin{\thita}, c = \cos\thita}, t = \tan{\thita} = s/c b_pq = a_pq ( c^2 - s^2 ) + ( a_pp - a_qq ) cs より、 a_pq t^2 + ( a_qq - a_pp ) t - a_pq = 0 この二次方程式を解いて、 t = \frac{\sign{\phai}}{\abs{\phai}+\sqrt{\phai^2+1}} を得る ( ただし、二つの根の内、小さい方をとっている )。 t = \tan{\thita} が求まれば、あとは、s, c も計算できる。 c = \frac{1}{\sqrt{1+t^2}} s = t c # 数学的には、\arctan を計算して、具体的に \thita を求めればよ # いのだが、 \tan は、誤差が出易い関数 ( \pi/2 の近くは大変.. # ) なので、数値計算的には、\arctan を計算したくない # => \thita を計算せずに、\sin{\thita}, \cos{\thita} を求める ## 三角関数の計算は大変 ## 普通の計算の 100 倍の計算になる ## この計算では、複雑にみえるけど、計算そのものそれほど問題ない この変換によって、一つの項目を 0 にしたあと、他の要素を 0 にしようとすると、 折角 0 にした要素がまた、非 0 にもどってしまう ( fill in ) => このままでは終らないではないか... !! 実は、この変換を行うと、必ず、対角要素の絶対値が大きくなり、対角要素 以外の要素の絶対値が小くなるので、何度か繰り返せば、非対角要素の絶対値 は、十分に 0 に近付くので、その時点で、Okey # 一番大きな、非対角要素を選べば、効率的 ( 回転の回数 # を減らせる ) なのだが.. ## 一番大きな、非対角要素を選ぶのにもコストが.. ### \epsiron 法 ### 全部なめると大変なので\epsiron より大きい要素を見付けたら、それを最大値だと思うことにする。 次元が 3 ( と 4 のとき ) は、fill in がおきない # 固有値問題は、実は、代数方程式と同値であり、代数方程式に直接 # 解法があることと、fill in がおきない方法があることは同値した # がって、5 次元以上の固有値問題は必ず、fill in が生じてしまう fill in がおきる理由 連立方程式の場合は、行と行の計算しかしない 行の結果が、列に影響しない 相似変換の場合、行と列の双方に、影響が生じる => fill in ができる理由 fill in を辟には ? # もちろん、原理的には不可だが.. 条件を緩和すればよい 三重対角要素が非 0 でよければ.. それ以外の要素を fill in なしに 0 にできる 三重対角行列だと、行列のかけ算が、密行列に比較して、非常に楽 => QR 法 ( -> QR 分解 ) => バイセクション法 ( 行列式の零点を探す ) # いずれも、三重対角行列の方が計算量が少いので有利 == 来週 Text の p. 76 のヤコビ法を使うので、今週から初めておくとよいこ の プログラムでは p. 64 にある簡易行列 Libirary も利用しな いといけない ( これがないと動かないにも係らわず、毎年、これを入れずに 「動かない」と宣う学生がいる )。今週は、これを入れておくとよいでしょう。