5.2 数列、级数与无穷过程

上一节建立了极限的语言，并给出了判断收敛的六条等价定理。这一节用它们处理无穷求和：把无穷多个数加起来，和会不会稳定到某个有限值。级数是分析里出现频率最高的对象之一，Taylor 展开是幂级数的和，函数的逼近是函数项级数的部分和，算法复杂度的估计靠的是级数的主项，数值计算中的求和误差则直接取决于级数的收敛速度。

级数的判敛是本节的主线。判断方法有一整套：正项级数用比较、比值、根值、积分判别，一般项级数用 Leibniz、Abel、Dirichlet 判别。这些判别法各有适用范围，其中比值与根值判别在 $p$ 级数上全部失效（极限都等于 $1$），理解这一点比记住公式更重要。级数的第二个主题是条件收敛带来的反常现象：绝对收敛的级数可以任意重排而不改变和，条件收敛的级数重排后可以变成任何指定的值。这一现象有严格的证明与直观的数值形态，本节用一段代码把它演示出来。

最后一段内容面向计算：级数的收敛速度决定数值求和的代价，交错级数可以用加速方法把误差压低几个数量级；浮点求和的累积误差与求和顺序、数据类型有关，累加 ${10}^6$ 项时朴素升序求和的相对误差约 $5\times {10}^{-14}$，补偿求和可以把误差压到零。这一节把纯理论（收敛判别）与纯工程（求和误差控制）放在一起，两者的连接点是误差估计。

5.2.1 数列极限的补充工具

上下极限与子列

有界数列不一定收敛（如 $a_n=(-1{)}^n$），但它总有「最靠上的部分极限」与「最靠下的部分极限」。定义

$$\underset{n\to \mathrm{\infty }}{\bar{\lim }}{a}_n=\underset{n\to \mathrm{\infty }}{lim}\left(\underset{k\ge n}{sup}{a}_k\right),\underset{n\to \mathrm{\infty }}{\underset{―}{\lim }}{a}_n=\underset{n\to \mathrm{\infty }}{lim}\left(\underset{k\ge n}{inf}{a}_k\right)$$

第一个式子中的 $\underset{k\ge n}{sup}{a}_k$ 随 $n$ 增大单调不增，因此它的极限总存在（可以是 $\pm \mathrm{\infty }$）。三条常用性质：$\underset{―}{\lim }{a}_n\le \bar{\lim }{a}_n$；数列收敛的充要条件是上下极限相等，此时公共值就是极限；有界数列必有子列收敛到它的上极限（由 Bolzano-Weierstrass 定理与上极限的定义得到）。上下极限在处理不收敛但有界的数列时替代极限的位置，例如判断级数在边界情形下的行为。

Stolz 定理

数列版本的洛必达法则。设 $\{b_n\}$ 严格递增且趋于无穷，若

$$\underset{n\to \mathrm{\infty }}{lim}\frac{a_{n+1}-a_n}{b_{n+1}-b_n}=L$$

则 $lim{a}_n/b_n=L$（$L$ 为有限值或无穷大时都成立）。使用条件是分母的差已知且容易计算，常用于处理部分和之比。

例：求 $\underset{n\to \mathrm{\infty }}{lim}{\displaystyle \frac{H_n}{\ln n}}$，其中 $H_n=1+\frac{1}{2}+\cdots +\frac{1}{n}$。

取 $a_n=H_n$、$b_n=\ln n$（严格增且趋于无穷），则

$$\frac{a_{n+1}-a_n}{b_{n+1}-b_n}=\frac{1/(n+1)}{\ln (n+1)-\ln n}=\frac{1/(n+1)}{\ln (1+1/n)}$$

由 $\ln (1+x)\sim x$（$x\to 0$）得比值的极限为 $1$，因此 $H_n/\ln n\to 1$。数值上（练习题 3 给出数据）：$n={10}^3$ 时比值 $1.0836$，$n={10}^6$ 时 $1.0418$，向 $1$ 缓慢靠近，误差按 $1/\ln n$ 量级缩小。

渐近记号

比较两个数列（或函数）在极限过程中的增长快慢，用四组记号。

$f(n)=O(g(n))$：存在常数 $C>0$ 与 $N$，当 $n>N$ 时 $|f(n)|\le C|g(n)|$。含义是 $f$ 的增长不快于 $g$。

$f(n)=o(g(n))$：$limf(n)/g(n)=0$。含义是 $f$ 的增长慢于 $g$。

$f(n)=\mathrm{\Theta }(g(n))$：$f=O(g)$ 且 $g=O(f)$。含义是两者同阶。

$f(n)\sim g(n)$：$limf(n)/g(n)=1$。含义是两者之比趋于 $1$，比同阶更强。

使用这组记号时要记住三点。第一，等号方向是单向的：$n=O(n^2)$ 正确，$O(n^2)=n$ 没有意义。第二，常数与低阶项都被吸收：$3n^2+5n+7=O(n^2)$。第三，不同量级的对照关系需要记住：对数增长慢于任何正幂次（$\ln n=o(n^{ϵ})$ 对任意 $ϵ>0$），幂次增长慢于指数（$n^k=o(a^n)$ 对任意 $a>1$），指数慢于阶乘（$a^n=o(n!)$）。这几个不等式是算法复杂度分析与统计渐近分析的基础，第 5.12 节会给出它们的证明工具。

例：$H_n=\ln n+\gamma +O(1/n)$，其中 $\gamma \approx 0.5772$ 是 Euler 常数。这条展开式在算法分析中反复出现（例如调和级数求和的分析）。

递推数列

由递推关系定义的数列用单调有界定理处理最方便。步骤是三步：证明有界（常用归纳法）、证明单调、对递推式两端取极限解出极限值。

