2 二分法

2.1 考え方

二分法の考え方は単純であるが，非常に強力な方程式の近似解を求める方法である． 考え方の基本は，閉区間$[a,\,b]$ で連続な関数$f(x)$ の値が，

$$f(a)f(b)<0$$ (2)

ならば， $f(\alpha)=0$ となる$\alpha$ が区間$[a,\,b]$ にある．これは，中間値の定理か ら保証される．こんなことを言わないまでもあたりまえである．ただ，連続な区間で適用 できることを忘れてはならない．

実際の数値計算は， $f(a)f(b)<0$ であるような2点 $a,\,b(a<b)$ から出発する． そして，区間$[a,\,b]$ を2分する点$c=(a+b)/2$ に対して，$f(c)$ を計算を行う． $f(c)f(a)<0$ ならば$b$ を$c$ と置き換え， $f(c)f(a)>0$ ならば$a$ を$c$ と置き 換える．絶えず，区間$[a,b]$ の間に解があるようにするのである．この操作 を繰り返して，区間の幅$\vert b-a\vert$ が与えられた値 $\varepsilon$ よりも小さく なったならば，計算を終了する．解へ収束は収束率1/2の一次収束という．

後は教科書を用いて説明する．

2.2 プログラム例

教科書の二分法のプログラムをリスト1にしめす(転載について)．前節の二分 法での説明とプログラムの変数の対応は，次の通りである．

$a\rightarrow$ left
$b\rightarrow$ riht
$c\rightarrow$ mid
$\varepsilon\rightarrow$ epsilon

言うまでもないと思うが，このプログラムは，方程式

$$x^5-10x^4+25x^3+40x^2+200x-500=0$$ (3)

の$[1,\,3]$ にある近似解の一つを求めている．

リスト1 教科 書の2分法のプログラム(転載について)

   1 #include <stdio.h>
   2 #include <math.h>
   3 #include <stdlib.h>
   4 
   5 /* 解析したい関数 */
   6 double func(double x)
   7 { 
   8     return x*x*x*x*x
   9         -10.0*x*x*x*x
  10         +25.0*x*x*x
  11         +40.0*x*x
  12         +200.0*x-500.0;
  13 }
  14 
  15 /* 2分探索法（バイナリサーチ） */
  16 double BinarySearch(void)
  17 {
  18     double left,mid,right,epsilon;
  19 
  20     /* ↓「答に非常に近い」という範囲を定義する。
  21         この値をいろいろと変えることで，答の精度を調節できる。
  22         ちなみに，あまり小さくしすぎると情報落ちの関係で
  23         答が求まらなくなってしまうので注意。 */
  24     epsilon=0.00001;
  25 
  26     /* 「leftとrightの間に確実に解がある」という範囲を指定する */
  27     left=1.0;
  28     right=3.0;
  29 
  30     /* 範囲をひたすら絞り込む */
  31     while(fabs(right-left)>epsilon &&fabs(func(left))>epsilon)
  32     {
  33         mid=(left+right)/2.0;
  34 
  35         /* func(left)とfunc(mid)が同符号なら */
  36         if(func(left)*func(mid)>=0.0)
  37             left=mid;           /* leftの位置をmidに合わせる */
  38         else
  39             right=mid;          /* rightの位置をmidに合わせる */
  40     }
  41     return left;
  42 }
  43 
  44 int main(void)
  45 {
  46     double d;
  47     d=BinarySearch();
  48     printf("方程式の解は%lf，"
  49             "そのときのfunc(x)は%lfです。\n",d,func(d));
  50     return EXIT_SUCCESS;
  51 }

[転載について]
このページ中のリスト1のプログラムは，教科書として使用している以下の書籍

書名	プログラミングの宝箱　アルゴリズムとデータ構造 ISBN4-7973-2419-8
著作者	紀平拓男・春日伸弥
出版社	ソフトバンク　パブリッシング株式会社

から転載しました．この転載に関しては，著者と版元に許諾を得ています．

ホームページ: Yamamoto's laboratory
著者: 山本昌志