5.1 实数、完备性与极限的语言

数学分析研究的是不断逼近这件事。求曲线下的面积，做法是把区域切成许多细条再求和，细条越窄结果越准；求瞬时速度，做法是先算一段时间的平均速度，再把时间段压到零；迭代算法一步步逼近最优解，问的是误差会不会趋于零。这些过程都在追问同一个问题：一串数（或一串状态）不断变化，它最终会不会稳定到某个值。

讨论这个问题之前，需要先说清它建立在什么样的数系上。有理数在数轴上处处稠密：任意两个有理数之间还有有理数。看起来这已经足够密，但如果只用有理数做极限，会撞上两个麻烦。第一，有些应该存在的极限点不在有理数里，例如用二分法逼近的 $\sqrt{2}$ 就不是有理数，逼近它的有理数列找不到有理数极限。第二，判断一个数列是否收敛时，不应该要求事先知道极限值是多少，需要一条只看数列自身的判据，这条判据在有理数系里会失效，在实数系里成立。

本节按这条线索展开：先看清有理数的缺口，再引入实数系的完备性，用它的直接推论（确界原理）证明几个常用结论；然后建立数列极限的严格语言与完备性的六条等价定理；接着把数轴上的开集、闭集、紧性这些概念整理出来，为后面的连续与微分做准备；最后把极限从数轴搬到一般的度量空间，得到压缩映射原理，它是迭代类算法收敛性分析的标准工具。

5.1.1 有理数的缺口

有理数是什么

有理数是能写成分数 $p/q$ 形式的数，其中 $p$、$q$ 是整数、$q\ne 0$。有理数对加、减、乘、除（除数不为零）封闭，可以在数轴上按大小排列，任意两个有理数之间都有无穷多个有理数：取它们的平均值就得到一个介于两者之间的有理数，重复这一操作可以得到无穷多个。

稠密性容易让人以为有理数已经把数轴填满了。事实并非如此，数轴上有大量的洞，第一个著名的例子是 $\sqrt{2}$。

一个不存在的有理数

用反证法可以证明 $\sqrt{2}$ 不是有理数。假设 $\sqrt{2}=p/q$，其中 $p$、$q$ 是互质的正整数。两边平方得 $p^2=2q^2$，所以 $p^2$ 是偶数，从而 $p$ 是偶数（奇数的平方是奇数）。设 $p=2r$，代入得 $4r^2=2q^2$，即 $q^2=2r^2$，同样的推理给出 $q$ 也是偶数。这与 $p$、$q$ 互质矛盾，所以 $\sqrt{2}$ 不是有理数。

这个结论的几何含义是：边长为 $1$ 的正方形的对角线长度不是有理数。用有理数无法精确表示这条对角线，只能逼近它。

逼近序列的极限不在有理数中

用二分法构造一串有理数来逼近 $\sqrt{2}$：从区间 $[1,2]$ 开始，取中点 $3/2=1.5$，因 ${1.5}^2>2$，把区间换成 $[1,1.5]$；再取中点 $1.25$，因 ${1.25}^2<2$，区间换成 $[1.25,1.5]$。每一步区间长度减半，得到两个有理数列（左端点与右端点），它们的差趋于零。

如果只有有理数，这两个数列是没有极限的收敛数列：数列的项越来越挤在一起，却找不到一个有理数作为它们的极限。第 5.1.4 节的 Cauchy 收敛准则把越来越挤在一起这件事写成了判据，在有理数里这条判据不成立（存在满足判据却没有有理极限的数列），在实数里它成立。这一差别就是完备性的内容。

5.1.2 实数系与确界原理

实数的三组性质

实数系 $\text{R}$ 可以公理化地描述为满足以下三组性质的集合，其中任何一组性质都不足以刻画实数。

域性质：加法与乘法的交换律、结合律、分配律成立，有加法单位元 $0$ 与乘法单位元 $1$，每个元素有相反数、每个非零元素有倒数。

序性质：任意两个实数可以比较大小，这个序与运算相容（$a\le b$ 时 $a+c\le b+c$；$a\le b$ 且 $c\ge 0$ 时 $ac\le bc$）。

完备性：$\text{R}$ 的任一非空有上界的子集必有最小上界。

第三组性质是有理数缺失的那一条。从直觉上说，完备性把数轴上所有的洞补上了。收紧了这一点之后，才能谈论一个非空有界集合一定有最大值或上确界这类结论，进而得到连续函数的介值定理、最值定理这些基础结果。

实数的构造

公理化描述可以换成显式构造。两种标准做法是：把实数定义为有理数的 Dedekind 分割（把有理数分成左右两半，左半没有最大元），或者定义为一族有理数 Cauchy 列的等价类（两列之差趋于零时视为同一实数）。两种构造都满足上面三组性质，得到的实数系在同构意义下唯一。初学阶段记住一句话就够：实数是有理数的所有可能极限点的补全。

上界与上确界

设 $A$ 是非空实数集合。若存在实数 $M$ 使得对一切 $x\in A$ 有 $x\le M$，称 $M$ 是 $A$ 的上界，$A$ 是有上界的集合。上界不唯一：$M$ 是上界时，任何大于 $M$ 的数也是上界。所有上界中最小的一个称为上确界（supremum），记作 $supA$。下界与下确界（infimum，记作 $infA$）的定义对称。

上确界的定义可以写成两条性质：$supA$ 是 $A$ 的上界（对一切 $x\in A$，$x\le supA$）；任何比 $supA$ 小的数都不是上界（对任意 $\epsilon >0$，存在 $x\in A$ 使 $x>supA-\epsilon$）。第二条性质是使用上确界时的关键技术点：它给出任意接近上确界的元素存在，几乎所有由上确界出发的证明都要用到它。

几个例子：$A=\{1/n:n\ge 1\}$ 的 $supA=1$、$infA=0$（$0$ 不在集合中）；$A=(0,1)$ 的 $supA=1$、$infA=0$（两个都不在集合中）；$A=\{x\in \mathbb{Q}:x^2<2\}$ 的 $supA=\sqrt{2}$（在有理数中没有上确界，在实数中有）。

