二分法：修订间差异

2026年9月20日 (日) 07:17的最新版本

二分法（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 中对玻尔查诺与柯西证明的评论。
前置：函数、极限、连续映射；比较：牛顿法；应用背景：数学建模。

@@ 第1行： / 第1行： @@
-'''二分法'''（bisection method）是求连续实函数零点的区间迭代算法。在一个端点函数值异号的闭区间内，反复计算中点，并保留仍然异号的半个区间，从而把至少一个零点夹在越来越短的区间中。它的突出性质是具有可直接计算的位置误差上界，不需要导数，也不要求事先知道零点附近的曲线斜率。
+'''二分法'''（bisection method）是一种求连续实函数零点的方法：先找到函数值一正一负的两个端点，再反复取中点，把包含零点的区间缩短一半。每次缩减之后，区间本身都给出近似根的误差范围。
-二分法求的是一个区间中的某个零点，不是自动列出全部解。连续性与端点异号是保证的核心；它们分别排除“跳过零值”和“区间内根本没有被夹住的零点”这两类问题。算法、数学保证和计算机停止规则需要一起理解。
+== 不知道平方根二，怎样一步步夹住它 ==
+求 <math>\sqrt2</math> 等价于求 <math>f(x)=x^2-2</math> 的正零点。因为 <math>1^2<2<2^2</math>，根在 <math>[1,2]</math> 中。先试中点 <math>1.5</math>，其平方为 <math>2.25</math>，偏大，便把右端改为 <math>1.5</math>；再试新中点 <math>1.25</math>，其平方为 <math>1.5625</math>，偏小，便把左端改为 <math>1.25</math>。
-== 先夹住一个根，再逐步缩小不确定性 ==
+这两次试探都没有猜出精确根，但把一单位长的范围缩到了四分之一单位。继续使用同一规则：
-假设一个连续量从负值变成正值，中间必须经过零。对于函数 <math>f:[a,b]\to\mathbb R</math>，其中 <math>a<b</math>，若 <math>f(a)f(b)<0</math>，中间值定理保证存在 <math>r\in(a,b)</math> 使 <math>f(r)=0</math>。初始区间由此不是随意选择的搜索范围，而是一份根存在的证据。
-取中点 <math>m=(a+b)/2</math>。若 <math>f(m)=0</math>，已经找到根；否则，中点函数值必与某一个端点同号。丢弃这一侧的一半，保留异号的一半，就不会丢掉“至少有一个根”这一性质。长度减少一半，根的存在保证却保留下来。这种每次循环都成立的性质称为算法不变量。
+<div class="math-table-scroll" role="region" aria-label="二分法计算平方根二的前四轮" tabindex="0">
-关键是算法并不知道零点的精确位置，也不需要曲线单调。它通过保留一个有保证的集合来减小不确定性。若初始区间中有多个零点，某次舍弃的那一半可能仍包含别的根，因此不能把舍弃操作理解为证明那一半完全没有根。[https://ece.uwaterloo.ca/~dwharder/NumericalAnalysis/10RootFinding/bisection/complete.html University of Waterloo，Bisection Method]
-== 输入、循环和输出的明确约定 ==
-输入包括连续函数、两个有限端点、所要求的位置精度，以及最大迭代次数。先计算两个端点的函数值；若某端点已经是零，返回该端点。如果二者同号，应报告“没有建立异号夹逼”，而不是报告“函数没有根”。如果数值不是有限实数，则需先处理定义域或溢出问题。
-在精确实数运算下，循环可表达为：
-# 计算当前区间中点，并检查当前半宽是否满足位置误差要求。
-# 计算中点函数值；若它恰为零，返回中点。
-# 若中点与左端点异号，令右端点等于中点；否则令左端点等于中点。
-# 保存新的端点值，重复上述步骤，直到达到精度或触及迭代上限。
-实际程序可直接比较符号，不必计算两个函数值的乘积；乘积可能在端点值本身有限时仍然溢出。重复使用已经计算过的端点值，每轮只需要一个新函数值，这对函数计算昂贵的模型尤其重要。
-输出最好包括近似根、最终夹逼区间、半宽误差界、函数残差、迭代次数与停止原因。只返回一个带很多小数的数字，会丢掉二分法最有价值的证据。达到最大次数与达到误差目标是不同状态，不能为了给出结果而把前者标记为成功。
-== 收敛证明与迭代次数的计算 ==
-令初始区间为 <math>[a_0,b_0]</math>，在完成 <math>n</math> 次保留半区间之后得到 <math>[a_n,b_n]</math>。区间嵌套，长度为
-<math display="block">b_n-a_n=\frac{b_0-a_0}{2^n}.</math>
-左端点单调不减且有上界，右端点单调不增且有下界。实数的完备性保证二者有极限，长度趋零说明极限相同，记为 <math>r</math>。端点函数值始终异号，而连续性使其极限同为 <math>f(r)</math>，故只能有 <math>f(r)=0</math>。这把区间几何、实数完备性与函数连续性连接在一起。
-若把当前中点记为 <math>m_n=(a_n+b_n)/2</math>，则根留在区间内，所以
-<math display="block">|m_n-r|\le\frac{b_n-a_n}{2}=\frac{b_0-a_0}{2^{n+1}}.</math>
-这一估计不依赖导数，也不依赖根的唯一性。为使误差不超过 <math>\varepsilon_x>0</math>，只需完成
-<math display="block">n\ge\max\left(0,\left\lceil\log_2\frac{b_0-a_0}{2\varepsilon_x}\right\rceil\right)</math>
-次区间缩减。不同教材可能把第一次中点计算记为第一步，因此公式指数有时差一；必须先说明计数约定，而不能只比较外观。
-例如初始长度为一，要求位置误差不超过百万分之一，则十九次缩减已足够，因为 <math>2^{-20}<10^{-6}</math>。区间误差每步固定减半，属于稳定可预测的线性收敛。更多迭代并不会像理想牛顿法那样突然成倍增加正确小数位，但它提供了明确的最坏情形成本。
-== 算例一：计算平方根二 ==
-令 <math>f(x)=x^2-2</math>。在 <math>[1,2]</math> 上函数连续，端点值分别为负一和二，根被夹住。前四次中点检查如下；表中的区间是检查之前的区间。
-<div class="math-table-scroll" role="region" aria-label="平方根二的二分法迭代" tabindex="0">
 {| class="wikitable"
-! 检查次数 !! 当前区间 !! 中点 !! 中点函数值 !! 保留区间
+! 轮次 !! 检查前区间 !! 中点 !! 中点的 <math>x^2-2</math> !! 保留区间
 |-
-| 1 || [1, 2] || 1.5 || 0.25 || [1, 1.5]
+| 1 || [1,2] || 1.5 || 0.25 || [1,1.5]
 |-
-| 2 || [1, 1.5] || 1.25 || −0.4375 || [1.25, 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]
+| 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]
+| 4 || [1.375,1.5] || 1.4375 || 0.06640625 || [1.375,1.4375]
 |}
 </div>
