误差知识与算法知识

1、第第1 1章章 绪论绪论 (Introduction)1.1 数值分析的研究对象数值分析的研究对象1.2 误差知识与算法知识误差知识与算法知识1.3 向量范数与矩阵范数向量范数与矩阵范数1.2 误差与有效数字误差与有效数字 (Error and Significant Digits)1.2 误差误差 /* Error */1.2.1 来源与分类来源与分类 /* Source & Classification */ 从实际问题中抽象出数学模型从实际问题中抽象出数学模型 模型误差模型误差 /* Modeling Error */例例: :质量为质量为m的物体，在重力作用下的物体，在重力作用

2、下, ,自由下落，其下落距自由下落，其下落距离离s 与时间与时间t 的关系是：的关系是： 22dsmm gd t 其中其中 g 为重力加速度。为重力加速度。 求近似解求近似解 方法误差方法误差 (截断误差截断误差) /* Truncation Error */ ( )200001!2!nnnfffPxfxxxn 近似代替时，数值方法的截断误差是近似代替时，数值方法的截断误差是(1)1( )( )( )( )(1)!nnnnfRxf xP xxn 例如，当函数例如，当函数 用用TaylorTaylor多项式多项式( )f x 与与0 0之间。之间。在在x 通过测量得到模型中参数的值通过测量得到模

3、型中参数的值 观测误差观测误差 /* Measurement Error */ 机器字长有限机器字长有限 舍入误差舍入误差 /* Roundoff Error */用计算机、计算器和笔算，都只能用有限位小数来用计算机、计算器和笔算，都只能用有限位小数来 = 3.1415926 代替无穷小数或用位数较少的小数来代替无穷小数或用位数较少的小数来代替代替位数较多的位数较多的有限小数，如：有限小数，如：10.33333 四舍五入后四舍五入后0000074. 01416. 31 e000033. 0333. 0312 e在数值计算方法中，主要研究在数值计算方法中，主要研究和和（包括初始数据的误差）对计算

4、结果的影响！（包括初始数据的误差）对计算结果的影响！ 绝对误差绝对误差 /* absolute error */1.2.2 绝对误差、相对误差、有效数字绝对误差、相对误差、有效数字是近似值是近似值 的的, ,简称为简称为。 a定义定义：设设 是准确值，是准确值， 为为 的一个近似值，称的一个近似值，称xax( )e ax a 例例 : :若用以厘米为最小刻度的尺去量桌子的长，大约若用以厘米为最小刻度的尺去量桌子的长，大约为为1.451.45米，求米，求1.451.45米的绝对误差。米的绝对误差。1.45米的米的绝对误差绝对误差= =？不知道！不知道！ 10006074302.dxex例如：例如

5、：xa 工程上常记为工程上常记为|e的上限记为的上限记为 , ,称为称为绝对误差限绝对误差限 /* accuracy */，有了绝对误差限有了绝对误差限就可以知道就可以知道 的范围为的范围为xa x a 即即 落在落在 内。内。xa,a 相对误差相对误差 ( relative error )|rx x 的的相对误差上限相对误差上限 定义为定义为rexaexx 一般情况下是不知一般情况下是不知道的，怎么办？道的，怎么办？通常取通常取rexaeaa 有效数字有效数字 （significant digits ）用科学计数法，记用科学计数法，记定义定义 : :若近似值若近似值 的误差限是某一位的半个单

