二分求根法

形式陈述 ​

二分法的输入是一元函数 $f:[a_0,b_0]\to \mathbb{R}$、初始区间和绝对或相对容差。算法要求 $f$ 在整个区间连续；若端点不是根，还要求 $f(a_0)$ 与 $f(b_0)$ 异号。连续性是问题前提，有限次函数采样无法替用户验证它。

若 $f(a_0)=0$ 或 $f(b_0)=0$，可直接返回相应端点。否则每一步计算中点 $m_k$ 和 $f(m_k)$：若中点为根便返回；若 $f(a_k)$ 与 $f(m_k)$ 异号，令

$$[a_{k+1},b_{k+1}]=[a_k,m_k],$$

否则令 $[a_{k+1},b_{k+1}]=[m_k,b_k]$。实现不应通过乘积 $f(a_k)f(m_k)<0$ 判断异号，因为乘积可能溢出或下溢；应分别处理零值、非有限值和符号。

每轮都保持以下区间不变量：$f$ 在 $[a_k,b_k]$ 连续，端点异号，因而由介值定理公理库介值定理Intermediate value theorem连续实函数在区间上取得端点函数值之间的每个值。知区间内至少有一个根。在精确算术中，经过 $n$ 次更新后

$$b_n-a_n=\frac{b_0-a_0}{2^n}.$$

若输出中点 $m_n$，对区间内任一目标根 $r$ 都有

$$|m_n-r|\le \frac{b_n-a_n}{2}=\frac{b_0-a_0}{2^{n+1}}.$$

要保证绝对误差不超过 $\epsilon$，可取

$$n\ge max\{0,\lceil {\log }_2\frac{b_0-a_0}{2\epsilon }\rceil \}.$$

除初始端点外，每轮只新增一次函数求值，时间成本为 $O(\log ((b_0-a_0)/\epsilon ))$ 次求值，额外存储为 $O(1)$。这是确定的区间误差保证，不依赖函数在根附近的斜率。

实际停止可用混合尺度，例如

$$b_k-a_k\le 2(\mathrm{atol}+\mathrm{rtol}max(|a_k|,|b_k|)).$$

单独检查 $|f(m_k)|$ 不可靠：函数缩放后残差可以任意变小，陡峭或平坦根附近残差与位置误差的关系也不同。算法还应有函数求值失败、最大迭代数和浮点分辨率耗尽的退出状态。

直觉 ​

二分法不猜根会向哪边快速移动，而是维护一份不会失效的证据：区间两端的符号不同。每次只扔掉确定不再需要的一半，证据随新区间一起保留下来。它的速度不取决于曲线形状，因此不会像局部迭代那样突然加速，也不容易因坏初值离开搜索区间。

返回一个很窄的括根区间，比只返回某个小残差更有信息。前者直接给根的位置误差尺度；后者还要知道函数在根附近怎样把位置变化映射为函数值变化。

例子与边界 ​

继续考察求根问题公理库非线性方程求根问题Root-finding problem · Nonlinear equation solving定义标量与向量求根问题，并区分根的存在、隔离、重数、残差和局部敏感性。中的函数

$$f(x)=\cos x-x,$$

初始区间为 $[0,1]$。第一次中点为 $0.5$，$f(0.5)>0$，所以新区间是 $[0.5,1]$；第二次中点为 $0.75$，$f(0.75)<0$，新区间变成 $[0.5,0.75]$；第三次取 $0.625$ 后得到 $[0.625,0.75]$。区间持续减半并收敛到约 $0.7390851332$ 的根。

二分过程只证明每个保留区间中至少有根。这个例子的唯一性来自 $f^{\prime }(x)=-\sin x-1<0$，而不是来自二分更新本身。若初始区间含有多个奇重根，算法可能收敛到其中一个，却不会顺便给出“区间原来只有一个根”的证书。

偶重根不会引起符号变化。例如 $(x-1{)}^2$ 在 $x=1$ 为零，但区间两端通常同号，标准二分法无法从端点符号发现它。连续性也不可省略：$f(x)=1/x$ 在 $[-1,1]$ 两端异号，却在区间内没有零点，因为函数在 $0$ 不连续且无定义。

浮点中点常写成

$$m=a+\frac{b-a}{2},$$

它比 $(a+b)/2$ 更不容易因同号大端点相加而溢出；极端异号端点仍可能使 $b-a$ 溢出，工程实现宜使用平台提供的安全 midpoint 操作或按符号缩放。更关键的终止边界来自浮点间距公理库舍入、机器精度与 ulpRounding and unit roundoff · Unit in the last place · ulp用舍入映射、ulp 与 unit roundoff 描述实数映到邻近浮点数时的局部精度。：当 $a$ 与 $b$ 已相邻或过近时，舍入后的 $m$ 可能等于某个端点。此时区间无法再缩小，算法必须返回当前最窄区间并报告“浮点分辨率耗尽”，而不是继续死循环。

若 $f(m)$ 为 NaN、无穷或函数评估带有足以翻转符号的噪声，括根不变量也失去可验证性。可靠实现应终止并暴露失败，而不是把异常值当作普通正负号继续更新。

推论与应用 ​

二分法提供全局可靠但线性收敛的基线。Newton、割线或逆二次插值可以在局部更快，却可能产生越出区间的步；混合求根方法常在候选步不可信时退回二分，从而兼顾速度与括根证据。

求根问题公理库非线性方程求根问题Root-finding problem · Nonlinear equation solving定义标量与向量求根问题，并区分根的存在、隔离、重数、残差和局部敏感性。区分括根与隔离，误差度量公理库误差度量：绝对、相对与分量误差Error measures · Absolute and relative error用绝对、相对、范数型与逐分量尺度准确说明近似量偏离真值的程度。说明绝对和相对容差如何匹配问题尺度。报告二分结果时，至少应给最终区间、采用的宽度准则、函数评估次数及退出状态；只有一个近似小数不足以说明算法是否完成了约定任务。

参考资料

• NIST Digital Library of Mathematical Functions, §3.8: Nonlinear Equations.
• MIT OpenCourseWare, 18.330, Introduction to Numerical Analysis, root-finding notes.
• Richard L. Burden, J. Douglas Faires, and Annette M. Burden, Numerical Analysis, 10th ed., Cengage, 2016, Ch. 2.