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.5 | f=0.25>0 | 保留 [1,1.5] |
| m=1.25 | f=−0.4375<0 | 保留 [1.25,1.5] |
| m=1.375 | f=−0.109375 | 保留 [1.375,1.5] |
| 继续折半 | 逐渐靠近 1.41421356 | 区间宽给出误差证书 |
窄屏可左右滑动表格,阅读完整计算与理由。
每步的数值近似都附带一个包含根的区间。
04为什么这个方法成立
- 初始连续且端点异号,区间内有根。
- 中点符号决定哪一半仍异号,所以根包含性质不变。
- 宽度严格折半,返回中点时半宽就是可证明的位置误差上界。
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,折半 10 次后中点误差至多多少?
需要一点提示
宽度再除 2。
查看解析与答案
至多 1/2048,约 0.000488。
两端同号就一定无根吗?
需要一点提示
考虑 x² 在 [−1,1]。
查看解析与答案
不一定;同号只说明本判据不能保证包根,偶重根可能不变号。
如何结合牛顿法加快?
需要一点提示
既要快步,也要保留区间。
查看解析与答案
维护有效包根区间,牛顿步落到区间外或不可靠时退回二分,构成保护式求根。
继续深入这个专题
本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。
Driscoll 与 Braun · Fundamentals of Numerical Computation