例：$a_1=\sqrt{2}$，$a_{n+1}=\sqrt{2+a_n}$，求极限。第一步用归纳法证明 $a_n<2$：$a_1<2$，且 $a_n<2$ 时 $a_{n+1}=\sqrt{2+a_n}<\sqrt{4}=2$。第二步证明单调递增：$a_{n+1}^2-a_n^2=2+a_n-a_n^2=(2-a_n)(1+a_n)>0$。第三步设极限为 $a$，对 $a_{n+1}^2=2+a_n$ 两端取极限得 $a^2=2+a$，解出 $a=2$（另一根 $-1$ 不合题意）。

5.2.2 级数的收敛与基本判据

部分和与收敛

给定数列 $\{a_n\}$，把无穷多个数相加的表达式 $\sum _{n=1}^{\mathrm{\infty }}{a}_n$ 称为级数。它的含义由部分和定义：令 $S_N=a_1+a_2+\cdots +a_N$，若数列 $\{S_N\}$ 收敛于有限值 $S$，称级数收敛，$S$ 是它的和，记作 $\sum _{n=1}^{\mathrm{\infty }}{a}_n=S$；否则称级数发散。

这个定义把级数问题完全化为数列问题，因此上一节的所有工具都可以使用。由 Cauchy 收敛准则立刻得到级数版的判据：级数收敛的充要条件是对任意 $\epsilon >0$ 存在 $N$，当 $m>n>N$ 时 $\left|\sum _{k=n+1}^m{a}_k\right|<\epsilon$。把这条件用在 $m=n+1$ 上，得到必要条件：收敛级数的通项趋于零，$a_n\to 0$。

必要条件不是充分条件。调和级数 $\sum 1/n$ 的通项趋于零，级数却发散，两种证明如下。

分组证明：把项按 $2^k$ 分组，

$$1+\frac{1}{2}+(\frac{1}{3}+\frac{1}{4})+(\frac{1}{5}+\cdots +\frac{1}{8})+\cdots$$

第 $k$ 组有 $2^{k-1}$ 项，每项不小于该组最后一项 $\frac{1}{2^k}$，因此每组的和不小于 $\frac{1}{2}$，部分和无界。

积分比较：由 $\frac{1}{k}\ge {\int }_k^{k+1}\frac{dx}{x}$ 累加得 $H_n\ge \ln (n+1)$，无界。

几何级数

$\sum _{n=0}^{\mathrm{\infty }}{q}^n$ 是最容易处理也最常用的级数。部分和有闭式：$S_N=\frac{1-q^{N+1}}{1-q}$（$q\ne 1$）。因此 $|q|<1$ 时收敛，和为 $\frac{1}{1-q}$；$|q|\ge 1$ 时发散。几何级数的尾巴有直接的界：$\sum _{n=N+1}^{\mathrm{\infty }}{q}^n=\frac{q^{N+1}}{1-q}$，把误差与截断位置的关系写得非常清楚。这一尾巴界在数值计算中用来估计截断误差，例如用级数计算 $e^x$ 时判断需要多少项。

5.2.3 正项级数的判别法

正项级数（$a_n\ge 0$）的部分和单调递增，因此收敛与有界等价（单调有界定理），所有的判别法都围绕「部分和是否有界」展开。

比较判别法：若 $0\le a_n\le b_n$ 且 $\sum b_n$ 收敛，则 $\sum a_n$ 收敛；若 $a_n\ge b_n\ge 0$ 且 $\sum b_n$ 发散，则 $\sum a_n$ 发散。使用的关键是找比较对象，常用对象是几何级数 $\sum q^n$ 与 $p$ 级数 $\sum 1/n^p$。

极限比较判别法：若 $a_n,b_n>0$ 且 $a_n/b_n\to c$（$0<c<\mathrm{\infty }$），则两个级数同时收敛或同时发散。这一形式省去了找不等式的功夫，只需计算比值的极限。

比值判别法：若 $lim{a}_{n+1}/a_n=r$，则 $r<1$ 时收敛、$r>1$ 时发散、$r=1$ 时无法判断。

根值判别法：若 $lim{a}_n^{1/n}=r$，结论与比值判别相同。

积分判别法：若 $f$ 在 $[1,\mathrm{\infty })$ 上非负单调递减且 $f(n)=a_n$，则 $\sum a_n$ 与 ${\int }_1^{\mathrm{\infty }}f(x)dx$ 同时收敛或同时发散。用它判断 $p$ 级数：${\int }_1^{\mathrm{\infty }}{x}^{-p}dx$ 在 $p>1$ 时收敛、$p\le 1$ 时发散，因此 $\sum 1/n^p$ 的收敛性由 $p>1$ 决定。

Cauchy 凝聚判别法：$\sum a_n$（$a_n$ 单调递减非负）与 $\sum 2^k{a}_{2^k}$ 同时收敛或同时发散。它把任意正项级数化成几何型的问题，可以证明 $p$ 级数的临界指数为 $1$，也可以处理 $\sum 1/(n\ln n)$ 这类没有简单比较对象的级数。

比值与根值判别的局限

这两种判别法依赖通项本身按几何速率衰减，对幂次或对数衰减的级数无效。$p$ 级数的数据可以说明这一点：在 $n={10}^6$ 处，$\sum 1/n$ 的比值是 $0.999999$，$\sum 1/n^{1.5}$ 是 $0.9999985$，$\sum 1/n^2$ 是 $0.999998$，三者都趋于 $1$，判别法给出的结论都是「无法判断」。判别法的输出是极限值，它只能看见几何衰减（极限小于 $1$）与增长（极限大于 $1$）两种情形，幂次衰减落在边界上。处理这类级数需要比较判别、积分判别或凝聚判别。

5.2.4 一般项级数与条件收敛

交错级数与 Leibniz 判别

Leibniz 判别：若 $a_n$ 单调递减趋于零，则交错级数 $\sum (-1{)}^{n+1}{a}_n$ 收敛，且余项满足

$$|S_N-S|\le a_{N+1}$$

即用前 $N$ 项近似和的误差不超过下一项的大小。这条余项界是交错级数在数值计算中受欢迎的原因：误差有显式且容易计算的上界，截断位置可以事先确定。

Abel 与 Dirichlet 判别

两者处理「通项不是单调递减」的交错型级数。

