二分法

二分法（bisection method）是一种求连续实函数零点的方法：先找到函数值一正一负的两个端点，再反复取中点，把包含零点的区间缩短一半。每次缩减之后，区间本身都给出近似根的误差范围。

不知道平方根二，怎样一步步夹住它

求 $\sqrt{2}$ 等价于求 $f (x) = x^{2} - 2$ 的正零点。因为 $1^{2} < 2 < 2^{2}$ ，根在 $[1, 2]$ 中。先试中点 $1.5$ ，其平方为 $2.25$ ，偏大，便把右端改为 $1.5$ ；再试新中点 $1.25$ ，其平方为 $1.5625$ ，偏小，便把左端改为 $1.25$ 。

这两次试探都没有猜出精确根，但把一单位长的范围缩到了四分之一单位。继续使用同一规则：

轮次	检查前区间	中点	中点的 $x^{2} - 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.375, 1.4375]$ 。若现在要给出一个数，取这个新区间的中点 $1.40625$ 。它到区间任意点的距离都不超过半宽 $0.03125$ ，所以到真根的误差也不超过这个值。注意返回的是更新后的中点，与第四轮已检查的 $1.4375$ 不同。

为什么一正一负就有用

上面的例子用到了平方函数递增的性质。不过二分法本身只需要更弱的条件。设 $f$ 在闭区间 $[a, b]$ 连续，且 $f (a), f (b)$ 异号。根据中间值定理，从负值连续走到正值时必经过零，因此区间内至少有一个根。

取中点 $m = (a + b) / 2$ 。如果 $f (m) = 0$ ，已经找到根；否则它不是正就是负，必与一个端点同号。保留另一侧，新的两个端点仍异号，中间值定理再次保证根存在。

例如初始左端为负、右端为正。中点为正时，保留左端到中点；中点为负时，保留中点到右端。每一步都把“至少存在一个根”这件事传递到新范围内。Waterloo：Bisection Method

函数可以上下起伏，区间也可能含多个根。二分仍会保住至少一个，但舍去的一半也可能有其他根。若问题要求列出所有根，还需要另外划分区间或分析根的数量。

迭代多少轮才能达到精度

用 $[a_{0}, b_{0}]$ 表示初始区间，完成 $n$ 次缩减后记为 $[a_{n}, b_{n}]$ 。每轮长度减半，所以 $b_{n} - a_{n} = \frac{b_{0} - a_{0}}{2^{n}} .$ 取更新后的中点 $m_{n}$ 作为近似，得到位置误差界 $| m_{n} - r | \leq \frac{b_{n} - a_{n}}{2} = \frac{b_{0} - a_{0}}{2^{n + 1}} .$ 这里的 $r$ 是最终嵌套区间共同包含的一个根。

初始长度为一时，十轮后的半宽是 $2^{- 11} = 0.00048828125$ 。平方根二的实际区间为 $[1.4140625, 1.4150390625]$ ，中点为 $1.41455078125$ ，与公式完全一致。

若要求位置误差不超过 $1 0^{- 6}$ ，需 $2^{- (n + 1)} \leq 1 0^{- 6}$ 。十九轮已经足够，因为 $2^{- 20} \approx 9.54 \times 1 0^{- 7}$ 。一般初始长度与容差 $ε_{x} > 0$ 对应的轮数为 $n \geq max (0, ⌈ \log_{2} \frac{b_{0} - a_{0}}{2 ε_{x}} ⌉) .$ 上取整符号表示选不小于所算数值的最小整数。这个计算让我们在开始迭代前就知道最坏需要多少轮。

嵌套区间为何最终指向根，也可完整说明。左端点只增不减，右端点只减不增，两者都被初始区间限制，因此各有极限。区间长度趋零，两个极限相同，记为 $r$ 。每个左端的函数值保持同一种符号，右端保持另一种；由连续性，两端函数值的极限都为 $f (r)$ 。它既不能严格为正，也不能严格为负，只能为零。

另一例：寻找余弦曲线与直线的交点

求 $\cos x = x$ ，角度用弧度。令 $g (x) = \cos x - x$ ，有 $g (0) = 1$ 、 $g (1) < 0$ ，所以从 $[0, 1]$ 开始。

第一中点 $0.5$ 的函数值约为 $0.3776$ ，保留 $[0.5, 1]$ 。第二中点 $0.75$ 的函数值约为 $- 0.0183$ ，保留 $[0.5, 0.75]$ 。第三中点 $0.625$ 为正，保留 $[0.625, 0.75]$ 。继续七轮后区间为 $[0.734375, 0.7421875]$ ，十轮后为 $[0.73828125, 0.7392578125]$ 。

返回最后区间中点 $0.73876953125$ ，误差不超过 $2^{- 11}$ 。由于区间上 $g^{'} (x) = - \sin x - 1 < 0$ ，它严格递减，所夹住的根还是唯一的。唯一性来自这一额外分析，区间缩减的过程则与平方根例子完全相同。

什么时候可以停止

若目标是根的位置，最直接的停止条件是区间半宽小于指定容差。输出近似值时同时给出端点和半宽，就保留了二分法的精度依据。实际程序还应处理几种状态：

先检查端点是否已经为零；若是，可直接返回。
确认端点值有限且异号，再开始迭代。
每轮只需新算中点值，已知端点值可以复用；符号用比较判断，避免计算乘积引起溢出。
达到精度后返回最终中点；若达到最大轮数或浮点中点已等于端点，则报告相应停止原因。

函数残差 $| f (m) |$ 是另一种量，它不直接等于位置误差。对 $f (x) = 1 0^{- 12} (x - 1)$ ，点零的残差只有 $1 0^{- 12}$ ，却距根一单位远。若已知区间内 $| f^{'} | \geq μ > 0$ ，才可由中值定理得到 $| m - r | \leq | f (m) | / μ$ 。二分的半宽界不需要这个导数条件。

接近零的根应有正的绝对容差；也可用 $a t o l + r t o l | m |$ 组合绝对与相对精度。浮点运算无法无限细分，中点与端点相等就意味着该表示精度下不能继续推进。若函数来自带误差的测量或模拟，符号本身也可能不确定，这时不能仅凭显示出的正负号宣称严格夹住了真根。

两个失败例与初始区间的选择

函数 $1 / x$ 在负一和一处异号，却没有零点。两端之间的零处未定义，连续性条件失效。缩小区间可能逼近的是奇点。

函数 $x^{2}$ 则正好相反：零是根，但负一与一处都为正。端点同号只说明没有建立异号夹逼，不说明没有根。用网格扫描符号变化也会漏掉这样的偶重根，或漏掉同一个小网格内的两个根。

选择初始区间时，可先利用变量的物理范围和函数单调性。例如求某个持续上升水位达到目标的时刻，可以令 $f (t) = H (t) - H_{*}$ ，找到一早一晚两个时刻的异号值。如果水位反复升降，二分得到一个达到时刻，却未必是首次达到时刻，需要先按时间顺序定位。

牛顿法可利用切线更快地改进近似；二分法则用区间保留误差证据。混合算法常先维持异号区间，再尝试区间内的牛顿候选点；不合适时改用中点。二者利用的信息不同，结合时仍要明确每一步怎样维持夹逼。

历史

反复折半是早期数值计算中的基本思想。现代二分法的存在性与收敛证明依赖连续函数的中间值性质，其严格化与玻尔查诺 1817 年的工作及随后柯西的分析体系相联系。MacTutor：Bolzano；相关数学史讨论

参考资料与知识联系

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