数値計算法について - 知識メモ

M2で受けた授業「コンピュータ実験数学（数理工学概論）」について
具体的内容はpdfがあるのでそれを見ろ

参考文献
「やさしいコンピュータ科学」
「NUMERICAL RECIPES in C」
「数値計算法の数理」
「Discrete Variational Derivative Method」

世の中に存在する方程式や微分方程式は厳密解を得ることが困難なものがほとんどなので、
数値的な近似解を得る手法を学ばなければならない．
もし金融工学に携わるなら必須なスキルであるといえるだろう．

第一回(p2)：
数値解析とは何か．
計算機の持つ有限性と、それによる限界．たとえば極限計算は無理なので、微分積分はできない．
浮動小数点で扱える値は桁の範囲が限られたもの．たとえば 100.0 + 10^(-100) なんて計算できない．
丸め誤差として切り捨てられて 100 になる．

第二回(p8)：
丸め誤差限界、非線型方程式の根の求解．
数値解で f(x) = 0 の解を求めたくても、コンピュータの有限性（離散性？）により、f(x) = 0 なる x が存在するとは限らない．
f の傾きを考慮して、マシンイプシロンと同程度くらい f(x) が小さくなれば f(x) = 0 になっているとみなす．
解法として、囲い込む手法の二分法・挟みうち法、囲い込まない手法の割線法が紹介される．

第三回(p19)：
多次元での f(x) = 0 の解の求め方．
縮小写像反復法．不動点定理を用いた求解．
反復法を用いる際の加速法．反復で解を求めるときに、解に近づくスピードを上げる．
Richardson加速、Aitken加速．Steffensen反復は縮小写像とAitken加速を混ぜた方法で、収束が早い．
汎用性が高いNewton法．わかりやすい．
ホモトピー法、連立法、Abirth法、Ozawa法

第四回(p44)、第五回(p62)：
線形代数計算．連立一次方程式の解法、固有値問題について．
連立一次方程式を効率的に解けることは重要．
後に出てくる「陰的スキーム」の計算でも使う．

第六回(p84)：
常微分方程式(ODE)の数値計算．
離散的に関数の値を求め、点をプロットしてグラフにすることもできる（差分法）．
スペクトル法的には、関数をフーリエ展開の形で得る解法も．
最も簡単で高速な解法はオイラー（Euler）法．精度は悪い．
よく知られていて簡単な解法はルンゲクッタ（Runge-Kutta）法．
これはオイラー法の修正にもなっている．
普通は４段ルンゲクッタ法が使われる．コスト的においしいので．
高階のODEは、1階連立のODEに等価に変形できるので、それを用いてルンゲクッタなどを適用する．

第七回(p95)：
線形多段解法について．
ルンゲクッタでは1つ前の点の位置と傾きしか用いずに関数を近似していったが、もっと前の情報も使おうという考え．
アダムス・バッシュフォース法、アダムス・ムルトン法（AB公式、AM公式）はそれぞれ陽的、陰的な解法．
陽的とは、反復計算で次の点を求める計算の時、u_{k+1} = f(u_{k}, u{k-1}, ...) のように陽関数表示された関数で求められること．
つまり、計算が簡単なので時間がかからない．陰的はそうでないとき．
陽的解法のほうが精度は悪い．予測子・修正子法ではこれらのいいとこどりをする．
これはルンゲクッタより速くなるようにできる．

第八回(p103)：
偏微分方程式(PDE)の数値解法．典型的な熱拡散方程式など．
有限差分法を用いる．前進差分、後退差分、中心差分．
１階差分（１階微分の近似）は工夫すればいくらでも誤差を減らせる？（その分まわりの多くの点の情報が必要で、コストはかかる）
PDEを差分近似してできる式を差分スキームと呼ぶ．
これも陽的なスキームと陰的なスキームがある．
陰的スキームでは連立一次方程式の求解が必要．
陽的スキームで安定性を得るには少し厳しめの条件が必要．
p108の陰的スキームはCrank-Nicolson差分方程式である．
p108の下の行列は正方行列ではないが、

のような正方行列を考えれば、境界条件式を含む連立方程式が考えられる．

第九回(p111)：
有限要素法．方程式ではなく、それよりも緩い条件式の「弱形式」が成り立つような近似解を考える方法．
弱形式での解がもとの方程式の解とは限らないかもしれないが．

第十回：
メッシュ生成と数値計算アルゴリズム．
Delauneyメッシュ→あんまり細長くない三角形による分割．
Voronoiメッシュ→図の点を「首都」とする．他の任意の領域の属する「国」は、一番近い「首都」が属する「国」と一致する．

第十一回：
離散変分法．構造保存解法．
もともとの偏微分方程式のもつ性質を再現することを目的のひとつとする．
構造保存解法→近似解が変にならないように（構造を保存して）微分方程式を解く手法．
例：物理現象ではエネルギーの減少など、一方向に進む何かがあるはずだが（もしくはエネルギーの保存）、
普通の離散的な手法で近似解を得るとそのようになっていないものが出てきてしまうかもしれない
これを離散的な手法（差分法など）でも成り立たせるように構成したスキームを考えるための方法．