专题进阶 · 数值算法推荐总顺序 · 第 100 / 148 课

用连续性保持异号区间,并把迭代次数转成可验证的根位置误差界。

先学会这些,再进入本课 二分查找
还有 1 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 数值算法

二分求根Bisection

连续函数在区间两端异号时,保留异号的一半;误差界随区间长度折半。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

用连续性保持异号区间,并把迭代次数转成可验证的根位置误差界。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

求 x²−2=0 的正根,没有解析公式时,怎样保证每一步都仍包住一个根?

02一步步得到方法

这里的二分依据是连续性

若连续函数在 a、b 两端异号,中间至少有一个零点。取中点 m,若 f(m)=0 就结束,否则在 [a,m] 与 [m,b] 中保留异号的一半。函数不必单调,但必须在所用区间连续。

这和有序数组查找的排除证明不同:数组二分依赖排序,这里依赖介值定理。一个区间中可能有多个根,方法只保证保留至少一个,不自动指出是哪一个。

误差来自区间长度

经过 k 次折半,区间宽为 (b−a)/2^k,返回中点与某个保留根的距离至多半个区间宽。要求位置误差≤ε,可据此估计迭代次数。

残差 |f(x)| 小与位置误差小不是同一个概念;平坦函数可能残差很小但离根仍远。浮点数相邻时中点可能等于端点,再迭代也无法缩小,应报告精度限制,而非无限循环。

符号夹逼与连续性缺一不可

端点函数值异号,加上区间内连续,才由介值定理保证至少一个根。若函数在中间有间断,例如倒数函数跨越0,异号本身不能保证存在零点。

每步保留仍然夹根的半区间,所以区间长度确定减半。停止时报告区间中点及误差界,比只看函数值很小更可靠;函数很平坦时,小残差未必意味着小位置误差。

03把一个小例子完全算清楚

f(x)=x²−2,初始 [1,2]。

步骤计算与状态为什么这样做
m=1.5f=0.25>0保留 [1,1.5]
m=1.25f=−0.4375<0保留 [1.25,1.5]
m=1.375f=−0.109375保留 [1.375,1.5]
继续折半逐渐靠近 1.41421356区间宽给出误差证书

窄屏可左右滑动表格,阅读完整计算与理由。

每步的数值近似都附带一个包含根的区间。

04为什么这个方法成立

  1. 初始连续且端点异号,区间内有根。
  2. 中点符号决定哪一半仍异号,所以根包含性质不变。
  3. 宽度严格折半,返回中点时半宽就是可证明的位置误差上界。

05把推导翻译成代码

Python · 可独立运行的教学实现

from math import isfinite
def bisection(f,a,b,tol=1e-10,iterations=200):
    assert a < b and tol > 0
    fa,fb = f(a),f(b)
    if not (isfinite(fa) and isfinite(fb)):
        raise ValueError("nonfinite endpoint")
    if fa == 0: return a
    if fb == 0: return b
    if (fa > 0) == (fb > 0):
        raise ValueError("opposite endpoint signs required")
    for _ in range(iterations):
        mid = a/2+b/2
        fm = f(mid)
        if not isfinite(fm): raise ValueError("nonfinite function")
        if fm == 0 or (b-a)/2 <= tol: return mid
        if mid == a or mid == b: raise ArithmeticError("precision limit")
        if (fa > 0) != (fm > 0):
            b,fb = mid,fm
        else:
            a,fa = mid,fm
    raise RuntimeError("iteration limit")

逐个理解关键决定

(fa > 0) != (fm > 0)
直接比较符号,避免相乘造成溢出或下溢后的错误判定。
(b-a)/2 <= tol
停止条件对应根位置误差,不只看函数值。

06时间、空间与实现范围

达到位置精度 ε 需 O(log((b−a)/ε)) 次函数计算,工作空间 O(1)。

函数评估本身若昂贵,要乘其成本;连续性是使用者的数学前提,代码只能检查有限点,无法自动证明。

07改变条件,检查哪里会出错

f(x)=1/x 在 [−1,1] 两端异号,所以有根

函数在 0 不连续,并无零点;异号条件必须与连续性一起使用。

只检测 f(mid) 很小就声称坐标精确

应结合区间长度与问题尺度;残差和根的位置误差是不同量。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

初始宽度 1,折半 10 次后中点误差至多多少?

需要一点提示

宽度再除 2。

查看解析与答案

至多 1/2048,约 0.000488。

练习 2 · 边界与辨析

两端同号就一定无根吗?

需要一点提示

考虑 x² 在 [−1,1]。

查看解析与答案

不一定;同号只说明本判据不能保证包根,偶重根可能不变号。

练习 3 · 变式与迁移

如何结合牛顿法加快?

需要一点提示

既要快步,也要保留区间。

查看解析与答案

维护有效包根区间,牛顿步落到区间外或不可靠时退回二分,构成保护式求根。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Driscoll 与 Braun · Fundamentals of Numerical Computation

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。