Dirichlet 判别：若部分和 $A_n=\sum _{k=1}^n{a}_k$ 有界，且 $\{b_n\}$ 单调趋于零，则 $\sum a_n{b}_n$ 收敛。

Abel 判别：若 $\sum a_n$ 收敛，且 $\{b_n\}$ 单调有界，则 $\sum a_n{b}_n$ 收敛。

这两条判别法的证明思路相同（分部求和，即 Abel 变换），可以理解为离散版的「分部积分」。

绝对收敛与条件收敛

若 $\sum |a_n|$ 收敛，称 $\sum a_n$ 绝对收敛；若 $\sum a_n$ 收敛而 $\sum |a_n|$ 发散，称条件收敛。绝对收敛的级数本身必收敛（由 Cauchy 准则与三角不等式），且有三条便利的性质：可以任意改变求和顺序（重排不变和）、可以逐项相乘（Cauchy 乘积收敛到两个和的乘积）、可以作为比较对象去判断其他级数。

条件收敛的级数失去所有这些性质，其中最强的一条结论是 Riemann 重排定理：条件收敛的级数经过重排可以收敛到任意给定的实数，也可以发散到 $\pm \mathrm{\infty }$。证明思路是条件收敛蕴含正项部分与负项部分都发散到无穷（否则级数会绝对收敛），因此可以先把正项加到超过目标值，再把负项加到低于目标值，交替进行，部分和被夹在越来越小的区间里收敛到目标值。

重排定理的数值形态

本节实验四把交错调和级数重排到 $1.5$：按「先用正项把部分和推到 $1.5$ 以上，再用负项压回 $1.5$ 以下」的规则取项，$1000$ 项时部分和为 $1.4942$，$200000$ 项时为 $1.49995$，向 $1.5$ 收敛。原来的顺序给出 $\ln 2\approx 0.6931$。同一组数的不同排列收敛到不同的值，这一事实在数值求和中的含义是：浮点求和的累加顺序不影响结果的前提是级数绝对收敛，对条件收敛的级数，顺序改变可以直接改变结果。

5.2.5 收敛速度与数值求和

误差估计

三种常用级数的截断误差有现成的估计。

几何级数：$\left|\sum _{n=N+1}^{\mathrm{\infty }}{q}^n\right|=\frac{|q{|}^{N+1}}{1-|q|}$。误差按 $|q{|}^N$ 缩小，要对精度 ${10}^{-12}$ 而 $q=0.5$ 时需要 $N\approx 40$ 项。

交错级数（Leibniz 型）：误差不超过下一项的绝对值 $a_{N+1}$。交错调和级数用 $1000$ 项近似 $\ln 2$，误差约 $5\times {10}^{-4}$，Leibniz 界给出 $1/1001\approx {10}^{-3}$，实际误差约为界的一半。

$p$ 级数：由积分比较，$\sum _{n>N}{n}^{-p}\le {\int }_N^{\mathrm{\infty }}{x}^{-p}dx=\frac{N^{1-p}}{p-1}$（$p>1$）。误差按 $N^{1-p}$ 缩小，比几何级数慢得多：$p=2$ 时要把误差降到 ${10}^{-12}$ 需要 $N\approx {10}^{12}$ 项。幂次级数的收敛速度是数值计算中的一个实际问题。

收敛加速

部分和的收敛速度可以用序列变换改善。Aitken ${\mathrm{\Delta }}^2$ 方法利用相邻三个部分和做一次外推：

$$\hat{S}=S_n-\frac{(S_{n+1}-S_n{)}^2}{S_{n+2}-2S_{n+1}+S_n}$$

它的原理适用于误差按几何规律衰减的情形：若 $S_n=S+c{q}^n$，则 $\hat{S}$ 精确等于 $S$。交错调和级数的误差恰好近似按 $1/n$ 与交替符号衰减，Aitken 外推把误差压低很多：本节实验二的输出显示，用 $n=998,999,1000$ 三个部分和外推，误差从 $5.0\times {10}^{-4}$ 降到 $1.3\times {10}^{-10}$，改善了约 $4\times {10}^6$ 倍。

Euler 变换处理交错级数：把它改写成对相邻项之差的级数，新级数的项衰减更快。Shanks 变换是 Aitken 方法的多项推广，Wynn 的 ε 算法用递推实现它。这些方法在特殊函数求值、常数计算与数值积分中有标准实现。

浮点求和的误差

浮点加法的每一次运算都可能引入舍入误差，误差量级是当前结果的 $2.22\times {10}^{-16}$（双精度）。累加 $N$ 项时误差大致按 $\sqrt{N}$ 到 $N$ 的量级累积，与被加项的分布有关。四条实践规则。

升序与降序的差别：把绝对值小的项放在前面累加更准。本节实验三的数据：调和级数的 ${10}^6$ 项，升序朴素求和的绝对误差是 $7.4\times {10}^{-13}$，降序是 $4.8\times {10}^{-14}$，差了一个数量级。原因是大数先出现时，后面的小数会被部分舍去。

补偿求和：Kahan 求和法维护一个补偿量记录每次加法的舍入损失，在下一次加法中补回。实验三中它给出的结果与精确值完全一致（误差为零）。

成对求和：NumPy 的 np.sum 使用成对（分块）求和的策略，误差约为 $1.8\times {10}^{-15}$，接近机器精度，且速度比逐项循环快。多数场合直接用库函数即可。

灾难性抵消：两个接近的大数相减会失去有效数字。实验三中的例子 $\sum _{k=1}^n(\frac{1}{k}-\frac{1}{k+1})$ 每一项都是两个接近的数相减，朴素求和的结果与 telescoping 公式 $1-\frac{1}{n+1}$ 相差 $4.7\times {10}^{-14}$；若把每一项改写为 $\frac{1}{k(k+1)}$ 再求和，抵消消除，误差随之消失。这条规则的实用形式是：能用代数化简消除相减就化简，需要保留小量时改用展开式。

5.2.6 数值实验

实验一：判别法的边界

正项级数的四个例子，观察比值与根值判别在幂次级数上的失效。

