留痕数值分析

CHAPTER 01

第一章 · 误差

数值分析的第一个问题不是「怎么算」,而是「算出来的结果还能信几位」。这一章所有公式都指向同一个判断:误差有多大,结果有几位可靠。

本页目录

1.1 误差从哪来

用计算机解一个数学问题,误差有四个来源。前两个不是这门课能处理的,后两个才是。

来源 典型情形 本课程是否研究
模型误差 把真实物理过程简化成微分方程 否
观测误差 测量仪器的读数偏差、参数标定误差 否
截断误差 用有限项级数代替无穷级数、用差商代替导数 是
舍入误差 计算机字长有限,0.10.1 存不进二进制 是

截断误差来自「方法本身做了近似」,加密网格、增加项数可以减小它。舍入误差来自「机器存不下精确值」,运算次数越多、量级差越大,它越容易积累。后面的稳定性讨论,本质上就是在问:舍入误差会不会被算法放大。

考试里常给一个具体做法,让你判断误差属于哪一类。判据是看近似发生在「建模」「测量」还是「计算过程」:把 exe^x 展开成前 nn 项是截断,把 1/31/3 存成 0.3333330.333333 是舍入。

1.2 绝对误差与相对误差

设 xx 是真值,x∗x^* 是近似值。按课件约定,绝对误差定义为近似值减真值:

e∗=x∗−xe^* = x^* - x

e∗e^* 带符号:e∗>0e^*>0 说明近似值偏大。实际判断精度时看它的绝对值 ∣e∗∣\lvert e^*\rvert。由于真值通常不知道,能给出的往往是一个界限 ε∗\varepsilon^*,满足

∣e∗∣=∣x∗−x∣≤ε∗\lvert e^*\rvert = \lvert x^* - x\rvert \le \varepsilon^*

ε∗\varepsilon^* 称为绝对误差限。它把真值框在区间 [x∗−ε∗, x∗+ε∗][x^*-\varepsilon^*,\ x^*+\varepsilon^*] 内。

绝对误差有量纲,不能跨对象比较。称量 11 kg 差 11 g 与称量 11 t 差 11 g,绝对误差相同,精度差三个数量级。所以引入相对误差:

er∗=e∗x=x∗−xx,εr∗=ε∗∣x∗∣e_r^* = \frac{e^*}{x} = \frac{x^*-x}{x},\qquad \varepsilon_r^* = \frac{\varepsilon^*}{\lvert x^*\rvert}

相对误差无量纲,通常写成百分数或 1010 的幂次。分母用真值 xx 是定义,实际计算时真值未知,才用 x∗x^* 代替;当误差相对很小时,这样做足以估计误差。上式的 εr∗\varepsilon_r^* 是按近似值归一化的误差限。若要求相对真值的严格上界,且 ∣x∗∣>ε∗\lvert x^*\rvert>\varepsilon^*,可用 ε∗/(∣x∗∣−ε∗)\varepsilon^*/(\lvert x^*\rvert-\varepsilon^*)。

符号方向容易混:有的教材定义 e=x−x∗e=x-x^*,课件定义 e∗=x∗−xe^*=x^*-x。答题时先写清定义式,再代数字。优先按本课件的约定写,别把定义与代入的符号方向弄反。

例 1-1(补充) 取 π=3.14159265…\pi=3.14159265\ldots,近似值 x∗=3.14x^*=3.14。求绝对误差、绝对误差限、相对误差。

e∗=3.14−3.14159265…=−1.5927×10−3e^* = 3.14 - 3.14159265\ldots = -1.5927\times 10^{-3}

取 ε∗=0.5×10−2\varepsilon^*=0.5\times 10^{-2} 是一个合法但不紧的误差限:3.143.14 是四舍五入到小数点后两位的结果,真正的舍入界是 0.5×10−20.5\times 10^{-2},而实际误差比它小。相对误差

er∗=−1.5927×10−33.14159265…≈−5.07×10−4e_r^* = \frac{-1.5927\times 10^{-3}}{3.14159265\ldots} \approx -5.07\times 10^{-4}

负号表示近似值偏小;精度看 5.07×10−45.07\times 10^{-4},即约 0.05%0.05\%。

「绝对误差限」不是「误差的绝对值」的精确值,而是一个可以保证的上界。题目给「x∗=3.14x^*=3.14 是 π\pi 的四舍五入值」,才能用 0.5×10−20.5\times 10^{-2};只给一个截断到两位小数的数,不能默认它满足四舍五入的界。

