目次 はじめに 収束性理論解析 数値実験 まとめ 特異値計算のための dqds 法 シフトによる収束の加速

Presentation on theme: "目次 はじめに 収束性理論解析 数値実験 まとめ 特異値計算のための dqds 法 シフトによる収束の加速"— Presentation transcript:

1 2つの最小特異値下界に対する dqds 法の収束性について 2007年3月4日 山本有作　　　　宮田考史 　 名古屋大学　大学院工学研究科　計算理工学専攻

2 目次 はじめに 収束性理論解析 数値実験 まとめ 特異値計算のための dqds 法 シフトによる収束の加速
dqds 法 + Ostrowski 型下界 dqds 法 + Brauer 型下界 数値実験 まとめ

3 はじめに 本研究で扱う問題 計算機を用いた特異値計算 特異値分解 行列を扱いやすい形に直交変換 直交変換で特異値は不変 二重対角化 対角化
二重対角化 対角化 対角成分に特異値

4 dqds 法 （The differential quotient-difference with shift method）
LR 法による 対称正定値行列の 固有値計算 特異値計算の数値解法 dqds 法 (K. Fernando and B. N. Parlett 1994) 高速 : Root free 高精度 : 減算なし　（収束を速めるシフト部分以外） ・・・ 二重対角行列 特異値 ・・・ ・・・ 相似変換 三重対角行列 固有値 = （特異値）2 非対角成分

5 dqds 法のアルゴリズム

6 目的 在来研究 (K. Aishima et al. 2006) 本研究の目的 dqds 法の収束性理論解析 大域的収束性のための条件
Johnson 下界 (C. R. Johnson 1989) 大域的な収束性保証 & 漸近的に 1.5 次収束 本研究の目的 Ostrowski 型下界 (C. R. Johnson 1989) 漸近的に？次収束 Brauer 型下界 (C. R. Johnson 1989) Nakatsukasa 下界 (Y. Nakatsukasa 2006)

7 最小特異値に対する いくつかの下界

8 シフト選択 大域的収束性の十分条件 Johnson 下界（Gerschgorin の定理） 本研究で用いるシフト 0 ≦ シフト ＜
大域的収束性保証 & 漸近的に 1.5 次収束 本研究で用いるシフト Ostrowski 型下界（Ostrowski の定理） 大域的収束性保証 Brauer 型下界（Cassini の卵形） Nakatsukasa 下界（Cassini の卵形の改良）

9 各下界の導出 (1) Johnson下界，Brauer型下界，Nakatsukasa下界 補題
三重対角行列の最小固有値に関する下界から導かれる。 補題 A，B をそれぞれ m×m の対称三重対角行列，上二重対角行列とし， lm(A)，sm(B) をそれぞれ A の最小固有値，B の最小特異値とする。このとき， 　　さらに，B の二重対角成分がすべて非零ならば，狭義の不等式が 　　成り立つ。

10 三重対角行列の最小固有値に対する下界 Gerschgorin 型下界 Brauer 型下界 Nakatsukasa 下界
Brauer の定理（Cassini の卵形） Nakatsukasa 下界 Brauer 型下界で実は j = k–1 と置いてよいことがわかるので， より

11 二重対角成分が非零の場合，これらはすべて狭義の下界
二重対角行列の最小特異値に対する下界 三重対角行列に対する3つの下界に補題を適用すると，最小特異値に対する次の3つの下界を導ける。 Johnson 下界 Brauer 型下界 Nakatsukasa 下界 sm < sm < sm < 二重対角成分が非零の場合，これらはすべて狭義の下界

12 Ostrowski 型下界では，等号が成立する場合が起こりうる。
各下界の導出 (2) Ostrowski 型下界 Ostrowski の定理 　 を非正則行列 　 に適用し，零固有値を含む領域が存在することを用いると，次の下界を導ける。 sm ≦ Ostrowski 型下界では，等号が成立する場合が起こりうる。