6、位的误差限是某一位的半个单位, ,a就说就说 有有 位有效数字。位有效数字。an该位该位到到 的的左边左边第一位非零数字共有第一位非零数字共有 位位, ,annaanm 10（即（即 的截取按四舍五入规则），则称的截取按四舍五入规则），则称 为有为有n 位有效数位有效数字，精确到字，精确到 。12010mka.a aa 01 a( (其中其中 ）nm.ax 1050|若若 1415.3;8979321415926535.3 a 例：例：问：问： 有几位有效数字？请证明你的结论。有几位有效数字？请证明你的结论。a10 3141510 ,a. 证明：证明：31 4and0 5100 510, |

7、a |. 有有4 位有效数字，精确到小数点后第位有效数字，精确到小数点后第 3 位。位。a注：注： 若一近似数是由原真值经四舍五入得到，则必若一近似数是由原真值经四舍五入得到，则必为有效数。为有效数。取取 作作 的近似值，的近似值， 就有五位有效数字。就有五位有效数字。3.1416a a取取 作作 的近似值，的近似值， 就有三位有效数字；就有三位有效数字；3.14a a1.2.3 数值运算的误差估计数值运算的误差估计 四则运算四则运算两个近似数两个近似数 与与其误差限分别为其误差限分别为 及及 进行加减乘除运算得到的误差限分别为进行加减乘除运算得到的误差限分别为ab( )a ( )b ()(

8、)( )abab()( )( )ababba2( )( ),0abbaabbb 函数误差估计函数误差估计当自变量有误差时，计算函数值也会产生误差，其当自变量有误差时，计算函数值也会产生误差，其误差限可利用函数的误差限可利用函数的TaylorTaylor展开式进行估计。展开式进行估计。设设 是一元函数，是一元函数， 的近似值为的近似值为 , ,以以 近近似似 ，其误差限记作，其误差限记作 ，可用，可用TaylorTaylor展开展开ax( )f x( )f a ( )f a ( )f x2( )( )( )( )()()2ff xf afaxaxa 2( )( )( )( )( )( )2ff

9、xf afaaa 介于介于, x a之间。取绝对值得之间。取绝对值得 当当 为多元函数时计算为多元函数时计算 , ,如果如果f 12,nufxxx 假定假定 与与 的比值不太大的比值不太大, ,可忽略可忽略 的高阶的高阶项项, ,于是可得计算函数的误差限为于是可得计算函数的误差限为( )fa ( )fa ( )a ( )( )( )f afaa 12,nAf a aa 12,nxxx的近似值为的近似值为 , ,则则 的近似值为的近似值为12,na aau于是函数值于是函数值 的误差的误差 由由TaylorTaylor展开展开, ,u( )e A于是误差限为于是误差限为而而 的相对误差限为的相对

10、误差限为A(1.1)(1.2) 1212( ),nne AuAfxxxf a aa 121,()nnkkkf a aae ax 121,( )()nnkkkf a aaAax 121,()( )( )nnkrrkkf a aaaAAAxA *,S ldS ldSldld其中其中 *,80,110,S ldS ldmmld例例: 已测得某场地长已测得某场地长 的值为的值为 , 宽宽 的值的值为为 , 已知已知 , 。试求。试求面积面积 的绝对误差限与相对误差限。的绝对误差限与相对误差限。 l*110lm d*80dm *0.2llm*0.1ddmSld 解解: 因因 由式由式(1.1)得得,SS

11、Slddlld而而 *0.2,0.1,lmdm于是绝对误差限为于是绝对误差限为 2280 0 2110 0 127*.;Smm 相对误差限为相对误差限为 *270.31.8800rSSSl dS 1.2.4 数值计算中应该注意的一些原则数值计算中应该注意的一些原则1. 要使用数值稳定的算法要使用数值稳定的算法例：求例：求10(0,1,2,8)5nnxIdx nx 的值。的值。解：解：由于由于nxxxxxxIInnnnn1dd5551011011 初值初值)2 . 1ln(5ln6lnd51100 xxI递推公式递推公式 )8, 2, 1(,51)2 . 1ln(10nInIInn按公式就可以逐

12、步算出按公式就可以逐步算出09. 05101 II05. 052112 II083. 053123 II165. 054134 II025. 155145 II952. 456156 II注意此公式注意此公式精确精确成立成立What happened?!不稳定的算法不稳定的算法 ！这就是误差传播所引起的危害这就是误差传播所引起的危害 ! 由题设中的递推公式可看出，由题设中的递推公式可看出， 的误差扩大了的误差扩大了1nI 5 5倍后传给倍后传给 ，因而初值，因而初值 的误差对以后各步的误差对以后各步nI0I这就造成这就造成 的计算结果的计算结果严重失真。严重失真。4I计算结果的影计算结果的影响

13、，随着响，随着 的增大愈来愈严重。的增大愈来愈严重。n要怎么做才能解决这个问要怎么做才能解决这个问题呢题呢? ?可求得可求得 I9 0.017，按改写后的公式可逐次求得按改写后的公式可逐次求得不妨设不妨设 I9 I10，于是由于是由,51501109II ) 1 , 1,( 51511 nnkIkIkknIInn151 将公式将公式变为变为I8 0.019 I7 0.021I6 0.024 I5 0.028I4 0.034 I3 0.043I2 0.058 I1 0.088I0 0.182 稳定的算法稳定的算法 ！ 在我们今后的讨论中，在我们今后的讨论中，误差误差将不可回避，将不可回避， 算法

14、的算法的稳定性稳定性会是一个非常重要的话题。会是一个非常重要的话题。2. . 要避免两个相近的数相减要避免两个相近的数相减在数值计算中，两个相近的数作减法时有效数字会在数值计算中，两个相近的数作减法时有效数字会损失。损失。例例: 求求xxy 1的值。的值。当当x = 1000，y 的准确值为的准确值为0.01580。 (1) 直接相减直接相减02. 062.3164.3110001001 y类似地类似地 yxyxlnlnln 2sin2cos2sin)sin(eexxex (2) 将将原式原式改写为改写为xxxxy 111则则 y = 0.01581 3. 尽量避免绝对值太小的数作分母尽量避免

15、绝对值太小的数作分母例：例：2.71822718.20.001 如分母变为如分母变为0.0011，也即分母只有，也即分母只有0.0001的变化时的变化时1 .24710011. 07182. 2 2718.22471.1247.1结果相差这么结果相差这么大大! !4. 避免大数吃小数避免大数吃小数精确解为精确解为. 110291 x,x 算法算法1 1：利用求根公式利用求根公式aacbbx242 例：用单精度计算例：用单精度计算 的根。的根。010)110(992 xx在计算机内，在计算机内，109存为存为0.1 1010，1存为存为0.1 101。做加法时，做加法时，两加数的指数先向大指数对

16、齐，再将浮点部分相加。即两加数的指数先向大指数对齐，再将浮点部分相加。即1 的指数部分须变为的指数部分须变为1010，则：，则：1 = 0.0000000001 1010，取，取单精度时就成为：单精度时就成为： 109+1=0.10000000 1010+0.00000000 1010=0.10000000 1010. 024,102422921 aacbbxaacbbx算法算法2 2：先解出先解出9211024)( aacbbsignbx再利用再利用11010991221 xacxacxx求和时从小到大相加，可使和的误差减小。求和时从小到大相加，可使和的误差减小。例：例：按从小到大、以及从大

17、到小的顺序分别计算按从小到大、以及从大到小的顺序分别计算1 + 2 + 3 + + 40 + 1095. 5. 简化计算步骤，避免误差积累简化计算步骤，避免误差积累一般来说，计算机处理下列运算的速度为一般来说，计算机处理下列运算的速度为 exp ,例：例：多项式求值多项式求值. .给定的给定的x 求下列求下列n 次多项式的值。次多项式的值。 nnxaxaxaaxP 2210)(解：解：1. 1. 用一般算法，即直接求和法；用一般算法，即直接求和法； 2. 2. 逐项求和法；逐项求和法；3. 3. 秦九韶方法；秦九韶方法；算法的递推性算法的递推性计算机上使用的算法常采用计算机上使用的算法常采用递推化递推化的形式，递推化的形式，递推化的基本思想是把一个复杂的计算过程归结为简单过的基本思想是把一个复杂的计算过程归结为简单过程的多次重复。这种重复在程序上表现为循环