二分法

二分法（bisection method）是求连续实函数零点的区间迭代算法。在一个端点函数值异号的闭区间内，反复计算中点，并保留仍然异号的半个区间，从而把至少一个零点夹在越来越短的区间中。它的突出性质是具有可直接计算的位置误差上界，不需要导数，也不要求事先知道零点附近的曲线斜率。

二分法求的是一个区间中的某个零点，不是自动列出全部解。连续性与端点异号是保证的核心；它们分别排除“跳过零值”和“区间内根本没有被夹住的零点”这两类问题。算法、数学保证和计算机停止规则需要一起理解。

先夹住一个根，再逐步缩小不确定性

假设一个连续量从负值变成正值，中间必须经过零。对于函数 $f : [a, b] \to ℝ$ ，其中 $a < b$ ，若 $f (a) f (b) < 0$ ，中间值定理保证存在 $r \in (a, b)$ 使 $f (r) = 0$ 。初始区间由此不是随意选择的搜索范围，而是一份根存在的证据。

取中点 $m = (a + b) / 2$ 。若 $f (m) = 0$ ，已经找到根；否则，中点函数值必与某一个端点同号。丢弃这一侧的一半，保留异号的一半，就不会丢掉“至少有一个根”这一性质。长度减少一半，根的存在保证却保留下来。这种每次循环都成立的性质称为算法不变量。

关键是算法并不知道零点的精确位置，也不需要曲线单调。它通过保留一个有保证的集合来减小不确定性。若初始区间中有多个零点，某次舍弃的那一半可能仍包含别的根，因此不能把舍弃操作理解为证明那一半完全没有根。University of Waterloo，Bisection Method

输入、循环和输出的明确约定

输入包括连续函数、两个有限端点、所要求的位置精度，以及最大迭代次数。先计算两个端点的函数值；若某端点已经是零，返回该端点。如果二者同号，应报告“没有建立异号夹逼”，而不是报告“函数没有根”。如果数值不是有限实数，则需先处理定义域或溢出问题。

在精确实数运算下，循环可表达为：

计算当前区间中点，并检查当前半宽是否满足位置误差要求。
计算中点函数值；若它恰为零，返回中点。
若中点与左端点异号，令右端点等于中点；否则令左端点等于中点。
保存新的端点值，重复上述步骤，直到达到精度或触及迭代上限。

实际程序可直接比较符号，不必计算两个函数值的乘积；乘积可能在端点值本身有限时仍然溢出。重复使用已经计算过的端点值，每轮只需要一个新函数值，这对函数计算昂贵的模型尤其重要。

输出最好包括近似根、最终夹逼区间、半宽误差界、函数残差、迭代次数与停止原因。只返回一个带很多小数的数字，会丢掉二分法最有价值的证据。达到最大次数与达到误差目标是不同状态，不能为了给出结果而把前者标记为成功。

收敛证明与迭代次数的计算

令初始区间为 $[a_{0}, b_{0}]$ ，在完成 $n$ 次保留半区间之后得到 $[a_{n}, b_{n}]$ 。区间嵌套，长度为 $b_{n} - a_{n} = \frac{b_{0} - a_{0}}{2^{n}} .$ 左端点单调不减且有上界，右端点单调不增且有下界。实数的完备性保证二者有极限，长度趋零说明极限相同，记为 $r$ 。端点函数值始终异号，而连续性使其极限同为 $f (r)$ ，故只能有 $f (r) = 0$ 。这把区间几何、实数完备性与函数连续性连接在一起。

若把当前中点记为 $m_{n} = (a_{n} + b_{n}) / 2$ ，则根留在区间内，所以 $| m_{n} - r | \leq \frac{b_{n} - a_{n}}{2} = \frac{b_{0} - a_{0}}{2^{n + 1}} .$ 这一估计不依赖导数，也不依赖根的唯一性。为使误差不超过 $ε_{x} > 0$ ，只需完成 $n \geq max (0, ⌈ \log_{2} \frac{b_{0} - a_{0}}{2 ε_{x}} ⌉)$ 次区间缩减。不同教材可能把第一次中点计算记为第一步，因此公式指数有时差一；必须先说明计数约定，而不能只比较外观。

例如初始长度为一，要求位置误差不超过百万分之一，则十九次缩减已足够，因为 $2^{- 20} < 1 0^{- 6}$ 。区间误差每步固定减半，属于稳定可预测的线性收敛。更多迭代并不会像理想牛顿法那样突然成倍增加正确小数位，但它提供了明确的最坏情形成本。

算例一：计算平方根二

令 $f (x) = x^{2} - 2$ 。在 $[1, 2]$ 上函数连续，端点值分别为负一和二，根被夹住。前四次中点检查如下；表中的区间是检查之前的区间。