import math

print("p 级数 sum 1/n^p 的比值与根值在 n = 10^6 处：")
for p in [1.0, 1.5, 2.0]:
    ratio = (10**6 / (10**6 + 1)) ** p
    root = (1.0 / 10**6) ** (p / 10**6)
    print(f"  p = {p}: a_{{n+1}}/a_n = {ratio:.10f}, (a_n)^(1/n) = {root:.10f}")

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

print("部分和（n = 10^6）：")
print(f"  sum 1/n    = {psum(1.0, 10**6):.6f}（发散，仍在增长）")
print(f"  sum 1/n^1.5 = {psum(1.5, 10**6):.6f}（收敛到 zeta(1.5) = 2.612375）")
print(f"  sum 1/n^2  = {psum(2.0, 10**6):.10f}（收敛到 pi^2/6 = 1.6449340668）")

s = 0.0
term = 1.0
for k in range(1, 60):
    term *= 2.0 / k
    s += term
print(f"sum 2^n/n! (n >= 1) = {s:.10f}（收敛到 e^2 - 1 = {math.exp(2) - 1:.10f}）")

输出：

p 级数 sum 1/n^p 的比值与根值在 n = 10^6 处：
  p = 1.0: a_{n+1}/a_n = 0.9999990000, (a_n)^(1/n) = 0.9999861846
  p = 1.5: a_{n+1}/a_n = 0.9999985000, (a_n)^(1/n) = 0.9999792769
  p = 2.0: a_{n+1}/a_n = 0.9999980000, (a_n)^(1/n) = 0.9999723694
部分和（n = 10^6）：
  sum 1/n    = 14.392727（发散，仍在增长）
  sum 1/n^1.5 = 2.610375（收敛到 zeta(1.5) = 2.612375）
  sum 1/n^2  = 1.6449330668（收敛到 pi^2/6 = 1.6449340668）
sum 2^n/n! (n >= 1) = 6.3890560989（收敛到 e^2 - 1 = 6.3890560989）

三个 $p$ 级数的比值都落在 $0.999998$ 到 $0.999999$ 之间，与 $1$ 的差是 ${10}^{-6}$ 量级，两个判别法都无法给出结论；根值同样趋于 $1$。部分和给出了判决：$p=1$ 时 $14.39$ 且仍在增长，$p=1.5$ 与 $p=2$ 分别收敛到 $2.610$ 与 $1.644933$，其中 $p=2$ 的部分和与 ${\pi }^2/6$ 的差为 $1.0\times {10}^{-6}$，与尾部积分估计 ${\int }_N^{\mathrm{\infty }}{x}^{-2}dx=1/N={10}^{-6}$ 一致（$p=1.5$ 的差为 $2.0\times {10}^{-3}$，同样与该量级的尾部估计相符）。

第四个例子说明比值判别有效的场景：$\sum 2^n/n!$ 的相邻项比值是 $\frac{2}{n+1}$，在 $n=10$ 时已经降到 $0.18$，衰减按几何速率加阶乘速率叠加，$60$ 项就把和算到 ${10}^{-10}$ 精度，结果与解析值 $e^2-1$ 逐位相符。

实验二：交错级数与收敛加速

用交错调和级数（和等于 $\ln 2$）观察 Leibniz 界与 Aitken 加速的效果。

import math

def alt_partials(n):
    s = 0.0
    hist = []
    for k in range(1, n + 1):
        s += (-1.0) ** (k + 1) / k
        hist.append(s)
    return hist

target = math.log(2)
hist = alt_partials(1000)
for n in [10, 100, 1000]:
    print(f"  n = {n:>4}: s_n = {hist[n-1]:.12f}, 误差 = {abs(hist[n-1] - target):.3e}, "
          f"Leibniz 界 = {1.0/(n+1):.3e}")

s0, s1, s2 = hist[-3], hist[-2], hist[-1]
d1, d2 = s1 - s0, s2 - s1
aitken = s0 - d1 * d1 / (d2 - d1)
print(f"  Aitken 加速（基于 n = 998, 999, 1000）: {aitken:.12f}, 误差 = {abs(aitken - target):.3e}")
print(f"  加速后误差缩小 {abs(hist[-1] - target)/abs(aitken - target):.0f} 倍")

输出：

  n =   10: s_n = 0.645634920635, 误差 = 4.751e-02, Leibniz 界 = 9.091e-02
  n =  100: s_n = 0.688172179310, 误差 = 4.975e-03, Leibniz 界 = 9.901e-03
  n = 1000: s_n = 0.692647430560, 误差 = 4.998e-04, Leibniz 界 = 9.990e-04
  Aitken 加速（基于 n = 998, 999, 1000）: 0.693147180435, 误差 = 1.252e-10
  加速后误差缩小 3992075 倍

直接求和时，误差严格按 $1/(2n)$ 量级下降（实际误差约等于 Leibniz 界的一半，这是交错级数的一般现象：误差落在 $a_{N+1}/2$ 附近），要把误差降到 ${10}^{-10}$ 需要约 ${10}^{10}$ 项，不可行。Aitken 外推只用三个相邻的部分和就把误差压到 $1.3\times {10}^{-10}$，相当于直接求和 ${10}^9$ 项的效果。

外推的收益随截断位置的推移而增大（练习题 3 给出数据）：用 $n=9,10,11$ 外推，误差 $1.1\times {10}^{-4}$（比同位置直接求和改善约 $400$ 倍）；用 $n=99,100,101$，误差 $1.2\times {10}^{-7}$（改善约 $4\times {10}^4$ 倍）；用 $n=997,998,999$，误差 $1.3\times {10}^{-10}$。每把截断位置推后 $100$ 倍，加速的改善倍数也提高约 $100$ 倍，总的效果是把 $1/n$ 的误差变成了 $1/n^2$ 或更好的量级。

实验三：浮点求和

同一个和用四种方法累加，比较误差。

import math
import numpy as np

n = 10**6
vals = [1.0 / k for k in range(1, n + 1)]
exact = math.fsum(vals)
s_up = 0.0
for v in vals:
    s_up += v
