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

二分法とは何ですか?

二分法は、多項式方程式の根を求める基本的な数値解法の 1 つです。方程式の根がある区間を括弧で囲み、根が見つかるまで各反復で区間を半分に分割します。そのため、二分法は括弧法とも呼ばれます。

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

方程式の根を求める

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

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

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

二等分法のグラフ表示

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

はじめに：

まず最初に XNUMX つの初期推測を行いました。₁ およびb_1, どれについて f(a₁)f(b₁) < 0。中間値定理によれば、根は [a にあるはずです。₁、b₁].
の中点を見つけることができます₁ およびb_1,どれがbです₂。したがって、初期間隔は [a₁、b₂] なぜなら f(a₁)f(b₂) < 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 を近似ルートとして表示します。

二分法アルゴリズムの例を見てみましょう。
二分法の公式を使用して、次の連続関数の根を見つける必要があります。

f（x）= x³ - バツ² + 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 が最初に計算されます。

ここで、次の条件を確認する必要があります。

(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