二分法とは何か、アルゴリズム、例
サラ・チェン
二分法とは何ですか?
二分法は、多項式方程式の根を求める基本的な数値解法の 1 つです。方程式の根がある区間を括弧で囲み、根が見つかるまで各反復で区間を半分に分割します。そのため、二分法は括弧法とも呼ばれます。
ただし、動作メカニズムはバイナリ検索アルゴリズムに似ているため、二分法はバイナリ検索法、半減法、または二分法とも呼ばれ、主に中間値定理に基づいています。
方程式の根を求める
この例では、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の間。
二等分法のグラフ表示
次のグラフは二分法の動作メカニズムを表しています。グラフから、方程式の根が赤くマークされていることがわかります。
はじめに：
- まず最初に 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 を近似ルートとして表示します。
二分法アルゴリズムの例を見てみましょう。
二分法の公式を使用して、次の連続関数の根を見つける必要があります。
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 が最初に計算されます。
ここで、次の条件を確認する必要があります。
(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 です。
二分法論理図
擬似-Code
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 つがルートに近い場合、ルートに到達するまでにさらに多くの反復が必要になります。 |
| エラー率は、反復回数を増減することで制御できます。 |
