第一讲 数值计算的误差.

Presentation on theme: "第一讲 数值计算的误差."— Presentation transcript:

1 第一讲 数值计算的误差

2 内容提要 什么是误差 误差的来源 绝对误差与相对误差 误差限 有效数字 误差估计 误差分析与数值稳定性 数值计算中算法设计的技术
数学软件（略） 误差的来源 绝对误差与相对误差 误差限 有效数字 误差估计

3 什么是误差 误差 是人们用来描述数值计算中近似解的精确程度，是科学计算中的一个十分重要的概念 误差的来源
从实际问题中抽象出数学模型 —— 模型误差 通过测量和实验得到模型中的各种数据 —— 观测误差 数学模型的数值求解 —— 截断误差（方法误差） 机器字长有限 —— 舍入误差 在数值分析中，我们总假定数学模型是准确的，因而不考虑模型误差和观测误差，主要研究截断误差和舍入误差对计算结果的影响

4 误差举例 例：近似计算 解法之一：将 作Taylor展开后再积分 S4 R4 取 则 称为 截断误差

5 误差举例 保留小数点后 4 位数字 舍入误差

6 绝对误差 |e*| = |x* - x|  * 定义：设 x 为精确值，x* 为它的一个近似值，则称 e* = x* - x
绝对误差可正可负 绝对误差通常是不可知的 定义：存在一个正数 * ，使得， |e*| = |x* - x|  * 则称 * 为绝对误差限，简称误差限。记： x = x*± * 做误差估计时所求的是绝对误差限，越小越好！ 但绝对误差限却不能很好地表示近似值的精确程度

7 相对误差 I can tell that distance between two planets is
1 million light year ±1 light year. I can tell that this part’s diameter is 20cm0.1cm. Of course mine is more accurate ! The accuracy relates to not only the absolute error, but also to the size of the exact value

8 相对误差 x* - x er* = x er* = x* - x x* 定义：设 x 为精确值，x* 为它的一个近似值，则称
由于精确值难以求出，通常也采用下面的定义 x* - x er* = x* 若存在正数 r*，使得 |er*|  r*，则称 r*为 相对误差限 近似值的精确程度取决于 相对误差 的大小 实际计算中我们所能得到的是 绝对误差限 或 相对误差限

9 有效数字 例： = 3.14159265 ··· ，近似值 x1 = 3.1415，x2 = 3.1416
定义：若近似值 x* 的误差限是某一位的半个单位，且该位到 x* 的第一位非零数字共有 n 位，则称 x* 有 n 位有效数字。 例： = ··· ，近似值 x1 = ，x2 = 问：x1, x2 分别有几位有效数字？ （4, 5） 例：根据四舍五入原则写出下列各数的具有 5 位有效数字的近似值： ， ， （187.93， ，8.0000） 按四舍五入原则得到的数字是有效数字 一个数末尾的 0 不可以随意添加或省略

10 有效数字 x* =  a1.a2···an ···  10m 0.5  10k-1 < |x*- x|  0.5  10k
另一个比较实用的描述 设 x* 为 x 的近似值， 若 x* 可表示为（ ai 是 0 到 9 中的数字且 a10 ） x* =  a1.a2···an ···  10m 且有 0.5  10k-1 < |x*- x|  0.5  10k 则 x* 有 m-k+1 位有效数字。 x*有 n 位有效数字 0.5  10m-n < |x*- x|  0.5  10m-n+1

11 有效数字与相对误差限   10-(n-1)   10-(n-1) 1 2a1 1 2(a1+1)
定理：设近似值 x* 可表示为 x* =  a1.a2···an ··· 10m (a10)， 若 x* 具有 n 位有效数字，则其相对误差限满足 1   10-(n-1) 2a1 反之，若 则 x* 至少有 n 位有效数字。 1   10-(n-1) 2(a1+1) 证明：板书 有效数字越多，相对误差限越小

12 误差估计 误差估计：估计误差限或相对误差限 简单算术运算的误差估计 记  (x*) 为 x* 的误差限，则有

13 误差估计 一元可微函数 f (x) 的误差估计 设一元函数 f (x) 可微，x*为 x 的近似值，则有

14 误差估计 x = (x1, x2, , xn) 的近似值，则有 ( f(x*) )  多元可微函数 f (x) 的误差估计
设多元函数 f (x) 可微， x*=(x1*, x2*, , xn*) 为 x = (x1, x2, , xn) 的近似值，则有 ( f(x*) )  例：测得某场地的长 L 和宽 D 分别为：L*=110m, D*=80m。其测量误差限分别为 0.2m 和 0.1m。 试求面积 S 的绝对误差限和相对误差限。 解：板书（教材第 8 页例 4）

15 内容提要 什么是误差 误差分析与数值稳定性 误差分析方法 算法的数值稳定性 数值计算中算法设计的技术 病态问题与条件数 避免误差危害
数学软件（略） 误差分析方法 算法的数值稳定性 病态问题与条件数 避免误差危害

