二分法算法及其示例

什么是二分法？

二分法是求解多项式或超越方程根的最基本数值方法之一。它的工作原理是先确定包含根的区间，然后在每次迭代中将该区间再细分为两半，直到根位于可接受的误差范围内。由于这种区间划分的特性，二分法也称为区间划分法。

由于其工作机制类似于二分查找，二分法也称为二分查找法、对半法或二分法。它建立在坚实的理论基础之上：介值定理，该定理保证了在区间内改变符号的连续函数必然在该区间内存在过零点。

有了基本定义，让我们来探讨一下为什么求方程的根很重要，以及二分法如何融入这个更广泛的框架中。

寻找方程的根

本文仅讨论只有一个自变量的方程。这类方程可以是线性方程，也可以是非线性方程。线性方程描述的是直线图像，而非线性方程描述的是曲线以及更复杂的形状。

方程的根是指满足该方程的自变量的值。例如，方程 f(x) = 4 – x 的根是 x = 0。² = 0 等于 2，因为 f(2) = 4 – 2² = 0。

设 f(x) 为实连续函数。根据介值定理，当 f(a)f(b) < 0 时，方程 f(x) = 0 在 a 和 b 之间至少有一个根。换句话说，函数 f(x) 在 a 和 b 之间有一个根“c”。

二分法正是利用了这种符号变化特性。下一节将以图形方式展示这一概念。

二分法的图形表示

下图展示了二分法的工作原理。从图中可以看出，方程的实际根用红色标出。

该流程可概括如下：

• 我们首先选择两个初始猜测值，a₁ 和b₁，其中 f(a₁)f(b₁) < 0。根据介值定理，根必定位于 [a] 内。₁，b₁].
• 然后我们计算a的中点₁ 和b₁，即 b₂初始区间现已缩短至[a₁，b₂] 因为 f(a₁)f(b₂）<0。
• 以此类推，将区间一次又一次地减半，直到在所需的容差范围内找到近似解。

既然几何直觉已经明确，我们现在就可以将该过程形式化为一个逐步算法。

二分法算法

应用二分法算法求方程 f(x) = 0 的根的步骤如下。

步骤1） 选择初始猜测值 a、b 和容差率 e。

步骤2） 如果 f(a)f(b) >= 0，则根不在该区间内。在这种情况下，区间 [a, b] 内无解。

步骤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） 如果绝对误差大于容差率，即 (b – a) > 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)³ – (-10)² + 2 = -1098
         f(b) = f(10) = (10)³ - （10）² + 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)³ - （0）² + 2 = 2，不等于 0。

（ii）f(a)f(c)是否小于0：
         f(c)f(a) = 2 * (-1098) < 0

条件已满足。下一次迭代的值将为：

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

步骤4） 由于 (b – a) = (0 – (-10)) = 10 > 0.01，因此重复该过程。后续迭代如下表所示。

步骤5） 在第 11 次迭代中，步骤 4 中的条件变为不成立。因此，该方程的近似根为 -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++

以下 C/C++ 该程序使用二分法求函数 f(x) = x 的根。³ - X² 在区间 [-10, 10] 内加 2。

输入：

#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

此 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

二分法的优点和局限性

与其他数值方法一样，二分法既有明显的优势，也存在一些实际的不足。下表总结了其最重要的优缺点。

二分法的应用

二分法在许多需要稳健求根步骤的实际现代计算场景中得到应用。

• 工程模拟： 求解传热、流体动力学和结构分析中出现的非线性方程。
• 财务建模： 计算收益率、内部收益率和盈亏平衡点（不存在闭式解）。
• 机器学习和人工智能： 在人工智能驱动的数值求解器中定位阈值、校准模型和调整超参数。
• 计算机图形学： 确定射线与曲面的交点以及沿曲线的参数值。
• 嵌入式系统： 在资源匮乏的控制器中，简单性和可预测性比速度更有价值，因此近似根算法尤为重要。

常见问题