2 数列极限与迭代收敛
能够使用 \(\varepsilon\)–\(N\) 定义证明收敛，依据单调性、有界性、子列与 Cauchy 准则判断极限是否存在；能够从误差递推式推导迭代次数与停止规则。先修内容为第1章的量词、确界和不等式。本章的一元迭代只需代数运算，不要求先学导数。
一列数不仅是若干数值的集合，而且含有排列顺序。数列 \(1,-1,1,-1,\ldots\) 只有两个不同的值，却持续振荡；数列 \(1,1/2,1/3,\ldots\) 有无穷多个不同的值，却趋向一个数。极限研究指标无限增大时的整体行为。由计算机产生的参数记录、误差记录和迭代差，也首先是这样的数列。
数列可以用通项公式给出，也可以由初值与递推规则给出。通项公式使每一项直接依赖指标，递推式则要求逐步确认下一项存在且唯一。含除法的递推要避免分母为零，含平方根的递推要保证根号内非负。只写一个递推表达式而不指定允许的初值，通常还没有完整定义一个数列。研究时先证明各步合法，再讨论单调、有界和极限，能够避免把无意义的计算误当成发散行为。
2.1 数列极限的严格定义与基本性质
定义 2.1 (数列收敛). 设 \((a_n)_{n\geqslant1}\) 为实数列。若存在 \(a\in\mathbb{R}\)，使对任意 \(\varepsilon>0\)，存在正整数 \(N\)，当 \(n\geqslant N\) 时均有 \(|a_n-a|<\varepsilon\)，则称 \(a_n\) 收敛于 \(a\)，记作 \(a_n\to a\) 或 \(\lim_{n\to\infty}a_n=a\)。不存在有限实数极限的数列称为发散数列。
定义中的”均有”排除了只在少数指标接近 \(a\) 的情形。\(N\) 不是唯一的；只要某个 \(N\) 有效，更大的整数也有效。因此证明时无需追求最小 \(N\)，而应找到一个可以核验的选择。改变或删去有限个初始项不影响收敛性和极限。
例 2.2 (给误差要求选择指标). 证明 \(a_n=(3n+1)/(n+2)\to3\)。直接整理得 \[|a_n-3|=\frac5{n+2}<\frac5n.\] 给定 \(\varepsilon>0\)，取 \(N=\lfloor5/\varepsilon\rfloor+1\)。当 \(n\geqslant N\) 时，\(n>5/\varepsilon\)，故 \(|a_n-3|<\varepsilon\)。当要求误差小于 \(10^{-3}\) 时，\(N=5001\) 是一个保证有效的取值；它不是最小取值，但足以完成证明。
定理 2.3 (极限唯一性与有界性). 收敛实数列的极限唯一，并且收敛实数列必有界。
证明. Proof. 若同一数列同时趋于 \(a\) 和 \(b\) 且 \(a\neq b\)，取 \(\varepsilon=|a-b|/3\)。对充分大的 \(n\)，有 \[|a-b|\leqslant|a-a_n|+|a_n-b|<\frac23|a-b|,\] 矛盾。再设 \(a_n\to a\)。取 \(\varepsilon=1\)，存在 \(N\) 使 \(n\geqslant N\) 时 \(|a_n|\leqslant|a|+1\)。有限个初始项也有界，故 \[|a_n|\leqslant\max\{|a_1|,\ldots,|a_{N-1}|,|a|+1\}\] 对所有 \(n\) 成立；若 \(N=1\)，只取最后一项即可。 ◻
命题 2.4 (保序性与最终保号性). 若 \(a_n\to a\)、\(b_n\to b\)，且从某项起 \(a_n\leqslant b_n\)，则 \(a\leqslant b\)。若 \(a_n\to a>0\)，则从某项起 \(a_n>a/2>0\)。
证明. Proof. 若 \(a>b\)，取 \(\varepsilon=(a-b)/3\)。充分大的 \(n\) 满足 \(a_n>a-\varepsilon>b+\varepsilon>b_n\)，矛盾。第二个结论取 \(\varepsilon=a/2\)，由 \(|a_n-a|<a/2\) 即得。 ◻
严格不等式一般不能原样传给极限。例如 \(1/n>0\) 对所有 \(n\) 成立，但极限等于零。最终保号性是从非零极限推出后部各项同号，而不是从各项同号推出非零极限。
\(a_n\to+\infty\) 表示对每个 \(M>0\)，存在 \(N\) 使 \(n\geqslant N\) 时 \(a_n>M\)；\(a_n\to-\infty\) 类似。它们不是有限实数收敛。无界数列可以反复返回零，例如 \(a_{2k}=k\)、\(a_{2k-1}=0\)；有界数列也可以发散，例如 \((-1)^n\)。
2.2 极限运算、夹逼与平均
定理 2.5 (四则运算法则). 若 \(a_n\to a\)、\(b_n\to b\)，则对固定实数 \(\lambda,\mu\) 有 \[\lambda a_n+\mu b_n\to\lambda a+\mu b, \qquad a_nb_n\to ab.\] 若另有 \(b\neq0\)，则从某项起 \(b_n\neq0\)，并且 \(a_n/b_n\to a/b\)。
证明. Proof. 线性组合由 \(|\lambda(a_n-a)+\mu(b_n-b)|\leqslant|\lambda||a_n-a|+|\mu||b_n-b|\) 得到，对两个误差分别分配容差即可。乘积可写为 \[a_nb_n-ab=a_n(b_n-b)+b(a_n-a).\] 收敛列 \((a_n)\) 有界，取 \(C\geqslant1\) 使 \(|a_n|\leqslant C\)。给定 \(\varepsilon>0\)，让 \(|b_n-b|<\varepsilon/(2C)\) 且 \(|a_n-a|<\varepsilon/(2(|b|+1))\)，即可把总误差控制在 \(\varepsilon\) 内。
若 \(b\neq0\)，充分大的 \(n\) 有 \(|b_n|\geqslant|b|/2\)，于是 \[\left|\frac1{b_n}-\frac1b\right| =\frac{|b_n-b|}{|b_n||b|} \leqslant\frac2{|b|^2}|b_n-b|\longrightarrow0.\] 再应用乘积法则即得商的结论。 ◻
这些法则的前提是相应有限极限存在。不能把 \(\infty-\infty\)、\(0/0\) 当作通常数值代入，也不能把两个未知敛散性的因子先各自取极限。
例 2.6 (有理化后的极限). 求 \(a_n=\sqrt{n^2+3n}-n\) 的极限。两个单独的项都趋向正无穷，不能用差的法则。先有理化： \[a_n=\frac{3n}{\sqrt{n^2+3n}+n} =\frac3{\sqrt{1+3/n}+1}.\] 由 \[0\leqslant\sqrt{1+3/n}-1 =\frac{3/n}{\sqrt{1+3/n}+1}\leqslant\frac{3}{2n}\] 知根号项趋于 \(1\)，再用商的法则得 \(a_n\to3/2\)。这个步骤只使用代数和误差估计，尚不依赖函数连续性。
定理 2.7 (夹逼定理). 若从某项起 \(a_n\leqslant c_n\leqslant b_n\)，且 \(a_n\to L\)、\(b_n\to L\)，则 \(c_n\to L\)。
证明. Proof. 给定 \(\varepsilon>0\)，充分大的 \(n\) 同时满足 \(L-\varepsilon<a_n\) 和 \(b_n<L+\varepsilon\)。于是 \(L-\varepsilon<c_n<L+\varepsilon\)，即 \(|c_n-L|<\varepsilon\)。 ◻
例 2.8 (振荡幅度与极限). 对 \(c_n=\sin(n^2)/\sqrt n\)，有 \(|c_n|\leqslant1/\sqrt n\)。给定 \(\varepsilon>0\)，只要 \(n>\varepsilon^{-2}\) 就有 \(|c_n|<\varepsilon\)，故 \(c_n\to0\)。不必知道 \(\sin(n^2)\) 本身是否收敛；振荡被趋于零的幅度统一控制。
命题 2.9 (收敛数列的算术平均). 若 \(a_n\to a\)，则 \(s_n=(a_1+\cdots+a_n)/n\to a\)。
证明. Proof. 给定 \(\varepsilon>0\)，取 \(N\) 使 \(k\geqslant N\) 时 \(|a_k-a|<\varepsilon/2\)。令 \(C=\sum_{k=1}^{N-1}|a_k-a|\)。当 \(n\geqslant N\) 时， \[|s_n-a|\leqslant\frac Cn+ \frac1n\sum_{k=N}^{n}|a_k-a| <\frac Cn+\frac\varepsilon2.\] 再要求 \(n>2C/\varepsilon\)，即得结论。有限的前段误差由除以 \(n\) 消去，后段则由收敛性统一控制。 ◻
逆命题不成立：取 \(a_n=(-1)^n\)，平均数的绝对值不超过 \(1/n\)，故平均数趋于零，而原数列发散。对训练记录求滑动或累计平均会改变所观察的数列；平均曲线平稳不能单独证明原始参数收敛。
2.3 单调收敛与区间套
定理 2.10 (单调有界收敛定理). 单调递增且有上界的实数列收敛于其值集的上确界；单调递减且有下界的实数列收敛于其值集的下确界。
证明. Proof. 设 \((a_n)\) 递增且有上界，令 \(a=\sup\{a_n:n\geqslant1\}\)。给定 \(\varepsilon>0\)，由确界性质存在 \(N\) 使 \(a_N>a-\varepsilon\)。对 \(n\geqslant N\)，单调性给出 \(a-\varepsilon<a_N\leqslant a_n\leqslant a\)，所以 \(|a_n-a|<\varepsilon\)。递减情形应用于 \((-a_n)\) 即可。 ◻
递推数列的常见错误是先设极限为 \(L\)，求出方程的一个解，就宣布数列收敛。极限方程只能给出候选值；存在性必须先由有界、单调或其他条件保证。
例 2.11 (平方根的递推逼近). 取 \(x_0=2\)，定义 \[x_{n+1}=\frac12\left(x_n+\frac2{x_n}\right),\qquad n\geqslant0.\] 先说明所有项均有定义且不小于 \(\sqrt2\)。只要 \(x_n>0\)，就有 \[x_{n+1}-\sqrt2=\frac{(x_n-\sqrt2)^2}{2x_n}\geqslant0.\] 从 \(x_0=2\) 出发可归纳得到 \(x_n\geqslant\sqrt2\)。再由 \[x_{n+1}-x_n=\frac{2-x_n^2}{2x_n}\leqslant0\] 知数列递减。因此它收敛于某个 \(L\geqslant\sqrt2\)。现在才可对递推式取极限，得 \(L=(L+2/L)/2\)，即 \(L^2=2\)，所以 \(L=\sqrt2\)。
误差 \(e_n=x_n-\sqrt2\) 还满足 \(e_{n+1}=e_n^2/(2x_n)\leqslant e_n^2/(2\sqrt2)\)。当误差已较小时，新误差具有平方量级；这个结论比”会收敛”更精确。
定理 2.12 (闭区间套定理). 设非空闭区间 \(I_n=[a_n,b_n]\) 满足 \(I_{n+1}\subseteq I_n\)。则交集 \(\bigcap_{n\geqslant1}I_n\) 非空。若另有 \(b_n-a_n\to0\)，交集恰含一个点。
证明. Proof. 左端点 \((a_n)\) 递增且被 \(b_1\) 控制，故趋于 \(a\)。固定 \(n\)，对所有 \(k\geqslant n\) 有 \(a_n\leqslant a_k\leqslant b_n\)，取极限得 \(a\in[a_n,b_n]\)。因此 \(a\) 属于全部区间。若交集中有两点 \(u<v\)，则 \(v-u\leqslant b_n-a_n\) 对所有 \(n\) 成立，与区间长度趋于零矛盾。 ◻
闭区间不能任意换成开区间。区间 \((0,1/n)\) 逐个非空且层层缩小，但交集为空；候选点零被每个区间排除。长度趋于零只负责唯一性，非空性来自闭性和嵌套结构。
2.4 子列、聚点与 Cauchy 收敛准则
定义 2.13 (子列). 若正整数 \(n_1<n_2<\cdots\)，则 \((a_{n_k})\) 称为 \((a_n)\) 的子列。若某子列趋于 \(\ell\)，称 \(\ell\) 为原数列的一个子列极限。
因为 \(n_k\geqslant k\)，原数列收敛时，每个子列均趋于同一个极限。因而只要找到两个极限不同的子列，就能证明原数列发散。
例 2.14 (有界但不收敛). 设 \(a_n=(-1)^n+1/n\)。偶数子列趋于 \(1\)，奇数子列趋于 \(-1\)，所以原数列不收敛。虽然 \(|a_n|\leqslant2\)，有界性只排除了逃向任意大的绝对值，没有排除多个聚集位置。
定理 2.15 (Bolzano–Weierstrass 定理). 每个有界实数列都有收敛子列。
证明. Proof. 取闭区间 \(I_1\) 包含全部项。将其二等分，至少有一个闭半区间包含无穷多个指标对应的项，选为 \(I_2\)。反复二分，得到嵌套闭区间 \(I_k\)，每个都含无穷多项，长度趋于零。由闭区间套定理，它们有唯一公共点 \(\ell\)。
先选 \(a_{n_1}\in I_1\)；已选 \(n_{k-1}\) 后，由 \(I_k\) 含无穷多项，可选 \(n_k>n_{k-1}\) 使 \(a_{n_k}\in I_k\)。于是 \(|a_{n_k}-\ell|\) 不超过 \(I_k\) 的长度，故子列趋于 \(\ell\)。 ◻
定义 2.16 (Cauchy 列). 若对每个 \(\varepsilon>0\)，存在正整数 \(N\)，使所有 \(m,n\geqslant N\) 都满足 \(|a_m-a_n|<\varepsilon\)，则称 \((a_n)\) 为 Cauchy 列。
Cauchy 条件比较后部任意两项，不需要预先猜出极限。特别要注意”任意两项”，它远强于相邻差 \(|a_{n+1}-a_n|\to0\)。
定理 2.17 (实数列的 Cauchy 收敛准则). 实数列收敛，当且仅当它是 Cauchy 列。
证明. Proof. 若 \(a_n\to a\)，充分大的 \(m,n\) 使两个误差都小于 \(\varepsilon/2\)，由三角不等式得 Cauchy 条件。
反之，先在 Cauchy 条件中取 \(\varepsilon=1\)，固定后段中的一项，得后段有界；与有限前段合并，原数列有界。由 Bolzano–Weierstrass 定理，存在子列 \(a_{n_k}\to a\)。给定 \(\varepsilon>0\)，取 \(N\) 使 \(m,n\geqslant N\) 时 \(|a_m-a_n|<\varepsilon/2\)。再选 \(k\) 满足 \(n_k\geqslant N\) 和 \(|a_{n_k}-a|<\varepsilon/2\)。于是每个 \(n\geqslant N\) 均满足 \[|a_n-a|\leqslant|a_n-a_{n_k}|+|a_{n_k}-a|<\varepsilon.\] 故原数列收敛。 ◻
例 2.18 (相邻变化趋于零仍可能不收敛). 令 \(h_n=1+1/2+\cdots+1/n\)。虽然 \(h_{n+1}-h_n=1/(n+1)\to0\)，但 \[h_{2n}-h_n=\sum_{k=n+1}^{2n}\frac1k\geqslant\frac n{2n}=\frac12.\] 任意靠后的两个指标 \(n,2n\) 仍可能相差至少 \(1/2\)，所以它不是 Cauchy 列，也不收敛。这个反例直接说明，仅观察某一次更新很小不足以证明整个序列已经接近极限。
上下极限的初步认识
对有界数列定义后段下界与上界 \[\alpha_n=\inf_{k\geqslant n}a_k,\qquad \beta_n=\sup_{k\geqslant n}a_k.\] 随着前部项被删除，\(\alpha_n\) 递增、\(\beta_n\) 递减，且都有界，故它们有极限，分别记为 \(\liminf a_n\) 和 \(\limsup a_n\)。它们描述后部数值能持续接近的最低与最高水平。由 \(\alpha_n\leqslant a_n\leqslant\beta_n\)，若两者具有相同极限 \(a\)，夹逼定理给出 \(a_n\to a\)；反过来若 \(a_n\to a\)，后部所有项最终位于任意误差带内，因此两者都趋于 \(a\)。
命题 2.19 (上下极限与子列极限). 设 \((a_n)\) 有界，\(\alpha=\liminf a_n\)、\(\beta=\limsup a_n\)。则每个子列极限都在 \([\alpha,\beta]\) 内，并且 \(\alpha\) 与 \(\beta\) 本身都是子列极限。
证明. Proof. 若 \(a_{n_k}\to\ell\)，固定正整数 \(N\)，充分大的 \(k\) 有 \(n_k\geqslant N\)，故 \(\alpha_N\leqslant a_{n_k}\leqslant\beta_N\)。先令 \(k\to\infty\)，再令 \(N\to\infty\)，得 \(\alpha\leqslant\ell\leqslant\beta\)。
为构造趋于 \(\beta\) 的子列，设已选到 \(n_{k-1}\)，令 \(N_k=\max\{k,n_{k-1}+1\}\)，首步取 \(N_1=1\)。由后段上确界性质，可选 \(n_k\geqslant N_k\) 使 \[\beta_{N_k}-\frac1k<a_{n_k}\leqslant\beta_{N_k}.\] 因 \(N_k\geqslant k\)，有 \(\beta_{N_k}\to\beta\)，由夹逼得 \(a_{n_k}\to\beta\)。下极限的构造同理，使用后段下确界即可。 ◻
对数列 \((-1)^n+1/n\)，上下极限分别为 \(-1\) 和 \(1\)，它们由奇、偶子列实现。区间 \([-1,1]\) 内的每一点却未必都是子列极限，本例只出现两个极限。因此，上下极限给出后部聚集行为的边界，不能据此断言数值填满整个边界区间。
还应区分”包含无穷多个不同数值”和”包含无穷多个数列项”。常数列只有一个不同数值，却有无穷多个指标。Bolzano–Weierstrass 定理二分证明中，每次保留的是含无穷多个指标的区间，这使下一步总能选择大于前一指标的新项，并且也覆盖常数列或重复值很多的数列。这个细节保证所构造对象确实是指标严格增加的子列。
完备性保证极限留在所研究的空间
Cauchy 准则不仅是一种计算技巧，还体现实数系的完备性。它说明：只要后部任意两项能彼此足够接近，就存在一个实数作为它们共同逼近的对象。若把允许的极限限制到较小集合内，这一结论可能失效。
例如，取 \(\sqrt2\) 的小数截断值 \(r_n=\lfloor10^n\sqrt2\rfloor/10^n\)。每个 \(r_n\) 都是有理数，且 \(0\leqslant\sqrt2-r_n<10^{-n}\)，故它在实数系中是 Cauchy 列并趋于 \(\sqrt2\)。但 \(\sqrt2\) 不是有理数，所以不存在有理数作为此列的极限。又如 \(1/(n+1)\) 的每一项均属于开区间 \((0,1)\)，其极限零却不属于该区间。相应地，压缩迭代定理要求映射保持一个闭区间，既保证各步有定义，也保证极限不会落在被排除的边界上。
如何否定收敛而不混淆量词
\(a_n\) 不趋于指定实数 \(a\)，是指存在一个固定 \(\varepsilon_0>0\)，使对每个 \(N\) 都能找到 \(n\geqslant N\) 满足 \(|a_n-a|\geqslant\varepsilon_0\)。这个反例指标可以随 \(N\) 改变，但误差门槛必须固定。若只证明对每个 \(n\) 都有 \(a_n\neq a\)，并不能否定收敛，因为 \(1/n\) 从未等于零却趋于零。
进一步，证明数列发散需要排除所有实数候选极限。寻找两个具有不同极限的子列，一次就排除了这种可能。若数列无界，则也能立即排除有限收敛，因为收敛列必有界。各种判别方法的结论力度不同，应先判断准备证明的是”不趋于某个数”还是”不存在任何有限极限”。
2.5 迭代映射、收敛速度与停止规则
递推式 \(x_{n+1}=T(x_n)\) 把当前状态映射为下一状态。满足 \(T(x_*)=x_*\) 的点称为不动点。不动点方程表达可能的极限，却不保证所有初值都会趋于它。
例 2.20 (仿射迭代的全部情形). 设 \(x_{n+1}=qx_n+b\)。当 \(q\neq1\) 时，不动点为 \(x_*=b/(1-q)\)，直接相减并归纳得到 \[\begin{equation} \label{eq:02-affine} x_n-x_*=q^n(x_0-x_*). \end{equation}\] 因此 \(|q|<1\) 时任意初值收敛；\(0<q<1\) 时误差不变号，\(-1<q<0\) 时误差交替变号。\(q=-1\) 时一般形成二周期，\(|q|>1\) 时除初值恰为不动点外均发散。\(q=1\) 时有 \(x_n=x_0+nb\)，仅在 \(b=0\) 时为常数列。
定理 2.21 (闭区间上的压缩迭代). 设 \(I=[a,b]\)，映射 \(T:I\to I\) 满足 \[|T(x)-T(y)|\leqslant q|x-y|\quad(x,y\in I),\qquad 0<q<1.\] 则 \(T\) 有唯一不动点 \(x_*\in I\)，任意 \(x_0\in I\) 生成的迭代都趋于 \(x_*\)，且 \[\begin{equation} \label{eq:02-contract} |x_n-x_*|\leqslant\frac{q^n}{1-q}|x_1-x_0|, \qquad |x_n-x_*|\leqslant\frac{|x_{n+1}-x_n|}{1-q}. \end{equation}\]
证明. Proof. 映射保持区间，故全部迭代有定义且在 \(I\) 中。由压缩条件归纳可得 \(|x_{k+1}-x_k|\leqslant q^k|x_1-x_0|\)。对 \(m>n\)，三角不等式和有限几何和给出 \[|x_m-x_n|\leqslant\sum_{k=n}^{m-1}|x_{k+1}-x_k| \leqslant\frac{q^n}{1-q}|x_1-x_0|.\] 右侧随 \(n\) 趋于零，因此迭代是 Cauchy 列，存在极限 \(x_*\in I\)。又 \[|T(x_*)-x_*|\leqslant q|x_*-x_n|+|x_{n+1}-x_*|\to0,\] 故 \(T(x_*)=x_*\)。若 \(y_*\) 也是不动点，则 \(|x_*-y_*|\leqslant q|x_*-y_*|\)，由 \(q<1\) 得两点相同。让上面的 \(m\to\infty\) 得第一条误差界；从第 \(n\) 步重新对相邻差求几何和，即得第二条。 ◻
若 \(q=0\)，\(T\) 是常值映射，至多一步到达不动点，可单独处理。对一般 \(0<q<1\)，若希望第一条误差界不超过 \(\varepsilon\)，可选择满足 \[q^n|x_1-x_0|\leqslant(1-q)\varepsilon\] 的整数 \(n\)。因 \(\log q<0\)，取对数解不等式时应注意方向。
例 2.22 (可手算的平滑更新). 考虑 \(T(x)=x/2+1\)，取 \(I=[0,2]\)、\(x_0=0\)。它把 \(I\) 映入 \(I\)，压缩系数为 \(1/2\)。由式[eq:02-affine]得 \(x_n=2-2^{1-n}\)，不动点是 \(2\)。
| \(n\) | \(x_n\) | \(|x_n-2|\) | \(|x_{n+1}-x_n|\) | 后验误差界 |
|---|---|---|---|---|
| 0 | 0 | 2 | 1 | 2 |
| 1 | 1 | 1 | \(1/2\) | 1 |
| 2 | \(3/2\) | \(1/2\) | \(1/4\) | \(1/2\) |
| 3 | \(7/4\) | \(1/4\) | \(1/8\) | \(1/4\) |
本例的后验界恰等于实际误差。若停止条件是 \(|x_{n+1}-x_n|\leqslant10^{-3}\)，则可保证当前点 \(x_n\) 到不动点的误差不超过 \(2\times10^{-3}\)；若没有压缩系数的依据，就不能从同样的更新量推出这一结论。
收敛速度：误差如何随指标缩小
只说明 \(x_n\to x_*\)，尚不能给出达到精度要求所需的工作量。令 \(e_n=|x_n-x_*|\)。若从某项起 \(e_{n+1}\leqslant qe_n\)，其中 \(0<q<1\)，则称误差至少具有线性收敛的几何上界。这里”线性”描述相邻误差的比例关系，不是说误差对指标 \(n\) 成一次函数。
当后部误差均非零时，若 \(e_{n+1}/e_n\to0\)，称为超线性收敛；若存在固定 \(C>0\) 使后部 \(e_{n+1}\leqslant Ce_n^2\)，称至少具有二次收敛的误差估计。若有限步后误差恒为零，可直接说明有限终止，无需再使用包含零分母的比值。前面平方根递推的恒等式 \(e_{n+1}=e_n^2/(2x_n)\)，便给出二次误差界。
相比之下，\(e_n=1/(n+1)\) 虽然趋于零，但 \(e_{n+1}/e_n=(n+1)/(n+2)\to1\)，不存在对全部足够大指标有效的固定压缩比例 \(q<1\)。要使 \(1/(n+1)\leqslant\varepsilon\)，需要 \(n+1\geqslant1/\varepsilon\)；要使 \(2^{-n}\leqslant\varepsilon\)，只需 \(n\geqslant\log_2(1/\varepsilon)\)。这两个要求在高精度下相差很大，尽管它们都可用一句”误差趋于零”描述。
| 指标 \(n\) | \(1/(n+1)\) | \(2^{-n}\) | \(2^{-2^n}\) |
|---|---|---|---|
| 0 | \(1\) | \(1\) | \(1/2\) |
| 1 | \(1/2\) | \(1/2\) | \(1/4\) |
| 2 | \(1/3\) | \(1/4\) | \(1/16\) |
| 3 | \(1/4\) | \(1/8\) | \(1/256\) |
| 4 | \(1/5\) | \(1/16\) | \(1/65536\) |
表中的三列是预先给定的精确数列，收敛速度来自公式而非五行数据。实际算法还须比较每步计算成本、可用的初值范围和舍入误差；不能只按局部收敛阶排列所有算法的适用性。
压缩系数也决定停止规则的解释。若已证明 \(q=0.999\)，相邻差 \(10^{-6}\) 对应的后验误差保证只有 \(10^{-3}\)。要保证误差不超过 \(10^{-6}\)，则相邻差需不超过 \(10^{-9}\)。系数越接近 \(1\)，后部的小更新越可能持续累积。因此应把压缩因子与相邻差一起记录，而不是孤立解释更新量。
带有计算扰动的迭代
若实际更新为 \(\widetilde x_{n+1}=T(\widetilde x_n)+r_n\)，且所比较的点始终处于压缩条件适用的范围，则对 \(e_n=|\widetilde x_n-x_*|\) 有 \[e_{n+1}\leqslant qe_n+|r_n|.\] 若 \(|r_n|\leqslant\delta\)，归纳得到 \[\begin{equation} \label{eq:02-noise} e_n\leqslant q^ne_0+\delta\frac{1-q^n}{1-q}. \end{equation}\] 第一项是初始误差的衰减，第二项是各次扰动的累计。它只保证后部误差的上限不超过 \(\delta/(1-q)\)，不保证实际误差收敛。若 \(r_n\to0\)，则可将累计和分成有限前段和小扰动后段，得到 \(e_n\to0\)。这两种结论应分开表述。
数学收敛讨论所有足够大的指标，有限停止由实际计算预算和容差决定。更新小、目标值小、目标值变化小、参数接近某个极限是不同陈述。只有建立残差或更新量到真实误差的上界，停止规则才具有相应的精度保证。
2.6 知识回顾与分层习题
极限定义给出误差要求；运算法则与夹逼处理可化简的数列；单调有界把确界转化为极限；子列刻画聚集行为；Cauchy 准则不预设极限；压缩估计进一步给出误差界和有依据的停止条件。
基础题
用定义证明 \((2n-1)/(n+3)\to2\)，给出一个明确的 \(N(\varepsilon)\)。
求 \(\lim_{n\to\infty}(5n^2+2n-1)/(2n^2+7)\)。
求 \(\lim_{n\to\infty}n(\sqrt{1+1/n}-1)\)，不得把 \(0\cdot\infty\) 当作数值代入。
判断 \((-1)^n/n\)、\(1+(-1)^n\)、\(n\sin(n\pi/2)\) 的敛散性及有界性。
若 \(a_n\to3\)，证明从某项起 \(a_n>2\)；说明能否推出对所有 \(n\) 都有 \(a_n>2\)。
解递推式 \(x_{n+1}=-x_n/3+2\)、\(x_0=0\)，并给出极限和绝对误差公式。
推理题
若 \((a_n)\) 有界而 \(b_n\to0\)，证明 \(a_nb_n\to0\)；说明是否需要 \((a_n)\) 收敛。
设 \(x_1=1\)，\(x_{n+1}=\sqrt{2+x_n}\)。证明它收敛并求极限。
若 \(|a_{n+1}-a_n|\leqslant Cq^n\)，其中 \(C>0\)、\(0<q<1\)，证明 \((a_n)\) 收敛，并给出 \(|a_n-\lim a_k|\) 的上界。
若有界实数列的每个收敛子列都趋于同一个数 \(a\)，证明原数列趋于 \(a\)。说明有界条件的作用。
拓展题
对 \(T(x)=x/4+3\)、\(x_0=0\)，求达到 \(|x_n-4|\leqslant10^{-4}\) 所需的最小非负整数 \(n\)。再由后验误差界写出一个只使用相邻迭代值的停止条件。
设非负数列满足 \(e_{n+1}\leqslant qe_n+\delta_n\)，其中 \(0<q<1\)、\(\delta_n\geqslant0\) 且 \(\delta_n\to0\)。用有限前段与后段分离的方法证明 \(e_n\to0\)。
2.7 本章选题解答
误差等于 \(7/(n+3)<7/n\)。给定 \(\varepsilon>0\)，取 \(N=\lfloor7/\varepsilon\rfloor+1\)，则 \(n\geqslant N\) 时误差小于 \(\varepsilon\)。
有理化得 \(n(\sqrt{1+1/n}-1)=1/(\sqrt{1+1/n}+1)\)。又 \(0\leqslant\sqrt{1+1/n}-1\leqslant1/(2n)\)，故分母趋于 \(2\)，极限为 \(1/2\)。
不动点满足 \(x_*=-x_*/3+2\)，得 \(x_*=3/2\)。误差递推为 \(x_{n+1}-3/2=-(x_n-3/2)/3\)，故 \[x_n=\frac32\left(1-\left(-\frac13\right)^n\right), \qquad |x_n-3/2|=\frac32\,3^{-n}.\] 因此振荡收敛于 \(3/2\)。
取 \(M\geqslant1\) 使 \(|a_n|\leqslant M\)。给定 \(\varepsilon>0\)，充分大的 \(n\) 有 \(|b_n|<\varepsilon/M\)，故 \(|a_nb_n|<\varepsilon\)。不要求 \(a_n\) 收敛，例如 \(a_n=(-1)^n\)。
归纳可得 \(1\leqslant x_n<2\)：若 \(x_n<2\)，则 \(x_{n+1}<2\)。在 \(1\leqslant x<2\) 上，\(2+x-x^2=(2-x)(x+1)>0\)，故 \(\sqrt{2+x}>x\)。于是数列递增有上界，存在 \(L\in[1,2]\)。由平方根差的估计或对 \(x_{n+1}^2=2+x_n\) 取极限，得 \(L^2=2+L\)，结合范围得 \(L=2\)。
对 \(m>n\)，有 \[|a_m-a_n|\leqslant\sum_{k=n}^{m-1}Cq^k\leqslant\frac{Cq^n}{1-q}.\] 所以它是 Cauchy 列。记极限为 \(a\)，令 \(m\to\infty\) 得 \(|a_n-a|\leqslant Cq^n/(1-q)\)。
若原数列不趋于 \(a\)，存在 \(\varepsilon_0>0\) 和子列 \((a_{n_k})\)，使每项都满足 \(|a_{n_k}-a|\geqslant\varepsilon_0\)。该子列有界，故有收敛子子列，设极限为 \(b\)；保序性给出 \(|b-a|\geqslant\varepsilon_0\)，与所有收敛子列均趋于 \(a\) 矛盾。有界条件用来保证所构造的子列仍有收敛子列。
由精确误差 \(4^{1-n}\leqslant10^{-4}\)，需 \(4^n\geqslant40000\)。因 \(4^7=16384\)、\(4^8=65536\)，最小 \(n=8\)。后验界为 \(|x_n-4|\leqslant\frac43|x_{n+1}-x_n|\)，因此 \(|x_{n+1}-x_n|\leqslant7.5\times10^{-5}\) 足以保证目标精度。
迭代展开得 \(e_n\leqslant q^ne_0+\sum_{j=0}^{n-1}q^{n-1-j}\delta_j\)。给定 \(\varepsilon>0\)，选 \(J\) 使 \(j\geqslant J\) 时 \(\delta_j<(1-q)\varepsilon/2\)，则后段和小于 \(\varepsilon/2\)。有限前段和与 \(q^ne_0\) 都是有限个随 \(n\) 衰减的几何项，充分大的 \(n\) 使其总和小于 \(\varepsilon/2\)。由 \(e_n\geqslant0\) 得 \(e_n\to0\)。