16 误差分析 误差分析 误差定量分析 数值计算中的误差分析很重要，但也很复杂 在计算过程中，误差会传播、积累、对消
对每一步运算都做误差分析比较不切实际 （运算次数通常都在千万次以上） 向后误差分析法：比较有效的方法 向前误差分析法，区间误差分析法，概率分析法 误差定量分析 定量分析工作量大，都到的误差界往往不太实用。 目前在数值计算中更关注的是误差的定性分析

17 误差分析 误差定性分析 算法有 “优劣” 之分，问题有 “好坏” 之别，即使不能定量地估计出最终误差，但是若能判别计算过程中误差不会被任意放大，那就能放心地实施计算，这就是定性分析的初衷。 定性分析包括研究数值问题的适定性，数值问题与原问题的相容性，数值算法的稳定性，避免扩大误差的准则等 定性分析的核心是原始数据的误差和计算中产生的误差对最终计算结果的影响

18 数值稳定性 稳定性：数学问题的稳定性和数值算法的稳定性 数学问题的稳定性（适定性，well-posedness）：满足
(1) 对任意满足一定条件的数据，存在一个解 (2) 对任意满足一定条件的数据，解是唯一的 (3) 问题的解关于输入数据是连续的 否则就称问题是不适定的（ill-posed） 通俗描述：如果输入数据的微小扰动会引起输出数据（即计算结果）的很大变化（误差），则称该数值问题是病态的。

19 病态问题举例 例：解线性方程组 解： 当 =1 时，无解 当 1 时，解为 当 1 时，误差可能会被大大地放大
比如取 =0.999，则 x=500.25; 如果输入数据为 *=0.9991，即带有误差 ， 则 x*=555.81，误差约为 55.56 这时的问题就是病态的

20 条件数 设一元函数 f (x) 可微，x*为 x 的近似值，则有 其中 Cp 就称为 f (x) 的条件数。
一般情况下，条件数大于 10 时，就认为问题是病态的 条件数越大问题病态就越严重 病态是问题本身固有的性质，与数值算法无关 对于病态问题，选择数值算法时需要谨慎

21 ? ? ? ? ? 算法的稳定性 例：近似计算 ，其中 n=1, 2, ..., 8 解： 此公式精确成立 保留 3 位有效数字 易知
通过递推公式可得（每次都保留 3 位有效数字） ? ? ? ? ?

22 算法稳定性 但显然有 What happened?!

23 算法稳定性 考察第 n 步的误差 即有 误差以 5 倍的速度增长！ 说明该计算过程是不稳定的！ 我们需要改变算法!

24 数值稳定性 解法二： 具体思路：先估计一个 SN ，再反过来求 Sn ( n < N ) ex11.m 在数值计算中，误差不可避免，
算法的稳定性是一个非常重要的性质。

25 数值稳定性 算法的稳定性 例：教材第 9 页，例 5 （板书） 在计算过程中，如果误差不增长，则称该算法是稳定的，否则为不稳定的。
数值计算中，不要采用不稳定的算法！ 例：教材第 9 页，例 5 （板书）

26 数值计算注意事项 避免相近的数相减 例：a1 = 0.12345，a2 = 0.12346，各有5位有效数字。
几种经验性避免误差危害的方法： 当 | x | << 1 时： 例：教材第 11 至 12 页，例 7，8，9，10 （板书）

27 数值计算注意事项 避免数量级相差很大的数相除 避免大数吃小数 例：计算 (109+10-9-109)/10-9
可能会产生溢出的情形（超出计算机所能表示的范围） 避免大数吃小数 例：计算 ( )/10-9 例：按从小到大、以及从大到小的顺序分别计算 S= … ex12.m 求和时 从小到大 相加，可使结果的误差减小

28 数值计算注意事项 简化计算，避免误差积累 例：已知 p(x) = xn + xn-1+ ··· + x + 1， 计算 n = 20 时， p(8) 的值。 如果直接代入计算，则需 n(n-1)/2 次乘法和 n 次加法运算 如果将 p(x) 改写为： p(x) = x (x ( ··· (x (x + 1)+1) + ··· + 1) + 1 则只需 n –1次乘法和 n 次加法运算。 秦九韶算法 或 Horner算法 选用稳定的算法

29 内容提要 什么是误差 误差分析与数值稳定性 数值计算中算法设计的技术 数学软件（略）

30 算法设计 多项式计算：秦九韶算法 或 Horner算法 迭代法与开方求值：如非线性方程的迭代法解法 以直代曲与化整为零：如差商代替微商
加权平均的松弛技术：如 Simpson 算法

31 作业 教材第 19 页：2、4、5、6、7、10、11 提示： 第 2 题中的误差指的是误差限 2、5 题可利用 Taylor 展开或条件数
整数的加减和乘法运算没有误差