区间怎样把目标逐步夹住？¶

先备知识¶

第 3 章已经证明存在唯一正数 \(\sqrt2\) 满足 \((\sqrt2)^2=2\)，第 2 章已经证明 \(\sqrt2\) 不是有理数。本单元不重新证明这个存在性；它从已知的有理端点 \(1,2\) 出发，持续保留一个含有 \(\sqrt2\) 的小区间。高等代数只用平方的单调比较和不等式。Python 活动只要求会定义函数、用 while 循环重复，以及用 if 分支按条件更新端点。

学习目标¶

完成本单元后，你应能：

1. 写出保持 \(0<a_n<\sqrt2<b_n\)（从而 \(a_n^2<2<b_n^2\)）的区间更新规则；
2. 证明每一步保留的半区间仍含有 \(\sqrt2\)，且区间长度减半；
3. 用中点和区间长度给出可检查的误差上界；
4. 说明这一算法为什么不是一般连续函数的求根法。

牵引问题¶

上一单元的递推从上方逼近 \(\sqrt2\)。另一种更稳健的想法是：不赌一个候选值正确，而是始终保留两个端点。已知

所以 \(0<a_0=1<\sqrt2<2=b_0\)。若取中点，怎样只保留一半区间、又绝不把目标丢掉？更重要的是：缩小多少次之后，怎样给出“误差不超过多少”的证书？

探索与猜想¶

令 \(a_0=1,b_0=2\)，并取

若 \(m_n^2<2\)，中点还在 \(\sqrt2\) 的左边，似乎应令 \(a_{n+1}=m_n\)；若 \(m_n^2>2\)，中点在右边，似乎应令 \(b_{n+1}=m_n\)。由于 \(a_n,b_n\) 都将是有理数，\(m_n\) 也是有理数；第 2 章的无理性结论排除了 \(m_n^2=2\) 这个第三种情形。

猜想是：每步都保持有理端点、正性和目标的严格夹逼

因而也保持

并且长度每步减半。下面把这两个猜想变成证明。

概念与理论¶

平方根的区间二分法¶

从 \(a_0=1,b_0=2\) 开始。第 \(n\) 步的工作不变量是

由此可得 \(a_n^2<2<b_n^2\)。令

再按下列规则定义下一对端点：

这里没有遗漏 \(m_n^2=2\)：端点由有理数的加、除法得到，故 \(m_n\in\mathbb Q\)；而 \(m_n^2=2\) 会使 \(m_n\) 成为有理平方根，与 \(\sqrt2\notin\mathbb Q\) 矛盾。

不变量、正确选边与长度¶

命题。 对每个 \(n\ge0\)，二分端点满足

从而满足

证明。 初始时 \(a_0=1,b_0=2\in\mathbb Q\)，并且 \(0<a_0=1<\sqrt2<2=b_0\)，长度为 \(b_0-a_0\)。假设第 \(n\) 步已有

先不比较平方；由 \(a_n<b_n\) 和中点定义，直接得到

特别地 \(m_n>0\)。由有理数对加法和除法封闭，\(m_n=(a_n+b_n)/2\in\mathbb Q\)；第 2 章的 \(\sqrt2\notin\mathbb Q\) 因而给出 \(m_n\ne\sqrt2\)。因为 \(m_n,\sqrt2\) 都为正，平方在正数上严格保序，所以 \(m_n^2<2\) 等价于 \(m_n<\sqrt2\)，而 \(m_n^2>2\) 等价于 \(m_n>\sqrt2\)。故两种更新情形恰有一种发生。

若 \(m_n^2<2\)，则 \(0<m_n<\sqrt2<b_n\)，故选 \((m_n,b_n)\) 后有

若 \(m_n^2>2\)，则 \(0<a_n<\sqrt2<m_n\)，故选 \((a_n,m_n)\) 后有

这证明了有理端点、正性、正确的半区间选择与严格夹逼的归纳步骤；两边平方随即给出 \(a_{n+1}^2<2<b_{n+1}^2\)。无论选哪一半，

反复代入（或归纳）即得 \(b_n-a_n=(b_0-a_0)/2^n\)。\(\square\)

闭区间 \(I_n=[a_n,b_n]\) 因而满足 \(I_{n+1}\subset I_n\)，这就是区间套。第 3 章给出的完备有序实数系先保证了唯一的 \(\sqrt2\) 存在；上面的不变量再保证 \(\sqrt2\in I_n\) 对每个 \(n\) 成立。若 \(x,y\) 同时属于所有 \(I_n\)，则