确界原理：$\text{R}$ 的任一非空有上界的子集有上确界；任一非空有下界的子集有下确界。这条原理与完备性公理等价，是实数系最常用的表达形式。

确界原理的三个常用推论

Archimedes 性质：对任意实数 $x$，存在正整数 $n$ 使 $n>x$。证明用反证法：若正整数全体有上界，由确界原理设上确界为 $s$，则 $s-1$ 不是上界，存在正整数 $n>s-1$，于是 $n+1>s$，与 $s$ 是上界矛盾。这条性质的直观说法是自然数没有上界，它的常用形式是：给定 $\epsilon >0$，总能取到足够大的 $n$ 使 $1/n<\epsilon$。

有理数的稠密性：任意两个实数 $a<b$ 之间存在有理数。做法是先取正整数 $n$ 使 $1/n<b-a$（Archimedes 性质），再取整数 $m$ 使 $m/n$ 落在 $[a,b]$ 内（用 Archimedes 性质把区间放大后取整），得到 $a<m/n<b$。这条性质说明有理数虽然有洞，但在任何区间里都能找到，因此可以用有理数近似任何实数。

$n$ 次方根的存在性：对任意 $a>0$ 与正整数 $n$，存在唯一的正实数 $x$ 使 $x^n=a$。以 $\sqrt{2}$ 为例，集合 $A=\{x\in \text{R}:x\ge 0,x^2<2\}$ 非空（$1\in A$）且有上界（$2$ 是上界），由确界原理设 $s=supA$；再证明 $s^2=2$ 不能小于也不能大于 $2$（用上确界的第二条性质排除两种情况），于是 $\sqrt{2}$ 作为实数存在。实数系补上了有理数的洞，这一存在性证明就是补洞的具体操作。

5.1.3 数列极限的语言

ε-N 定义

数列 $\{a_n\}$ 是定义在正整数上的函数，$a_n$ 称为第 $n$ 项。称数列收敛于实数 $a$，若对任意 $\epsilon >0$，存在正整数 $N$，使得当 $n>N$ 时

$$|a_n-a|<\epsilon$$

记作 $\underset{n\to \mathrm{\infty }}{lim}{a}_n=a$ 或 $a_n\to a$。不收敛的数列称为发散。

定义里的两句话分别控制两件事。$\epsilon$ 是任意给定的误差标准，它可以非常小但不能等于零；$N$ 是回答从第几项开始误差小于 $\epsilon$的指标，它依赖于 $\epsilon$（$\epsilon$ 越小，$N$ 通常越大）。这种任意给定误差，存在足够靠后的位置的结构在数学分析中反复出现，后续的 ε-δ 定义、一致收敛、连续模都是它的变体。

用定义证明两个例子

例 1：证明 $\underset{n\to \mathrm{\infty }}{lim}\frac{1}{n}=0$。

任给 $\epsilon >0$。要 $|1/n-0|=1/n<\epsilon$，等价于 $n>1/\epsilon$。由 Archimedes 性质，存在正整数 $N>1/\epsilon$。取这个 $N$，则当 $n>N$ 时 $1/n<1/N<\epsilon$。按定义，$lim1/n=0$。

例 2：证明 $\underset{n\to \mathrm{\infty }}{lim}\frac{3n+1}{n+2}=3$。

先估计差值：$|\frac{3n+1}{n+2}-3|=\left|\frac{3n+1-3n-6}{n+2}\right|=\frac{5}{n+2}<\frac{5}{n}$。任给 $\epsilon >0$，取正整数 $N>5/\epsilon$，则当 $n>N$ 时差小于 $\epsilon$。证毕。

这两例展示了标准套路：先把待控制量与极限值的差整理成一个关于 $n$ 的简单表达式，再解不等式得到 $N$ 的取法。顺利的情形下 $\epsilon$ 只影响 $N$ 的大小，不影响推理结构。

基本性质

四条性质最常用，都可以由定义直接推出。

唯一性：收敛数列的极限唯一。若 $a$ 与 $b$ 都是极限，取 $\epsilon =|a-b|/3$，则充分靠后的项必须同时满足与 $a$、$b$ 的距离小于 $\epsilon$，由三角不等式得 $|a-b|<2|a-b|/3$，矛盾。

有界性：收敛数列有界。取 $\epsilon =1$，存在 $N$ 使 $n>N$ 时 $|a_n|<|a|+1$；前 $N$ 项是有限个数，取它们与 $|a|+1$ 的最大值作为界。

四则运算：若 $a_n\to a$、$b_n\to b$，则 $a_n\pm b_n\to a\pm b$、$a_n{b}_n\to ab$，且当 $b\ne 0$ 时 $a_n/b_n\to a/b$。乘法证明的技巧是插进中间项：$a_n{b}_n-ab=(a_n-a)b_n+a(b_n-b)$，其中 $|b_n|$ 有界。

夹逼定理：若 $a_n\le c_n\le b_n$ 且 $a_n\to a$、$b_n\to a$，则 $c_n\to a$。这条定理是把复杂的数列夹到两个简单数列之间的工具，直接计算困难的数列（含阶乘、幂、递推）常靠它处理。

什么时候可以先看趋势再补证明

数学分析的推理顺序是先有定义、后有结论，而实际解题顺序常常相反：先用小规模数值实验（代入 $n=10,100,1000$）猜测极限值与收敛趋势，再用定义或定理补出证明。两条路线不冲突，数值实验用于发现结论，严格证明用于确认结论。后文的代码实验基本都是这样使用：数值用于观察与验证，结论仍然来自定义与定理。

5.1.4 完备性的六条等价定理

实数系的完备性有六种常用表达，它们在实数系内互相等价，各自在不同场景下方便使用。

确界原理：非空有上界的实数集有上确界。用于证明根的存在性、连续函数的最值定理与介值定理。

单调有界定理：单调递增且有上界的数列收敛（单调递减且有下界的数列同理）。用于处理递推数列，例如 $a_{n+1}=\sqrt{2+a_n}$ 这类由不动点迭代定义的数列：先证明单调性与有界性，再由定理得到收敛，最后对递推式两端取极限解出极限值。