检查次数	当前区间	中点	中点函数值	保留区间
1	[1, 2]	1.5	0.25	[1, 1.5]
2	[1, 1.5]	1.25	−0.4375	[1.25, 1.5]
3	[1.25, 1.5]	1.375	−0.109375	[1.375, 1.5]
4	[1.375, 1.5]	1.4375	0.06640625	[1.375, 1.4375]

二分法四轮区间逐步收缩到根号二附近，显示各轮中点和保留区间 — 从区间 [1,2] 出发，按中点符号保留包含根的一半；虚线是真值位置，金点是各轮试探中点。

四次缩减后，若取新夹逼区间的中点作为输出，则得到 $1.40625$ ，保证误差不超过 $0.03125$ 。这不是第四次被检查的中点，而是更新后区间的中点；两种输出惯例各自可行，但误差上界要与实际返回值相对应。

继续到十次缩减，区间为 $[1.4140625, 1.4150390625]$ ，中点为 $1.41455078125$ ，误差保证为 $0.00048828125$ 。近似数不必刚好位于根的同一侧，区间证书已经把不确定性完整表达出来。若想证明根唯一，可另外利用 $f^{'} (x) = 2 x > 0$ ；唯一性不是二分迭代能够开始的必要条件。

算例二：由余弦方程寻找固定点

考虑 $\cos x = x$ ，等价于求 $g (x) = \cos x - x$ 的零点，角度采用弧度。在区间 $[0, 1]$ 上， $g (0) = 1$ ， $g (1) < 0$ ，所以至少有一个根。其导数为 $- \sin x - 1 < 0$ ，故这个区间内根唯一。

中点依次为 $0.5, 0.75, 0.625, 0.6875, 0.71875, 0.734375, 0.7421875$ ，相应符号依次为正、负、正、正、正、正、负。七次缩减后根落在 $[0.734375, 0.7421875]$ ；继续到十次缩减，得到 $[0.73828125, 0.7392578125]$ 。中点 $0.73876953125$ 的保证误差仍为 $2^{- 11}$ 。

两例的函数外观和求值方式不同，一个只需乘法，另一个需要三角函数，但夹逼不变量完全相同。这正是通用数值算法的意义。计算三角函数时若把角度制误用为度数，求解的会是另一个函数；迭代本身再准确也不能修复模型输入的语义错误。

位置误差、残差与浮点数停止规则

残差 $| f (m) |$ 衡量方程满足得多好，位置误差 $| m - r |$ 衡量近似根离真根多远，二者不是同一个量。对函数 $f (x) = 1 0^{- 12} (x - 1)$ ，点零的残差只有 $1 0^{- 12}$ ，离根的距离却是一。仅凭残差小就宣布位置精确，会受函数缩放影响。

如果在包含根与近似点的区间上已知 $| f^{'} (x) | \geq μ > 0$ ，中值定理才给出 $| m - r | \leq | f (m) | / μ$ 。二分法的区间半宽不需要这种额外假设，所以通常以位置容差为主要保证。若问题本身关注方程残差，也可同时检查两种目标，清楚标明各自单位。

实际程序常采用绝对与相对容差的组合，例如要求半宽不超过 $a t o l + r t o l | m |$ ，其中绝对容差为正。接近零的根不能只用相对误差，因为参照尺度也会接近零。函数有噪声时，还应承认符号判断存在可信度限制，不能继续声称严格保持精确数学中的异号条件。

浮点数只有有限密度，区间很短时计算出的中点可能等于某个端点，继续迭代便不再缩小区间。程序应检测这种停滞并报告达到表示精度限制。计算中点也需留意大数溢出；常用 $a + (b - a) / 2$ 可以减少同号大数相加的风险，但极端异号大数的差仍可能溢出，严谨库函数会采用更稳健的分支实现。

失败例：条件为何不可少

对 $f (x) = 1 / x$ ，若只看负一与一两端，函数值异号，但区间中没有零点，而且零处函数未定义。二分可能趋向奇点，区间缩小却不能证明找到根。连续性是把符号变化变成零值存在的桥梁；它不能通过有限次采样自动证明，必须来自函数分析或明确模型假设。

反过来，对 $f (x) = x^{2}$ ，零是一个根，但任何跨过零且端点不为零的区间两端都同为正。标准异号二分法不能从这些端点启动。端点同号只说明这份证据不足，不说明没有根。偶重根尤其容易在仅检测符号变化的扫描中被遗漏，寻找全部根需要更强的信息或其他方法。

对一个具有多个根的连续函数，算法最终保留哪一个根依赖初始区间与中点符号。即使根唯一，函数求值错误、单位错误或把不连续片段放进初始区间，也会破坏保证。把算法称为“可靠”指的是在已陈述条件和可信计算之下有证明，不表示它能替使用者验证所有模型前提。

二分法可以与牛顿法配合：先保留可靠夹逼区间，尝试更快的牛顿步；若候选点离开区间、导数太小或进展不佳，就退回二分。这样保留区间证据，同时利用局部曲线信息。具体混合算法还要规定可接受步的条件，不能仅把两种公式交替写出就宣称有完整收敛证明。

找到初始区间与验证根的数量

在实际问题中，最费判断的步骤有时是建立初始区间。若参数有明确物理范围，可以先分析函数在范围端点的符号；若没有，可以围绕一个初值逐步扩大搜索范围，同时监测函数是否仍有定义。扩大范围只是搜寻证据的方法，不保证所有连续函数最终都出现异号端点，例如始终为正的函数就不会出现。

在网格上扫描相邻样本的符号，可以发现一些夹逼区间，却不能据此宣布找到了全部根。两个根可能落在同一网格小段内，使两端同号；偶重根甚至不改变符号。若目标是完整枚举多项式的实根，可以结合导数分割单调区间或使用专门代数方法。求一个已夹住的根与证明所有根已找到，是不同任务。

严格单调性常能提供唯一性。若区间内函数严格递增且端点异号，便恰有一个根；导数处处为正是常用但不是唯一的单调性充分条件。二分法本身只保留存在性，唯一性证据来自额外分析。把这两种证据分别记录下来，后续解释算法结果时会更清楚。

对模型输出寻找阈值也可以化为求根。若水位预测函数为 $H (t)$ ，目标水位为 $H_{*}$ ，令 $f (t) = H (t) - H_{*}$ ，二分便可求达到阈值的时刻。但如果水位在区间中多次升降，所找到的可能不是首次达到的时刻；首次事件需要时间顺序扫描及更明确的模型性质。算法公式没有变化，任务含义却增加了约束。

变量缩放有助于设置容差。若原变量以秒计而范围跨越多年，先把时间换成相对于某个基准的无量纲变量，能使相对容差更易解释，也可减少某些浮点问题。最终误差界必须再换回原单位。输出为某个时刻附近的窄区间，比只写一个不带单位的数字更能说明模型允许的精度。

一次可复核计算应保存函数版本、初始端点、容差与停止状态；若函数来自带随机噪声的模拟，还应说明重复求值是否会改变符号。二分法的证明假设每次评估同一个确定函数，随机输出需要另行设计统计判断，不能假装每轮的正负号都是精确事实。

输出根区间时还应保留足够有效数字，避免把两个不同端点四舍五入成同一个显示值；显示格式不能夸大内部计算已经达到的精度。

历史与算法定位

逐次折半是一种很早出现的计算思想，不能简单把现代通用二分程序归给某个唯一发明者。其分析基础与连续函数中间值定理的严格化密切相关：玻尔查诺于 1817 年发表相关证明，柯西随后在分析体系中使用逐步缩小区间的思路。讨论这种历史应区分计算程序、存在性证明以及现代浮点实现，不把后来的程序细节倒写进早期文献。MacTutor：Bolzano；数学史书评对相关证明的比较

English overview

The bisection method finds a zero of a continuous real function by maintaining an interval whose endpoint values have opposite signs. Each midpoint evaluation selects a half-interval that retains this property. The method therefore reduces uncertainty while preserving evidence that at least one root remains inside.

After a specified number of interval reductions, the width is the initial width divided by a power of two. Returning the midpoint gives a position-error bound equal to half the final width. Iteration counting and the choice of returned point must be stated consistently. A small function residual is a different measure: without a lower bound on the derivative, it does not necessarily imply a small error in the root's position.

Continuity is essential. A sign change across a pole does not establish a zero, and equal endpoint signs do not prove that no root exists. Even-multiplicity roots can escape a sign-change search. Practical implementations must handle endpoints, nonfinite evaluations, iteration limits, unreliable signs, and floating-point stagnation. The result should include its bracket and stopping reason, not merely many decimal digits. Bisection is predictable rather than rapidly convergent, making it a useful safeguard for faster local methods such as Newton iteration.

编者评注（AI 辅助）

本站把夹逼区间作为二分法的主要输出，因为它比一个孤立近似数更能表达算法已经证明什么。算例特意区分更新前中点与更新后中点，避免迭代次数和误差界差一位。连续性失败、偶重根与残差缩放分别检验三种不同前提。这样的组织旨在把“折半”的直觉提升为带证书的数值方法，同时保持数学保证与浮点实现限制之间的清楚边界。

参考资料与知识联系

Douglas Wilhelm Harder，Topic 10.1: Bisection Method，University of Waterloo：算法与误差分析背景；本文采用返回最终中点的计数约定。
MacTutor，University of St Andrews：Bernard Bolzano；Grattan-Guinness books 中对玻尔查诺与柯西证明的评论。
前置：函数、极限、连续映射；比较：牛顿法；应用背景：数学建模。