二分法

二分法

 

代数方程式

　　

は、nが５次以上の場合、解の公式が存在しない。そのため、何らかの方法で近似的に解を求めざるを得ない。このとき、よく用いられるのが二分法であり、ニュートン法である。

 

 

中間値の定理

関数f(x)が閉区間[a,b]において連続で、f(a)とf(b)が異符号であるとき、

　　

となるxがaとbの間に存在する。

 

中間値の定理によると、f(x)が[a,b]において連続であるとき、

　　

となるξが少なくとも一つ存在する。

 

そこで、f(a)f(b)<0で[a,b]にf(α)=0となるαがただ１つ存在するとする。

わかりやすくするために、aをa₁、bをとする。

点aと点bの中点

　　

とする。

　　

ならば、c=0が求める解である。

f(c₁)=0でない場合、αは[a₁,c₁]、[c₁,b₁]のいずれかに存在する。

αが[a₁,c₁]に存在するとすると、

　　

[c,b]に存在する、つまり、[a₁,c₁]に存在しないときには、

　　

となる。

（２）の場合はa₂=a₁、b₂=c₁

（３）の場合はa₂=c₁、b₂=b₁

として、[a₂,b₂]で同じ作業を繰り返す。

この作業を一回するたびに、区間の長さは1/2になるので、

　　

である。

このとき、

　　

かつ、

　　

だから、

　　

となる（区間縮小法の原理）。

 

定理　（区間縮小法の原理）

　　

とする。

ならば、数列はともに収束数列であって、

　　

したがって、この作業を繰り返せば繰り返すほどはαに近づき、その極限値が求める方程式f(x)=0の解αである。

しかし、この作業を無限に繰り返すことはできないので、有限回で打ち切らないとならない。

n回、この操作を行ったとき、区間の長さは

　　

したがって、１０回行えば、もとの長さの１０００分の１に、２０回行えば１００万分の１になる。

そして、n回で打ち切ったときの誤差は

　　
程度ということになる。

 

収束の速度は次に述べるニュートン法よりも遅いけれど、ニュートン法はときに計算が収束せず無限ループに陥ることがあるのに対し、２分法は解があれば必ず見つけてくれる極めて安全で確実な方法である。

 

アルゴリズムらしきものを書くと、次のようになる。

 

ステップ１　

ステップ２　f(c)=0ならば、cが方程式の解、計算終了

ステップ３　f(a)・f(c)<0ならばcをbにし、そうでなければ、cをaにする

ステップ４　「打ち切り条件」を満たしていなければ、ステップ１に戻る

 

計算の打ち切り条件には、「b−aがある値、たとえば、１００万分の１より小さい」などが使われる。

 

２分法の計算手順は、実際に、手計算でやるとよくわかる。

たとえば、

　　

f(1)=−2<0、f(2)=1>0だから、[1,2]に上の方程式の解がある。

だから、a=1、b=2とおき、中点cの値を求める。

　　

f(a)=f(1)=−2、f(c)=f(1.5)=−0.75だから、f(a)・f(c)>0となり、[1,1.5]に解はない。

よって、c=1.5をaにセットし直す。つまり、a=1.5、b=2。

[1.5,2]の中点を計算すると

　　

f(a)=f(1.5)=−0.75、f(c)=f(1.75)=3.0625だから、f(a)・f(c)<0となり、解は[1.5,1.75]にある。

よって、b=1.75にする。このとき、a=1.5、b=1.75

・・・・

 

表計算ソフトで使って計算した結果を示す。

aとbがどのように変わってゆくのか、手計算同様に理解できるのではないか。

なお、誤差は

　　

として計算している。