区间套定理：若闭区间列 $[a_n,b_n]$ 满足 $a_n\le a_{n+1}\le b_{n+1}\le b_n$（区间互相嵌套）且 $b_n-a_n\to 0$，则存在唯一的实数属于所有区间。用于二分法与逐次逼近的收敛性论证，5.1.7 节的实验一就是它的数值形态。

Bolzano-Weierstrass 定理：有界数列必有收敛子列。用于从有界序列中挑出收敛的部分，紧性与序列紧性的讨论都围绕它展开。

Cauchy 收敛准则：数列收敛的充要条件是它满足 Cauchy 条件，即对任意 $\epsilon >0$ 存在 $N$，当 $m,n>N$ 时 $|a_m-a_n|<\epsilon$。这条判据的价值在于不需要事先知道极限值：只要检查数列自身越来越挤，就能判定收敛。

有限覆盖定理：闭区间 $[a,b]$ 的任何开覆盖都有有限子覆盖。用于把局部性质提升为整体性质，例如证明闭区间上的连续函数一致连续。

六条定理的常用分工可以记成一张表：要证明某个值存在（根、最值、极限）用确界原理或区间套；处理递推数列用单调有界；从有界序列中提取收敛子列用 Bolzano-Weierstrass；判断收敛而不知道极限用 Cauchy 准则；从局部过渡到整体用有限覆盖。它们两两等价的证明常见做法是串成一条链（确界原理导出单调有界，单调有界导出区间套，区间套导出 Bolzano-Weierstrass，Bolzano-Weierstrass 导出 Cauchy 准则，Cauchy 准则导出确界原理），再补上有限覆盖定理与其他定理的等价。

Cauchy 条件与相邻项差趋于零的差别

Cauchy 条件要求任意两项充分靠后时都接近，写成下标是 $m,n>N$；只要求相邻两项接近的写法是 $|a_{n+1}-a_n|\to 0$。后者比前者弱得多，不足以判定收敛。5.1.7 节的实验三用调和级数给出数值反例：它的相邻项差趋于零，部分和却无界，因而不是 Cauchy 列。算法实现中常见的错误也是这里的混淆：把相邻两次迭代的差小于阈值当作收敛判据，对某些问题会提前停止。

5.1.5 实数直线的拓扑

极限与连续的概念都可以用开集重新表述，这套语言在多元分析与测度论中成为主要表述方式。

邻域与开集：点 $a$ 的 $\delta$ 邻域是 $(a-\delta ,a+\delta )$。集合 $U\subset \text{R}$ 是开集，若它的每个点都有一个完全包含在 $U$ 内的邻域。开区间的并是开集，单点是闭集而不是开集（它的任何邻域都包含点之外的部分）。

闭集：集合 $F$ 是闭集，若它的补集是开集。闭集对取极限封闭：$F$ 中的收敛数列的极限仍属于 $F$。有限个闭集之并、任意多个闭集之交仍是闭集，开集的性质与它对称（任意多个开集之并、有限个开集之交仍是开集）。

内点、聚点与边界：点是集合 $A$ 的内点，若某个邻域完全落在 $A$ 内；点是 $A$ 的聚点，若它的每个邻域都包含 $A$ 中异于该点的点；点是 $A$ 的边界点，若它的每个邻域既有 $A$ 中的点又有 $A$ 外的点。集合的内部是所有内点的集合，闭包是所有聚点与自身点的并，闭包也可以描述为包含 $A$ 的最小闭集。

紧性：集合 $K\subset \text{R}$ 是紧集，若它的任何开覆盖都有有限子覆盖。Heine-Borel 定理给出紧集在实数轴上的完整刻画：紧集恰好是有界闭集。紧性在分析中的作用是把局部成立升级为整体一致成立，最典型的应用是：紧集上的连续函数一致连续，紧集上的连续函数取到最大值与最小值。

连通性：实数轴上的连通集恰好是区间。连通性使介值定理成立：连续函数把区间映成区间，因而在函数值取到两个数之后，中间的数也会被取到。

5.1.6 度量空间与压缩映射原理

度量空间

许多收敛性问题与数轴无关，只依赖距离的定义。度量空间是一个集合 $X$ 加上距离函数 $d:X\times X\to \text{R}$，满足三条性质：$d(x,y)\ge 0$，等号成立当且仅当 $x=y$；对称性 $d(x,y)=d(y,x)$；三角不等式 $d(x,z)\le d(x,y)+d(y,z)$。

三个例子：实数轴取 $d(x,y)=|x-y|$；$n$ 维欧氏空间取欧氏距离；函数集合 $C[a,b]$（闭区间上的连续函数全体）取上确界度量 $d(f,g)=\underset{x\in [a,b]}{max}|f(x)-g(x)|$。

度量空间中，数列收敛、Cauchy 列、完备性的定义与数轴上完全一样，只需把绝对值换成距离：$\{x_n\}$ 收敛于 $x$ 指 $d(x_n,x)\to 0$；$\{x_n\}$ 是 Cauchy 列指 $d(x_m,x_n)\to 0$（$m,n\to \mathrm{\infty }$）；空间完备指其中的每个 Cauchy 列都收敛于空间内的点。

压缩映射原理

定义：映射 $T:X\to X$ 是压缩映射，若存在常数 $q\in [0,1)$ 使

$$d(T(x),T(y))\le qd(x,y),\mathrm{\forall }x,y\in X$$

常数 $q$ 称为压缩常数。

定理（压缩映射原理）：完备度量空间 $(X,d)$ 上的压缩映射 $T$ 有唯一不动点 $x^{\ast }$（即 $T(x^{\ast })=x^{\ast }$），且对任意初始点 $x_0$，迭代 $x_{n+1}=T(x_n)$ 收敛于 $x^{\ast }$，并有误差估计

$$d(x_n,x^{\ast })\le \frac{q^n}{1-q}d(x_1,x_0)$$