1.3 有效数字

有效数字把误差大小翻译成「可信的数字位数」。设

x∗=±0.a1a2⋯an×10m,a1≠0x^* = \pm 0.a_1a_2\cdots a_n\times 10^m,\qquad a_1\neq 0

若

∣x−x∗∣≤0.5×10m−n\lvert x - x^*\rvert \le 0.5\times 10^{m-n}

则称 x∗x^* 有 nn 位有效数字。这里 mm 是最高非零位的位权,a1a_1 是第一位有效数字,nn 是数到的位数(包括末尾的 00)。

判定分三步:

  1. 把 x∗x^* 写成 0.a1a2⋯×10m0.a_1a_2\cdots\times 10^m,确定 mm 和第一位非零数字 a1a_1。
  2. 数出准备声称的位数 nn,算出界限 0.5×10m−n0.5\times 10^{m-n}。
  3. 用真实的 ∣x−x∗∣\lvert x-x^*\rvert 与这个界限比较;成立就至少有 nn 位,不成立就退一位再试。
有效数字从**第一个非零数字**数起,与小数点位置无关。0.023400.02340 有 44 位(2,3,4,02,3,4,0),不是 55 位,也不是 66 位;2.340×10−22.340\times 10^{-2} 同样是 44 位。末尾的 00 算不算,取决于它是否被明确写出。
图 1-1 误差限是否覆盖真值,决定能声称几位有效数字。x∗=3.14x^*=3.14 对 π\pi 的误差 1.59×10−31.59\times 10^{-3} 落在 0.0050.005 内、落在 0.00050.0005 外,所以只有 3 位。

有效数字与按近似值归一化的相对误差限之间有一个常用的上界。

定理 1.1 若 x∗x^* 有 nn 位有效数字,则其相对误差限满足

εr∗≤12a1×101−n\varepsilon_r^* \le \frac{1}{2a_1}\times 10^{1-n}

这个定理只要求知道第一位有效数字 a1a_1 和位数 nn,不必知道真值,所以特别适合反解题:「要保证相对误差不超过某个值,至少需要几位有效数字?」

例 1-2(课件例题) 设 x=20=4.47213595…x=\sqrt{20}=4.47213595\ldots,要求近似值的相对误差不超过 0.5×10−30.5\times 10^{-3},问按定理 1.1 的上界估计,至少应取几位有效数字?

a1=4a_1=4。由定理 1.1,令

12×4×101−n≤0.5×10−3\frac{1}{2\times 4}\times 10^{1-n} \le 0.5\times 10^{-3}

即 101−n≤4×10−310^{1-n}\le 4\times 10^{-3},两边取对数得 1−n≤−2.3981-n\le -2.398,所以 n≥3.398n\ge 3.398。取整数 n=4n=4。

验算:n=4n=4 时界为 1.25×10−4≤5×10−41.25\times 10^{-4}\le 5\times 10^{-4},成立;n=3n=3 时界为 1.25×10−31.25\times 10^{-3},未达标。按定理的上界估计,取 4 位。

按定理反解,得到的是让估计上界达标的最小位数,不是实际所需位数。本题直接用三位近似值 4.474.47 验算,按真值计算的实际相对误差约为 4.78×10−44.78\times10^{-4},也满足容许值。

1.4 误差传播

实际计算是一连串运算,初始数据的误差会被逐步放大或缩小。设 x1,x2x_1,x_2 的绝对误差限为 ε1,ε2\varepsilon_1,\varepsilon_2,下表给出传播误差的估计;其中加减法的绝对误差上界是严格的,乘除法只保留一阶项:

运算 绝对误差上界或估计 相对误差估计
x1±x2x_1\pm x_2 ε1+ε2\varepsilon_1+\varepsilon_2 视量级而定,可能急剧放大
x1x2x_1x_2 ∣x2∣ε1+∣x1∣ε2\lvert x_2\rvert\varepsilon_1+\lvert x_1\rvert\varepsilon_2 εr1+εr2\varepsilon_{r1}+\varepsilon_{r2}
x1/x2x_1/x_2 ∣x2∣ε1+∣x1∣ε2∣x2∣2\dfrac{\lvert x_2\rvert\varepsilon_1+\lvert x_1\rvert\varepsilon_2}{\lvert x_2\rvert^2} εr1+εr2\varepsilon_{r1}+\varepsilon_{r2}

