CHAPTER 01
第一章 · 误差
数值分析的第一个问题不是「怎么算」,而是「算出来的结果还能信几位」。这一章所有公式都指向同一个判断:误差有多大,结果有几位可靠。
本页目录
1.1 误差从哪来
用计算机解一个数学问题,误差有四个来源。前两个不是这门课能处理的,后两个才是。
来源
典型情形
本课程是否研究
模型误差
把真实物理过程简化成微分方程
否
观测误差
测量仪器的读数偏差、参数标定误差
否
截断误差
用有限项级数代替无穷级数、用差商代替导数
是
舍入误差
计算机字长有限,0.1 0.1 0.1 存不进二进制
是
截断误差 来自「方法本身做了近似」,加密网格、增加项数可以减小它。舍入误差 来自「机器存不下精确值」,运算次数越多、量级差越大,它越容易积累。后面的稳定性讨论,本质上就是在问:舍入误差会不会被算法放大。
考试里常给一个具体做法,让你判断误差属于哪一类。判据是看近似发生在「建模」「测量」还是「计算过程」:把
e x e^x e x 展开成前
n n n 项是截断,把
1 / 3 1/3 1/3 存成
0.333333 0.333333 0.333333 是舍入。
1.2 绝对误差与相对误差
设 x x x 是真值,x ∗ x^* x ∗ 是近似值。按课件约定,绝对误差 定义为近似值减真值:
e ∗ e^* e ∗ 带符号:e ∗ > 0 e^*>0 e ∗ > 0 说明近似值偏大。实际判断精度时看它的绝对值 ∣ e ∗ ∣ \lvert e^*\rvert ∣ e ∗ ∣ 。由于真值通常不知道,能给出的往往是一个界限 ε ∗ \varepsilon^* ε ∗ ,满足
ε ∗ \varepsilon^* ε ∗ 称为绝对误差限 。它把真值框在区间 [ x ∗ − ε ∗ , x ∗ + ε ∗ ] [x^*-\varepsilon^*,\ x^*+\varepsilon^*] [ x ∗ − ε ∗ , x ∗ + ε ∗ ] 内。
绝对误差有量纲,不能跨对象比较。称量 1 1 1 kg 差 1 1 1 g 与称量 1 1 1 t 差 1 1 1 g,绝对误差相同,精度差三个数量级。所以引入相对误差 :
相对误差无量纲,通常写成百分数或 10 10 10 的幂次。分母用真值 x x x 是定义,实际计算时真值未知,才用 x ∗ x^* x ∗ 代替;当误差相对很小时,这样做足以估计误差。上式的 ε r ∗ \varepsilon_r^* ε r ∗ 是按近似值归一化的误差限。若要求相对真值的严格上界,且 ∣ x ∗ ∣ > ε ∗ \lvert x^*\rvert>\varepsilon^* ∣ x ∗ ∣ > ε ∗ ,可用 ε ∗ / ( ∣ x ∗ ∣ − ε ∗ ) \varepsilon^*/(\lvert x^*\rvert-\varepsilon^*) ε ∗ / (∣ x ∗ ∣ − ε ∗ ) 。
符号方向容易混:有的教材定义
e = x − x ∗ e=x-x^* e = x − x ∗ ,课件定义
e ∗ = x ∗ − x e^*=x^*-x e ∗ = x ∗ − x 。答题时先写清定义式,再代数字。优先按本课件的约定写,别把定义与代入的符号方向弄反。
例 1-1(补充) 取 π = 3.14159265 … \pi=3.14159265\ldots π = 3.14159265 … ,近似值 x ∗ = 3.14 x^*=3.14 x ∗ = 3.14 。求绝对误差、绝对误差限、相对误差。
取 ε ∗ = 0.5 × 10 − 2 \varepsilon^*=0.5\times 10^{-2} ε ∗ = 0.5 × 1 0 − 2 是一个合法但不紧的误差限:3.14 3.14 3.14 是四舍五入到小数点后两位的结果,真正的舍入界是 0.5 × 10 − 2 0.5\times 10^{-2} 0.5 × 1 0 − 2 ,而实际误差比它小。相对误差
负号表示近似值偏小;精度看 5.07 × 10 − 4 5.07\times 10^{-4} 5.07 × 1 0 − 4 ,即约 0.05 % 0.05\% 0.05% 。
「绝对误差限」不是「误差的绝对值」的精确值,而是一个可以保证的上界。题目给「
x ∗ = 3.14 x^*=3.14 x ∗ = 3.14 是
π \pi π 的四舍五入值」,才能用
0.5 × 10 − 2 0.5\times 10^{-2} 0.5 × 1 0 − 2 ;只给一个截断到两位小数的数,不能默认它满足四舍五入的界。
1.3 有效数字
有效数字把误差大小翻译成「可信的数字位数」。设
若
则称 x ∗ x^* x ∗ 有 n n n 位有效数字 。这里 m m m 是最高非零位的位权,a 1 a_1 a 1 是第一位有效数字,n n n 是数到的位数(包括末尾的 0 0 0 )。
判定分三步:
把 x ∗ x^* x ∗ 写成 0. a 1 a 2 ⋯ × 10 m 0.a_1a_2\cdots\times 10^m 0. a 1 a 2 ⋯ × 1 0 m ,确定 m m m 和第一位非零数字 a 1 a_1 a 1 。
数出准备声称的位数 n n n ,算出界限 0.5 × 10 m − n 0.5\times 10^{m-n} 0.5 × 1 0 m − n 。
用真实的 ∣ x − x ∗ ∣ \lvert x-x^*\rvert ∣ x − x ∗ ∣ 与这个界限比较;成立就至少有 n n n 位,不成立就退一位再试。
有效数字从**第一个非零数字**数起,与小数点位置无关。
0.02340 0.02340 0.02340 有
4 4 4 位(
2 , 3 , 4 , 0 2,3,4,0 2 , 3 , 4 , 0 ),不是
5 5 5 位,也不是
6 6 6 位;
2.340 × 10 − 2 2.340\times 10^{-2} 2.340 × 1 0 − 2 同样是
4 4 4 位。末尾的
0 0 0 算不算,取决于它是否被明确写出。
图 1-1 误差限是否覆盖真值,决定能声称几位有效数字。x ∗ = 3.14 x^*=3.14 x ∗ = 3.14 对 π \pi π 的误差 1.59 × 10 − 3 1.59\times 10^{-3} 1.59 × 1 0 − 3 落在 0.005 0.005 0.005 内、落在 0.0005 0.0005 0.0005 外,所以只有 3 位。
有效数字与按近似值归一化的相对误差限之间有一个常用的上界。
定理 1.1 若 x ∗ x^* x ∗ 有 n n n 位有效数字,则其相对误差限满足
这个定理只要求知道第一位有效数字 a 1 a_1 a 1 和位数 n n n ,不必知道真值,所以特别适合反解题:「要保证相对误差不超过某个值,至少需要几位有效数字?」
例 1-2(课件例题) 设 x = 20 = 4.47213595 … x=\sqrt{20}=4.47213595\ldots x = 20 = 4.47213595 … ,要求近似值的相对误差不超过 0.5 × 10 − 3 0.5\times 10^{-3} 0.5 × 1 0 − 3 ,问按定理 1.1 的上界估计,至少应取几位有效数字?
a 1 = 4 a_1=4 a 1 = 4 。由定理 1.1,令
即 10 1 − n ≤ 4 × 10 − 3 10^{1-n}\le 4\times 10^{-3} 1 0 1 − n ≤ 4 × 1 0 − 3 ,两边取对数得 1 − n ≤ − 2.398 1-n\le -2.398 1 − n ≤ − 2.398 ,所以 n ≥ 3.398 n\ge 3.398 n ≥ 3.398 。取整数 n = 4 n=4 n = 4 。
验算:n = 4 n=4 n = 4 时界为 1.25 × 10 − 4 ≤ 5 × 10 − 4 1.25\times 10^{-4}\le 5\times 10^{-4} 1.25 × 1 0 − 4 ≤ 5 × 1 0 − 4 ,成立;n = 3 n=3 n = 3 时界为 1.25 × 10 − 3 1.25\times 10^{-3} 1.25 × 1 0 − 3 ,未达标。按定理的上界估计,取 4 位。
按定理反解,得到的是让估计上界达标的最小位数,不是实际所需位数。本题直接用三位近似值
4.47 4.47 4.47 验算,按真值计算的实际相对误差约为
4.78 × 10 − 4 4.78\times10^{-4} 4.78 × 1 0 − 4 ,也满足容许值。
1.4 误差传播
实际计算是一连串运算,初始数据的误差会被逐步放大或缩小。设 x 1 , x 2 x_1,x_2 x 1 , x 2 的绝对误差限为 ε 1 , ε 2 \varepsilon_1,\varepsilon_2 ε 1 , ε 2 ,下表给出传播误差的估计;其中加减法的绝对误差上界是严格的,乘除法只保留一阶项:
运算
绝对误差上界或估计
相对误差估计
x 1 ± x 2 x_1\pm x_2 x 1 ± x 2
ε 1 + ε 2 \varepsilon_1+\varepsilon_2 ε 1 + ε 2
视量级而定,可能急剧放大
x 1 x 2 x_1x_2 x 1 x 2
∣ x 2 ∣ ε 1 + ∣ x 1 ∣ ε 2 \lvert x_2\rvert\varepsilon_1+\lvert x_1\rvert\varepsilon_2 ∣ x 2 ∣ ε 1 + ∣ x 1 ∣ ε 2
ε r 1 + ε r 2 \varepsilon_{r1}+\varepsilon_{r2} ε r 1 + ε r 2
x 1 / x 2 x_1/x_2 x 1 / x 2
∣ x 2 ∣ ε 1 + ∣ x 1 ∣ ε 2 ∣ x 2 ∣ 2 \dfrac{\lvert x_2\rvert\varepsilon_1+\lvert x_1\rvert\varepsilon_2}{\lvert x_2\rvert^2} ∣ x 2 ∣ 2 ∣ x 2 ∣ ε 1 + ∣ x 1 ∣ ε 2
ε r 1 + ε r 2 \varepsilon_{r1}+\varepsilon_{r2} ε r 1 + ε r 2
乘除的相对误差可用输入相对误差限之和作一阶估计:两个 1 % 1\% 1% 精度的数相乘,结果大约只有 2 % 2\% 2% 精度。加减则要看结果本身有多大——两个大数相减得到小数,绝对误差没变,相对误差会爆炸,这就是 1.5 节要处理的抵消问题。
对一元可微函数 y = f ( x ) y=f(x) y = f ( x ) ,用泰勒展开一阶项:
方括号里的量称为条件数 ,记作 C o n d \mathrm{Cond} Cond 。它只由函数和点决定,衡量函数在该点对输入的敏感程度:
C o n d ≈ 1 \mathrm{Cond}\approx 1 Cond ≈ 1 :良态,相对误差基本不变;
C o n d ≫ 1 \mathrm{Cond}\gg 1 Cond ≫ 1 :病态,输入的微小相对误差会被放大若干倍;
C o n d < 1 \mathrm{Cond}<1 Cond < 1 :误差被压缩,例如开方。
例 1-3(补充) 计算 y = x 1 x 2 y=x_1x_2 y = x 1 x 2 ,已知 x 1 = 2.0 ± 0.01 x_1=2.0\pm 0.01 x 1 = 2.0 ± 0.01 ,x 2 = 3.0 ± 0.02 x_2=3.0\pm 0.02 x 2 = 3.0 ± 0.02 ,求 y y y 的一阶误差估计,并给出严格的绝对误差上界。
用近似结果 6.0 6.0 6.0 归一化,相对误差的一阶估计为 0.07 / 6.0 ≈ 1.17 % 0.07/6.0\approx 1.17\% 0.07/6.0 ≈ 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 ∣ y − 6.0 ∣ ≤ 0.07 + 0.01 × 0.02 = 0.0702 。
例 1-4(补充) 比较 f ( x ) = x f(x)=\sqrt{x} f ( x ) = x 在 x = 1.21 x=1.21 x = 1.21 与 g ( x ) = 1 / ( 1 − x ) g(x)=1/(1-x) g ( x ) = 1/ ( 1 − x ) 在 x = 0.99 x=0.99 x = 0.99 的条件数。
x \sqrt{x} x 的条件数为 ∣ x ⋅ 1 2 x ∣ / x = 1 / 2 \lvert x\cdot \frac{1}{2\sqrt{x}}\rvert/\sqrt{x}=1/2 ∣ x ⋅ 2 x 1 ∣ / x = 1/2 ,输入 1 % 1\% 1% 的相对误差传到输出只剩 0.5 % 0.5\% 0.5% 。g ( x ) g(x) g ( x ) 的条件数为 ∣ x / ( 1 − x ) ∣ = 99 \lvert x/(1-x)\rvert=99 ∣ x / ( 1 − x )∣ = 99 ,输入 1 % 1\% 1% 的误差会被放大到约 99 % 99\% 99% ,结果基本不可信。这就是「避免除以接近零的数」的定量版本。
1.5 数值稳定性
定义 一个算法,如果运算过程中舍入误差在给定条件下能得到控制,误差增长不影响产生可靠结果,则称该算法是数值稳定的 ;否则称为数值不稳定 的。
稳定性不是问题的性质,是算法 的性质。同一个积分,正向递推发散,反向递推就稳定;同一个多项式,逐项求幂误差大,秦九韶算法就稳。四条常用原则:
避免两个相近数相减。 差的有效数字会大量丢失。
避免大数吃小数。 绝对值相差悬殊时,小数会被舍入掉;求和时先加小数,或用补偿求和。
避免除以绝对值很小的数。 除数一小,误差被成倍放大。
减少运算次数,选稳定的递推方向。 运算越少,舍入误差积累越少;递推要看误差是逐步放大还是逐步衰减。
相近数相减
设 x x x 很大,直接算 x + 1 − x \sqrt{x+1}-\sqrt{x} x + 1 − x 。两个数几乎相等,相减后前面的有效数字全部抵消,只剩下舍入噪声。把它有理化:
分母是两个大数相加,不再抵消,结果稳定。
图 1-2 双精度下两种写法的相对误差。直接相减的误差随 x x x 线性增长,x = 10 12 x=10^{12} x = 1 0 12 时已损失约 6 位有效数字;有理化后的误差始终停在机器精度附近。
同类改写还有:
秦九韶算法
多项式 p ( x ) = a n x n + ⋯ + a 1 x + a 0 p(x)=a_nx^n+\cdots+a_1x+a_0 p ( x ) = a n x n + ⋯ + a 1 x + a 0 直接按幂计算需要约 2 n 2n 2 n 次乘法;改写成嵌套形式
只需 n n n 次乘法、n n n 次加法,而且中间结果量级更可控。
例 1-5(补充) 用秦九韶算法求 p ( x ) = 3 x 4 + 2 x 3 − 5 x 2 + x − 7 p(x)=3x^4+2x^3-5x^2+x-7 p ( x ) = 3 x 4 + 2 x 3 − 5 x 2 + x − 7 在 x = 2 x=2 x = 2 处的值。
按 3 , 2 , − 5 , 1 , − 7 3,\ 2,\ -5,\ 1,\ -7 3 , 2 , − 5 , 1 , − 7 依次做「乘 2 2 2 加下一个系数」:
步骤
计算
结果
b 0 b_0 b 0
3 3 3
3 3 3
b 1 b_1 b 1
3 × 2 + 2 3\times 2+2 3 × 2 + 2
8 8 8
b 2 b_2 b 2
8 × 2 − 5 8\times 2-5 8 × 2 − 5
11 11 11
b 3 b_3 b 3
11 × 2 + 1 11\times 2+1 11 × 2 + 1
23 23 23
b 4 b_4 b 4
23 × 2 − 7 23\times 2-7 23 × 2 − 7
39 39 39
p ( 2 ) = 39 p(2)=39 p ( 2 ) = 39 。直接按幂计算要做 7 7 7 次乘法,这里只做 4 4 4 次,少了近一半的舍入机会。
递推的稳定性
考虑积分
把被积函数写成 x n − 1 − 5 x n − 1 / ( x + 5 ) x^{n-1}-5x^{n-1}/(x+5) x n − 1 − 5 x n − 1 / ( x + 5 ) (n ≥ 1 n\ge1 n ≥ 1 ),逐项积分得
每递推一步,I n − 1 I_{n-1} I n − 1 的误差被乘以 − 5 -5 − 5 ,绝对值放大 5 5 5 倍。初始只有 10 − 16 10^{-16} 1 0 − 16 的舍入误差,到 n = 20 n=20 n = 20 已放大到 5 20 ≈ 9.5 × 10 13 5^{20}\approx 9.5\times 10^{13} 5 20 ≈ 9.5 × 1 0 13 倍,结果完全失真。
图 1-3 同一递推的正向与反向计算。图中正向采用双精度,以 `Math.log(1.2)` 的计算结果为起点。正向 n = 10 n=10 n = 10 已有 2.5 × 10 − 8 2.5\times 10^{-8} 2.5 × 1 0 − 8 的相对误差,n = 20 n=20 n = 20 约 47 % 47\% 47% ,n = 25 n=25 n = 25 结果量级都错了;反向递推每步把误差缩小到 1 / 5 1/5 1/5 ,始终稳定。
把递推反过来用:
先取一个较大的 N N N ,用粗略估计 I N ≈ 1 5 ( N + 1 ) I_N\approx \dfrac{1}{5(N+1)} I N ≈ 5 ( N + 1 ) 1 作起点,再倒推到需要的 n n n 。起点误差在每一步缩小 5 5 5 倍,倒推十几步后就降到机器精度,这就是反向递推稳定 。
判断递推稳定性的通用方法:写出误差满足的关系
e n ≈ c e n − 1 e_n\approx c\,e_{n-1} e n ≈ c e n − 1 。
∣ c ∣ > 1 \lvert c\rvert>1 ∣ c ∣ > 1 时误差放大,正向不稳定;
∣ c ∣ < 1 \lvert c\rvert<1 ∣ c ∣ < 1 时误差衰减,正向稳定。反向递推的系数正好是
1 / c 1/c 1/ c ,所以稳定方向与正向相反。
1.6 本章小结
概念
核心式子
常见用途
绝对误差
e ∗ = x ∗ − x e^*=x^*-x e ∗ = x ∗ − x
判断偏大偏小、给区间
相对误差
e r ∗ = e ∗ / x e_r^*=e^*/x e r ∗ = e ∗ / x
跨量级比较精度
有效数字
∣ x − x ∗ ∣ ≤ 0.5 × 10 m − n \lvert x-x^*\rvert\le 0.5\times 10^{m-n} ∣ x − x ∗ ∣ ≤ 0.5 × 1 0 m − n
数出可信位数
定理 1.1
ε r ∗ ≤ 1 2 a 1 10 1 − n \varepsilon_r^*\le \dfrac{1}{2a_1}10^{1-n} ε r ∗ ≤ 2 a 1 1 1 0 1 − n
由精度要求反解位数
误差传播
ε ( f ) ≈ ∣ f ′ ∣ ε ( x ) \varepsilon(f)\approx\lvert f'\rvert\varepsilon(x) ε ( f ) ≈ ∣ f ′ ∣ ε ( x )
估计结果精度
条件数
∣ x f ′ f ∣ \left\lvert\dfrac{xf'}{f}\right\rvert f x f ′
判断问题是否病态
稳定性
误差是否被算法放大
选择计算公式与递推方向
这一章最常见的四类题:
① 给真值和近似值,算绝对、相对误差与有效数字位数——注意先定
m m m 和
a 1 a_1 a 1 ,再逐位试算;
② 给相对误差要求,反解至少几位有效数字——套定理 1.1,解出
n n n 后向上取整;
③ 给一个算式,判断是否稳定并改写——优先找相近数相减、大数吃小数、小分母;
④ 给递推式,判断误差放大倍数与稳定方向——写出
e n ≈ c e n − 1 e_n\approx c e_{n-1} e n ≈ c e n − 1 即可。