二分法 – 什么是二分法、算法和示例

什么是二分法？

二分法是求多项式方程根的基本数值解法之一。二分法将方程根所在的区间括起来，在每次迭代中将其分成两半，直到找到根。因此，二分法又称为括号法。

但由于其工作机制与二分查找算法类似，二分法又称为二分查找法、减半法或二分法，其主要基础是中值定理。

寻找方程的根

在这个例子中，我们只考虑具有一个独立变量的方程。它可以是线性的，也可以是非线性的。线性方程用于表示直线的图形，而非线性方程用于表示曲线。

方程的根是指满足方程的独立变量的值。例如：方程的根 f(x)= 4-x² = 0 为 2，因为 f(2) = 4-2² = 0。

我们将 f(x) 视为一个实连续函数。根据中间值定理，如果 f(a)f(b) < 0，则方程 f(x)=0 至少有一个根位于 a 和 b 之间。函数 f(x) 有一个根“c”，位于 a 和 b 之间。

二分法的图形表示

下图表示二分法的工作机制。从图中我们可以看到方程的根用红色标记。

首先：

我们首先做了两个初步猜测，₁ 和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³ - 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

（二）若 f(a)f(c) < 0：
f(c)f(a) = 2*(-1098) < 0

条件已满足。对于下一次迭代，值将是，

一个=一个= -10
b = c = 0

步骤4） 由于 (ba) = (0-(-10)) = 10>0.05，因此将重复该过程。表中显示了下一次迭代。

迭代	a	b	c	巴	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 的条件将为假。因此，该等式的根为 -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