乘除的相对误差可用输入相对误差限之和作一阶估计:两个 1%1\% 精度的数相乘,结果大约只有 2%2\% 精度。加减则要看结果本身有多大——两个大数相减得到小数,绝对误差没变,相对误差会爆炸,这就是 1.5 节要处理的抵消问题。

对一元可微函数 y=f(x)y=f(x),用泰勒展开一阶项:

ε(f(x∗))≈∣f′(x∗)∣ ε(x∗),εr(f(x∗))≈∣x∗f′(x∗)f(x∗)∣εr(x∗)\varepsilon(f(x^*))\approx \lvert f'(x^*)\rvert\,\varepsilon(x^*),\qquad \varepsilon_r(f(x^*))\approx \left\lvert \frac{x^*f'(x^*)}{f(x^*)}\right\rvert \varepsilon_r(x^*)

方括号里的量称为条件数,记作 Cond\mathrm{Cond}。它只由函数和点决定,衡量函数在该点对输入的敏感程度:

例 1-3(补充) 计算 y=x1x2y=x_1x_2,已知 x1=2.0±0.01x_1=2.0\pm 0.01,x2=3.0±0.02x_2=3.0\pm 0.02,求 yy 的一阶误差估计,并给出严格的绝对误差上界。

ε(y)≈3.0×0.01+2.0×0.02=0.07\varepsilon(y)\approx 3.0\times 0.01+2.0\times 0.02=0.07

用近似结果 6.06.0 归一化,相对误差的一阶估计为 0.07/6.0≈1.17%0.07/6.0\approx 1.17\%。若要严格上界,还需加上二阶项:∣y−6.0∣≤0.07+0.01×0.02=0.0702\lvert y-6.0\rvert\le 0.07+0.01\times0.02=0.0702。

例 1-4(补充) 比较 f(x)=xf(x)=\sqrt{x} 在 x=1.21x=1.21 与 g(x)=1/(1−x)g(x)=1/(1-x) 在 x=0.99x=0.99 的条件数。

x\sqrt{x} 的条件数为 ∣x⋅12x∣/x=1/2\lvert x\cdot \frac{1}{2\sqrt{x}}\rvert/\sqrt{x}=1/2,输入 1%1\% 的相对误差传到输出只剩 0.5%0.5\%。g(x)g(x) 的条件数为 ∣x/(1−x)∣=99\lvert x/(1-x)\rvert=99,输入 1%1\% 的误差会被放大到约 99%99\%,结果基本不可信。这就是「避免除以接近零的数」的定量版本。

1.5 数值稳定性

定义 一个算法,如果运算过程中舍入误差在给定条件下能得到控制,误差增长不影响产生可靠结果,则称该算法是数值稳定的;否则称为数值不稳定的。

稳定性不是问题的性质,是算法的性质。同一个积分,正向递推发散,反向递推就稳定;同一个多项式,逐项求幂误差大,秦九韶算法就稳。四条常用原则:

  1. 避免两个相近数相减。 差的有效数字会大量丢失。
  2. 避免大数吃小数。 绝对值相差悬殊时,小数会被舍入掉;求和时先加小数,或用补偿求和。
  3. 避免除以绝对值很小的数。 除数一小,误差被成倍放大。
  4. 减少运算次数,选稳定的递推方向。 运算越少,舍入误差积累越少;递推要看误差是逐步放大还是逐步衰减。

相近数相减

设 xx 很大,直接算 x+1−x\sqrt{x+1}-\sqrt{x}。两个数几乎相等,相减后前面的有效数字全部抵消,只剩下舍入噪声。把它有理化:

x+1−x=1x+1+x\sqrt{x+1}-\sqrt{x}=\frac{1}{\sqrt{x+1}+\sqrt{x}}

分母是两个大数相加,不再抵消,结果稳定。

图 1-2 双精度下两种写法的相对误差。直接相减的误差随 xx 线性增长,x=1012x=10^{12} 时已损失约 6 位有效数字;有理化后的误差始终停在机器精度附近。

同类改写还有:

1x−1x+1=1x(x+1),1−cos⁡x=2sin⁡2x2,ln⁡(x+1)−ln⁡x=ln⁡(1+1x)\frac{1}{x}-\frac{1}{x+1}=\frac{1}{x(x+1)},\qquad 1-\cos x=2\sin^2\frac{x}{2},\qquad \ln(x+1)-\ln x=\ln\left(1+\frac{1}{x}\right)

秦九韶算法

多项式 p(x)=anxn+⋯+a1x+a0p(x)=a_nx^n+\cdots+a_1x+a_0 直接按幂计算需要约 2n2n 次乘法;改写成嵌套形式