s_down = 0.0
for v in reversed(vals):
    s_down += v
s_kahan = 0.0
c = 0.0
for v in vals:
    y = v - c
    t = s_kahan + y
    c = (t - s_kahan) - y
    s_kahan = t
s_pair = float(np.sum(np.array(vals)))
print(f"调和级数前 10^6 项（精确值 math.fsum = {exact:.10f}）：")
print(f"  升序朴素求和: {s_up:.10f}, 误差 = {abs(s_up - exact):.3e}")
print(f"  降序朴素求和: {s_down:.10f}, 误差 = {abs(s_down - exact):.3e}")
print(f"  Kahan 补偿求和: {s_kahan:.10f}, 误差 = {abs(s_kahan - exact):.3e}")
print(f"  NumPy 成对求和: {s_pair:.10f}, 误差 = {abs(s_pair - exact):.3e}")

s_cancel = 0.0
for k in range(1, n + 1):
    s_cancel += 1.0 / k - 1.0 / (k + 1)
formula = 1.0 - 1.0 / (n + 1)
print(f"sum (1/k - 1/(k+1)) 的朴素求和 = {s_cancel:.12f}，"
      f"telescoping 精确结果 = {formula:.12f}，差 = {abs(s_cancel - formula):.3e}")

输出：

调和级数前 10^6 项（精确值 math.fsum = 14.3927267229）：
  升序朴素求和: 14.3927267229, 误差 = 7.354e-13
  降序朴素求和: 14.3927267229, 误差 = 4.796e-14
  Kahan 补偿求和: 14.3927267229, 误差 = 0.000e+00
  NumPy 成对求和: 14.3927267229, 误差 = 1.776e-15
sum (1/k - 1/(k+1)) 的朴素求和 = 0.999999000001，telescoping 精确结果 = 0.999999000001，差 = 4.696e-14

四种方法的精度排序与理论预期一致。升序朴素求和把大项先加上去，之后的小项在与大数相加时被舍去一部分，误差 $7.4\times {10}^{-13}$；降序把小数先累加，误差降低到 $4.8\times {10}^{-14}$；Kahan 补偿把每次加法的舍入损失记录下来并在后续补回，误差为零；NumPy 的成对求和在分块内部与块之间都做局部累加，误差 $1.8\times {10}^{-15}$，接近单次舍入的水平。

误差还随项数增长。同样的升序朴素求和，$n={10}^3$ 时相对误差 $2.4\times {10}^{-16}$（恰好等于一次舍入），$n={10}^6$ 时 $5.1\times {10}^{-14}$，$n={10}^7$ 时 $1.5\times {10}^{-13}$，近似按 $n$ 的平方根到一倍的量级累积（练习题 3 给出数据）。

最后一个例子是灾难性抵消：$\frac{1}{k}-\frac{1}{k+1}$ 的两个操作数接近，差值的有效数字少于操作数本身，${10}^6$ 项累加后误差 $4.7\times {10}^{-14}$。把每一项代数化简为 $\frac{1}{k(k+1)}$ 之后，没有相减发生，误差回到机器精度水平。

实验四：重排改变级数的和

交错调和级数是条件收敛的典型例子，按「先用正项超过目标、再用负项压回目标以下」的规则重排，观察部分和的轨迹。

import math

target_sum = 1.5
s = 0.0
pos = 1      # 下一个正项的分母（奇数）
neg = 1      # 下一个负项的分母（偶数）
for step in range(200000):
    if s <= target_sum:
        s += 1.0 / pos
        pos += 2
    else:
        s -= 1.0 / neg
        neg += 2
    if step in (0, 20, 100, 1000, 10000, 100000, 199999):
        print(f"  前 {step + 1:>6} 项: 部分和 = {s:.6f}（已用正项 {pos // 2 + 1} 个，"
              f"负项 {neg // 2} 个）")
print(f"  原顺序（交错级数）的极限 = ln 2 = {math.log(2):.6f}")

输出：

  前      1 项: 部分和 = 1.000000（已用正项 2 个，负项 0 个）
  前     21 项: 部分和 = 1.479673（已用正项 21 个，负项 1 个）
  前    101 项: 部分和 = 1.476630（已用正项 97 个，负项 5 个）
  前   1001 项: 部分和 = 1.494198（已用正项 954 个，负项 48 个）
  前  10001 项: 部分和 = 1.499233（已用正项 9527 个，负项 475 个）
  前 100001 项: 部分和 = 1.499960（已用正项 95259 个，负项 4743 个）
  前 200000 项: 部分和 = 1.499954（已用正项 190515 个，负项 9486 个）
  原顺序（交错级数）的极限 = ln 2 = 0.693147

重排后的部分和在 $1.5$ 附近波动并收敛，${10}^5$ 项时已经是 $1.49996$，与原顺序的极限 $0.69315$ 相差一倍多。数据还显示了操作的代价：正项被大量消耗（$190515$ 个）而负项只用掉很少（$9486$ 个），这是因为正项衰减慢（$1/1,1/3,1/5,\dots$），需要很多项才能把部分和推高一次。若把目标改成 $2.0$，同样的构造仍然收敛到 $2.0$，只是消耗的正项更多（练习题 3 给出数据）。

这个实验是 Riemann 重排定理的直观形态：条件收敛的级数不带任何「顺序依赖」的和，任意指定的目标值都可以通过重排达到。绝对收敛的级数没有这个性质，重排不改变它的和。

5.2.7 本节小结

级数的判敛与求和