-[[File:Gezhi-bisection-interval.svg|frame|center|alt=二分法四轮区间逐步收缩到根号二附近，显示各轮中点和保留区间|从区间 [1,2] 出发，按中点符号保留包含根的一半；虚线是真值位置，金点是各轮试探中点。]]
+[[File:Gezhi-bisection-interval-theme.svg|frame|center|alt=二分法四轮区间逐步收缩到根号二附近，显示各轮中点和保留区间|从区间 [1,2] 出发，按中点符号保留包含根的一半；虚线是真值位置，金点是各轮试探中点。]]
-四次缩减后，若取新夹逼区间的中点作为输出，则得到 <math>1.40625</math>，保证误差不超过 <math>0.03125</math>。这不是第四次被检查的中点，而是更新后区间的中点；两种输出惯例各自可行，但误差上界要与实际返回值相对应。
+图中每一行对应一次区间检查，金点是当轮中点。观察每轮保留下来的线段，它始终跨在表示真根位置的虚线两侧。计算时并不知道虚线的位置，只靠端点函数值的正负来决定保留哪半段。
-继续到十次缩减，区间为 <math>[1.4140625,1.4150390625]</math>，中点为 <math>1.41455078125</math>，误差保证为 <math>0.00048828125</math>。近似数不必刚好位于根的同一侧，区间证书已经把不确定性完整表达出来。若想证明根唯一，可另外利用 <math>f'(x)=2x>0</math>；唯一性不是二分迭代能够开始的必要条件。
+四轮之后，根在 <math>[1.375,1.4375]</math>。若现在要给出一个数，取这个新区间的中点 <math>1.40625</math>。它到区间任意点的距离都不超过半宽 <math>0.03125</math>，所以到真根的误差也不超过这个值。注意返回的是更新后的中点，与第四轮已检查的 <math>1.4375</math> 不同。
-== 算例二：由余弦方程寻找固定点 ==
+== 为什么一正一负就有用 ==
-考虑 <math>\cos x=x</math>，等价于求 <math>g(x)=\cos x-x</math> 的零点，角度采用弧度。在区间 <math>[0,1]</math> 上，<math>g(0)=1</math>，<math>g(1)<0</math>，所以至少有一个根。其导数为 <math>-\sin x-1<0</math>，故这个区间内根唯一。
+上面的例子用到了平方函数递增的性质。不过二分法本身只需要更弱的条件。设 <math>f</math> 在闭区间 <math>[a,b]</math> 连续，且 <math>f(a),f(b)</math> 异号。根据中间值定理，从负值连续走到正值时必经过零，因此区间内至少有一个根。
-中点依次为 <math>0.5,0.75,0.625,0.6875,0.71875,0.734375,0.7421875</math>，相应符号依次为正、负、正、正、正、正、负。七次缩减后根落在 <math>[0.734375,0.7421875]</math>；继续到十次缩减，得到 <math>[0.73828125,0.7392578125]</math>。中点 <math>0.73876953125</math> 的保证误差仍为 <math>2^{-11}</math>。
+取中点 <math>m=(a+b)/2</math>。如果 <math>f(m)=0</math>，已经找到根；否则它不是正就是负，必与一个端点同号。保留另一侧，新的两个端点仍异号，中间值定理再次保证根存在。
-两例的函数外观和求值方式不同，一个只需乘法，另一个需要三角函数，但夹逼不变量完全相同。这正是通用数值算法的意义。计算三角函数时若把角度制误用为度数，求解的会是另一个函数；迭代本身再准确也不能修复模型输入的语义错误。
+例如初始左端为负、右端为正。中点为正时，保留左端到中点；中点为负时，保留中点到右端。每一步都把“至少存在一个根”这件事传递到新范围内。[https://ece.uwaterloo.ca/~dwharder/NumericalAnalysis/10RootFinding/bisection/complete.html Waterloo：Bisection Method]
-== 位置误差、残差与浮点数停止规则 ==
+函数可以上下起伏，区间也可能含多个根。二分仍会保住至少一个，但舍去的一半也可能有其他根。若问题要求列出所有根，还需要另外划分区间或分析根的数量。
-残差 <math>|f(m)|</math> 衡量方程满足得多好，位置误差 <math>|m-r|</math> 衡量近似根离真根多远，二者不是同一个量。对函数 <math>f(x)=10^{-12}(x-1)</math>，点零的残差只有 <math>10^{-12}</math>，离根的距离却是一。仅凭残差小就宣布位置精确，会受函数缩放影响。
-如果在包含根与近似点的区间上已知 <math>|f'(x)|\ge\mu>0</math>，中值定理才给出 <math>|m-r|\le|f(m)|/\mu</math>。二分法的区间半宽不需要这种额外假设，所以通常以位置容差为主要保证。若问题本身关注方程残差，也可同时检查两种目标，清楚标明各自单位。
+== 迭代多少轮才能达到精度 ==
+用 <math>[a_0,b_0]</math> 表示初始区间，完成 <math>n</math> 次缩减后记为 <math>[a_n,b_n]</math>。每轮长度减半，所以
+<math display="block">b_n-a_n=\frac{b_0-a_0}{2^n}.</math>
+取更新后的中点 <math>m_n</math> 作为近似，得到位置误差界
+<math display="block">|m_n-r|\le\frac{b_n-a_n}{2}=\frac{b_0-a_0}{2^{n+1}}.</math>
+这里的 <math>r</math> 是最终嵌套区间共同包含的一个根。
-实际程序常采用绝对与相对容差的组合，例如要求半宽不超过 <math>\mathrm{atol}+\mathrm{rtol}|m|</math>，其中绝对容差为正。接近零的根不能只用相对误差，因为参照尺度也会接近零。函数有噪声时，还应承认符号判断存在可信度限制，不能继续声称严格保持精确数学中的异号条件。
+初始长度为一时，十轮后的半宽是 <math>2^{-11}=0.00048828125</math>。平方根二的实际区间为 <math>[1.4140625,1.4150390625]</math>，中点为 <math>1.41455078125</math>，与公式完全一致。
-浮点数只有有限密度，区间很短时计算出的中点可能等于某个端点，继续迭代便不再缩小区间。程序应检测这种停滞并报告达到表示精度限制。计算中点也需留意大数溢出；常用 <math>a+(b-a)/2</math> 可以减少同号大数相加的风险，但极端异号大数的差仍可能溢出，严谨库函数会采用更稳健的分支实现。
+若要求位置误差不超过 <math>10^{-6}</math>，需 <math>2^{-(n+1)}\le10^{-6}</math>。十九轮已经足够，因为 <math>2^{-20}\approx9.54\times10^{-7}</math>。一般初始长度与容差 <math>\varepsilon_x>0</math> 对应的轮数为
+<math display="block">n\ge\max\left(0,\left\lceil\log_2\frac{b_0-a_0}{2\varepsilon_x}\right\rceil\right).</math>
+上取整符号表示选不小于所算数值的最小整数。这个计算让我们在开始迭代前就知道最坏需要多少轮。
-== 失败例：条件为何不可少 ==
+嵌套区间为何最终指向根，也可完整说明。左端点只增不减，右端点只减不增，两者都被初始区间限制，因此各有极限。区间长度趋零，两个极限相同，记为 <math>r</math>。每个左端的函数值保持同一种符号，右端保持另一种；由连续性，两端函数值的极限都为 <math>f(r)</math>。它既不能严格为正，也不能严格为负，只能为零。
-对 <math>f(x)=1/x</math>，若只看负一与一两端，函数值异号，但区间中没有零点，而且零处函数未定义。二分可能趋向奇点，区间缩小却不能证明找到根。连续性是把符号变化变成零值存在的桥梁；它不能通过有限次采样自动证明，必须来自函数分析或明确模型假设。
-反过来，对 <math>f(x)=x^2</math>，零是一个根，但任何跨过零且端点不为零的区间两端都同为正。标准异号二分法不能从这些端点启动。端点同号只说明这份证据不足，不说明没有根。偶重根尤其容易在仅检测符号变化的扫描中被遗漏，寻找全部根需要更强的信息或其他方法。
+== 另一例：寻找余弦曲线与直线的交点 ==
+求 <math>\cos x=x</math>，角度用弧度。令 <math>g(x)=\cos x-x</math>，有 <math>g(0)=1</math>、<math>g(1)<0</math>，所以从 <math>[0,1]</math> 开始。
-对一个具有多个根的连续函数，算法最终保留哪一个根依赖初始区间与中点符号。即使根唯一，函数求值错误、单位错误或把不连续片段放进初始区间，也会破坏保证。把算法称为“可靠”指的是在已陈述条件和可信计算之下有证明，不表示它能替使用者验证所有模型前提。
+第一中点 <math>0.5</math> 的函数值约为 <math>0.3776</math>，保留 <math>[0.5,1]</math>。第二中点 <math>0.75</math> 的函数值约为 <math>-0.0183</math>，保留 <math>[0.5,0.75]</math>。第三中点 <math>0.625</math> 为正，保留 <math>[0.625,0.75]</math>。继续七轮后区间为 <math>[0.734375,0.7421875]</math>，十轮后为 <math>[0.73828125,0.7392578125]</math>。
-二分法可以与[[牛顿法]]配合：先保留可靠夹逼区间，尝试更快的牛顿步；若候选点离开区间、导数太小或进展不佳，就退回二分。这样保留区间证据，同时利用局部曲线信息。具体混合算法还要规定可接受步的条件，不能仅把两种公式交替写出就宣称有完整收敛证明。
+返回最后区间中点 <math>0.73876953125</math>，误差不超过 <math>2^{-11}</math>。由于区间上 <math>g'(x)=-\sin x-1<0</math>，它严格递减，所夹住的根还是唯一的。唯一性来自这一额外分析，区间缩减的过程则与平方根例子完全相同。
-== 找到初始区间与验证根的数量 ==
+== 什么时候可以停止 ==
-在实际问题中，最费判断的步骤有时是建立初始区间。若参数有明确物理范围，可以先分析函数在范围端点的符号；若没有，可以围绕一个初值逐步扩大搜索范围，同时监测函数是否仍有定义。扩大范围只是搜寻证据的方法，不保证所有连续函数最终都出现异号端点，例如始终为正的函数就不会出现。
+若目标是根的位置，最直接的停止条件是区间半宽小于指定容差。输出近似值时同时给出端点和半宽，就保留了二分法的精度依据。实际程序还应处理几种状态：
-在网格上扫描相邻样本的符号，可以发现一些夹逼区间，却不能据此宣布找到了全部根。两个根可能落在同一网格小段内，使两端同号；偶重根甚至不改变符号。若目标是完整枚举多项式的实根，可以结合导数分割单调区间或使用专门代数方法。求一个已夹住的根与证明所有根已找到，是不同任务。
+# 先检查端点是否已经为零；若是，可直接返回。
+# 确认端点值有限且异号，再开始迭代。
+# 每轮只需新算中点值，已知端点值可以复用；符号用比较判断，避免计算乘积引起溢出。
+# 达到精度后返回最终中点；若达到最大轮数或浮点中点已等于端点，则报告相应停止原因。
-严格单调性常能提供唯一性。若区间内函数严格递增且端点异号，便恰有一个根；导数处处为正是常用但不是唯一的单调性充分条件。二分法本身只保留存在性，唯一性证据来自额外分析。把这两种证据分别记录下来，后续解释算法结果时会更清楚。
+函数残差 <math>|f(m)|</math> 是另一种量，它不直接等于位置误差。对 <math>f(x)=10^{-12}(x-1)</math>，点零的残差只有 <math>10^{-12}</math>，却距根一单位远。若已知区间内 <math>|f'|\ge\mu>0</math>，才可由中值定理得到 <math>|m-r|\le|f(m)|/\mu</math>。二分的半宽界不需要这个导数条件。
-对模型输出寻找阈值也可以化为求根。若水位预测函数为 <math>H(t)</math>，目标水位为 <math>H_*</math>，令 <math>f(t)=H(t)-H_*</math>，二分便可求达到阈值的时刻。但如果水位在区间中多次升降，所找到的可能不是首次达到的时刻；首次事件需要时间顺序扫描及更明确的模型性质。算法公式没有变化，任务含义却增加了约束。
+接近零的根应有正的绝对容差；也可用 <math>\mathrm{atol}+\mathrm{rtol}|m|</math> 组合绝对与相对精度。浮点运算无法无限细分，中点与端点相等就意味着该表示精度下不能继续推进。若函数来自带误差的测量或模拟，符号本身也可能不确定，这时不能仅凭显示出的正负号宣称严格夹住了真根。
-变量缩放有助于设置容差。若原变量以秒计而范围跨越多年，先把时间换成相对于某个基准的无量纲变量，能使相对容差更易解释，也可减少某些浮点问题。最终误差界必须再换回原单位。输出为某个时刻附近的窄区间，比只写一个不带单位的数字更能说明模型允许的精度。
+== 两个失败例与初始区间的选择 ==
+函数 <math>1/x</math> 在负一和一处异号，却没有零点。两端之间的零处未定义，连续性条件失效。缩小区间可能逼近的是奇点。
-一次可复核计算应保存函数版本、初始端点、容差与停止状态；若函数来自带随机噪声的模拟，还应说明重复求值是否会改变符号。二分法的证明假设每次评估同一个确定函数，随机输出需要另行设计统计判断，不能假装每轮的正负号都是精确事实。
+函数 <math>x^2</math> 则正好相反：零是根，但负一与一处都为正。端点同号只说明没有建立异号夹逼，不说明没有根。用网格扫描符号变化也会漏掉这样的偶重根，或漏掉同一个小网格内的两个根。
-输出根区间时还应保留足够有效数字，避免把两个不同端点四舍五入成同一个显示值；显示格式不能夸大内部计算已经达到的精度。
+选择初始区间时，可先利用变量的物理范围和函数单调性。例如求某个持续上升水位达到目标的时刻，可以令 <math>f(t)=H(t)-H_*</math>，找到一早一晚两个时刻的异号值。如果水位反复升降，二分得到一个达到时刻，却未必是首次达到时刻，需要先按时间顺序定位。
-== 历史与算法定位 ==
+[[牛顿法]]可利用切线更快地改进近似；二分法则用区间保留误差证据。混合算法常先维持异号区间，再尝试区间内的牛顿候选点；不合适时改用中点。二者利用的信息不同，结合时仍要明确每一步怎样维持夹逼。
-逐次折半是一种很早出现的计算思想，不能简单把现代通用二分程序归给某个唯一发明者。其分析基础与连续函数中间值定理的严格化密切相关：玻尔查诺于 1817 年发表相关证明，柯西随后在分析体系中使用逐步缩小区间的思路。讨论这种历史应区分计算程序、存在性证明以及现代浮点实现，不把后来的程序细节倒写进早期文献。[https://mathshistory.st-andrews.ac.uk/Biographies/Bolzano/ MacTutor：Bolzano]；[https://mathshistory.st-andrews.ac.uk/Extras/Grattan-Guinness_books/ 数学史书评对相关证明的比较]
-== English overview ==
+== 历史 ==
-<div lang="en" class="math-english-summary">
+反复折半是早期数值计算中的基本思想。现代二分法的存在性与收敛证明依赖连续函数的中间值性质，其严格化与玻尔查诺 1817 年的工作及随后柯西的分析体系相联系。[https://mathshistory.st-andrews.ac.uk/Biographies/Bolzano/ MacTutor：Bolzano]；[https://mathshistory.st-andrews.ac.uk/Extras/Grattan-Guinness_books/ 相关数学史讨论]
-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.
-</div>
-== 编者评注（AI 辅助） ==
-<div class="math-editorial-note">
-本站把夹逼区间作为二分法的主要输出，因为它比一个孤立近似数更能表达算法已经证明什么。算例特意区分更新前中点与更新后中点，避免迭代次数和误差界差一位。连续性失败、偶重根与残差缩放分别检验三种不同前提。这样的组织旨在把“折半”的直觉提升为带证书的数值方法，同时保持数学保证与浮点实现限制之间的清楚边界。
-</div>
 == 参考资料与知识联系 ==