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

Slides:



Advertisements
Similar presentations
2. 数値微分法. 数値微分が必要になる場合として、次の 2 つが考えられる。 関数が与えられていて、その微分を近似的に計算する。 (数値微分の精度が十分で、かつ、計算速度が数値微分の方が 早い場合など。) 離散的な点の上で離散的なデータしかわかっていない関数の微 分を近似的に計算する。(偏微分方程式の数値解を求めたい時.
Advertisements

摂南大学理工学部における 数学教育と EMaT への取組み 東武大、小林俊公、中津了勇、島田伸一、寺本惠昭、友枝 恭子 ( 摂南大学理工学部 基礎理工学機構 ) 日本工学教育協会 第 63 回年次大会 2015 年 9 月 4 日 ( 金 ) 9:30-9:45.
数値解析シラバス C言語環境と数値解析の概要(1 回) C言語環境と数値解析の概要(1 回) 方程式の根(1回) 方程式の根(1回) 連立一次方程式(2回) 連立一次方程式(2回) 補間と近似(2回) 補間と近似(2回) 数値積分(1回) 数値積分(1回) 中間試験(1回) 中間試験(1回) 常微分方程式(1回)
放射線の計算や測定における統計誤 差 「平均の誤差」とその応用( 1H) 2 項分布、ポアソン分布、ガウス分布 ( 1H ) 最小二乗法( 1H )
新設科目:応用数学 イントロダクション 情報工学科 2 年前期 専門科目 担当:准教授 青木義満.
Computational Fluid Dynamics(CFD) 岡永 博夫
研究内容の紹介 電磁場の計算機シミュレーション 卒業研究 研究室の紹介
プログラミング演習II 2004年11月 30日(第6回) 理学部数学科・木村巌.
有限差分法による 時間発展問題の解法の基礎
工学部 知能情報工学科 准教授 高 尚策 (コウ ショウサク)
確率・統計Ⅰ 第11回 i.i.d.の和と大数の法則 ここです! 確率論とは 確率変数、確率分布 確率変数の独立性 / 確率変数の平均
応用数理工学特論 - コンピュテーショナル・ファイナンスの基礎 -
Finger patternのブロック化による 陰的wavelet近似逆行列前処理の 高速化
スペクトル法による数値計算の原理 -一次元線形・非線形移流問題の場合-
Scilab で学ぶ  わかりやすい数値計算法 舞鶴高専 電子制御工学科 川田 昌克.
AllReduce アルゴリズムによる QR 分解の精度について
重力3体問題の数値積分Integration of 3-body encounter.
東京工業大学 機械制御システム専攻 山北 昌毅
情報数理Ⅱ 平成27年9月30日 森田 彦.
身近にある曲線や曲面の数理的構造に興味を持ったら,
第二回 連立1次方程式の解法 内容 目標 連立1次方程式の掃出し法 初期基底を求める 連立1次方程式を掃出し法を用いてExcelで解析する
Mathematica入門 数学を数式処理システムで 上智大学理工学部 大槻東巳 TA: 吉本行気,清水元気 2012年6月.
4.2 連立非線形方程式 (1)繰返し法による方法
計算の理論 I -講義について+αー 月曜3校時 大月美佳.
数値解析シラバス C言語環境と数値解析の概要(1回) 方程式の根(1回) 連立一次方程式(2回) 補間と近似(2回) 数値積分(1回)
応用数理工学特論 線形計算と ハイパフォーマンスコンピューティング
流体のラグランジアンカオスとカオス混合 1.ラグランジアンカオス 定常流や時間周期流のような層流の下での流体の微小部分のカオス的運動
非線形方程式の近似解 (2分法,はさみうち法,Newton-Raphson法)
応用数理工学特論 線形計算と ハイパフォーマンスコンピューティング
電気回路学Ⅱ エネルギーインテリジェンスコース 5セメ 山田 博仁.
電気回路Ⅱ 演習 特別編(数学) 三角関数 オイラーの公式 微分積分 微分方程式 付録 三角関数関連の公式
Ibaraki Univ. Dept of Electrical & Electronic Eng.
応用数理工学特論 線形計算と ハイパフォーマンスコンピューティング
計算アルゴリズム 計算理工学専攻 張研究室 山本有作.
情報科学 第6回 数値解析(1).
応用数学 計算理工学専攻 杉原研究室 山本有作.
奈良女子大集中講義 バイオインフォマティクス (9) 相互作用推定
スペクトル法の一部の基礎の初歩への はじめの一歩
数値計算ゼミの進行に 関する提案 ~実りある春にするために           新しい形のゼミを求めて~ 清水慎吾、野村光春.
プログラミング演習I ―数値解析― 平成16年度 前期 上 村 佳 嗣.
第7回 授業計画の修正 中間テストの解説・復習 前回の補足(クロックアルゴリズム・PFF) 仮想記憶方式のまとめ 特別課題について
システム制御基礎論 システム工学科2年後期.
知能システム論I(13) 行列の演算と応用(Matrix) 2008.7.8.
電気回路学Ⅱ コミュニケーションネットワークコース 5セメ 山田 博仁.
コンクリート構造学及び演習  ガイダンス 子田 康弘.
変換されても変換されない頑固ベクトル どうしたら頑固になれるか 頑固なベクトルは何に使える?
TA (teaching assistant) :尾関 伸之
情報処理Ⅱ 第2回:2003年10月14日(火).
Microsoft PowerPoint 2001 Netscape Communicator Fetch 3.03
コンクリート構造学及び演習  ガイダンス コンクリート工学研究室 岩城 一郎.
情報処理基礎A・B 坂口利裕 横浜市立大学・商学部
シミュレーション論 Ⅱ 第1回.
用例とそのコンピューター上での実行に重点を置く
講義ガイダンス 「宇宙の物質循環を理解するために使われる物理・化学・数学」
情報基礎Ⅱ (第1回) 月曜4限 担当:北川 晃.
ガイダンス 電子計算機 電気工学科 山本昌志 1E
教育学概論 第一回オリエンテーション.
情報科学 第6回 数値解析(1).
ガウス分布における ベーテ近似の理論解析 東京工業大学総合理工学研究科 知能システム科学専攻 渡辺研究室    西山 悠, 渡辺澄夫.
計算の理論 I -講義について+αー 月曜3校時 大月美佳 平成31年5月18日 佐賀大学理工学部知能情報システム学科.
実験計画法 Design of Experiments (DoE)
電気回路学Ⅱ 通信工学コース 5セメ 山田 博仁.
情報数理Ⅱ 平成28年9月21日 森田 彦.
2008年6月5日 非線形方程式の近似解 2分法,はさみうち法,Newton-Raphson法)
宿題を提出してください. 配布物:ノート 3枚 (p.49~60), 中間アンケート, 解答用紙 3枚 (1枚は小テスト,2枚は宿題用)
Cプログラミング演習 ニュートン法による方程式の求解.
計算の理論 I -講義について+αー 火曜3校時 大月美佳 平成31年8月23日 佐賀大学理工学部知能情報システム学科.
目次 はじめに 収束性理論解析 数値実験 まとめ 特異値計算のための dqds 法 シフトによる収束の加速
情報処理Ⅱ 第2回 2004年10月12日(火).
応用数学 計算理工学専攻 張研究室 山本有作.
Presentation transcript:

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

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

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

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

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

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

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

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

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

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

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

情報落ちの例 S =Σi=1n(1/i2) の計算結果(単精度) ・n = 4097で情報落ち。 ・nをそれ以上増やしても, 1000 1.64393 4846 2000 1.64443 2068 3000 1.64459 4669 4000 1.64471 3879 4097 1.64472 5323 5000 10000 50000 100000 ・n = 4097で情報落ち。 ・nをそれ以上増やしても,  和の値は増加しない。 n = ∞の真値 1.64493 0668

情報落ちを防ぐ方法 (1) S =Σi=n1 (1/i2) の計算結果(単精度) ・小さい値の項から足して いくことで,情報落ちが 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を増やすと,和の値も  順調に増加する。 n = ∞の真値 1.64493 0668

情報落ちを防ぐ方法 (2) S =Σi=1n(1/i2) の計算結果(単精度と倍精度) n 計算結果(単精度) 計算結果(倍精度) 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.64473 4087 10000 1.64483 4072 50000 1.64491 4067 100000 1.64492 4067 n = ∞の真値 1.64493 0668