応用数学

計算アルゴリズム
計算理工学専攻 張研究室
山本有作
物理における数値計算

解析的に求められない式の計算



データ解析



非線形方程式の解
積分で表示された式の値の計算
最小二乗法による実験データのフィッティング
フーリエ変換を用いた結晶解析
シミュレーション


分子動力学シミュレーション
流体シミュレーション
数値計算の必要性
数値計算とは

数値計算とは


計算の対象


方程式など数学的に定式化された問題の解を計
算機を用いて求めること
計算機のメモリ内に格納された数値
計算の手順

有限回の演算を用いて(近似的な)解を返すよう
に設計された計算手順(アルゴリズム)
数値計算の特徴: 有限性

表現できる数値の有限性



無限大・無限小が扱えない




表現できる数値は実数の一部のみ (Cf. π,√2)
丸め誤差の存在 → 今回の授業で解説
無限級数の和は有限級数で近似
微積分で現れる無限小は有限の微小量で近似
打ち切り誤差の存在 → 今回の授業で解説
計算能力・記憶領域の有限性



実用的な時間・記憶領域で計算するためには,効率的な
アルゴリズムが必要
収束の次数の概念
計算量のオーダーの概念
授業で学ぶこと

基本的な数値計算法



アルゴリズムの振る舞いの解析





アルゴリズム
数学的原理
計算量
記憶領域
誤差
各アルゴリズムの適用範囲
各アルゴリズム使用の際の注意事項
授業の構成
1.
2.
3.
4.
5.
6.
7.
8.
9.
数値計算における誤差
非線形方程式の解法
関数の補間
数値積分法
数値微分法と加速法
常微分方程式の解法
偏微分方程式の解法
連立一次方程式の解法
固有値の計算法
テーマ間の関連
偏微分方程式
固有値の計算
常微分方程式の解法
連立一次方程式
非線形方程式
数値積分法
数値微分法と加速法
関数の補間
数値計算における誤差
授業の進め方(1)

レポート



2回出題
提出は授業後10日以内に3号館4階479号室まで
中間テスト


前半の講義内容について簡単な問題を出題
12/8 に実施予定
授業の進め方(2)

期末テスト



通常の筆記テスト(昨年度のHPを参照)
出題範囲は本講義全体
出題募集(希望者のみ)




期末試験には,受講者が出題した問題を含める。
出題者には,出題された問題の良さに応じて成績(A,B,Cなど)
を保証
1/26締切、3号館479室まで、またはメールで
質問シート


授業の終わりの5分間に,感想,質問,コメントなどを紙
に書いて提出
全部で2回程度実施予定
授業の進め方(3)

授業のホームページ



http://www.na.cse.nagoya-u.ac.jp/~yamamoto
/lectures/algorithms2008/algorithms2008.html
授業ノート,C/Javaプログラム,授業に関するお知らせ等
は,すべてホームページに掲載の予定
質問など


3号館4階479号室 山本まで
あるいはメールで
[email protected] まで
数値計算に関する参考書

水島二郎,柳瀬眞一郎: 「理工学のための数値
計算法」,数理工学社,2002.

杉浦洋: 「数値計算の基礎と応用」,サイエンス社,
1997.

伊理正夫,藤野和建: 「数値計算の常識」,共立
出版,1985.

山本哲朗: 「数値解析入門」,サイエンス社,
1976.

森正武: 「数値解析(第2版)」,共立出版,2002.
情報落ちの例

S =Σi=1n(1/i2) の計算結果(単精度)
n
計算結果(単精度)
1000
1.64393 4846
2000
1.64443 2068
3000
1.64459 4669
4000
1.64471 3879
4097
1.64472 5323
5000
1.64472 5323
10000
1.64472 5323
50000
1.64472 5323
100000
1.64472 5323
n = ∞の真値 1.64493 0668
・n = 4097で情報落ち。
・nをそれ以上増やしても,
和の値は増加しない。
情報落ちを防ぐ方法 (1)

S =Σi=n1 (1/i2) の計算結果(単精度)
n
計算結果(単精度)
1000
1.64393 4488
2000
1.64443 4214
3000
1.64460 0749
5000
1.64473 4025
10000
1.64483 4042
100000
1.64492 4045
n = ∞の真値 1.64493 0668
・小さい値の項から足して
いくことで,情報落ちが
生じにくくなる。
・nを増やすと,和の値も
順調に増加する。
情報落ちを防ぐ方法 (2)

S =Σi=1n(1/i2) の計算結果(単精度と倍精度)
計算結果(単精度)
計算結果(倍精度)
1000
1.64393 4846
1.64393 4567
2000
1.64443 2068
1.64443 4192
3000
1.64459 4669
1.64460 0789
4000
1.64471 3879
1.64468 4098
4097
1.64472 5323
1.64468 9956
5000
1.64472 5323
1.64473 4087
10000
1.64472 5323
1.64483 4072
50000
1.64472 5323
1.64491 4067
100000
1.64472 5323
1.64492 4067
n
n = ∞の真値 1.64493 0668
安定な漸化式と不安定な漸化式
n
In(f) (不安定)
In(b) (不安定)
0
9.53101 8×10-2
9.53101 8×10-2
1
4.68982 0×10-2
4.68982 0×10-2
2
3.10180 0×10-2
3.10179 8×10-2
3
2.31533 0×10-2
2.31535 3×10-2
4
1.84670 0×10-2
1.84647 1×10-2
5
1.53300 0×10-2
1.53529 0×10-2
6
1.33667 0×10-2
1.31376 6×10-2
7
9.19010 0×10-2
真値
1.14805 6×10-2
1.14805 6×10-2
8
1.01943 9×10-2
1.01943 9×10-2
9
9.16724 9×10-3
9.16720 4×10-3
10
8.32750 6×10-3
8.32796 6×10-3
11
7.63403 2×10-3
7.62943 6×10-3
12
6.99300 7×10-3
7.03897 6×10-3