01-数值计算的误差

误差 -误差的来源 -绝对误差与相对误差 -误差限 -有效数字 -误差估计 误差分析与数值稳定性 数值计算中算法设计的技术
展开查看详情

1.1 第一章 数值计算的误差

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

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

4.4 误差举例 例: 近似计算 解 : 将 作 Taylor 展开后再积分 S 4 R 4 取 则 称为 截断误差

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

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

7.7 相对误差 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 I can tell that distance between two planets is 1 million light year ±1 light year.

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

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

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

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

12.12 误差估计 误差估计: 估计误差限或相对误差限 记  ( x *) 为 x * 的误差限,则有 简单算术运算的误差估计

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

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

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

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

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

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

19.19 病态问题举例 例: 解线性方程组 解: 当  =1 时,无解 当  1 时,解为 若  1 ,则  的微小误差 可能 会引起解的很大变化 比如  = 0.9990 时, x  500.25 ; 如果 输入数据 有 0.0001 的误差, 即  * =0.9991 , 则 x *  555.81 , 误差约为 55.56 ! 因此,此时的 问题就是病态 的!

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

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

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

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

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

25.25 数值稳定性 算法的稳定性 例: 教材第 9 页,例 5 ( 自己练习) 在计算过程中,如果 误差 不 增长或能得到有效控制, 则称该算法是 稳定 的,否则为 不稳定 的。 数值计算中,不要采用不稳定的算法!

26.26 数值计算注意事项 避免相近的数相减 例: a 1 = 0.12345, a 2 = 0.12346, 各有5位有效数字。 而 a 2  a 1 = 0.00001, 只剩下1位有效数字。 几种经验性避免误差危害的方法: 当 | x | << 1 时: 例: 教材第 11 至 12 页,例 7 , 8 , 9 , 10 (自己练习)

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

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

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