“越来越近”怎样说得严格？¶

先备知识¶

上一单元已经构造出夹住 \(\sqrt2\) 的二分区间，并证明做完 \(n\) 次更新后，区间长度为

这里 \([a,b]\) 是初始区间，\(m_n=(a_n+b_n)/2\) 是完成 \(n\) 次更新后的中点。第 3 章的阿基米德性质和整数部分（取整）结论保证：正数再小，也总能找到足够大的自然数幂使 \(2^n\) 超过它。高等代数还会用到对数把幂不等式转写为步数不等式。

学习目标¶

完成本单元后，你应能：

1. 按“先给误差、再选步数、随后每一步都有效”的顺序读写量词；
2. 从二分区间长度推出中点近似的有限误差保证；
3. 用对数和上取整算出达到指定误差所需的更新次数；
4. 说明这种保证为何只是极限语言的预演，而不是数列极限理论本身。

牵引问题¶

“做得更多”并不等于“足够接近”。若某人说“不断二分以后一定很准”，还缺少三个可检查的信息：容许多大的误差？从第几步开始？此后每一步是否都满足？

例如，若希望用中点近似 \(\sqrt2\) 的误差不超过 \(10^{-6}\)，不应只运行程序并观察小数位；应当在运行前写出一个自然数 \(N\)，并证明完成任何 \(n\ge N\) 次更新时，输出都满足误差要求。这个“先给标准、后给门槛”的顺序正是严格语言的关键。

探索与猜想¶

对初始区间 \([a,b]\) 中的目标 \(r\)，二分后总有 \(r\in[a_n,b_n]\)。若输出中点 \(m_n\)，上一单元已给出

因此猜想：对任意容许误差 \(\varepsilon>0\)，只要 \(n\) 足够大，就有 \(|m_n-r|\le\varepsilon\)。但“足够大”不能留作感觉；我们必须由 \(a,b,\varepsilon\) 写出一个可计算的整数 \(N\)。

概念与理论¶

给定误差的有限步骤保证¶

设一个过程在第 \(n\) 步输出 \(x_n\)，目标为 \(r\)。一种可核验的误差保证具有形状

它的阅读顺序不可颠倒：先给出容许误差 \(\varepsilon\)；再依据它选一个门槛 \(N\)；最后对所有 \(n\ge N\) 检查同一误差界。\(N\) 可以依赖 \(\varepsilon\)，却不能在看到具体的 \(n\) 后临时改变。若写成“对每个 \(n\) 都能挑一个足够大的 \(\varepsilon\)”，就失去了精度控制的意义。

这里我们只把它作为二分法的有限误差语言：每个 \(N\) 都由一个明确不等式算出。它不是本单元的数列收敛定义；第二部将系统讨论数列、极限存在性、唯一性及运算法则。

二分中点的步数定理¶

定理。 设二分过程始于长度 \(b-a>0\) 的区间，并且每次保留含目标 \(r\) 的一半。把初始区间记为第 \(0\) 个区间，完成 \(n\) 次更新后输出中点 \(m_n\)。若

则 \(|m_n-r|\le\varepsilon\)。特别地，取

便对每个 \(n\ge N\) 有 \(|m_n-r|\le\varepsilon\)。

本书约定 \(\mathbb N=\{1,2,\ldots\}\)，所以即使容许误差不小于初始长度，也取 \(N=1\) 而不取 \(0\)；这当然仍是有效（只是未必最小）的门槛。

当所要求的精度使右侧已非负时，这句话常简写为

证明。 第 \(n\) 个区间的长度为 \((b-a)/2^n\)，而 \(r,m_n\) 都在其中，故

令 \(L=\log_2((b-a)/\varepsilon)\)。由 \(N\ge\lceil L\rceil-1\)，对任意 \(n\ge N\) 有 \(n+1\ge\lceil L\rceil\ge L\)，所以 \(2^{n+1}\ge2^L=(b-a)/\varepsilon\)。整理即得

将此代入中点误差界便完成证明。这里 \(\lceil L\rceil\) 的存在和“它是不小于 \(L\) 的最小整数”的性质，正是第 3 章的整数部分（取整）结论在算法步数中的一次使用。\(\square\)

不要丢失一个“半区间”¶

公式中的 \(-1\) 不是笔误，而是索引和输出位置共同决定的。这里“第 \(0\) 个区间”长度为 \(b-a\)，完成 \(n\) 次更新后长度为 \((b-a)/2^n\)；输出的是该区间的中点，再获得一半长度的误差界。

若改为输出端点，只能直接用 \(|a_n-r|\le b_n-a_n\) 或 \(|b_n-r|\le b_n-a_n\)，为了误差不超过 \(\varepsilon\) 需取

这正是常见的“二分次数”公式。它适合端点输出，或适合把“完成的二分次数”另行从 \(1\) 开始计数；本单元的中点约定则应使用上面的 \(-1\)。写证明时必须先说明索引和输出对象，不能只复制一个对数公式。

例题与迁移¶

例：先算清二分次数¶

从 \([1,2]\) 二分逼近 \(\sqrt2\)，初始长度 \(b-a=1\)。希望中点误差不超过 \(10^{-3}\)。因为

取 \(N=10-1=9\)。完成 \(9\) 次更新后，中点误差至多为

若只要求误差不超过 \(1/64\)，则 \(\lceil\log_2 64\rceil=6\)，中点只需完成 \(5\) 次更新。这里不必先算出任何近似小数；误差证书完全由区间长度给出。

从误差界到表述训练¶

对于同一个例子，下面两句话并不等价：

1. “存在一个 \(n\)，使中点误差不超过 \(10^{-3}\)。”
2. “完成任意 \(n\ge9\) 次更新后，中点误差都不超过 \(10^{-3}\)。”

第一句只说明偶然找到一个合格步骤；第二句说明门槛之后不会再失去保证。二分区间每步嵌套并且长度减半，所以第二句成立。量词中的 \(\forall n\ge N\) 正是把“以后始终有效”写进数学陈述的部分。

即时检验与回望¶

1. 在 \(\forall\varepsilon>0\;\exists N\;\forall n\ge N\) 中，\(N\) 可不可以依赖 \(\varepsilon\)？

1. 初始长度为 \(1\)，完成 \(4\) 次更新后输出中点。误差证书是多少？

1. 为什么“存在一个足够小的误差”不能替代“对任意给定误差”？

回看牵引问题：二分法不只产生越来越长的小数，而是产生“给定精度便能给出步数”的证书。下一单元将考察哪些过程即使看似在变化，也可能不能提供这样的稳定保证。

习题与答案¶

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

从长度为 \(8\) 的初始区间开始，输出中点。要保证误差不超过 \(1/8\)，至少完成多少次更新？

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

初始长度为 \(1\)。若输出左端点而非中点，要保证误差不超过 \(1/32\)，至少完成多少次更新？

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

把下列句子改写为带量词的误差保证：“对任意正误差，二分足够多次以后，中点同目标的距离不超过该误差。”

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

完整解答。 设 \(r\) 在二分产生的每个闭区间 \([a_n,b_n]\) 中，且 \(b_n-a_n=(b-a)/2^n\)。完成 \(n\) 次更新后输出 \(m_n=(a_n+b_n)/2\)。证明：对任意 \(\varepsilon>0\)，令

则每个 \(n\ge N\) 都满足 \(|m_n-r|\le\varepsilon\)。解释为何如果改为输出端点，\(N\) 的公式会变化。