3.3 二分法

まずサンプル・プログラム bisection.c を示す。 ブラウザーで読み込み、 [ファイル] メニューから [名前をつけて保存] を選び、保存すること。

コンパイルと実行

a308-01% gcc -o bisection bisection.c
a308-01% ./bisection
探す区間の左端, 右端, 要求精度: 0 1 1e-15
... (実行結果は実際に見てもらうことにします)

計算の原理は中間値の定理「連続な関数 $f\colon[a,b]\to\R$ が、 $f(a)f(b)<0$ を満たせば、$(a,b)$ に解が少なくとも一つ存在する」 とその区間縮小法による証明 (付録に書いておいた) に基づく。

$[a,b]$ に解が存在するならば、 二つに分割した区間 $[a,(a+b)/2]$, $[(a+b)/2, b]$ のどちらかに 存在する (両方に存在することもある) が、どちらであるか判断できれば、 繰り返すことで区間の幅を半分半分にしていけて、 解を追い詰めることができる。

なお、上の計算では要求精度 (区間の幅がどこまで小さくなったら反復を停止するか) を (意味は $1\times10^{-15}$ という意味) としたが、 これは演習に用いている C 言語処理系の double の精度が 10 進法に 換算して 16 桁弱であることから決めたものである。

(詳しいことはこの文書の付録を参照せよ。)