Mathematicaによる固有値計算の高速化 Eigenvalue calculation speed by Mathematica 情報工学部 06A2055 平塚翔太 •前回のあらすじ •自己相関 •行列の対角化 •行列のスペクトル分解 •プログラムの内容 •参考文献 スライド一覧 バックグラウンド 前回のあらすじ VPN下でのストリーミング配信における人の振舞い（デー タ等の劣化によりクライアントがキャンセルかリトライす る確率）を行列化する。 Client α p rp β p : キャンセルした確率 r : リトライした確率 (1 - r)p 1-α α 行列化 0 ・・・・・・・0 β 1-α-β α ・・・・・・・・0 ・ β 1-α-β α ・・・・・・0 ・・・・・・・・・・・・・・0 0 0 0 ・・・・・・・1-β β 自己相関 同じ時系列での相関 0 1 2 3 4 5 6 7 8 9 0 秒後 ⇒ 0本 1 秒後 ⇒ 5本 2 秒後 ⇒ 3本 ： ｘk 秒後 ： ｘk+t 秒後 ｘkとｘk+tの相関グラフ ｘk+t r=0 r=1 r = -1 ｘk rを相関係数という r = 1 ： 正の相関 r = -1 ： 負の相関 r = 0 ： 相関無し t 秒時の相関係数 r (r(t))は r(t) = Cov(ｘk ,ｘk+t ) Var(ｘk ) と定義される Var(ｘk+t ) 分散（Variance） 複数のデータの二乗和を求めることで データの散らばり具合が求まる ∞ 2 Var(ｘk ) = ∑ (ｘk ) P(ｘk ) – ｘ 2 ｘk =0 P(ｘk )はある状態からｘk になる確立を表す Pとｘkの関係をグラフ化 1 P ｘk+t ≈ ・・・・ ｘk 0 1 ∞ 2 3 4 5 6 ・・・・ ｘk ｘk = ∑ ｘk P(ｘk ) ｘk =0 定常 P(ｘk 、ｘk+t )＝ P(ｘk+l 、ｘk+t+l) でどんな l でも成り立つとき P(ｘk 、ｘk+t )は定常である 共分散（ Covariance） 複数のデータの積和を求めることで データ間の関係性や連動性が求まる ∞ Cov(ｘk , ｘk+t ) = ∑ ∞ ∑ (ｘk -ｘk ) (ｘk+ｔ -ｘk+ｔ) P(ｘk , ｘk+t ) ｘk =0 ｘk+t =0 (ｘk -ｘk ) ：ｘkからｘkになる確率の変量 (ｘk+ｔ -ｘk+ｔ)：ｘk+ｔからｘk+ｔになる確率の変量 P(ｘk , ｘk+t ) ：ｘkからにｘk+ｔなる確率 また、相関係数 r (t) とデータを転送する時間 t のグラフを 以下に示す r(t) データ：長 データ：短 0 t 長いデータを転送 ⇒ 時間がかかる分、相関が比較的長い 間相関が強くなる 短いデータを転送 ⇒ 時間がかからない分、相関が比較的 すぐ相関が弱まる 行列の対角化 固有値 ある行列 A に対して「Aｘ = λｘ」を満たす ベクトルｘと、スカラーλが存在するとき、 λ：固有値 ｘ：固有ベクトル と呼ぶ。 「方向を持たない大きさ」 行列 A には固有ベクトルという方向と 固有値という大きさからなる なぜ固有値なのか？？？ ここで、固有ベクトルｘを列ベクトル S とする S = ｘ1，ｘ2，・・・，ｘn そして、対角成分に固有値を並べた対角行列をΛ とする λ1 Λ= λ2 ・ ０ ・ ・ ０ λｎ これらの行列から A S = Λ S がわかる -1 これを変形すると S A S = Λ となる この S をA の対角行列という S -1 A S = Λは、S -1Λ S = A とも書ける n ここで、行列 A を n 乗算したときA と書く n A = = = = A A A A ･･･ A SΛS -1 SΛS -1 SΛS-1 SΛS-1 ･･･ SΛS-1 SΛΛΛΛ ･･･ ΛS -1 SΛn S-1 Λ n = n λ1 n λ2 ・ ０ ※ S S -1 = I ０ ・ ・ n λｎ 固有値と固有ベクトルを用いると行列の乗算が著しく簡略化される 行列のスペクトル分解 行列 A、固有値 λ、とするとき直交する固有ベクトルを選ぶと λ1 λ2 A ｙ1，ｙ2，・・・，ｙn = ｘ1，ｘ2，・・・，ｘn 0 と表すことができる。これを λ1 A = ｘ1，ｘ2，・・・，ｘn λ2 0 と転置する。 0 ・ ・ ・ λｎ ｙ1 ｙ2 ・ ・ ・ ｙn 0 ・ ・ ・ λｎ A = λ 1 ｘ1 ｙ1 + λ 2 ｘ2 ｙ2 + ・・・ + λ n ｘn ｙn これを行列 A のスペクトル分解という ｘi ｙi ：行列 λi ：スペクトル n m m m A = λ 1 ｘ1 ｙ1 + λ 2 ｘ2 ｙ2 + ・・・ + λ n ｘn ｙn A がn乗の時の固有値λのm乗を求めることができる ｙ λ ｙi ｙi 0 ｘ ｘi λ ｘi プログラムの内容 Ｃ Ｌ Ｉ Ｅ Ｎ Ｔ 誰が（何人）キャンセル するかわからない VPN キャンセル率の最も多い時をhMAXとして定量化する 例： hMAX：キャンセル率が最大 -1 Δ ：0からhMAXを刻む数 σ ： hMAX * Δ：定量化した時の一めもり w ：配信が正常に行える最大数 el ：終了 hMAX 配信の劣化が始まる σ 0 1 2 w+1 w+2 ・・・・・・・ el ストリーミングを受けるクライアントが増加するとキャンセル 率は増加、あるいは不変な場合はあるが、減少することはない と仮定する hMAX 下がることはない 上がるか変わらないのは 有り σ 0 1 2 w+1 w+2 w+3 ・・・・・ ストリーミング配信の悪化増 el 青線のみをΔ-1+１進数で定量化する hMAX σ 0 1 2 w+1 w+2 ・・・・・ el その内の最大値(relaxmax)と最小値(relaxmin)を出力する プログラム 参考文献 相関係数と回帰直線 加藤千恵子、石村貞夫 著 秋田工業専門学校ＨＰ http://akita-nct.jp/ Wikipedia http://ja.wikipedia.org/wiki/ やさしく学べる線形代数 石村園子 著 千葉大学理学部ＨＰ http://www.math.s.chiba-u.ac.jp/ 御清聴ありがとうございました
© Copyright 2024 ExpyDoc
