数値計算 京都大学大学院情報学研究科 大木 健太郎 連絡先： [email protected] 第12回 ・ ３重対角行列の固有値問題 ・ 特異値問題 本日の内容 対称行列の固有値問題 ３重対角行列の固有値 二分法（バイセクション法） べき乗法 Wielandt の逆反復法 特異値分解 dqds法 mdLVs法 2014/07/03 数値計算：第十二回 ３重対角行列の固有値問題 ２分法（バイセクション法） べき乗法 Sturm の方法で固有値を求める 固有値の絶対値が最大の固有値と固有ベクトル を求める方法 Wielamdtの逆反復法 固有ベクトルを求める方法 2014/07/03 数値計算：第十二回 ３重対角行列と特性方程式 ３重対角行列 次の代数方程式（特性多項式）の根が行列 A の固有値 あまり嬉しくない 2014/07/03 数値計算：第十二回 主小行列式の関係 ３重対角行列 計算量の低減 ⇒ 数値誤差の低減 2014/07/03 数値計算：第十二回 Sturm列と固有値の数の関係 補題3.2 一般性を失わない とする．このとき， 多項式の列 実軸上の閉区間においてSturm 列をなす は 定理3.1 区間 [a, b] が与えられ，pn(a) ≠ 0，pn(b) ≠ 0 とする． N(λ) : λ∈[a, b] を固定した列{ pn(λ)， pn-1(λ)，…， p0(λ)} における符号変化の回数 区間[a, b] に含まれる行列 A の固有値の数 n0 は， 2014/07/03 数値計算：第十二回 ２分法（バイセクション法） 区間[a, b]を２等分しながら，Sturmの方法で 固有値の存在する区間を探索する方法． 十分狭い区間に追い込めば，固有値の近似 値が得られる 初期区間は，例えば教科書 p. 16の固有値の 存在範囲を基に決めればよい 2014/07/03 数値計算：第十二回 ２分法の補足 代数方程式の解は係数に対して敏感 ⇒ 丸め誤差があると，解は大きく変わりうる （例） 倍変わる 特性方程式を直接用いたくないのは，計算に よる数値誤差を減らしたいため 2014/07/03 数値計算：第十二回 本日の内容 対称行列の固有値問題 ３重対角行列の固有値 二分法（バイセクション法） べき乗法 Wielandt の逆反復法 特異値分解 dqds法 mdLVs法 2014/07/03 数値計算：第十二回 べき乗法 固有値の大きい方から数個の固有値，固有 ベクトルを求める方法 固有値 適当な初期値から出発 固有ベクトル 2014/07/03 数値計算：第十二回 べき乗法 固有値と固有ベクトルの関係 １未満 2014/07/03 数値計算：第十二回 べき乗法 原理的には，u1成分を除いて同じように第二 の固有値 λ2 と固有ベクトルを求められる 数値誤差があると，第一固有値の成分が大き くなってくるため，数個程度の固有値・固有ベ クトルを求めるために使われる 2014/07/03 数値計算：第十二回 本日の内容 対称行列の固有値問題 ３重対角行列の固有値 二分法（バイセクション法） べき乗法 Wielandt の逆反復法 特異値分解 dqds法 mdLVs法 2014/07/03 数値計算：第十二回 Wielandtの逆反復法： 固有ベクトルを求める方法 固有値 λs の近似値 μ が得られた場合， べき乗法が使える： 逆行列を求めておくか，次の連立一次方程式を 各ステップで解くことで固有ベクトルが得られる 2014/07/03 数値計算：第十二回 本日の内容 対称行列の固有値問題 ３重対角行列の固有値 二分法（バイセクション法） べき乗法 Wielandt の逆反復法 特異値分解 dqds法 mdLVs法 2014/07/03 数値計算：第十二回 特異値分解 特異値を求める問題は工学で頻繁に出会う 主成分分析（データサイエンス，統計学） システム同定（システム制御） よく用いられる方法： dqds法(Differential Quotient Difference with Shifts) 数値的安定性，計算速度，精度が良い 2014/07/03 数値計算：第十二回 特異値分解の概要 行列 A を直交行列を用いて上２重対角化 上２重対角行列の特異値分解 Householder法を繰り返して 上２重対角化 乗算・加減算ともに 回程度 2014/07/03 数値計算：第十二回 上２重対角行列の特異値問題 dqds法の導出の概要 にシフト付きCholesky LR法を用いる 2014/07/03 数値計算：第十二回 dqds法の導出法 Cholesky分解 対角成分 非対角成分 ゼロに収束 2014/07/03 数値計算：第十二回 dqds 法のアルゴリズム（要素毎） Bk の r 行 r 列を除いて r−１次の行列に対して 同じようにして求める 2014/07/03 数値計算：第十二回 特異値分解の補足 特異値分解の詳細は， [杉原，室田： 線形計算の数理，岩波書店] と，その参考文献を参照されたい 特異値分解のアルゴリズムは，物理学とも関 連がある（ソリトン，可積分系）． mdLVs法（modified discrete Lotka-Volterra with shift） 2014/07/03 数値計算：第十二回 mdLVs法 修正シフト付き離散 Lotka-Vilterra 法 （2006年） (modified discrete Lotka-Volterra with shift) 適切に選ばれた に対し， メリット • 数値誤差：dqds法よりよい • スピード： dqds法より少し遅い • 重複特異値の収束性の保証 対角行列に収束 Iwasaki M. and Nakamura Y., ``Accurate computation of singular values in terms of shifted integrable schemes,” Japan J. Indust. APPl. Math. 23 (2006), 239-259. 2014/07/03 数値計算：第十二回 Lotka-Volterra方程式 被食者（e.g., シマウマ），捕食者（e.g., ライオン）の 平均数の方程式 x : 被食者 y : 捕食者 Lotka-Volterra 方程式 dLVs法で t を固定して を満たすようにパラメータを変化させると， 有限 Lotka-Volterra 方程式へ収束 2014/07/03 数値計算：第十二回 次回の講義予定 関数近似：最小二乗法，直交多項式 2014/07/03 数値計算：第十二回
© Copyright 2024 ExpyDoc
