| ゴロゴロ | 2005年9月10日(土) | |
| Infoseek | ||
| 今日は曇時々雨。ゴロゴロ。 | ||
| 疲れた | 2005年9月8日(木) | |
| Infoseek | ||
| 今日は晴。疲れた。 | ||
| Riccati-Davidson法 | 2005年9月7日(水) | |
| Infoseek | ||
| 今日は雨後晴。9/3の続きだが、Arnoldi法に前処理演算子を加えて出来た方法がDavidson法、Davidson法の前処理演算に憑き物だった曖昧さを払拭した方法がJacobi-Davidson法である。さて、Jacobi-Davidson法に於ける前処理演算とは、 | ||
| [(1-xixiT)(ei-A)(1-xixiT)]ti=ri | ||
| である。この式で、riは残差、tiは前処理の結果で、部分空間の拡張に用いられるベクトルである。問題点は真の固有値eが不明な場合、その代用品としてRayleigh商eiを用いざるを得ない事。eiの収束は速い為(2次収束)、そんなに気にすべき事ではないかもしれないが、実際に計算を行うと、前処理を厳密に行う程、初期の収束の立ち上がりが遅くなる、と言った困った現象が現れる場合もある。これを乗り越えたのがRiccati-Davidson法で、前処理は | ||
| (1-xixiT)Ati-(ei+xiTAti)ti=ri | ||
| によりなされる。xiTAtiが、固有値の推定値に付きまとう曖昧さを除去する項。但し、この式は | ||
| A(xi+ti)=(ei+δei)(xi+ti) | ||
| から導出されている。これは一見、複雑そうだが、実は元の永年方程式そのもの。従ってRiccati-Davidson法はDavidson法の2重ループ化に他ならない。 | ||
| 疲れた | 2005年9月6日(火) | |
| Infoseek | ||
| 今日は曇時々雨。疲れた。 | ||
| 疲れた | 2005年9月5日(月) | |
| Infoseek | ||
| 今日は雨時々曇。疲れた。 | ||
| 今日の日経より | 2005年9月4日(日) | |
| Infoseek | ||
今日は曇後雨。日経表紙の左上には"元気な地方 衰退に克つ"と称した囲み記事がある。そこにこんな話が。
| ||
| Jacobi-Davidosn法 | 2005年9月3日(土) | |
| Infoseek | ||
| 今日は晴。暑い。昨日の続きだが、Davidson法その他で勾配即ち残差ベクトルriに対して前処理演算子Kを作用させる理由は、近似固有ベクトルxiを真の固有ベクトルxへ素早く収束させる為である。前処理演算子Kは大抵 | ||
| (ei-A)-1 | ||
| に対する近似的な演算子で、Aの対角成分のみを抜き出すとか、不完全Cholesky分解を行うとか、SSORとか、やり方はいろいろ。eiは真の固有値に対する最善の近似値即ちRayleigh商。但し事前に固有値だけを別途予想出来る場合、予想値で置き換える事も可能である。だがこの流儀には大きな問題がある。大抵、Kが(ei-A)-1に似ている程、収束も速まる。しかしもし前処理演算子が完全な演算子即ち、 | ||
| K=(ei-A)-1 | ||
| ならば、残差riが | ||
| ri=(ei-A)xi | ||
| で与えられている事に着目すると、前処理演算子Kは | ||
| xi=Kri | ||
| と言う、無駄な演算を行う事になる。この矛盾に真正面から取り組む過程で生まれたDavidson法の改良版がJacobi-Davidson法。Jacobi-Davidson法では、前処理演算子Kは | ||
| [(1-xixiT)(ei-A)(1-xixiT)]-1 | ||
| に対する近似演算子として定義される。なお通常、単にDavidson法と言う場合に現れる前処理演算子は上述の様に、Aの対角成分のみを抜き出すとか、不完全Cholesky分解を行うとか、SSORとか、ともかく逆行列を近似する行列を意味する場合が多い。而るにJacobi-Davidson法での前処理演算子とはそうした特定の演算子よりも寧ろ、連立1次方程式を反復法で解く行為を指す場合が多い。 | ||
| Davidosn法とKnyazevのLOBPCG法 | 2005年9月2日(金) | |
| Infoseek | ||
| 今日は晴。暑い。さて、今日は滅多にしない仕事の話。固有値問題 | ||
| Ax=ex | ||
|
を解く方法はいろいろとあるが、特にこの固有値問題が大規模である場合には、Krylovの部分空間から固有ベクトルを抽出する方法が用いられる場合が多い。Lanczos法·Arnoldi法はその典型だが、Davidson法もこの範疇に入る。何れの方法も、高次元即ち求める固有解の数を超えた大きさのKrylov部分空間を意識して生成する所を特徴としている。Lanczos法で固有値のみを求める場合、言い換えると固有ベクトルを求めない場合はこの限りではないが。 而るに固有値又は残差を最小化すると言う観点からは、最急·共役勾配法も使えるが、この場合対象が固有値問題、即ち線形ではないが1つの式で簡単に表現出来ている問題である点に注目すれば、勾配法で不可欠なステップ長は試行錯誤を伴う事なく、係数行列AのKrylov部分空間から決定出来る事が分かる。例えば共役勾配法に於いては | ||
| xi=a xi-1+b (xi-1-xi-2)+c K(ei-1xi-1-Axi-1) | ||
| で真の固有ベクトルxの近似解xiが生成される。Kは前処理演算子。bとcの比はFletcher-Reevesの公式等で、これらとaの比は試行錯誤的な1次元探索で決める。これが非線形共役勾配法の流儀だ。しかし、係数a·b·cをもっと効率的に決めるには、 | ||
|
M11=(xi-1)TA(xi-1) M12=(xi-1)TA(xi-1-xi-2) M13=(xi-1)TAK(ei-1xi-1-Axi-1) M22=(xi-1-xi-2)TA(xi-1-xi-2) M23=(xi-1-xi-2)TAK(ei-1xi-1-Axi-1) M33=(ei-1xi-1-Axi-1)TKTAK(ei-1xi-1-Axi-1) | ||
| を成分とする小さい行列Mの対角化が有効だ。このやり方を多数の固有ベクトルが一斉に出るべく改造すれば、KnyazevのLOBPCG法の出来上がり。だがこの方法は寧ろ、Davidson法に似ている。逆にDavidson法から迫るならば、Davidson法とは部分空間 | ||
| {xi-1, K(ei-1xi-1-Axi-1), K(ei-2xi-2-Axi-2),,,} | ||
| からxiを抽出する方法だが、実用上考えなければならない点は部分空間の大きさの上限と、上限に達した後の再出発の方法だ。そこで、部分空間の上限を求める固有解の数の3倍とし、且つ、ei-2xi-2-Axi-2以下の情報が再帰的にxi-1に含まれる事に着目しよう。そうすると | ||
| {xi-1, xi-1-xi-2, K(ei-1xi-1-Axi-1)} | ||
| も有力候補だが、これはLOBPCG法そのもの。LOBPCG法は、Davidosn法のインプリメンテーションの1つの在り方だ。しかし数値線形代数の世界では、そうした解釈が行われる事は少ない。 | ||
| 懐メロ | 2005年9月1日(木) | |
| Infoseek | ||
今日は薄曇。深夜はともかく、まだまだ暑い。日経夕刊第4面は懐メロCDの全面広告だ。題名は
| ||
| 表紙へ戻る | ||