13 実用上は，狭義の下界を与えると考えても問題ない。
Ostrowski 型下界の等号成立条件 定理： B を二重対角成分がすべて非零の上二重対角行列とする。このとき，次の3つの条件は同値である。 (1) B に対する Ostrowski 型下界が最小特異値を与える。 (2) B に対する Ostrowski 型下界の式において，min の中の式が k によらずすべて同じ値を与える。 (3) B の正規化された右特異ベクトル，左特異ベクトルをそれぞれ x，y とするとき，|yk| = |xk+1| （1≦k≦m – 1）かつ |ym| = |x1| が成り立つ。 これより，次のことが言える。 Ostrowski 型下界の値は最小特異値に一致する状況はありうるが，それは極めて特殊な場合である。 この状況が起こったときは，容易に検知できる。 実用上は，狭義の下界を与えると考えても問題ない。

14 下界のまとめと演算量 Johnson 下界 Ostrowski 型下界 Brauer 型下界 Nakatsukasa 下界 下界 J O B

15 下界間の関係 下界 包含関係 Johnson 下界 : Ostrowski 型下界 : Brauer 型下界 :
Nakatsukasa 下界 : 包含関係 大域的収束性の保証 Johnson 下界よりも 効果的なシフト（？） より効果的なシフト

16 収束性理論解析

17 理論的な結果 定理 1 （dqds 法 + Ostrowski 型下界） 定理 2 （dqds 法 + Brauer 型下界）
漸近的に 1.5 次収束 1 反復 定理 2 （dqds 法 + Brauer 型下界） 漸近的に超 1.5 次収束 （Nakatsukasa 下界に対しても成立） ・・・

18 証明のあらすじ（Ostrowski 型下界 ，1/5）
シフトの設定法 Ostrowski 型下界 　 を使って，シフトを次のように設定。 すると，（特殊な場合を除いて） 0 ≦ sO(n) < sm　が成り立つ。

19 証明のあらすじ（2/5）

20 証明のあらすじ（3/5） n が十分大きいとき，シフト量の式が確定

21 証明のあらすじ（4/5）

22 証明のあらすじ（5/5）

23 証明のあらすじ（Brauer 型下界） 証明の道筋は Ostrowski 型下界の場合とほぼ同じ
ただし，各補題の証明において，不等式のより精密な評価が必要 特に，「ある整数 N が存在して，任意の n > N で Brauer 型下界の値が正となる」ことを示すのが難しい

24 数値実験

25 数値実験 テスト問題 計算機環境 厳密解の分かる上二重対角行列 B (n = 10)
Type 1 : (a, b) = (1.0, 0.2) Type 2 : (a, b) = (1.0, 0.02) 計算機環境 PowerPC G5 (2.0 GHz) , Memory (2.0 GB) 特異値分布が密集

26 収束次数 (Type1) Ostrowski 型下界 Brauer 型下界 Ostrowski 型下界 ： 漸近的に 1.5 次収束
Nakatsukasa 下界は，より速く収束

27 収束次数 (Type2) Ostrowski 型下界 Brauer 型下界 Ostrowski 型下界 ： 漸近的に 1.5 次収束
Nakatsukasa 下界は，より速く収束

28 収束履歴 Type 1 Type 2 Johnson 収束の速さ 1. Nakatsukasa 下界
Ostrowski Johnson Brauer 収束の速さ　1. Nakatsukasa 下界 2. Ostrowski，Brauer 型下界 3. Johnson 下界

29 まとめ 本研究では dqds 法の収束性を理論的に解析した． 数値実験より 今後の課題
Ostrowski 型下界 ： 漸近的に 1.5 次収束 Brauer 型下界 ： 漸近的に 超 1.5 次収束 数値実験より dqds 法のシフトに Ostrowski，Brauer，Nakatsukasa 下界を用いると， Johnson 下界よりも速く収束した． 今後の課題 減次を含めた場合の性能比較 より多様な行列での性能比較 より良いシフトの提案と理論解析