計算アルゴリズム 計算理工学専攻　張研究室 山本有作.

Presentation on theme: "計算アルゴリズム 計算理工学専攻　張研究室 山本有作."— Presentation transcript:

1 計算アルゴリズム 計算理工学専攻　張研究室 山本有作

2 物理における数値計算 解析的に求められない式の計算 データ解析 シミュレーション 数値計算の必要性 非線形方程式の解
積分で表示された式の値の計算 データ解析 最小二乗法による実験データのフィッティング フーリエ変換を用いた結晶解析 シミュレーション 分子動力学シミュレーション 流体シミュレーション たとえ実験系であっても，様々な場面で数値計算は必要になってくる。 数値計算の必要性

3 数値計算とは 数値計算とは 計算の対象 計算の手順 方程式など数学的に定式化された問題の解を計算機を用いて求めること
計算機のメモリ内に格納された数値 計算の手順 有限回の演算を用いて（近似的な）解を返すように設計された計算手順（アルゴリズム）

4 数値計算における有限性 表現できる数値の有限性 無限大・無限小が扱えない 計算能力・記憶領域の有限性 表現できる数値は実数の一部のみ
丸め誤差の存在　→　今回の授業で解説 無限大・無限小が扱えない 無限級数の和は有限級数で近似 微積分で現れる無限小は有限の微小量で近似 打ち切り誤差の存在　→　今回の授業で解説 計算能力・記憶領域の有限性 実用的な時間・記憶領域で計算するためには，効率的なアルゴリズムが必要 収束の次数の概念 計算量のオーダーの概念 有限性ゆえの固有な様々な問題が出てくる。 上２つは原理的なもの。 最後は，原理的ではないが，実用上からの制約。 では有限なら何でもいいかというと，そうではない。実用性からの要求もあり。

5 授業で学ぶこと 基本的な数値計算法 アルゴリズムの振る舞いの解析 各アルゴリズムの適用範囲 各アルゴリズム使用の際の注意事項 アルゴリズム
数学的原理 アルゴリズムの振る舞いの解析 計算量 記憶領域 誤差 各アルゴリズムの適用範囲 各アルゴリズム使用の際の注意事項 単にアルゴリズムがこうなっていると学ぶのではなく，なぜそれで計算できるのかという数学的原理もきちんと理解する。

6 授業の構成 数値計算における誤差 非線形方程式の解法 関数の補間 数値積分法 数値微分法と加速法 常微分方程式の解法 偏微分方程式の解法
連立一次方程式の解法 固有値の計算法 前のスライドで述べたようなことを念頭におきながら，次のような解法を勉強する。

7 テーマ間の関連 偏微分方程式 固有値の計算 常微分方程式の解法 連立一次方程式 非線形方程式 数値積分法 数値微分法と加速法 関数の補間
・関連図を示す。 ・実は必ずしも矢印の根元から先の方へ，授業が進むわけではない。親しみやすいトピックから先に話をしたり，あるいは，偏微分方程式のように，物理的な重要性がわかりやすい問題から先に話をして，それに必要な計算法として，連立一次方程式の話をすることもある。 ・ただし，各回の授業を聞くに当たっては，この図を思い出して，その回で勉強したことがどんなふうに使われるのかを頭に置いて欲しい。 数値微分法と加速法 関数の補間 数値計算における誤差

8 授業の進め方(1) レポート 中間テスト ２回出題 提出は授業後10日以内に5号館6階625号室まで 前半の講義内容について簡単な問題を出題
11/19 に実施予定

9 授業の進め方(2) 期末テスト 質問シート 通常の筆記テスト（昨年度のHPを参照） 出題範囲は本講義全体 出題募集（希望者のみ）
期末試験には，受講者が出題した問題を含める。 出題者には，出題された問題の良さに応じて成績（A，B，Cなど）を保証 質問シート 授業の終わりの５分間に，感想，質問，コメントなどを紙に書いて提出 全部で２、３回実施予定 この授業では，新しい試みとして，学生さんによる授業ノート作りをお願いしたい。 ノート担当は，ぜひ積極的に。 こちらで必要な補足などを行ってから，HPに載せる。

10 授業の進め方(3) 授業のホームページ 質問など http://www.na.cse.nagoya-u.ac.jp/~yamamoto
　　/lectures/algorithms2007/algorithms2007.html 授業ノート，C/Javaプログラム，授業に関するお知らせ等は，すべてホームページに掲載の予定 質問など 5号館6階625号室　山本まで あるいはメールで

11 数値計算に関する参考書 水島二郎，柳瀬眞一郎： 「理工学のための数値計算法」，数理工学社，2002.
水島二郎，柳瀬眞一郎：　「理工学のための数値計算法」，数理工学社，2002. 杉浦洋：　「数値計算の基礎と応用」，サイエンス社，1997. 伊理正夫，藤野和建：　「数値計算の常識」，共立出版，1985. 山本哲朗：　「数値解析入門」，サイエンス社，1976. 森正武：　「数値解析（第２版）」，共立出版，2002.

12 情報落ちの例 S =Σi=1n(1/i2) の計算結果（単精度） ・n = 4097で情報落ち。 ・nをそれ以上増やしても，
1000 2000 3000 4000 4097 5000 10000 50000 100000 ・n = 4097で情報落ち。 ・nをそれ以上増やしても， 　和の値は増加しない。 n = ∞の真値

13 情報落ちを防ぐ方法 (1) S =Σi=n1 (1/i2) の計算結果（単精度） ・小さい値の項から足して いくことで，情報落ちが
1000 2000 3000 5000 10000 100000 ・小さい値の項から足して 　いくことで，情報落ちが 　生じにくくなる。 ・nを増やすと，和の値も 　順調に増加する。 n = ∞の真値

14 情報落ちを防ぐ方法 (2) S =Σi=1n(1/i2) の計算結果（単精度と倍精度） n 計算結果（単精度） 計算結果（倍精度） 1000
2000 3000 4000 4097 5000 10000 50000 100000 n = ∞の真値