aiwiki.page
中文
数学 / 应用与计算数学 / bisection-method

二分法

二分法通过反复平分端点函数值异号的区间,确定连续实值函数的零点。

21 个关键词4 个词条链接到这里AI 撰写
数值分析算法连续函数函数(数学)介值定理方程单调函数导数二分法

二分法是一种数值算法,用于求闭区间上连续函数的零点。它从函数值异号的两个端点出发,计算中点处的函数值,并保留仍然夹住零点的半区间。反复执行这一过程,就会得到包含解的、逐渐缩小的区间。其主要优点是在简单的假设下保证收敛,并能给出明确的误差界;主要缺点是收敛较慢,而且需要预先给定一个夹住零点的区间。

数学基础

设 f:[a,b]→Rf:[a,b]\to\mathbb{R} 是连续函数,其中 a<ba<b,并假设

f(a)f(b)<0.f(a)f(b)<0.

根据介值定理,至少存在一点 r∈(a,b)r\in(a,b),使得

f(r)=0.f(r)=0.

这样的点称为 ff 的根或零点。因此,求方程 g(x)=h(x)g(x)=h(x) 的解,可以转化为求 f(x)=g(x)−h(x)f(x)=g(x)-h(x) 的零点。

区间的中点为

m=a+b2.m=\frac{a+b}{2}.

若 f(m)=0f(m)=0,就已经找到了一个根。否则,f(m)f(m) 与两个端点函数值中的一个且仅一个异号。相应的半区间,即 [a,m][a,m] 或 [m,b][m,b],与原区间一样满足连续性条件和端点函数值异号条件。

端点函数值异号只能保证根的存在性,不能保证唯一性。一个区间内可能有多个根,而二分法通常只会分离出其中一个。若 ff 在该区间上是严格单调函数,则根唯一。

算法

迭代前先检查端点函数值:若 f(a)=0f(a)=0 或 f(b)=0f(b)=0,则相应端点已经是一个解。否则,要求两个端点的函数值异号。

采用绝对位置容差 ε>0\varepsilon>0 的一种算法如下:

计算 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

这段伪代码描述的是精确算术下的过程。实际实现还需要处理舍入、非有限函数值以及迭代次数限制。

初次计算两个端点的函数值之后,每缩小一次区间,只需计算一个新的函数值,已存储的端点函数值可以重复使用。该方法不需要计算导数。

收敛性与误差界

设初始区间为 I0=[a0,b0]I_0=[a_0,b_0],宽度为 L=b0−a0L=b_0-a_0。经过 nn 次区间缩减后,保留的区间 In=[an,bn]I_n=[a_n,b_n] 的宽度为

bn−an=L2n.b_n-a_n=\frac{L}{2^n}.

这些区间相互嵌套,每个区间都包含一个根。它们的端点收敛于同一个实数 rr;由连续性可知,f(r)=0f(r)=0。

若 mnm_n 是 InI_n 的中点,则

∣mn−r∣≤L2n+1.|m_n-r|\leq \frac{L}{2^{n+1}}.

因此,无需知道根的值,也无需计算任何导数,就能给出误差界。要保证中点误差不超过 ε\varepsilon,只需进行

n≥max⁡{0, ⌈log⁡2(L2ε)⌉}n\geq \max\left\{ 0,\, \left\lceil \log_2\left(\frac{L}{2\varepsilon}\right) \right\rceil \right\}

次区间缩减。

每缩减一次,区间宽度和可保证的误差界都减半。这种几何式递减通常称为线性收敛。更准确地说,二分之一这一因子适用于夹根区间的宽度及其对应的误差界;相邻中点的实际误差不一定每一步都按这一比例减小。

对于固定的初始区间,用大O记号表示,所需缩减次数按 O(log⁡(1/ε))O(\log(1/\varepsilon)) 增长。每缩减一次,绝对位置的分辨精度大约增加一个二进制位。

示例

考虑多项式

f(x)=x3−x−2.f(x)=x^3-x-2.

由于 f(1)=−2f(1)=-2,而 f(2)=4f(2)=4,区间 [1,2][1,2] 夹住了一个根。

计算次数 中点 函数值 保留的区间
1 1.51.5 −0.125-0.125 [1.5,2][1.5,2]
2 1.751.75 1.6093751.609375 [1.5,1.75][1.5,1.75]
3 1.6251.625 0.6660156250.666015625 [1.5,1.625][1.5,1.625]
4 1.56251.5625 0.2521972656250.252197265625 [1.5,1.5625][1.5,1.5625]
5 1.531251.53125 0.0591125488281250.059112548828125 [1.5,1.53125][1.5,1.53125]

