(数値解析) 二分法による解の決定
今回は方程式の解を求める方法である二分法について学んだのでここに書き記したいと思います。
二分法の流れはこうです
解を挟む範囲を決めてそれを半分(二分)にしてそのうちの解を含んでいる範囲に注目してそれを半分に・・・
そうすれば範囲が解の点に収束していくという流れです。
二分法は
という方程式がありこの方程式の解が一つとわかっている時にのみ使えます。
そしてこの方程式の解を挟む と
に関しては
(つまり と
は異符号 下の図見るとわかり易い)
という性質が成り立つことを利用して解を求めていきます。
そのため解が一つという他にその解の大体の位置もわかっていないと解を挟むと
を決めることができないので少し制約の多い計算方法となります。
しかし理論はシンプルで分かりやすいです。
図で見ていこう
解を挟む範囲を決めて
まず と
で解をはさみ
それを半分に！
と
のちょうど真ん中をxcを求めます。
半分の範囲のどこに解が入っているかの判定
このそしてこの に対して
の条件判断を行います。 この条件判断よりそこで負になった x0もしくはxn とxcの間に解があることになり解を挟む範囲を狭めることができます。
今回は
であり]に解があることになるので
の位置を
へと縮めます。
もう一回半分➡︎解がどこにあるかの判定➡︎範囲を縮める
次に新しく設定された[x0,xn]という範囲に対してもう一度 上記のようにして判定をして範囲を縮めていきます。
何度もやって範囲が小さくなったら終わり
繰り返していく中で<(適当な小さな値)
つまり
の差が十分小さくなればそこで終了して
そのときの が解となります。
非常にシンプルです。しかしこれは解を求めるのに 解が一つであることや最初で解をだいたい知って置かなければ解を含む範囲を設定できないこと 計算回数が多くなってしまうことなどの欠点が挙げられます。
次回で具体的にC言語でコードを書いています。