查看“︁二分法”︁的源代码

'''二分法'''（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>。

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

<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]
|-
| 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]
|}
</div>

[[File:Gezhi-bisection-interval-theme.svg|frame|center|alt=二分法四轮区间逐步收缩到根号二附近，显示各轮中点和保留区间|从区间 [1,2] 出发，按中点符号保留包含根的一半；虚线是真值位置，金点是各轮试探中点。]]

图中每一行对应一次区间检查，金点是当轮中点。观察每轮保留下来的线段，它始终跨在表示真根位置的虚线两侧。计算时并不知道虚线的位置，只靠端点函数值的正负来决定保留哪半段。

四轮之后，根在 <math>[1.375,1.4375]</math>。若现在要给出一个数，取这个新区间的中点 <math>1.40625</math>。它到区间任意点的距离都不超过半宽 <math>0.03125</math>，所以到真根的误差也不超过这个值。注意返回的是更新后的中点，与第四轮已检查的 <math>1.4375</math> 不同。

== 为什么一正一负就有用 ==
上面的例子用到了平方函数递增的性质。不过二分法本身只需要更弱的条件。设 <math>f</math> 在闭区间 <math>[a,b]</math> 连续，且 <math>f(a),f(b)</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>[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>2^{-11}=0.00048828125</math>。平方根二的实际区间为 <math>[1.4140625,1.4150390625]</math>，中点为 <math>1.41455078125</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>\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>\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/ 相关数学史讨论]

== 参考资料与知识联系 ==
* Douglas Wilhelm Harder，[https://ece.uwaterloo.ca/~dwharder/NumericalAnalysis/10RootFinding/bisection/complete.html Topic 10.1: Bisection Method]，University of Waterloo：算法与误差分析背景；本文采用返回最终中点的计数约定。
* MacTutor，University of St Andrews：[https://mathshistory.st-andrews.ac.uk/Biographies/Bolzano/ Bernard Bolzano]；[https://mathshistory.st-andrews.ac.uk/Extras/Grattan-Guinness_books/ Grattan-Guinness books] 中对玻尔查诺与柯西证明的评论。
* 前置：[[函数]]、[[极限]]、[[连续映射]]；比较：[[牛顿法]]；应用背景：[[数学建模]]。
[[分类:数值分析]]