本节把无穷求和化为部分和的极限。判敛工具按适用对象分成两组：正项级数用比较、极限比较、比值、根值、积分判别与 Cauchy 凝聚判别，一般项级数用 Leibniz、Abel、Dirichlet 判别。比值与根值判别只对几何型衰减有效，在 $p$ 级数上失效（$n={10}^6$ 时三个 $p$ 值的比值都在 $0.999998$ 到 $0.999999$ 之间），$p$ 级数的临界指数 $1$ 需要积分判别或凝聚判别确定。条件收敛带来两个重要现象：交错级数的余项有显式界（不超过下一项，实测误差约为界的一半），条件收敛的级数重排后可以收敛到任意值（重排到 $1.5$ 的实验在 ${10}^5$ 项时达到 $1.49996$，原顺序为 $\ln 2=0.69315$）。数值求和部分处理收敛速度与舍入误差两个问题：几何级数与交错级数收敛快，$p$ 级数慢（$p=2$ 时误差按 $1/N$ 下降），Aitken 外推用三个部分和把交错调和级数的误差从 $5.0\times {10}^{-4}$ 压到 $1.3\times {10}^{-10}$（改善 $4\times {10}^6$ 倍）；浮点求和方面，升序朴素求和的误差 $7.4\times {10}^{-13}$，降序 $4.8\times {10}^{-14}$，Kahan 补偿为零误差，NumPy 成对求和 $1.8\times {10}^{-15}$，而接近数相减造成的灾难性抵消需要靠代数化简消除。

级数处理的是「无穷多个数相加」。下一节把极限用到函数上：函数在某点的极限、连续性的定义与性质，以及连续函数在闭区间上的三条基本定理。那里出现的 ε-δ 语言与本节定义级数收敛时使用的 ε-N 语言结构相同，区别只在于控制的变量从下标换成了点的距离。

练习题

第 1 题 概念推导

(a) 用 Stolz 定理求 $\underset{n\to \mathrm{\infty }}{lim}{\displaystyle \frac{H_n}{\ln n}}$，说明每一步的依据。(b) 用有界数列的上下极限证明：有界数列必存在收敛子列，且存在子列收敛到上极限。(c) 说明为什么比值判别法对 $p$ 级数失效，并给出一条在 $p$ 级数上有效的判别思路。

参考答案

(a) 取 $a_n=H_n$、$b_n=\ln n$。验证 Stolz 定理的条件：$\{b_n\}$ 严格递增（对数函数单调增）且 $b_n\to \mathrm{\infty }$。计算比值的极限

$$\frac{a_{n+1}-a_n}{b_{n+1}-b_n}=\frac{1/(n+1)}{\ln \left(\frac{n+1}{n}\right)}=\frac{1/(n+1)}{\ln (1+1/n)}$$

令 $x=1/n$，分母为 $\ln (1+x)=x-x^2/2+O(x^3)$，分子为 $\frac{1/n}{1+1/n}=x(1-x+O(x^2))$，比值为

$$\frac{x(1-x+O(x^2))}{x-x^2/2+O(x^3)}\to 1$$

因此 $H_n/\ln n\to 1$。数值核对：$n={10}^3$ 时比值 $1.0836$，$n={10}^6$ 时 $1.0418$，按 $1/\ln n$ 缓慢靠近 $1$。

(b) 设 $\{a_n\}$ 有界，记 $L=\bar{\lim }{a}_n=\underset{n}{lim}\underset{k\ge n}{sup}{a}_k$。对每个 $n$，由上确界的定义存在 $k_n\ge n$ 使 $a_{k_n}>\underset{k\ge n}{sup}{a}_k-1/n$。取子列时注意下标要递增：先取 $k_1$，再在 $n>k_1$ 的范围内取 $k_2$（这样的 $k_2$ 存在，因为上面构造的 $k_n$ 可以任意大），依次进行得到严格递增的子列下标 $k_1<k_2<\cdots$。于是

$$\underset{k\ge k_j}{sup}{a}_k-\frac{1}{k_j}<a_{k_j}\le \underset{k\ge k_j}{sup}{a}_k$$

两端都趋于 $L$（左端由 $sup$ 的收敛性与 $1/k_j\to 0$ 得到），由夹逼得 $a_{k_j}\to L$。取 $L$ 为任意上极限值即可；这条结论是 Bolzano-Weierstrass 定理的一个加强版本（后者只保证存在收敛子列，不指明极限值）。

(c) 对 $p$ 级数，比值 $a_{n+1}/a_n={\left(\frac{n}{n+1}\right)}^p\to 1$，根值 $a_n^{1/n}=n^{-p/n}=e^{-p\ln n/n}\to 1$，无论 $p$ 取何值都落在判别法的失效区间 $r=1$。原因是这两种判别法的判据基于「通项按几何速率 $r^n$ 衰减」，而幂次衰减 $n^{-p}$ 落在几何衰减的边界上：对任意 $r>1$ 它最终比 $r^{-n}$ 慢，对任意 $r<1$ 它最终比 $r^{-n}$ 快，判别法无法区分。有效的思路是积分判别（把和与 ${\int }_N^{\mathrm{\infty }}{x}^{-p}dx$ 比较，得到临界指数 $p=1$）或比较判别（与已知收敛的级数比较，例如 $\sum 2^{-n}$ 或 $\sum n^{-q}$（$q>1$））。

第 2 题 计算推理

判断下列级数的收敛性并说明理由：(a) $\sum _{n=2}^{\mathrm{\infty }}{\displaystyle \frac{1}{n\ln n}}$；(b) $\sum _{n=1}^{\mathrm{\infty }}{\displaystyle \frac{n!}{n^n}}$；(c) $\sum _{n=1}^{\mathrm{\infty }}{\displaystyle \frac{2^n}{n!}}$；(d) $\sum _{n=1}^{\mathrm{\infty }}{\displaystyle \frac{(-1{)}^n}{\sqrt{n}}}$。再估计 (d) 用前 $100$ 项近似时的误差，并与实测值比较。

参考答案

(a) 发散。用 Cauchy 凝聚判别：$a_n=\frac{1}{n\ln n}$ 单调递减非负，凝聚级数为

$$\sum _k{2}^k{a}_{2^k}=\sum _k{2}^k\cdot \frac{1}{2^k\ln 2^k}=\frac{1}{\ln 2}\sum _k\frac{1}{k}$$

