二分法是一种数值算法,用于求闭区间上连续函数的零点。它从函数值异号的两个端点出发,计算中点处的函数值,并保留仍然夹住零点的半区间。反复执行这一过程,就会得到包含解的、逐渐缩小的区间。其主要优点是在简单的假设下保证收敛,并能给出明确的误差界;主要缺点是收敛较慢,而且需要预先给定一个夹住零点的区间。
数学基础
设 是连续函数,其中 ,并假设
根据介值定理,至少存在一点 ,使得
这样的点称为 的根或零点。因此,求方程 的解,可以转化为求 的零点。
区间的中点为
若 ,就已经找到了一个根。否则, 与两个端点函数值中的一个且仅一个异号。相应的半区间,即 或 ,与原区间一样满足连续性条件和端点函数值异号条件。
端点函数值异号只能保证根的存在性,不能保证唯一性。一个区间内可能有多个根,而二分法通常只会分离出其中一个。若 在该区间上是严格单调函数,则根唯一。
算法
迭代前先检查端点函数值:若 或 ,则相应端点已经是一个解。否则,要求两个端点的函数值异号。
采用绝对位置容差 的一种算法如下:
计算 fa = f(a) 和 fb = f(b)。
若 fa = 0,返回 a。
若 fb = 0,返回 b。
若 fa 和 fb 同号,则拒绝该夹根区间。
重复:
m = midpoint(a, b)
若 (b - a)/2 <= ε:
返回 m 以及夹根区间 [a, b]
fm = f(m)
若 fm = 0:
返回 m
若 fa 和 fm 异号:
b = m
fb = fm
否则:
a = m
fa = fm
这段伪代码描述的是精确算术下的过程。实际实现还需要处理舍入、非有限函数值以及迭代次数限制。
初次计算两个端点的函数值之后,每缩小一次区间,只需计算一个新的函数值,已存储的端点函数值可以重复使用。该方法不需要计算导数。
收敛性与误差界
设初始区间为 ,宽度为 。经过 次区间缩减后,保留的区间 的宽度为
这些区间相互嵌套,每个区间都包含一个根。它们的端点收敛于同一个实数 ;由连续性可知,。
若 是 的中点,则
因此,无需知道根的值,也无需计算任何导数,就能给出误差界。要保证中点误差不超过 ,只需进行
次区间缩减。
每缩减一次,区间宽度和可保证的误差界都减半。这种几何式递减通常称为线性收敛。更准确地说,二分之一这一因子适用于夹根区间的宽度及其对应的误差界;相邻中点的实际误差不一定每一步都按这一比例减小。
对于固定的初始区间,用大O记号表示,所需缩减次数按 增长。每缩减一次,绝对位置的分辨精度大约增加一个二进制位。
示例
考虑多项式
由于 ,而 ,区间 夹住了一个根。
| 计算次数 | 中点 | 函数值 | 保留的区间 |
|---|---|---|---|
| 1 | |||
| 2 | |||
| 3 | |||
| 4 | |||
| 5 |
根的近似值为 。经过五次缩减,夹根区间的宽度为 ,因此可以保证其中点的误差不超过 ,而这一保证并不依赖于上述更精确的根值。
停止准则与有限精度算术
区间宽度与残差
区间宽度准则控制的是根的位置不确定性。另一种准则使用残差 ,当残差足够小时停止。这两种准则不能相互替代。
例如,将函数乘以一个很小的正常数,就可以使残差变小,但这既不改变其根,也不改善当前近似值。只有在具备额外信息时,才能由残差得到位置误差界。若在整个夹根区间内都有
则由中值定理可得
没有这类信息时,夹根区间的宽度能更直接地保证位置精度。
实际实现通常结合绝对容差和相对容差,例如将区间半宽与下式比较:
在零附近,绝对容差部分仍然很重要,因为此时仅使用相对误差并不合适。
舍入与可靠的符号判断
在浮点运算中,若干细节会影响可靠性:
- **中点计算:**即使中点可以表示, 也可能溢出。另一种写法 可以避免部分溢出情形,但并非全部;稳健的中点计算程序会考虑端点的符号和数值大小。
- **符号比较:**通过显式相乘来判断是否满足 ,可能导致上溢或下溢。直接比较符号可以避免这次乘法。
- **停滞:**当两个端点之间不再有可表示的数时,算出的中点最终可能等于某个端点。此时,在当前工作精度下已无法继续细分。
- **求值误差:**舍入、消去或近似函数求值可能产生错误的符号。精确算术下的保证不仅依赖于连续性,也依赖于符号判断的可靠性。
- **计算得到的零:**浮点计算中的零值可能由下溢或消去造成,而不一定对应数学上的精确根。
具有验证保证的实现可以使用区间算术包围函数值;当所得包围区间不包含零时,就能确认函数值的符号。
局限性
**连续性必不可少。**仅凭端点函数值异号,并不能确定存在根。例如, 在 和 处异号,却没有零点;它在中点处无定义。
**有些根的两侧不发生符号变化。**函数 在根的两侧均非负。对于一个包围该根且端点函数值均非零的区间,普通的基于异号夹根的二分法无法检测出这个根。这一问题常见于偶重根。
**必须提供初始夹根区间。**寻找这样的区间可能需要采样、扩大搜索区间或利用解析信息。二分法本身并不保证能找到合适的初始区间。
**基本不利用函数值的大小。**区间更新仅取决于符号,因此,那些可能支持更大步长或更精确步长的信息被舍弃了。这使该方法的行为易于预测,但也往往比其他方法更慢。
相关方法与应用
牛顿法利用导数信息,在适当条件下可以在单根附近达到二次收敛。不过,若初始点选择不当,它可能失败,也可能离开所关注的区域。割线法无需显式计算导数,收敛速度可以快于二分法,但通常不保持夹根区间。
布伦特法将二分法与割线步骤、逆二次插值步骤相结合。它在保持夹根区间的同时,所需函数求值次数往往远少于纯二分法。这类混合方法在加速步骤不合适时,会使用二分法作为可靠的后备方案。
二分法与二分查找密切相关:两者都反复舍弃搜索区间的一半。二分查找通常在有序数据中定位目标或变化位置;数值二分法则利用连续性和端点异号条件,保留包含零点的区间。
其应用包括求解物理模型中的标量方程、求单调函数的反函数,以及对于连续且具有合适夹根区间的累积分布函数,通过求解 来确定分位数。对于存在跳跃的分布,需要采用广义逆的表述,而不能假定该方程一定有解。在数学优化中,当所需的连续性和符号条件成立时,二分法可以用于定位导数的零点;要将该零点判定为极小值点,还需要额外的假设。