二分法とは何か、アルゴリズム、例

二分法とは何ですか?

二分法は、多項式の根を求めるための基本的な数値解法の XNUMX つです。 方程式の根が存在する区間を括弧で囲み、根が見つかるまで各反復でそれらを半分に分割します。 したがって、二分法はブラケット法とも呼ばれます。

ただし、動作メカニズムが二分探索アルゴリズムに似ているため、二分法は二分探索法、二分法、二分法とも呼ばれます。 これは主に中間値定理に基づいています。

方程式の根を求める

この例では、XNUMX つの独立変数を持つ方程式のみを考慮します。 線形または非線形のいずれかになります。 線形方程式は直線のグラフを表すために使用され、非線形方程式は曲線を表すために使用されます。

方程式の根とは、方程式を満たす独立変数の値を意味します。 例: 方程式の根 f(x)= 4-x2 f(0) = 2-2 であるため、= 4 は 2 です。2 = 0。

f(x) を実連続関数として考えてみましょう。 中間値定理によれば、f(a)f(b) < 0 の場合、方程式 f(x)=0 には a と b の間に少なくとも XNUMX つの根があります。関数 f(x) には根「c」があります。 aとbの間。

方程式の根を求める

二等分法のグラフ表示

次のことwing グラフは二分法の動作メカニズムを表しています。 グラフから、方程式の根が赤いマークで示されていることがわかります。

はじめに:

  • まず最初に XNUMX つの初期推測を行いました。1 およびb1, どれについて f(a1)f(b1) < 0。中間値定理によれば、根は [a にあるはずです。1、b1].
  • の中点を見つけることができます1 およびb1, どれがbです2。 したがって、初期間隔は [a1、b2] なぜなら f(a1)f(b2) < 0。
  • 同様に、近似解が見つかるまで区間を減らしていきます。

二等分法のグラフ表示

二分法アルゴリズム

二分法アルゴリズムを適用して方程式 f(x)=0 の根を求める手順は次のとおりです。

ステップ1) 初期推定 a、b、および許容率 e を選択します

ステップ2) f(a)f(b) >=0 の場合、ルートはこの区間内にありません。 したがって、解決策はありません。

ステップ3) 中点 c = (a+b)/2 を求めます。

(i) 中点の関数値 f(c) = 0 の場合、c は根です。 ステップ5に進みます。
(ii) f(a)f(c) < 0 の場合、根は a と c の間にあります。 次に、a = a、b = c と設定します。
(iii) それ以外の場合は、a = c、b = b を設定します。

ステップ4) 絶対誤差が許容率より大きい場合、または (ba) > e の場合は、ステップ 3 に進みます。

ステップ5) c を近似ルートとして表示します。

二分法アルゴリズムの例を見てみましょう。
フォローのルートを見つけなければなりませんwing 二分法公式を用いた連続関数。

f(x)= x3 - バツ2 + 2

二等分法の例

ステップ1) 仮定してみますと、

         a = -10、
         b = 10、および
         e = 1% または 0.01

ステップ2) ここで、f(a)f(b) >= 0 かどうかを確認します。

         f(a) = f(-10) = (-10)3 – (-10)2 + 2 = -1098
         f(b) = f(10) = (10)3 – (10)2 + 2 = 902
         f(a)f(b) = f(-10)f(10) = (-1098)(902) < 0

したがって、上記の関数の根はこの区間 [-10, 10] にあります。

ステップ3) 次に、中点 c が最初に計算されます。

二等分法の例

さあ、次はwing 条件を確認する必要があります:

(i) f(c) = 0 かどうか:
         f(c) = f(0) = (0)3 – (0)2 + 2 = 2 ≠ 0

(ii) f(a)f(c) < 0 の場合:
         f(c)f(a) = 2*(-1098) < 0

条件は満たされています。 次の反復では、値は次のようになります。

         a = a = -10
         b = c = 0

ステップ4) (ba) = (0-(-10)) = 10>0.05 なので、このプロセスが繰り返されます。 次の反復が表に示されています。

繰り返し a b c ba f(c)
1 -10 0 0 10 2
2 -5 0 -5 5 -148
3 -2.5 0 -2.5 2.5 -19.875
4 -1.25 0 -1.25 1.25 -1.52562
5 -1.25 -0.625 -0.625 0.625 1.36523
6 -1.25 -0.9375 -0.9375 0.3125 0.297119
7 -1.09375 -0.9375 -1.09375 0.15625 -0.50473
8 -1.01562 -0.9375 -1.01562 0.078125 -0.0791054
9 -1.01562 -0.976562 -0.976562 0.0390625 0.115003
10 -1.01562 -0.996094 -0.996094 0.0195312 0.0194703
11 -1.00586 -0.996094 -1.00586 0.00976562 -0.0294344

ステップ5) 11 回目の反復では、ステップ 4 の条件が false になります。 したがって、この方程式の根は -1.00586 です。

二分法論理図

二分法論理図

疑似コード

Start
Set a, b, e
if f(a)*f(b) >=0 
	Output("Root does not exist in this interval")
	Stop
while (b-a)>e do   
	c ← (a + b)/2    
	if f(c) = 0
        	break    
	end if 
	if f(c)*f(a) < 0 then
      	b ← c    
	else        
		a ← c
end while
Output(c)
Stop

C/C++ での二分法メソッドの例

入力:

#include<bits/stdc++.h>
using namespace std;
#define Error 0.01
double value(double x)
{
	return x*x*x - x*x + 2;
}
void bisection_method(double a, double b)
{
	if (value(a) * value(b) >= 0)
	{
		cout << "The root does not lie in this interval\n";
		return;
	}
	double c = a;
	while ((b-a) >= Error)
	{
		c = (a+b)/2;
		if (value(c) == 0.0)
			break;
		else if (value(c)*value(a) < 0)
			b = c;
		else
			a = c;
	}
	cout << "The root is :" << c;
}
int main()
{
	double a =-10 , b = 10;
	bisection_method(a, b);
	return 0;
}

出力:

The root is :-1.00586

Python での二分法例

入力:

def value(x):
	return x*x*x - x*x + 2
def bisection_method(a,b):
	if (value(a) * value(b) >= 0):
		return
	c = a
	while ((b-a) >= 0.01):
		c = (a+b)/2
		if (value(c) == 0.0):
			break
		if (value(c)*value(a) < 0):
			b = c
		else:
			a = c			
	print("The root is : ","%.4f"%c)	
a =-10
b = 10
bisection_method(a, b)

出力:

The root is :  -1.0059

二等分法の利点と制限

二分法の長所と短所は次のとおりです。

メリット デメリット
実装するのが簡単でシンプルなルート検索方法。 単に間隔を半分にすることに基づいているため、収束は遅くなります。
ルートを括弧で囲むため、常に収束します。 最初の推測の XNUMX つがルートに近い場合、ルートに到達するまでにさらに多くの反復が必要になります。
エラー率は、反復回数を増減することで制御できます。