狠狠撸

アルゴリズムとデータ構造
8 章　浮動小数点型と数値計
算
1

浮動小数点とは？
コンピューターでは（数値） ×2n
（ n は整数）で小数を表す
。
たとえば、
12.8 = 0.8 × 24
となる。このとき 0.8 を基数、 4 を指数という。
基数と指数を用いて表された実数値を浮動小数点数という
。
浮動小数点型は double 型と float 型がある。
符号
(+-)
指数
(n)
基数
(a)
2

浮動小数点型の特徴
浮動小数点型ではビット数が決まっている。
そのため
?ある程度以上細かい数字は表現できない
?数が大きくなればなるほど、数を大雑把にしか
表せなくなる
という特徴がある。
3

生じる誤差
浮動小数点型の数値計算で生じる誤差は 4 つ
?丸め誤差
?桁落ち
?情報落ち
?打ち切り誤差
4

丸め誤差
浮動小数点型のビット数の制限によって生まれる
計算結果の誤差のこと
プログラム例
コンソール
f1 、 f2 ともに同じ値となってしまった。
5

桁落ち
浮動小数点計算で計算結果が 0 に極端に近くなる
加減算を行ったときに有効数字の桁数が極端に小さくなる現象
プログラム例
コンソール
加算、減算とも計算結果がずれている。
減算で特に誤差が大きくなっている。
6

情報落ち
浮動小数点計算で絶対値が著しく異なる数値の加減算を行うときに
小さい方の数値が計算に反映されなくなる現象
プログラム
コンソール
求めている値は 1000001 だが、
f2 を 100 万回足したのが
反映されていない
7

打ち切り誤差
無限または数多くの回数の演算を有限項の計算で
打ち切ったときに発生する誤差
例
i = 10 で打ち切った場合、 i =11 以降の無視された部分が
そのまま打ち切り誤差となる
8

誤差とその対策
9
丸め誤差
桁落ち
情報落ち
打ち切り誤差
演算桁数を大きくするのが最も簡単
絶対値のほぼ等しい同符号の減算をなるべく
少なくなるように、計算式を工夫する
複数の数値の加減では絶対値の小さい順に
並べ替えて計算を行う。
目的に応じて時間と精度のどちらを優先させるか
最適なバランスを考える

ループの脱出条件と浮動小数点
型
for 文や while 文などのループの脱出条件として
浮動小数点型の変数を用いると計算誤差によって
?無限ループになってしまう
?ループが余分に実行される
といったプログラムになってしまう可能性がある。
ループの脱出条件の判定にはなるべく整数変数を利用する。
if 文での条件分岐などでも同様。
10

ループの脱出条件と浮動小数点
型
例 1 　無限ループになってしまうプログラム
11
例 2 　ループが余分に実行されるプログラム
f1+=0.1f の計算を行うときに
わずかな誤差が蓄積し
50 回目のループで f1 が 5.0 より
少しずれた値になっている。
ループは 51 回実行される。
0.1 を 50 回足したら
誤差の影響で
50 より小さくなる。

数値計算の例　複雑な方程式を解
く
数値計算のアルゴリズムを使えば、２次元方程式、 3 次元方程式
やさらに複雑な方程式を解くことができる。
アルゴリズムの例
? Euler 法
? Runge-Kutta 法
?バイナリサーチを使う
? Newton 法
?ブレント法
12

バイナリサーチによる方程式の解
法
バイナリサーチ
2 分探索と呼ばれるサーチ方法。
全体を 2 つに分け、目的の値が分割点の前後どちらにあるかを
判断して検索範囲を狭めていく。
バイナリサーチを数値計算に応用することで
簡単に方程式を解くことができる。
バイナリサーチで解くにはグラフが連続していることが
必要である
13

法
14
y
x
y=0
y=f(x)
left right
1. y < 0 となる適当な点 left と
y < 0 となる適当な点 right の
2 点を開始点として設定する。

法
15
2. left と right の中点 mid を求める
left rightmid
3. mid < 0 ならば mid を新しい left とし、
mid > 0 ならば mid を新しい right とする
left rightmid>0
left right

法
16
4. 値が絞り込まれるまで 2~3 を繰り返し、
打ち切り条件に達したら left または right を解とする
打ち切り条件は真の答えと非常に近い範囲を定義する。
この条件を変えることで答えの精度を調節できる。
ある条件で計算を打ち切っているので厳密な解そのもので
はない。

Newton 法による方程式の解法
f(x)=0 となるような x を求めるアルゴリズムの一種。
方程式の解を近似的に求めることができる。
Newton 法の考え方
f(x)=0 となるような値 x を探すとき、ある値 x1 における
接線の切片 x2 は元の値 x1 より真の値 x に近くなる。
バイナリサーチとの違いはバイナリサーチよりも
効率よく答えに近づけること、開始点が 1 点でよいことである。
17

Newton 法の考え方
ある点 xn での導関数 f’
(xn) が与えられるとき (xn,f(xn)) を通り、
傾きが f’
(xn) の方程式は
で与えられる。これを f(x) の近似解とみなすと、 f(x)=0 の
近似解は y=0 のときなので
このように 1 次式で近似するのを繰り返して
求めたい解 x により近い値を求める。
18
y = f '
(xn )(x ? xn )+ f (xn )
xn+1 = xn ?
f (xx )
f '
(xn )

19
開始点 x
y=0
y=f(x)
x
y=0
y=f(x)
2. 開始点 x における
グラフの傾きを求める
傾き
1. 任意の開始点 x を設定する

20
x
y=0
y=f(x)3. グラフの傾きを利用して解に近づく
4. この作業を繰り返し、関数の値が限りなくゼロに近づいたら
処理を打ち切り、そのときの x を答えとする。

Newton 法が使えない例
21
y=0
Newton 法はグラフの形状や開始点の位置に
よって、解が求まらないケースもある。

狠狠撸

浮动小数点型と数値计算

Recommended

More Related Content

Featured (20)

浮动小数点型と数値计算