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

Slides:



Advertisements
Similar presentations
Determining Optical Flow. はじめに オプティカルフローとは画像内の明る さのパターンの動きの見かけの速さの 分布 オプティカルフローは物体の動きの よって変化するため、オプティカルフ ローより速度に関する情報を得ること ができる.
Advertisements

有限差分法による 時間発展問題の解法の基礎
Fill-in LevelつきIC分解による 前処理について
概要 基礎理論 1.応力とひずみおよび平衡方程式 2.降伏条件式 3.構成式(応力-ひずみ関係式)
Finger patternのブロック化による 陰的wavelet近似逆行列前処理の 高速化
4.3 連立1次方程式   Ax = b   (23) と書くことができる。
スペクトル法による数値計算の原理 -一次元線形・非線形移流問題の場合-
AllReduce アルゴリズムによる QR 分解の精度について
重力3体問題の数値積分Integration of 3-body encounter.
「データ学習アルゴリズム」 第3章 複雑な学習モデル 3.1 関数近似モデル ….. … 3層パーセプトロン
上坂吉則 尾関和彦 文一総合出版 宮崎大輔2003年6月28日(土)
「基礎OR」/「OR演習」 第3回 10/13/2009 森戸 晋.
PCクラスタ上での 連立一次方程式の解の精度保証
流体のラグランジアンカオスとカオス混合 1.ラグランジアンカオス 定常流や時間周期流のような層流の下での流体の微小部分のカオス的運動
理学部情報科学科 金田研究室 指導教官 金田 康正 工藤 誠
(ラプラス変換の復習) 教科書には相当する章はない
第6章 カーネル法 修士2年 藤井 敬士.
原子核物理学 第4講 原子核の液滴模型.
サポートベクターマシン によるパターン認識
高次元データの解析 -平均ベクトルに関する検定統計量の 漸近分布に対する共分散構造の影響-
非エルミート 量子力学と局在現象 羽田野 直道 D.R. Nelson (Harvard)
独立成分分析 1.問題は何か:例:解法:全体の見通し 2007/10/17 名雪 勲.
電磁波 アンテナ.
第9章 混合モデルとEM 修士2年 北川直樹.
電磁気学C Electromagnetics C 5/28講義分 電磁波の反射と透過 山田 博仁.
古典論 マクロな世界 Newtonの運動方程式 量子論 ミクロな世界 極低温 Schrodinger方程式 ..
超弾性体解析で現れる剛性行列の性質とその解法に関して
独立成分分析 5 アルゴリズムの安定性と効率 2007/10/24   名雪 勲.
第6章 特徴空間の変換 6.1 特徴選択と特徴空間の変換 6.2 特徴量の正規化 平成15年5月23日(金) 発表者 藤井 丈明
6. ラプラス変換.
川崎浩司:沿岸域工学,コロナ社 第2章(pp.12-22)
第7章 疎な解を持つカーネルマシン 修士2年 山川佳洋.
独立成分分析 (ICA:Independent Component Analysis )
システム制御基礎論 システム工学科2年後期.
原子核の質量 B (束縛エネルギー) 束縛エネルギー *束縛エネルギーが大きいほど安定(質量が軽い)
知能システム論I(13) 行列の演算と応用(Matrix) 2008.7.8.
量子系における 確率推論の平均場理論 田中和之 東北大学大学院情報科学研究科
電気回路学Ⅱ コミュニケーションネットワークコース 5セメ 山田 博仁.
量子力学の復習(水素原子の波動関数) 光の吸収と放出(ラビ振動)
主成分分析 Principal Component Analysis PCA
多変量解析 ~主成分分析~ 1.主成分解析とは 2.適用例と解析の目的 3.解析の流れ 4.変数が2個の場合の主成分分析
変換されても変換されない頑固ベクトル どうしたら頑固になれるか 頑固なベクトルは何に使える?
ポリゴンメッシュ (2) - 変形と簡略化- 東京大学 精密工学専攻 大竹豊 資料および授業の情報は :
連続体とは 連続体(continuum) 密度*が連続関数として定義できる場合
パターン認識特論 担当:和田 俊和 部屋 A513 主成分分析
FEM勉強会 (第3回).
部分的最小二乗回帰 Partial Least Squares Regression PLS
プロセスデータ解析学5 -主成分分析- 担当:長谷部伸治     金 尚弘.
電磁気学Ⅱ Electromagnetics Ⅱ 8/11講義分 点電荷による電磁波の放射 山田 博仁.
© Yukiko Abe 2015 All rights reserved
知識科学研究科 知識システム構築論講座 林研究室 佛明 智
4. システムの安定性.
ナップサック問題 クマさん人形をめぐる熱いドラマの結末.
第3章 線形回帰モデル 修士1年 山田 孝太郎.
サポートベクターマシン Support Vector Machine SVM
Max Cut and the Smallest Eigenvalue 論文紹介
土木計画学 第12回(1月14日) 計画における代替案の作成2 担当:榊原 弘之.
α decay of nucleus and Gamow penetration factor ~原子核のα崩壊とGamowの透過因子~
原子核物理学 第7講 殻模型.
C:開放,L:短絡として回路方程式を解く
Jh NAHI 横田 理央 (東京工業大学) Hierarchical low-rank approximation methods on distributed memory and GPUs 背景  H行列、H2行列、HSS行列などの階層的低ランク近似法はO(N2)の要素を持つ密行列をO(N)の要素を持つ行列に圧縮することができる。圧縮された行列を用いることで、行列積、LU分解、固有値計算をO(Nlog2N)で行うことができるため、従来密行列の解法が用いられてきた分野では階層的低ランク近似
メモリ使用量の少ないGCR法の提案 東京大学理学部情報科学科 工藤 誠 東京大学情報基盤センター 黒田 久泰
【第六講義】非線形微分方程式.
密行列固有値解法の最近の発展 (I) - Multiple Relatively Robust Representation アルゴリズム - 2004年11月26日 名古屋大学 計算理工学専攻 山本有作 日立製作所の山本有作です。 「~」について発表いたします。
モデルの微分による非線形モデルの解釈 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
パターン認識特論 カーネル主成分分析 和田俊和.
わかりやすいパターン認識 第6章 特徴空間の変換 6.5 KL展開の適用法 〔1〕 KL展開と線形判別法 〔2〕 KL展開と学習パターン数
How shall we do “Numerical Simulation”?
Orientifolding of IIB matrix model
目次 はじめに 収束性理論解析 数値実験 まとめ 特異値計算のための dqds 法 シフトによる収束の加速
Presentation transcript:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

収束性の数値実験結果 h 1/8 1/16 1/32 1/64 非対称前処理 41 58 113 258 対称前処理 70 127 541 2次元非圧縮性超弾性体問題に対する収束までの 反復回数 (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に比例している。 対称前処理は、非対称の2倍の反復数を要する。

対称問題の場合(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)

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

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

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

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

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

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