p(x)=(⋯((anx+an−1)x+an−2)x+⋯+a1)x+a0p(x)=(\cdots((a_nx+a_{n-1})x+a_{n-2})x+\cdots+a_1)x+a_0

只需 nn 次乘法、nn 次加法,而且中间结果量级更可控。

例 1-5(补充) 用秦九韶算法求 p(x)=3x4+2x3−5x2+x−7p(x)=3x^4+2x^3-5x^2+x-7 在 x=2x=2 处的值。

按 3, 2, −5, 1, −73,\ 2,\ -5,\ 1,\ -7 依次做「乘 22 加下一个系数」:

步骤 计算 结果
b0b_0 33 33
b1b_1 3×2+23\times 2+2 88
b2b_2 8×2−58\times 2-5 1111
b3b_3 11×2+111\times 2+1 2323
b4b_4 23×2−723\times 2-7 3939

p(2)=39p(2)=39。直接按幂计算要做 77 次乘法,这里只做 44 次,少了近一半的舍入机会。

递推的稳定性

考虑积分

In=∫01xnx+5 dx,n=0,1,2,…I_n=\int_0^1\frac{x^n}{x+5}\,dx,\qquad n=0,1,2,\ldots

把被积函数写成 xn−1−5xn−1/(x+5)x^{n-1}-5x^{n-1}/(x+5)(n≥1n\ge1),逐项积分得

In=1n−5In−1,I0=ln⁡1.2≈0.18232156I_n=\frac{1}{n}-5I_{n-1},\qquad I_0=\ln 1.2\approx 0.18232156

每递推一步,In−1I_{n-1} 的误差被乘以 −5-5,绝对值放大 55 倍。初始只有 10−1610^{-16} 的舍入误差,到 n=20n=20 已放大到 520≈9.5×10135^{20}\approx 9.5\times 10^{13} 倍,结果完全失真。

图 1-3 同一递推的正向与反向计算。图中正向采用双精度,以 `Math.log(1.2)` 的计算结果为起点。正向 n=10n=10 已有 2.5×10−82.5\times 10^{-8} 的相对误差,n=20n=20 约 47%47\%,n=25n=25 结果量级都错了;反向递推每步把误差缩小到 1/51/5,始终稳定。

把递推反过来用:

In−1=1/n−In5I_{n-1}=\frac{1/n-I_n}{5}

先取一个较大的 NN,用粗略估计 IN≈15(N+1)I_N\approx \dfrac{1}{5(N+1)} 作起点,再倒推到需要的 nn。起点误差在每一步缩小 55 倍,倒推十几步后就降到机器精度,这就是反向递推稳定。

判断递推稳定性的通用方法:写出误差满足的关系 en≈c en−1e_n\approx c\,e_{n-1}。∣c∣>1\lvert c\rvert>1 时误差放大,正向不稳定;∣c∣<1\lvert c\rvert<1 时误差衰减,正向稳定。反向递推的系数正好是 1/c1/c,所以稳定方向与正向相反。

1.6 本章小结

概念 核心式子 常见用途
绝对误差 e∗=x∗−xe^*=x^*-x 判断偏大偏小、给区间
相对误差 er∗=e∗/xe_r^*=e^*/x 跨量级比较精度
有效数字 ∣x−x∗∣≤0.5×10m−n\lvert x-x^*\rvert\le 0.5\times 10^{m-n} 数出可信位数
定理 1.1 εr∗≤12a1101−n\varepsilon_r^*\le \dfrac{1}{2a_1}10^{1-n} 由精度要求反解位数
误差传播 ε(f)≈∣f′∣ε(x)\varepsilon(f)\approx\lvert f'\rvert\varepsilon(x) 估计结果精度
条件数 ∣xf′f∣\left\lvert\dfrac{xf'}{f}\right\rvert 判断问题是否病态
稳定性 误差是否被算法放大 选择计算公式与递推方向
这一章最常见的四类题: ① 给真值和近似值,算绝对、相对误差与有效数字位数——注意先定 mm 和 a1a_1,再逐位试算; ② 给相对误差要求,反解至少几位有效数字——套定理 1.1,解出 nn 后向上取整; ③ 给一个算式,判断是否稳定并改写——优先找相近数相减、大数吃小数、小分母; ④ 给递推式,判断误差放大倍数与稳定方向——写出 en≈cen−1e_n\approx c e_{n-1} 即可。