调和级数发散，因此原级数发散。也可以用积分判别：${\int }_2^{\mathrm{\infty }}\frac{dx}{x\ln x}=\ln \ln x{|}_2^{\mathrm{\infty }}=\mathrm{\infty }$。这条结论给出了 $p$ 级数临界指数的加强版：$\sum \frac{1}{n(\ln n{)}^q}$ 在 $q>1$ 时收敛、$q\le 1$ 时发散。

(b) 收敛。用比值判别：$\frac{a_{n+1}}{a_n}=\frac{(n+1)!/(n+1{)}^{n+1}}{n!/n^n}=\frac{n^n}{(n+1{)}^n}={\left(\frac{n}{n+1}\right)}^n\to \frac{1}{e}\approx 0.368<1$，级数收敛。

(c) 收敛，且收敛很快。比值判别给出 $\frac{a_{n+1}}{a_n}=\frac{2}{n+1}\to 0$，几何加阶乘的衰减使 $60$ 项就达到 ${10}^{-10}$ 精度（本节实验一的数据：和 $6.3890560989$ 与 $e^2-1$ 逐位相符）。

(d) 条件收敛。$\frac{1}{\sqrt{n}}$ 单调递减趋于零，由 Leibniz 判别收敛；但 $\sum \frac{1}{\sqrt{n}}$ 是 $p=0.5<1$ 的 $p$ 级数，发散，所以是条件收敛，不是绝对收敛。

误差估计：Leibniz 判别给出余项不超过下一项，$|S_{100}-S|\le \frac{1}{\sqrt{101}}\approx 0.0995$。实测误差约为该界的一半（交错级数的一般现象，误差落在 $a_{N+1}/2$ 附近）：本节实验二中交错调和级数在 $n=100$ 处实测误差 $4.975\times {10}^{-3}$，界为 $9.901\times {10}^{-3}$，比值 $0.502$。对 (d) 同样有实测误差约 $0.05$。这条估计的实用含义是：条件收敛的级数用部分和求值的代价很高（误差按 $1/\sqrt{N}$ 下降，要到 ${10}^{-6}$ 需要 ${10}^{12}$ 项），实际计算应当改用加速方法或把这些级数的和化为已知常数。

第 3 题 代码验证

用本节代码做三组实验并解释：(a) 把 Aitken 外推的起点从 $n=998,999,1000$ 改为 $9,10,11$ 与 $99,100,101$，比较加速效果；(b) 观察升序朴素求和的相对误差随项数 $n$ 的变化规律；(c) 把实验四的重排目标从 $1.5$ 改为 $2.0$，说明结果与正负项消耗的变化。

参考答案

(a) 三组起点对应的误差（对照同位置直接求和的误差）：

Aitken 用 n = (9, 10, 11): 结果 = 0.693253968254, 误差 = 1.068e-04, 同位置直接误差 = 4.340e-02
Aitken 用 n = (99, 100, 101): 结果 = 0.693147303688, 误差 = 1.231e-07, 同位置直接误差 = 4.926e-03
Aitken 用 n = (997, 998, 999): 结果 = 0.693147180686, 误差 = 1.256e-10, 同位置直接误差 = 5.002e-04

三组的改善倍数约为 $4\times {10}^2$、$4\times {10}^4$、$4\times {10}^6$，与截断位置的推移同步（截断位置每推后 $100$ 倍，改善倍数提高约 $100$ 倍）。原因在于 Aitken 外推对误差按几何规律衰减的情形有效，而交错调和级数的误差近似按 $1/n$ 与交替符号衰减，外推一次把一阶误差项消去，剩余误差降到二阶；截断位置推后时一阶项本身变小，二阶项变小得更快。

(b) 升序朴素求和的相对误差数据：

n =      1000: 升序误差 = 1.776e-15, 相对误差 = 2.373e-16
n =     10000: 升序误差 = 3.375e-14, 相对误差 = 3.448e-15
n =    100000: 升序误差 = 9.237e-14, 相对误差 = 7.640e-15
n =   1000000: 升序误差 = 7.354e-13, 相对误差 = 5.110e-14
n =  10000000: 升序误差 = 2.579e-12, 相对误差 = 1.545e-13

相对误差从 $2.4\times {10}^{-16}$ 增到 $1.5\times {10}^{-13}$，随项数大致按 $\sqrt{n}$ 到 $n$ 的量级增长（$n$ 增大 ${10}^4$ 倍，误差增大三个数量级左右）。增长的机制是每次加法都可能引入半机器精度的舍入，而被加的项越来越小，逐渐低于当前部分和所能分辨的最小间隔。结论是朴素求和的精度随项数退化，长求和应当使用补偿求和或分块求和。

(c) 把目标改为 $2.0$ 后：

重排目标 2.0: 前 400000 项部分和 = 1.999963, 用正项 392806 个, 负项 7195 个

部分和仍然收敛，这次到 $2.0$（$400000$ 项时为 $1.999963$）。与目标 $1.5$ 的情形相比，正项消耗更多（从 $381030$ 增到 $392806$ 个），负项消耗更少（从 $18971$ 减到 $7195$ 个）。原因是目标越高，需要把部分和推得越高，使用的正项越多；而把部分和压回来的任务更轻（只需少量负项即可压过 $2.0$ 以下）。这组数据印证了重排定理证明中的操作：由于正项部分与负项部分都发散，无论目标定在哪里都可以通过调整两类项的取用比例达到，目标的大小只影响两类项的消耗比例。

第 4 题 综合应用

某程序需要计算一个条件收敛的交错级数到相对精度 ${10}^{-12}$，级数通项按 $1/n$ 衰减，无法用解析式求值。请给出一个可行的计算方案：截断准则的选择、加速方法的使用方式、浮点求和的实现细节、如何验证结果的可信度；并说明若不使用加速方法，需要多少项才能达到同样的精度。

参考答案

