情報科学 第６回　数値解析(1).

Presentation on theme: "情報科学 第６回　数値解析(1)."— Presentation transcript:

1 情報科学 第６回　数値解析(1)

2 数値計算とは？ 代数演算 数値計算 等式を一定の規則のもとに変形して解析的に求める 反復計算によって“近似的に”解を求める
解析的に求めることが困難な方程式を解く場合に用いる 例）　物理学、化学、天文学などにおける数値積分 　　　や微分方程式の解法など

3 数値解析(1)トピック 数値計算における誤差 数値積分 微分方程式の解法

4 1. 数値計算における誤差 実数データ表現 丸め誤差 桁落ち 情報落ち 打切り誤差 浮動小数点表現
0.1の2進数表記・ 単精度表現・倍精度表現 桁落ち 情報落ち 打切り誤差 Taylor展開・級数展開の高次項の影響

5 この表記は、例えば、1.0101…010を２進数として解釈するという意味である
実数データ表現 計算機内の数値データは，有限長のビット列で表現される 大きな数や小さな数を表現するためには， 符号部と指数部，仮数部をもった実数表現　　(浮動小数点表現)が利用される IEEE 754　実数表現に関する規格 符号 仮数 指数 この表記は、例えば、1.0101…010を２進数として解釈するという意味である バイアス（指数が負の値をとれるようにするため）

6 単精度と倍精度 単精度 32ビットで実数を表現 倍精度 64ビットで実数を表現 IEEE 754 実数表現に関する規格
単精度　32ビットで実数を表現 倍精度　64ビットで実数を表現 指数部と仮数部がすべて０の実数は０（±０）を意味する このほかにも±無限大などの表現が可能 整数の大小比較回路がそのまま使える

