読者です 読者をやめる 読者になる 読者になる

(数値解析) 二分法による解の決定

数学 プログラミング 遊び

今回は方程式の解を求める方法である二分法について学んだのでここに書き記したいと思います。

二分法の流れはこうです

解を挟む範囲を決めてそれを半分(二分)にしてそのうちの解を含んでいる範囲に注目してそれを半分に・・・
そうすれば範囲が解の点に収束していくという流れです。

二分法は F(x)=0

という方程式がありこの方程式の解が一つとわかっている時にのみ使えます。

そしてこの方程式の解を挟む x_0x_n に関しては

 F(x_0) \cdot F(x_n) < 0  

 (つまりF(x_0)F(x_n)は異符号 下の図見るとわかり易い)

という性質が成り立つことを利用して解を求めていきます。 そのため解が一つという他にその解の大体の位置もわかっていないと解を挟むxaxbを決めることができないので少し制約の多い計算方法となります。

しかし理論はシンプルで分かりやすいです。

図で見ていこう

解を挟む範囲を決めて

f:id:mashiroyuya:20160507231852j:plain

まずx_0x_nで解をはさみ

それを半分に!

x_0x_nのちょうど真ん中をxcを求めます。 x_c = \frac{x_0+x_n}{2}

f:id:mashiroyuya:20160507231841j:plain

半分の範囲のどこに解が入っているかの判定

このそしてこの x_c に対して

F(x_0) \cdot F(x_c) < 0

もしくは

F(x_c) \cdot F(x_n)<0

  の条件判断を行います。 この条件判断よりそこで負になった x0もしくはxn とxcの間に解があることになり解を挟む範囲を狭めることができます。

今回は

F(x_c) \cdot F(x_0)<0

であり[x_0,x_c]に解があることになるのでx_nの位置をx_cへと縮めます。

f:id:mashiroyuya:20160507231857j:plain

もう一回半分➡︎解がどこにあるかの判定➡︎範囲を縮める

次に新しく設定された[x0,xn]という範囲に対してもう一度 上記のようにして判定をして範囲を縮めていきます。

f:id:mashiroyuya:20160507231847j:plain

何度もやって範囲が小さくなったら終わり

繰り返していく中で |x_n-x_0|<(適当な小さな値) つまりx_nとx_0の差が十分小さくなればそこで終了して
そのときの x_c が解となります。

非常にシンプルです。しかしこれは解を求めるのに 解が一つであることや最初で解をだいたい知って置かなければ解を含む範囲を設定できないこと 計算回数が多くなってしまうことなどの欠点が挙げられます。

次回で具体的にC言語でコードを書いています。

mashiroyuya.hatenablog.com