证明。先证迭代序列是 Cauchy 列。由压缩性反复使用得 $d(x_{n+1},x_n)=d(T(x_n),T(x_{n-1}))\le qd(x_n,x_{n-1})\le \cdots \le q^{n}d(x_1,x_0)$。对 $m>n$ 用三角不等式把这些差值累加：

$$d(x_m,x_n)\le \sum _{k=n}^{m-1}{q}^{k}d(x_1,x_0)\le \frac{q^n}{1-q}d(x_1,x_0)$$

右端随 $n$ 增大趋于零，所以迭代序列是 Cauchy 列。空间完备，故存在 $x^{\ast }$ 使 $x_n\to x^{\ast }$。

再证 $x^{\ast }$ 是不动点。压缩映射是连续映射（$d(T(x),T(y))\le qd(x,y)$ 直接给出连续性），于是 $T(x_n)\to T(x^{\ast })$；另一方面 $T(x_n)=x_{n+1}\to x^{\ast }$。极限唯一，得 $T(x^{\ast })=x^{\ast }$。

最后证唯一性。若 $x^{\ast }$ 与 $y^{\ast }$ 都是不动点，则 $d(x^{\ast },y^{\ast })=d(T(x^{\ast }),T(y^{\ast }))\le qd(x^{\ast },y^{\ast })$，移项得 $(1-q)d(x^{\ast },y^{\ast })\le 0$，故 $x^{\ast }=y^{\ast }$。误差估计在上面 Cauchy 估计中令 $m\to \mathrm{\infty }$ 即得（距离函数连续）。

与迭代算法的联系

压缩映射原理给出了迭代算法收敛性的通用模板，其中的三个部件在具体问题中分别对应不同的数学事实：压缩性（由函数的导数界或 Lipschitz 常数提供）、完备性（由问题所在的函数空间提供）、不动点（由问题的方程提供）。公式中的误差估计还说明收敛速度是几何速率：每迭代一次，误差至少缩小 $q$ 倍，要把误差降到 $\epsilon$ 需要约 $\log (\epsilon )/\log q$ 步。

与最优化一章的接口

第三章讨论的梯度下降需要假设目标函数的梯度 Lipschitz 连续，这个假设保证迭代映射 $T(x)=x-\eta \mathrm{\nabla }f(x)$ 在合适步长下是压缩映射，收敛速率因子为正则化参数与步长的组合。Newton 法之所以更快，是因为它在不动点处的导数为零，压缩常数 $q$ 在极限意义下趋于零，误差按平方规律收缩。本节给出的框架可以用来重新推导那些结论，区别只在距离空间的选择与压缩常数估计的精细程度。

5.1.7 数值实验

实验一：二分法与区间套

用二分法求 $\sqrt{2}$，同时观察区间长度按什么规律收缩。每一步把当前区间的中点代入 $x^2$ 与 $2$ 比较，决定保留哪一半。

import math

lo, hi = 0.0, 2.0
for k in range(1, 61):
    mid = (lo + hi) / 2
    if mid * mid < 2:
        lo = mid
    else:
        hi = mid
    if k in (1, 5, 10, 20, 30, 40, 45, 50, 53, 60):
        print(f"k = {k:>2}: 区间长度 = {hi - lo:.3e}, 中点 = {mid:.17f}, "
              f"相对误差 = {abs(mid - math.sqrt(2)) / math.sqrt(2):.3e}")

输出：

k =  1: 区间长度 = 1.000e+00, 中点 = 1.00000000000000000, 相对误差 = 2.929e-01
k =  5: 区间长度 = 6.250e-02, 中点 = 1.43750000000000000, 相对误差 = 1.647e-02
k = 10: 区间长度 = 1.953e-03, 中点 = 1.41601562500000000, 相对误差 = 1.274e-03
k = 20: 区间长度 = 1.907e-06, 中点 = 1.41421318054199219, 相对误差 = 2.700e-07
k = 30: 区间长度 = 1.863e-09, 中点 = 1.41421356238424778, 相对误差 = 7.886e-12
k = 40: 区间长度 = 1.819e-12, 中点 = 1.41421356237151485, 相对误差 = 1.117e-12
k = 45: 区间长度 = 5.684e-14, 中点 = 1.41421356237304963, 相对误差 = 3.219e-14
k = 50: 区间长度 = 1.776e-15, 中点 = 1.41421356237309404, 相对误差 = 7.850e-16
k = 53: 区间长度 = 2.220e-16, 中点 = 1.41421356237309515, 相对误差 = 0.000e+00
k = 60: 区间长度 = 2.220e-16, 中点 = 1.41421356237309492, 相对误差 = 1.570e-16

两个现象。区间长度按 $2^{-k}$ 收缩，与区间套定理的假设一致：第 $k$ 步长度为 $2^{1-k}$，第 $10$ 步约 $2\times {10}^{-3}$，第 $30$ 步约 $2\times {10}^{-9}$。这一收缩与具体函数无关，只取决于每次折半的操作，因此二分法的迭代次数可以由精度要求直接算出：要把区间长度降到 $\epsilon$ 以下需要 $k\approx {\log }_2(2/\epsilon )$ 步。

第二个现象是浮点数的限制。第 $53$ 步之后区间长度停在 $2.22\times {10}^{-16}$ 不再减小，继续迭代到第 $60$ 步中点的相对误差甚至略有回升。原因在 5.1.7 节实验三说明：双精度浮点数在 $1$ 附近的最小间隔是 $2.22\times {10}^{-16}$，再往下细分时 $lo$、$hi$、$mid$ 已经无法表示更接近的数，迭代在数值上停滞。数学上的区间套定理与数值上的可实现精度之间隔着这一层限制，做数值计算时应当知道它的位置。

实验二：三种迭代的误差序列

同一个求不动点的目标，三种迭代的误差下降方式完全不同：线性压缩、Newton 迭代、以及一个不满足压缩条件的迭代。

import math

# (a) 线性压缩：h(x) = 0.5x + 1，不动点 2，压缩常数 0.5
x = 1.0
err_a = []
for k in range(12):
    err_a.append(abs(x - 2.0))
    x = 0.5 * x + 1.0