7 丸め誤差 10進数を2進数で表現する場合、有限桁では近似的にしか表せないことに起因する誤差 例）
0.1 (10) = … = … (2) x 20 = … (2) x 2-4 0.1(10)は有限桁では近似的にしか表現できない (10進数の小数で1/3や1/7を表す場合に相当） 1/3 = … 1/7 = …

8 丸め誤差の例 誤差 # irbで以下を試してみる (0.1*3==0.3) # 上記と同じことを実現するのに以下の書き方もある
Ruby # irbで以下を試してみる (0.1*3==0.3) # 上記と同じことを実現するのに以下の書き方もある (0.1*3-0.3).zero? これは0.1の3倍が0.3に等しいかどうかを真偽で評価するための表現で 数学的には真(true)という結果になるはずであるが、実際は偽(false)となる 符号部 指数部 仮数部 0捨1入 倍精度表現では ["0", " ", " … "] 0捨1入 ["0", " ", " … "] 誤差 ["0", " ", " … "] 丸め誤差は # （検証）irbで以下を試してみよ 0.1*3-0.3 2**-54 0が52個

9 ０捨1入 ..0110011010 ..1100110100 ------------------- ..0011001110

10 単精度表現 仮数部23ビット 指数部8ビット 仮数の表現範囲は有効桁数は24ビット これは10進数で7桁程度の精度しかないことを意味する
1.00…0 (2) =1 から1.11…1(2) = ≈ x 10-7 ≈ 2 指数の表現範囲は 1.2 x から1.7 x 1038 (2) -127 =2-126 ≈ 1.2 x 10-38 (2) -127 =2127 ≈ 1.7 x 1038 (2) と、 (2) は 特別な意味を持つので 除外してある 最大値の限界は　 ≈ 2 x 2127=2128 ≈ 3.4 x 1038 となる

11 倍精度表現 仮数部52ビット 指数部11ビット 仮数の表現範囲は有効桁数は53ビット これは10進数で16桁程度の精度
1.00…0 (2) =1 から1.11…1(2) = ≈ x 10-16≈ 2 指数の表現範囲は 2.2 x から9.0 x 10307 2000…01 (2) = ≈ 2.2 x 2111…10 (2) =21023 ≈ 9.0 x 10307 2000…000 (2) と 2111…111 (2) は 特別な意味を持つので 除外してある 最大値の限界は　2 x 2102３=21024 ≈ 1.7 x となる

12 桁落ち誤差と情報落ち誤差 計算機の数値計算では誤差が拡大する可能性がある 桁落ち誤差 情報落ち誤差 桁落ち誤差と情報落ち誤差がある
近い数値間の減算による誤差 ほぼ同じような数値の差をとると有効桁数が減少する 情報落ち誤差 大きさの異なる数値間の加減算による誤差 大きさの異なる数値の加減算では、小さな数値は大きな数値の有効桁範囲外になり無視されてしまう

13 桁落ち誤差の例 err1.rbの実行結果 桁落ち誤差 打切り誤差 def f(x)
Ruby err1.rbの実行結果 h を十分小さく取れば微係数は、 　　　　　　　　　で近似できる 桁落ち誤差 h を変えてx=1における微係数の誤差を調べる 打切り誤差 def f(x) return Math.log(x); # f(x)=ln(x) end x=1.0; 15.times { |i| h =0.1**i #h=0.1, 0.01, …, 1e-15 df=(f(x+h)-f(x))/h err=(df-1.0).abs print "h=",h,"\t f'(",x,")=",df," err=",err,"\n" } 　　　を小さくしていくと、 ある程度までは打切り誤差が 減少していくが、より微小になると 　　　　　と　　　　　の差も微小となり 有効桁数が減少する err1.rb その結果、桁落ち誤差が大きくなる ※打切り誤差については 後ほど述べる

14 打切り誤差 ある関数の値を無限級数を用いて数値計算する場合、有限の項数で打切って近似することにより生じる誤差 （たとえ，実数が無限精度で表現できても生じる） 例）指数関数の原点の周りのテイラー展開 無限回の計算を行うことはできないので、有限回（n回）で 打切って近似を行う スライド13では 微係数を求める場合の 打切り誤差の例を紹介した 誤差の主要成分は

15 2. 数値積分 台形公式 シンプソン公式

16 台形公式 積分を区分線形(piecewise linear)で近似する方法 全積分区間をn等分し各部分区間
　の積分を台形の面積として計算し総和をとる

17 台形公式（続き） ある関数 の から までの 積分の近似値を求めるには、 各部分区間 における台形の総和で近似する

18 シンプソン公式 積分を1次式ではなく2次式で近似する方法 台形公式(1次式近似) シンプソン公式(2次式近似)

19 ラグランジュ補間 ある関数　　　を3点 　で補間する2次関数

20 シンプソン公式（続き） 部分区間 とし 区間 の部分の積分近似値は となるため、 から までの 積分近似値の総和は

21 3．常微分方程式の解法 Euler Method Runge-Kutta (Gill) Method

22 常微分方程式の数値解法 高階(n階)の常微分方程式は一般に n組の連立1階常微分方程式に帰着される 1階の常微分方程式の解法が基本となる
(1階)常微分方程式の数値解法にはTaylor展開を利用する場合が多い 常微分方程式 を初期条件 で解く場合 初期条件近傍の解 はTaylor展開で求まる In the order of

23 Euler法 常微分方程式 を初期条件 で解く場合 を起点としてその近傍 を以下のように逐次求める (Eulerの公式) 任意の値
はこの漸化式を数値計算することにより 数列として求めることができる 問題点：精度が良くない・誤差が蓄積する

24 簡単な例 def euler(n) y = 1.0 h = 1.0/n for i in 0..n-1
Ruby 簡単な例 def euler(n) y = 1.0 h = 1.0/n for i in 0..n-1 y = y + (1.0/(2*y))*h end y

25 y sqrt[2] 1 x 1 2

26 Taylor展開・数値解法の問題 アイデア：Euler法（１次）よりも高次の微分係数を用いる方法が考えられる
問題点：計算機では高次の導関数を求める数式処理が一般に容易ではない 例） ではどうするか？

27 Taylor級数（下の式）と一致するように
Runge-Kutta法 別の方法でTaylor級数と同値なものを計算する方法を考える アイデア：高次導関数を求めるのではなく、高次導関数の値を差分で近似する ※高次導関数が 現れていないこと に注意 上の式で の値が、 の2次の項までは、 Taylor級数（下の式）と一致するように を決めたい

28 Runge-Kutta法（続き） に注意すると そこで と の両式が に関係なく等しくなるためには 従って (Taylor展開 2次まで）
の項は に含まれる そこで と (Taylor展開 2次まで） の両式が に関係なく等しくなるためには 従って

29 天下りに与えられているとすると、 上2式を代入 　　　に注意して偏微分を常微分に 　　を代入すると２次までの Taylor展開になっている

30 Runge-Kutta法（続き） 従って、以下の方法での数値解法は、 の2次の項まではTaylor級数と一致する
同様の手法用いることにより、 高次のRunge-Kutta法を導くこともできる

31 簡単な例 def runge_kutta(n) y = 1.0 h = 1.0/n for i in 0..n-1
Ruby 簡単な例 def runge_kutta(n) y = 1.0 h = 1.0/n for i in 0..n-1 k1 = 1.0/(2*y)*h k2 = (1.0/(2*(y+k1)))*h y = y + (k1+k2)/2.0 end y f(x,y)=1/2y に注意すると この式が簡単に導かれる

32 収束に関するコメント Euler Runge-Kutta hの項まで近似している 各ステップの誤差はh^2に比例 ステップ数は1/hに比例

33 数値解析(1) まとめ 数値計算には種々の誤差が生じる 数値積分の数値解法 常微分方程式の数値解法 実数表現 丸め誤差 打切り誤差 桁落ち
情報落ち 数値積分の数値解法 台形公式 シンプソン公式 常微分方程式の数値解法 Euler法 Runge-Kutta (Gill)法