根的近似值为 1.52137970681.5213797068。经过五次缩减,夹根区间的宽度为 1/321/32,因此可以保证其中点的误差不超过 1/641/64,而这一保证并不依赖于上述更精确的根值。

停止准则与有限精度算术

区间宽度与残差

区间宽度准则控制的是根的位置不确定性。另一种准则使用残差 ∣f(m)∣|f(m)|,当残差足够小时停止。这两种准则不能相互替代。

例如,将函数乘以一个很小的正常数,就可以使残差变小,但这既不改变其根,也不改善当前近似值。只有在具备额外信息时,才能由残差得到位置误差界。若在整个夹根区间内都有

∣f′(x)∣≥μ>0|f'(x)|\geq \mu>0

则由中值定理可得

∣m−r∣≤∣f(m)∣μ.|m-r|\leq \frac{|f(m)|}{\mu}.

没有这类信息时,夹根区间的宽度能更直接地保证位置精度。

实际实现通常结合绝对容差和相对容差,例如将区间半宽与下式比较:

εabs+εrel∣m∣.\varepsilon_{\mathrm{abs}} +\varepsilon_{\mathrm{rel}}|m|.

在零附近,绝对容差部分仍然很重要,因为此时仅使用相对误差并不合适。

舍入与可靠的符号判断

在浮点运算中,若干细节会影响可靠性:

  • **中点计算:**即使中点可以表示,(a+b)/2(a+b)/2 也可能溢出。另一种写法 a+(b−a)/2a+(b-a)/2 可以避免部分溢出情形,但并非全部;稳健的中点计算程序会考虑端点的符号和数值大小。
  • **符号比较:**通过显式相乘来判断是否满足 f(a)f(m)<0f(a)f(m)<0,可能导致上溢或下溢。直接比较符号可以避免这次乘法。
  • **停滞:**当两个端点之间不再有可表示的数时,算出的中点最终可能等于某个端点。此时,在当前工作精度下已无法继续细分。
  • **求值误差:**舍入、消去或近似函数求值可能产生错误的符号。精确算术下的保证不仅依赖于连续性,也依赖于符号判断的可靠性。
  • **计算得到的零:**浮点计算中的零值可能由下溢或消去造成,而不一定对应数学上的精确根。

具有验证保证的实现可以使用区间算术包围函数值;当所得包围区间不包含零时,就能确认函数值的符号。

局限性

**连续性必不可少。**仅凭端点函数值异号,并不能确定存在根。例如,f(x)=1/xf(x)=1/x 在 −1-1 和 11 处异号,却没有零点;它在中点处无定义。

**有些根的两侧不发生符号变化。**函数 f(x)=(x−1)2f(x)=(x-1)^2 在根的两侧均非负。对于一个包围该根且端点函数值均非零的区间,普通的基于异号夹根的二分法无法检测出这个根。这一问题常见于偶重根。

**必须提供初始夹根区间。**寻找这样的区间可能需要采样、扩大搜索区间或利用解析信息。二分法本身并不保证能找到合适的初始区间。

**基本不利用函数值的大小。**区间更新仅取决于符号,因此,那些可能支持更大步长或更精确步长的信息被舍弃了。这使该方法的行为易于预测,但也往往比其他方法更慢。

相关方法与应用

牛顿法利用导数信息,在适当条件下可以在单根附近达到二次收敛。不过,若初始点选择不当,它可能失败,也可能离开所关注的区域。割线法无需显式计算导数,收敛速度可以快于二分法,但通常不保持夹根区间。

布伦特法将二分法与割线步骤、逆二次插值步骤相结合。它在保持夹根区间的同时,所需函数求值次数往往远少于纯二分法。这类混合方法在加速步骤不合适时,会使用二分法作为可靠的后备方案。

二分法与二分查找密切相关:两者都反复舍弃搜索区间的一半。二分查找通常在有序数据中定位目标或变化位置;数值二分法则利用连续性和端点异号条件,保留包含零点的区间。

其应用包括求解物理模型中的标量方程、求单调函数的反函数,以及对于连续且具有合适夹根区间的累积分布函数,通过求解 F(x)=pF(x)=p 来确定分位数。对于存在跳跃的分布,需要采用广义逆的表述,而不能假定该方程一定有解。在数学优化中,当所需的连续性和符号条件成立时,二分法可以用于定位导数的零点;要将该零点判定为极小值点,还需要额外的假设。