制約条件付問題より生じる 線形方程式反復解法 の 理論的な諸問題について

Presentation on theme: "制約条件付問題より生じる 線形方程式反復解法 の 理論的な諸問題について"— Presentation transcript:

1 制約条件付問題より生じる 線形方程式反復解法 の 理論的な諸問題について
鷲尾　巧　（ＪＳＴ・東京大学） 久田　俊明、鈴木　健二（東京大学）

2 制約条件付き変分問題 で生じる行列 エネルギー: の制約条件: のもとでの変分問題を考える。

3 ラグランジュ未定乗数法 以下の汎関数の停留点を求める。
ラグランジュ未定乗数法でも変分問題の解を求めるわけであるが、後にみるように係数行列は不定値になる。 保存則が含まれる方程式系では、ラグランジュ未定乗数法が陽に適用されていないにせよ、上のような構造の行列が現れる。

4 例えば回路問題の場合 第二式は電流の保存則を示すキルヒホフの法則 中心点での電圧ｖがラグランジュ未定乗数に対応する。

5 制約条件付き問題の固有値は？ 対称行列での場合
シルベスターの慣性律より正の固有値数はdim(A), 負の固有値数はrank(B) C=0 の場合は　Bx = λyとなるので以下のように固有値は評価できる。

6 制約条件付き問題の固有値は？ 歪対称化した場合
固有値は右半面に入るが、虚軸方向の分布が大きくなる可能性がある。

7 安定な離散化とは？ 小さな残差ｒが大きな誤差eを生まない!! 楕円型方程式の場合は メッシュサイズｈに依存しない定数ｃが存在して
ラグランジュ未定乗数に関しては

8 安定性のためにＡとＢが満たすべき条件は？
C=0 の場合を考える。 Shの最小固有値をλｈその固有ベクトルをehとすると λｈがhに依存せずに下から抑えられなければならない。

9 inf-sup条件 Shの最小固有値がｈに依存せず下から抑えられる。 ｈに依存しないδ>0が存在して

10 inf-sup条件は簡単には満たされない（例１）
[-1,1] [1,1] 上の非圧縮性制約条件式を四角形要素上で 圧力ｐに対しては定数で、 流速ｖに対しては双一次関数で補間し、 離散化したとする。 δp [-1,-1] [1,-1] BBTを計算してみると縦横方向がdecoupleした行列が生成される。 2

11 Cavity flow問題での圧力振動例 Tol = 1.e-6 Tol = 1.e-10 Tol = 1.e-8

12 ペナルティ法 vs ラグランジュ未定乗数法 yは簡単に消去できて、以下の正定値問題に帰着できる。
これはペナルティ法の考え方に他ならないように見える。 しかし、BTBはランク落ちの行列であるため、上記係数行列の条件数は小さなεに対して極端に悪くなる。 逆に、ペナルティ法で与えられた問題を逆の変形をたどってラグランジュ型にすることにより固有値が分離され解き易くなるのでは？ 体積変化に関わるポテンシャル項 例：

13 二つの前処理行列 ILU factorization with special fill-ins
Inexact block LU factorization

14 P1におけるフィルインの決定法 j (bi,bk,bj)=(block(i),block(k),block(j)) k i
Allowed fill-ins (2,1,1) , (1,1,2) Level 0 or 1 (2,1,2) All fill-ins (1,1,1), (2,2,2) No fill-ins

15 P1における分解安定性について 以下のような場合ILU分解でDBにマイナス成分が現れる
-　inf-sup条件が満たされていないか十分な安定化が施されていない。 - メッシュが破綻している。この場合は、 DAですでに逆符号が現れる。

16 ILU分解の安定性とM-matrix 理論的にILU分解の安定性が保証されている代表的な行列クラスとしてM行列が挙げられる。
AがM行列であるための条件 ILU分解のアルゴリズム しかし、有限要素離散化の場合は、Poisson方程式においてさえ２番目の条件は満足されない。一方で、高次の要素を用いない限りは、複雑なポテンシャルで定義される連続体でさえ、ほとんどの場合ILU分解は安定となっている。 より本質的なILU分解安定性の条件はないか？

17 P1-1Kの固有値分布の評価 ILU分解が成功した場合には、いつもP1-1Kの固有値は右半面に分布しているが、どうしてか？
この部分の正定値性が保証できない。

18 P2 におけるQA とQB の作成法について BA-1BTは密行列、しかしinf-sup条件のことを考えると条件数はO(1) 例えば：

19 P2-1Kの固有値分布の評価

20 前処理に対する二つの考え方 P-1Kを単位行列に近づけようとする考え方 前処理後も対称性を保存しようとする考え方
前処理後の行列の対角ブロックは正定値、非対角ブロックは歪対称となる。 前処理後も対称性を保存しようとする考え方 前処理後の行列は対称、しかし第２対角ブロックは負値行列となる。

21 収束性の数値実験結果 h 1/8 1/16 1/32 1/64 非対称前処理 41 58 113 258 対称前処理 70 127 541
２次元非圧縮性超弾性体問題に対する収束までの 反復回数　（tol=1.e-8) 4/3c （MINI)要素 h 1/8 1/16 1/32 1/64 非対称前処理 41 58 113 258 対称前処理 70 127 541 どちらの場合も反復数は、ほぼ1/hに比例している。 対称前処理は、非対称の２倍の反復数を要する。

22 対称問題の場合（CG, MINRES法） CGの場合 MINRESの場合 a b
a=O(h2), b=O(1)ならば　＃Iterations=O(1/h) c d a b MINRESの場合 c=O(h2), a,b,d=O(1)ならば 　#Iterations=O(1/h)

23 前処理された行列の固有値分布 対称前処理の場合

24 前処理された行列の固有値分布 非対称前処理の場合
非対称の場合は、固有値分布の評価より妥当な反復数評価（O(1/h))を得ることは困難。

25 局所的な緩和法は安定化か？ 係数行列Ａが対称である限りは、上の等式は成立するが、Ａが不定値の場合は、安定性が不明。
局所的な緩和法はMultigrid法にとって重要

26 Element by Element緩和法の可能性
久田研究室　鈴木　健二　博士論文より C=εh2Δhが適当な大きさならば安定な緩和法が実現できる。

27 P2の安定性解析 ノルムを定義する行列

28 あらゆる問題に登場する制約条件 連続体 非圧縮性 電磁気 電荷や磁荷の保存 回路問題 キルヒホフの法則 量子力学 パウリの排他律
連続体　非圧縮性 電磁気　電荷や磁荷の保存 回路問題　キルヒホフの法則 量子力学　パウリの排他律 固有値問題も