print("线性压缩 h(x) = 0.5x + 1（不动点 2）:")
print("  误差序列:", "  ".join(f"{e:.3e}" for e in err_a))
print("  相邻误差比值:", "  ".join(f"{err_a[i+1]/err_a[i]:.4f}" for i in range(6)))

# (b) Newton 迭代求解 sqrt(2)
x = 1.0
err_b = []
for k in range(8):
    err_b.append(abs(x - math.sqrt(2)))
    x = (x + 2.0 / x) / 2.0
print("Newton 迭代 f(x) = (x + 2/x)/2（不动点 sqrt(2)）:")
print("  误差序列:", "  ".join(f"{e:.3e}" for e in err_b))
print("  误差平方比值:", "  ".join(f"{err_b[i+1]/err_b[i]**2:.4f}" for i in range(4)))

# (c) 非压缩迭代：g(x) = x + 0.5(x^2 - 2)，在 sqrt(2) 处导数大于 1
x = 1.5
seq = []
for k in range(10):
    seq.append(x)
    x = x + 0.5 * (x * x - 2.0)
print("非压缩迭代 g(x) = x + 0.5(x^2 - 2):")
print("  迭代值:", "  ".join(f"{v:.4f}" for v in seq))

输出：

线性压缩 h(x) = 0.5x + 1（不动点 2）:
  误差序列: 1.000e+00  5.000e-01  2.500e-01  1.250e-01  6.250e-02  3.125e-02  1.562e-02  7.812e-03  3.906e-03  1.953e-03  9.766e-04  4.883e-04
  相邻误差比值: 0.5000  0.5000  0.5000  0.5000  0.5000  0.5000
Newton 迭代 f(x) = (x + 2/x)/2（不动点 sqrt(2)）:
  误差序列: 4.142e-01  8.579e-02  2.453e-03  2.124e-06  1.595e-12  2.220e-16  2.220e-16  2.220e-16
  误差平方比值: 0.5000  0.3333  0.3529  0.3535
非压缩迭代 g(x) = x + 0.5(x^2 - 2):
  迭代值: 1.5000  1.6250  1.9453  2.8374  5.8629  22.0500  264.1515  35151.1559  617837031.9770  190861299658937728.0000

三种情形的差别可以由压缩映射原理统一解释，只是压缩常数不同。

线性压缩的误差每步严格减半，比值恒为 $0.5$，与定理中的误差估计 $d(x_n,x^{\ast })\le q^{n}d(x_0,x^{\ast })/(1-q)$ 给出的几何速率一致。由 ${0.5}^n\approx {10}^{-3}$ 得 $n\approx 10$，即误差降到千分之一需要约十步，与输出相符。

Newton 迭代的误差没有固定比例，它按平方规律缩小：误差平方比值稳定在 $0.3535$ 附近，理论值为 $1/(2\sqrt{2})\approx 0.3536$（由 $f^{\prime }(\sqrt{2})=0$ 与二阶 Taylor 展开得到）。前三步误差从 $0.41$ 降到 ${10}^{-6}$，第五步已经触到 $2.22\times {10}^{-16}$ 的机器精度。这种速度在压缩映射的语言里表现为：迭代映射在不动点处的导数等于零，压缩常数在局部趋于零，定理给出的界失去了意义，实际的收敛比几何速率更快。第 5.4 节会给出收敛阶的正式定义。

非压缩迭代在几步之内发散，$g^{\prime }(\sqrt{2})=1+\sqrt{2}>1$ 违背了压缩条件，定理的假设不成立，序列落到 ${10}^{17}$ 量级。这个反例说明压缩常数必须严格小于 $1$：导数等于 $1$ 或更大时不保证收敛。

实验三：Cauchy 判据与浮点数

Cauchy 判据要求任意两项充分靠后时都接近，比相邻两项接近强得多。调和级数与平方倒数和给出两组对照数据。

def harm(n):
    s = 0.0
    for k in range(1, n + 1):
        s += 1.0 / k
    return s

def inv_sq(n):
    s = 0.0
    for k in range(1, n + 1):
        s += 1.0 / (k * k)
    return s

print("调和级数部分和（发散）:")
for n in [100, 1000, 10000, 100000, 1000000]:
    print(f"  n = {n:>8}: s_n = {harm(n):.6f}, s_n - s_{{n/2}} = {harm(n) - harm(n // 2):.6f}")
print("平方倒数和部分和（收敛到 pi^2/6 = 1.6449340668）:")
for n in [100, 1000, 10000, 100000, 1000000]:
    print(f"  n = {n:>8}: s_n = {inv_sq(n):.10f}")
print("浮点数与实数:")
print("  0.1 + 0.2 - 0.3 =", 0.1 + 0.2 - 0.3)
print("  0.1 + 0.2 == 0.3:", 0.1 + 0.2 == 0.3)
print("  1 + 1e-16 == 1:", 1 + 1e-16 == 1)

输出：

调和级数部分和（发散）:
  n =      100: s_n = 5.187378, s_n - s_{n/2} = 0.688172
  n =     1000: s_n = 7.485471, s_n - s_{n/2} = 0.692647
  n =    10000: s_n = 9.787606, s_n - s_{n/2} = 0.693097
  n =   100000: s_n = 12.090146, s_n - s_{n/2} = 0.693142
  n =  1000000: s_n = 14.392727, s_n - s_{n/2} = 0.693147
平方倒数和部分和（收敛到 pi^2/6 = 1.6449340668）:
  n =      100: s_n = 1.6349839002
  n =     1000: s_n = 1.6439345667
  n =    10000: s_n = 1.6448340718
  n =   100000: s_n = 1.6449240669
  n =  1000000: s_n = 1.6449330668
浮点数与实数:
  0.1 + 0.2 - 0.3 = 5.551115123125783e-17
  0.1 + 0.2 == 0.3: False
  1 + 1e-16 == 1: True

调和级数的数据是相邻项差趋于零但序列不收敛的量化版本。相邻两项之差是 $1/n$，确实趋于零；但取下标相距 $n/2$ 的两项，差值稳定在 $0.693$ 附近（理论值 $\ln 2\approx 0.6931$），不趋于零，因此它不满足 Cauchy 条件。部分和本身也在增长，从 $100$ 项的 $5.19$ 增到 ${10}^6$ 项的 $14.39$，没有上界。