阿基米德性质使右端可以任意小，故 \(x=y\)。因此，这个越来越短的区间套所锁定的数是唯一的，正是 \(\sqrt2\)。

中点误差证书¶

中点 \(m_n\) 与 \(\sqrt2\) 同在 \([a_n,b_n]\)，所以

这是一个有限步骤的误差证书：当 \(b_n-a_n\le2\varepsilon\) 时，输出 \(m_n\) 就有 \(|m_n-\sqrt2|\le\varepsilon\)。它不要求先说“已经收敛”，而是直接告诉我们达到给定精度所需检查的量。

边界。 这不是一般连续函数求根，更不是介值定理的应用。这里的选边正确性只来自平方根已存在、平方在正数上保序以及 \(\sqrt2\) 的无理性。一般连续函数的变号二分法与介值定理将在第 12 章建立。

例题与迁移¶

例：用区间长度控制 \(\sqrt2\) 的误差¶

前两步为

因为 \((3/2)^2=9/4>2\)。再取 \(m_1=5/4\)，有 \((5/4)^2=25/16<2\)，所以

此时输出中点 \(m_2=11/8\)；不必计算小数，也已知

一般地，初始长度为 \(1\)。只要完成 \(n\) 次更新，输出 \(m_n\) 的误差便不超过 \(2^{-(n+1)}\)。例如希望误差不超过 \(10^{-3}\)，只需选择满足 \(2^{-(n+1)}\le10^{-3}\) 的步数；这是一张在运行程序前就能写出的保证书。

算法活动：精确有理数实现¶

下面使用 Fraction，使端点、中点和比较都在有理数中精确完成；因此返回的 error_bound 正是上面证明的误差证书。代码块是静态文本，不会在书中执行。

from fractions import Fraction


def bisect_sqrt2(tolerance: Fraction) -> tuple[Fraction, Fraction]:
    if tolerance <= 0:
        raise ValueError("tolerance must be positive")

    a, b = Fraction(1), Fraction(2)
    while b - a > 2 * tolerance:
        m = (a + b) / 2
        if m * m < 2:
            a = m
        else:
            b = m

    midpoint = (a + b) / 2
    error_bound = (b - a) / 2
    assert error_bound <= tolerance
    return midpoint, error_bound


approximation, certificate = bisect_sqrt2(Fraction(1, 1000))
print(float(approximation), certificate)

分支中的 else 在数学上对应 \(m^2>2\)，因为精确有理数比较和 \(\sqrt2\) 无理性已经排除了相等。若改用二进制浮点数，舍入可能影响临界比较；那时打印出的数字不能自动替代本单元的证明。这里选择精确分数，正是为了使停止条件与误差证书可逐项核验。

即时检验与回望¶

1. 为什么 \(m_n^2=2\) 在本算法中不会发生？

1. 若本步满足 \(m_n^2<2\)，为什么不能保留 \([a_n,m_n]\)？

1. 停止时 \(b-a\le2\varepsilon\)，为什么输出中点而非左端点能立即得到误差不超过 \(\varepsilon\)？

回看牵引问题：区间法不依赖“猜得接近”，而是把目标一直放在经证明的夹逼关系中。下一单元会问：只凭区间不断缩短，怎样更一般地理解“越来越近”？

习题与答案¶

ex-u-01-04-02-01¶

从 \([1,2]\) 开始，写出二分法的前三个保留区间（把初始区间记为第 \(0\) 个）。

ex-u-01-04-02-02¶

证明：若 \(0\le x<y\)，则 \(x^2<y^2\)。据此解释本单元如何由 \(a_n^2<2<b_n^2\) 推出 \(a_n<\sqrt2<b_n\)。

ex-u-01-04-02-03¶

初始区间长度为 \(1\)。要使中点误差不超过 \(1/64\)，至少要完成多少次更新？

ex-u-01-04-02-04¶

完整解答。 设 \(0<a_0<\sqrt2<b_0\)，且 \(a_0,b_0\in\mathbb Q\)。按本单元规则构造 \(a_n,b_n\)。完整证明：每一步规则都有且只有一种可用选择；对任意 \(n\) 有 \(a_n,b_n\in\mathbb Q\) 与 \(0<a_n<\sqrt2<b_n\)；并证明输出中点 \(m_n\) 的误差至多为 \((b_0-a_0)/2^{n+1}\)。