截断与加速：通项按 $1/n$ 衰减，Leibniz 界给出误差不超过 $a_{N+1}\approx 1/N$，直接截断要达到 ${10}^{-12}$ 需要 $N\approx {10}^{12}$ 项，不可行。改用加速：先算到 $N={10}^4$ 左右（代价可接受），再用这些部分和做外推。做法是保留最后若干个部分和（例如最近 $10$ 个），对相邻三元组分别做 Aitken 外推，再对结果做一次 Aitken 外推（两级加速，等价于 Shanks 变换的 $e_2$ 或 $e_3$ 阶形式）。本节实验二显示，单级 Aitken 用 $n\approx {10}^3$ 已经把误差压到 $1.3\times {10}^{-10}$，两级加速可以在同样项数下再压低几个数量级，达到 ${10}^{-12}$ 的目标。

浮点实现：累加时用 Kahan 补偿求和或分块求和（若语言提供 fsum 之类的正确舍入求和则直接用），避免朴素逐项升序累加；外推公式中出现相邻部分和之差，这些差本身很小，要留意灾难性抵消：把三个部分和存为双精度并做差时有效数字损失约 $10$ 位，因此部分和本身的精度必须高于目标精度（相对精度 ${10}^{-16}$ 的部分和相减得到的差仍有约 ${10}^{-6}$ 的相对精度，对 ${10}^{-12}$ 的目标足够）。如果目标精度继续提高（例如 ${10}^{-15}$），需要改用双精度加倍或任意精度算术。

可信度验证：三条独立证据。第一，外推结果在不同截断位置应当一致：分别在 $N={10}^3,{10}^4,{10}^5$ 处做外推，比较三个结果，差值应当落在目标精度附近；第二，用交替顺序的项做同样的计算（改变正负项的处理顺序），结果不应变化；第三，如果级数对应于已知常数（如 $\ln 2$、$\pi /4$），用已知值核对，核对通过后再应用到未知情形。第二项在本节实验四的意义下尤为重要：条件收敛级数的部分和依赖顺序，因此求和过程的顺序必须固定，且要在文档中写明。

代价对比：不用加速时需要约 ${10}^{12}$ 项，每项计算一次通项（约 $10$ 次浮点运算），总运算量 ${10}^{13}$ 量级，在单机上需要数小时到数天；用加速后约 ${10}^4$ 项，运算量 ${10}^5$ 量级，耗时在毫秒量级。两者的差别就是本节反复出现的主题：级数的收敛速度决定了数值计算的可行性，而对收敛速度的分析依赖本节前半部分的判敛工具与误差估计。

常见错误

错误 1 · 用通项趋于零判断级数收敛

原因：$a_n\to 0$ 只是必要条件，不是充分条件。调和级数是最常见的反例：$\frac{1}{n}\to 0$ 而部分和无界（本节实验一的数据：${10}^6$ 项时部分和已经到 $14.39$ 且仍在增长）。这条混淆在实现中的后果是：程序按通项小于阈值就停止求和，对发散的级数会返回一个远小于真值（或不存在）的结果。

解决：判断收敛用判别法（比较、比值、根值、积分、凝聚判别），通项趋于零只用来快速排除明显发散的级数。实现中把停止条件写成余项估计而不是通项阈值：几何级数用 $\frac{q^{N+1}}{1-q}$，交错级数用 $a_{N+1}$，$p$ 级数用 $\frac{N^{1-p}}{p-1}$，这些界直接给出误差与截断位置的对应关系。

错误 2 · 在条件收敛的级数上随意改变求和顺序

原因：绝对收敛的级数可以任意重排，条件收敛的级数重排后可以收敛到任意值（Riemann 重排定理，本节实验四把交错调和级数重排到 $1.5$，原顺序为 $0.6931$）。数值实现的后果更隐蔽：并行求和、分块求和、向量化求和都会改变累加顺序，对条件收敛的级数可能产生与单线程不同的结果，误差量级可能远大于机器精度。

解决：先判定级数是绝对收敛还是条件收敛（检查 $\sum |a_n|$）。绝对收敛时顺序无关，可以放心用并行与分块求和；条件收敛时必须固定顺序，把求和过程写成显式的顺序循环并在文档中说明，或者先把级数变形为绝对收敛的形式（常见做法是合并相邻项、提出符号因子、化为积分表示）。

错误 3 · 用比值或根值判别处理幂次级数时得出错误结论

原因：这两种判别法在 $p$ 级数上给出的极限都是 $1$，落在失效区间。把「极限等于 $1$」误读为「收敛」或「发散」会得到相反结论：$\sum 1/n$ 发散、$\sum 1/n^2$ 收敛，两者的比值极限都是 $1$。类似地，把 $r<1$ 的判据套用到非几何型衰减的级数上（如 $\sum \frac{1}{n\ln n}$，比值极限也是 $1$）同样失效。

解决：记住判别法的适用边界（几何型衰减），遇到幂次或对数型通项改用积分判别、凝聚判别或直接比较。实践中的做法是先判断通项属于哪一类衰减（几何、幂次、对数幂次），据此选择判别法；通项里同时出现幂与对数时，用凝聚判别把问题化为纯幂次形式，或与 $\sum \frac{1}{n(\ln n{)}^q}$ 这类已知结论比较。

错误 4 · 直接相减计算接近的数，或用朴素升序累加长序列

原因：两类浮点误差。其一，$\frac{1}{k}-\frac{1}{k+1}$ 这类接近数的差会丢失有效数字（本节实验三的数据：${10}^6$ 项累加后误差 $4.7\times {10}^{-14}$，而代数化简后误差回到机器精度）。其二，朴素升序累加长序列时，小数与大和相加被舍去，相对误差随项数增长（$n={10}^3$ 时 $2.4\times {10}^{-16}$，$n={10}^7$ 时 $1.5\times {10}^{-13}$）。

解决：相减之前先做代数化简（把差值写成乘积或通分形式），或者用展开式处理小量（$\ln (1+x)$、$e^x-1$、$\sqrt{1+x}-1$ 都有专门的稳定算法）。累加时用正确舍入的求和函数（math.fsum）、补偿求和（Kahan）或分块求和，避免逐项升序累加；把绝对值小的项放在前面也能改善精度（实验三中降序求和的误差比升序低一个数量级）。