平方倒数和的行为相反：从 $100$ 项到 ${10}^6$ 项，部分和从 $1.63498$ 增到 $1.64493$，与极限值 ${\pi }^2/6=1.6449341$ 的差从 $0.0099$ 降到 $1\times {10}^{-6}$。任意两项靠后之差也随之趋于零，满足 Cauchy 条件。

最后三行说明浮点数与实数的区别。$0.1+0.2$ 与 $0.3$ 之差是 $5.55\times {10}^{-17}$，因为在二进制下 $0.1$ 与 $0.2$ 都无法用有限位表示；$1+{10}^{-16}$ 在双精度下等于 $1$，因为 ${10}^{-16}$ 小于 $1$ 附近的最小间隔 $2.22\times {10}^{-16}$。这些事实的含义是：数学分析里的实数系满足完备性，而计算机里表示的是它的有限子集，任何以误差小于某个阈值为条件的数值判据都必须考虑这一层限制。实验一中二分法在 $53$ 步后停滞，原因就在这里。

5.1.8 本节小结

从欠缺到完备

本节从有理数的缺口出发建立了实数系与极限的语言。有理数稠密但有洞，$\sqrt{2}$ 这类数无法用分数表示，逼近它的有理数列没有有理极限，因此需要完备性：任一非空有上界的集合有上确界。由上确界的两条性质（本身是上界、任何更小的数都不是上界）可以直接推出 Archimedes 性质、有理数稠密性与 $n$ 次方根的存在性。数列极限用 ε-N 语言定义，四条基本性质（唯一性、有界性、四则运算、夹逼）是后续所有计算的工具。完备性有六条等价定理，各自对应一类论证：存在性用确界原理或区间套，递推数列用单调有界，提取子列用 Bolzano-Weierstrass，判断收敛而不知道极限用 Cauchy 准则，从局部到整体用有限覆盖。数轴上的开集、闭集、紧集、连通集提供了另一种语言，其中紧等价于有界闭，是局部性质升级为整体性质的开关。度量空间把距离抽象出来，压缩映射原理给出迭代收敛的通用模板：压缩常数 $q$ 决定几何速率，完备性保证极限存在，误差估计 $q^{n}d(x_1,x_0)/(1-q)$ 可以直接用来估算需要的迭代步数。三个数值实验分别展示了区间套的收缩速率与浮点限制（$53$ 步后停滞在 $2.22\times {10}^{-16}$）、三种迭代的误差形态（线性压缩比值恒为 $0.5$，Newton 的误差平方比值稳定在 $0.3535$、六步内到机器精度，非压缩迭代发散到 ${10}^{17}$）、以及 Cauchy 条件的必要性（调和级数相邻差趋于零而相隔 $n/2$ 项之差稳定在 $\ln 2$）。

极限的语言建立之后，下一节用它处理无穷求和：级数的收敛判别、条件收敛的重排现象、以及数值求和中的误差控制。那里出现的渐近记号与收敛速度概念，是后面每一节都要使用的工具。

练习题

第 1 题 概念推导

用 ε-N 定义证明下列极限，并说明 $N$ 的取法如何依赖 $\epsilon$：(a) $\underset{n\to \mathrm{\infty }}{lim}{\displaystyle \frac{2n+1}{n+3}}=2$；(b) $\underset{n\to \mathrm{\infty }}{lim}{\displaystyle \frac{n^2}{2^n}}=0$（提示：对 $n\ge 6$ 用 $2^n>n^3$ 或直接估计）。(c) 说明为什么相邻项差趋于零不足以保证收敛，并给出一个数列作为反例。

参考答案

(a) 先整理差值：

$$|\frac{2n+1}{n+3}-2|=\left|\frac{2n+1-2n-6}{n+3}\right|=\frac{5}{n+3}<\frac{5}{n}$$

任给 $\epsilon >0$，由 Archimedes 性质取正整数 $N>5/\epsilon$（例如取 $N=\lfloor 5/\epsilon \rfloor +1$）。当 $n>N$ 时 $\frac{5}{n+3}<\frac{5}{N}<\epsilon$，故极限为 $2$。$N$ 的取法与 $1/\epsilon$ 成正比：误差标准缩小十倍，需要多算约十倍的项。

(b) 对 $n\ge 6$，用二项式展开 $2^n=(1+1{)}^n\ge (\genfrac{}{}{0ex}{}{n}{3})=\frac{n(n-1)(n-2)}{6}>\frac{n^3}{7}$（$n\ge 3$ 时 $(n-1)(n-2)\ge 7$ 成立），于是

$$\frac{n^2}{2^n}<\frac{7n^2}{n^3}=\frac{7}{n}$$

任给 $\epsilon >0$，取 $N=max(6,\lfloor 7/\epsilon \rfloor +1)$。当 $n>N$ 时 $\frac{n^2}{2^n}<\epsilon$。这个例子的要点是分子是多项式、分母是指数时，指数最终占绝对优势，放大成 $7/n$ 之后归入第一种情况。

(c) 相邻项差趋于零只控制下标相差 $1$ 的两项，Cauchy 条件控制任意两项。反例取调和级数的部分和 $s_n=1+\frac{1}{2}+\cdots +\frac{1}{n}$：相邻差 $s_{n+1}-s_n=\frac{1}{n+1}\to 0$，但取 $m=2n$ 时

$$s_{2n}-s_n=\frac{1}{n+1}+\cdots +\frac{1}{2n}\ge n\cdot \frac{1}{2n}=\frac{1}{2}$$

差值不小于 $0.5$，不趋于零，因而不是 Cauchy 列，数列发散（本节实验三中该差值稳定在 $\ln 2\approx 0.693$）。

第 2 题 计算推理

(a) 求集合 $A=\{1-1/n:n\ge 1\}$ 的上确界与下确界，并说明它们是否属于 $A$。(b) 用确界原理证明 $A=\{x\in \text{R}:x^2<3\}$ 的上确界满足 $s^2=3$。(c) 说明压缩映射 $h(x)=0.5x+1$ 的压缩常数，并用误差估计计算从 $x_0=1$ 出发把误差降到 ${10}^{-6}$ 以内需要的迭代步数。

参考答案

(a) $A$ 的元素为 $0,\frac{1}{2},\frac{2}{3},\frac{3}{4},\dots$，随 $n$ 增大单调递增趋于 $1$。因此 $infA=0$（属于 $A$，$n=1$ 时取到），$supA=1$（不属于 $A$，因为 $1-1/n<1$ 对一切 $n$ 成立）。这个例子说明上确界可以不在集合中，与最大值的区别正在这里。

(b) $A$ 非空（$0\in A$）且有上界（$2$ 是上界，因为 $x\ge 2$ 时 $x^2\ge 4>3$），由确界原理设 $s=supA$。先排除 $s^2<3$：取 $\delta =min(s,\frac{3-s^2}{2s+1})>0$，则 $(s+\delta {)}^2=s^2+2s\delta +{\delta }^2\le s^2+(2s+1)\delta \le 3$，与 $s$ 是上界矛盾。再排除 $s^2>3$：由 5.1.2 节证过的 $n$ 次方根存在性可取 $r$ 使 $r^2=3$，则 $r<s$；由稠密性取有理数（或实数）$t$ 使 $r<t<s$，则 $t^2>3$，于是任何大于 $t$ 的数都不在 $A$ 中，$t$ 是比 $s$ 小的上界，与 $s$ 是最小上界矛盾。两处矛盾合起来得 $s^2=3$，即 $s=\sqrt{3}$。

(c) $h^{\prime }(x)=0.5$，由中值定理 $|h(x)-h(y)|=0.5|x-y|$，压缩常数 $q=0.5$，不动点为 $x^{\ast }=2$。误差估计给出

$$|x_n-2|\le \frac{q^n}{1-q}|x_1-x_0|=\frac{{0.5}^n}{0.5}\cdot 0.5={0.5}^n$$

要求 ${0.5}^n<{10}^{-6}$，即 $n{\log }_{10}0.5<-6$，$n>6/{\log }_{10}2\approx 19.9$，取 $n=20$。直接核对：$|x_{20}-2|={0.5}^{20}\approx 9.5\times {10}^{-7}$，与估计相符（本例的估计是精确的，因为误差恰好按 $q$ 等比缩小）。

第 3 题 代码验证

用本节代码做三组实验并解释：(a) 把二分法的循环上限从 $60$ 提高到 $80$，观察区间长度与中点的变化；(b) 把 Newton 迭代的初始值从 $1.0$ 改成 $0.01$ 与 $100.0$，观察前几步误差与总步数；(c) 把实验三中的调和级数换成 $\sum 1/n^{1.5}$，观察 $s_n-s_{n/2}$ 的行为，并判断它是否满足 Cauchy 条件。

参考答案

(a) 循环上限提高后，区间长度仍然停在 $2.22\times {10}^{-16}$，中点在第 $53$ 步附近的几个相邻浮点数之间来回跳动，不继续改进。原因是双精度浮点数在 $[1,2)$ 内的最小间隔是 $2^{-52}=2.22\times {10}^{-16}$：当 $hi-lo$ 已经等于一个间隔时，中点或者等于 $lo$ 或者等于 $hi$，区间不再收缩。结论：二分法的数学迭代可以任意深入，浮点实现的有效迭代次数有上限，约为有效位数除以每步缩小位数，双精度下约 $52$ 步。

(b) 初始值 $0.01$ 时第 $0$ 步误差为 $|0.01-1.4142|\approx 1.40$，第一次迭代后变为 $|(0.01+200)/2-\sqrt{2}|\approx 68.7$，误差反而放大（Newton 迭代在远处可能跳出定义域附近的区域）；随后误差迅速回落，约 $7$ 步后到机器精度。初始值 $100$ 时同理，第一步变成约 $50$，再用 $5$ 到 $6$ 步收敛。两组初始值的总步数差别只有两三步，说明 Newton 迭代对初始值的要求是足够接近即可，远处的初值也只损失常数步；但如果初值恰好使迭代落到 $x=0$（例如 $x_0=\sqrt{2}/2$ 的情形以外还有构造出的坏点），会出现除零错误，实现时需要加保护。

(c) $\sum 1/n^{1.5}$ 的部分和满足

$$s_{2n}-s_n=\sum _{k=n+1}^{2n}\frac{1}{k^{1.5}}\le n\cdot \frac{1}{n^{1.5}}=\frac{1}{\sqrt{n}}\to 0$$

差值随 $n$ 趋于零，且用同样的估计可以得到任意 $m>n$ 的差值界，因此满足 Cauchy 条件，级数收敛（收敛值约为 $2.612$，即 $\zeta (1.5)$）。数值上：$n=100$ 时 $s_n\approx 2.5857$，$n={10}^6$ 时 $s_n\approx 2.6123$，与极限的差按 $1/\sqrt{n}$ 缩小。这个练习说明判别收敛时把相邻差换成相隔 $n$ 项的差是必要的，指数的临界值 $p=1$ 也在这里显出来：$p\le 1$ 时这种估计失效（$s_{2n}-s_n$ 不趋于零），$p>1$ 时成立。

第 4 题 综合应用

某个迭代算法用来求解方程 $x=T(x)$，其中 $T$ 在区间 $[1,2]$ 上满足 $|T^{\prime }(x)|\le 0.8$，且 $T$ 把 $[1,2]$ 映入自身。请给出这个算法收敛性的完整论证，包括：所用到的空间与完备性、压缩常数的来源、误差按什么速率下降、把误差降到 ${10}^{-9}$ 需要多少步、以及实现中应当监控哪两项指标。再说明如果 $|T^{\prime }|$ 在区间上是 $0.99$ 或 $1.2$，结论分别如何变化。

参考答案

空间与完备性：取 $X=[1,2]$ 配上距离 $d(x,y)=|x-y|$。作为实数轴上的有界闭集，$[1,2]$ 是完备的度量空间：其中的 Cauchy 列收敛到 $[1,2]$ 内的点（有界闭集的极限点仍在集合内）。这一点必须验证，否则定理不适用（例如在开区间 $(1,2)$ 上，迭代可能收敛到端点而端点不在空间内）。

压缩常数：由中值定理，对任意 $x,y\in [1,2]$ 有 $|T(x)-T(y)|=|T^{\prime }(\xi )||x-y|\le 0.8|x-y|$，压缩常数 $q=0.8$。

收敛与速率：$T$ 把 $[1,2]$ 映入自身，所以迭代序列定义良好且始终落在 $[1,2]$ 内。由压缩映射原理，$T$ 在 $[1,2]$ 上有唯一不动点 $x^{\ast }$，迭代收敛，误差满足 $|x_n-x^{\ast }|\le \frac{{0.8}^n}{0.2}|x_1-x_0|=5\cdot {0.8}^n|x_1-x_0|$。指数下降，即几何收敛，比值约为 $0.8$。

步数估计：最坏的初始误差 $|x_1-x_0|$ 不超过 $1$（区间长度为 $1$），要求 $5\times {0.8}^n<{10}^{-9}$，取对数得 $n>\frac{\log (5\times {10}^9)}{\log (1/0.8)}=\frac{22.33}{0.2231}\approx 100$ 步。实际实现中应当在约 $120$ 步后检查一次，或者用后验误差估计 $|x_n-x^{\ast }|\le \frac{q}{1-q}|x_n-x_{n-1}|=4|x_n-x_{n-1}|$ 动态判断。

监控指标：一是相邻两次迭代的差 $|x_n-x_{n-1}|$，它给出了误差的上界估计（乘以 $q/(1-q)$）；二是迭代值是否越出 $[1,2]$，一旦越界说明函数实现或参数与假设不符，继续迭代没有理论依据。第二项在调试阶段尤其重要，因为压缩条件 $q<1$ 只在整个区间上成立时才有效，局部检查容易漏掉违规区域。

两种变化：$|T^{\prime }|\le 0.99$ 时定理仍然成立，压缩常数 $q=0.99$，收敛变成缓慢的几何速率：达到同样精度需要的步数约为 $0.8$ 情形的 $5$ 倍以上（$\log (1/0.8)/\log (1/0.99)\approx 22$ 倍中的一部分被初始误差抵消），实现中常改用加速方法或换用 Newton 迭代。$|T^{\prime }|=1.2>1$ 时压缩条件不成立，定理的结论全部失效，迭代可能发散（本节实验二中的非压缩迭代就是这种情形），此时需要重新设计迭代函数，使它在不动点附近的导数绝对值小于 $1$。

常见错误

错误 1 · 用相邻两项的差趋于零判断收敛

原因：这只用到下标相差 $1$ 的项，Cauchy 条件要求任意两项。调和级数是标准反例：相邻差 $1/n\to 0$，但相隔 $n/2$ 项的差稳定在 $\ln 2\approx 0.693$，部分和无界。同样的混淆出现在算法实现中：以相邻两次迭代差小于阈值作为停止条件，对收敛缓慢或周期振荡的问题会提前停止，输出一个误差远大于阈值的解。

解决：判断收敛用 Cauchy 条件（任意 $m,n>N$）或用收敛定理（单调有界、比较判别等）。实现中把停止条件写成误差上界而不是误差本身：利用问题的结构给出当前迭代值与真解的距离的界（例如压缩映射的 $q|x_n-x_{n-1}|/(1-q)$，或优化问题中梯度范数与目标值误差的关系），据此设定阈值。

错误 2 · 忘记验证不动点所在的集合是完备的

原因：压缩映射原理要求空间完备。把迭代限制在开区间或无界集合上使用时结论可能失效：空间不完备时 Cauchy 列可能收敛到空间外的点，不动点也可能落在空间之外。用函数把区间映入自身这一条件时，也要逐个验证，否则迭代可能一步跨出区间。

解决：用实数轴上的闭区间（有界闭集完备，且只要验证端点处的取值满足 $T([a,b])\subset [a,b]$ 即可），或者用完整的欧氏空间、连续函数空间这类已知完备的空间。验证方式写成两条：$T(x)\in X$ 对一切 $x\in X$ 成立；压缩常数 $q<1$ 对一切 $x\in X$ 成立。两条都成立再引用定理。

错误 3 · 把浮点数的行为当作实数的性质

原因：双精度浮点数只有约 $16$ 位有效数字，$1$ 附近的最小间隔是 $2.22\times {10}^{-16}$。依赖误差可以任意小的迭代在数值上会停滞（本节实验一的二分法在 $53$ 步后不再收缩），依赖**$a+b=b$ 蕴含 $a=0$**的推理在浮点上不成立（$1+{10}^{-16}=1$），$0.1+0.2\ne 0.3$ 也是同一类现象。

解决：把理论结论与数值实现分开评估。设定收敛阈值时不低于机器精度的合理倍数（例如相对误差 ${10}^{-12}$）；避免用相等比较浮点数，改用差值小于容差；对需要高精度的累加使用补偿求和或更高的数值类型（如双精度加倍、任意精度库）；在报告中区分迭代收敛与迭代在浮点精度下停滞两种状态。

错误 4 · 把上确界与最大值混为一谈

原因：上确界是最小的上界，可以不属于集合（例如 $A=\{1-1/n\}$ 的上确界为 $1$ 而 $1\notin A$）；最大值必须在集合内取到。混淆会导致两处错误：用存在 $x\in A$ 使 $x=supA$做推理（不成立）；证明中忽略上确界的第二条性质，只验证 $supA$ 是上界就结束。

解决：使用上确界时明确写出两条性质（本身是上界；对任意 $\epsilon >0$ 存在元素大于 $supA-\epsilon$），第二条往往是证明的关键步骤。需要最大值时另外验证取到性：紧集上的连续函数一定取到最大值，非紧集合上要单独讨论（例如开区间上连续函数的极值可能在端点处取不到）。