数值计算第一章引论

1、数值分析数值分析 一、什么是数值分析一、什么是数值分析 数值分析是计算数学的一个主要部分,计算数学是数 学科学的一个分支,它研究用计算机求解各种数学问题 的数值计算方法及其理论与软件实现. 实际问题实际问题数学模型数学模型数值计算方法数值计算方法 程序设计程序设计上机计算求出结果上机计算求出结果 第第1 1章章 绪论绪论 1 数值分析的研究对象与特点数值分析的研究对象与特点 二、数值分析的基本内容二、数值分析的基本内容 1 1、数值逼近、数值逼近 插值法 函数逼近与曲线拟和 数值积分与数值微分 2 2、数值代数、数值代数 线性代数问题(方程组和特征值) 非线性方程(组)数值解法 3 3、常微方

2、程数值解法和偏微方程数值解法、常微方程数值解法和偏微方程数值解法 三、数值分析的特点三、数值分析的特点 , 1 ) 1( 3 1 2 1 12ln 1 n n ). 3 1 7 1 3 1 5 1 3 1 3 1 3 1 (22ln 753 vs , 32 )1ln( 32 xx x x 1 1、面向计算机、面向计算机 2 2、可靠的理论分析、可靠的理论分析, ,保证收敛性、稳定性保证收敛性、稳定性 3 3、良好的计算复杂性、良好的计算复杂性 4 4、数值实验、数值实验 Cramer法则 vs Gauss消去法. 3 1 ln1 2() 3 1 3 x x x x x 取 四、如何学好数值分析

3、四、如何学好数值分析 1 1、注意掌握基本原理、处理技巧，误差分析、注意掌握基本原理、处理技巧，误差分析 3 3、积极动手上机实践、积极动手上机实践 2 2、注重实际问题，练习、作业、注重实际问题，练习、作业 五、教学参考书五、教学参考书 数值计算引论 白峰杉 高等教育出版社 科学和工程计算基础 施妙根等 清华大学出版社 数值分析，易大义等编，浙江科学技术出版社 数值方法教程，刘钦圣等编 , 冶金出版社,1998 计算方法，秦林祥等编, 兵器工业出版社,1992 数值分析基础，关治等编 , 高教出版社,1998 一、误差来源、分类一、误差来源、分类 观测误差观测误差 截断误差截断误差或方法误差

4、方法误差 模型误差模型误差 2 数值计算的误差数值计算的误差 截断误差： n n n x n f x f x f fxPxf ! )0( ! 2 )0( ! 1 )0( )0()()( )( 2 1 ) 1( )!1( )( )( n n n x n f xR 舍入误差舍入误差 .0000026. 014159. 3R数制转换、机器数. 在用数值方法解题过程中可能产生的误差归 纳起来有如下几类： 1. 模型误差 2. 观测误差 3. 截断误差 4. 舍入误差 误差误差误差误差误差误差 用数学方法解决一个具体的实际问题，首先要建立 数学模型，这就要对实际问题进行抽象、简化，因 而数学模型本身总含

5、有误差，这种误差叫做模型误 差 数学模型是指那些利用数学语言模拟现实而建立起 来的有关量的描述 数学模型的准确解与实际问题的真解不同 实际问题的实际问题的 真解真解 数学模型的数学模型的 真解真解 为减化模型忽略次要为减化模型忽略次要 因素因素 定理在特定条件下建立与实定理在特定条件下建立与实 际条件有别际条件有别 模型误差模型误差 在数学模型中通常包含各种各样的参变量，如温度、 长度、电压等，这些参数往往是通过观测得到的， 因此也带来了误差，这种误差叫观测误差 数学模型中的参数和原始数据，是由观测和试验得 到的 由于测量工具的精度、观测方法或客观条件的限制, 使数据含有测量误差,这类误差叫做

6、观测误差或数据 误差 根据实际情况可以得到误差上下界 数值方法中需要了解观测误差,以便选择合理的数值 方法与之适应 观测误差观测误差 精确公式用近似公式代替时,所产生的误差叫截断误 差 例如, 函数f(x)用泰勒(Taylor)多项式 截断误差截断误差 n n n x n f x f x f fxp ! )0( ! 2 )0( ! 1 )0( )0()( )( 2 1 ) 1( )!1( )( )()()( n n nn x n f xpxfxR （介于0与x之间） 近似代替，则数值方法的截断误差是近似代替，则数值方法的截断误差是 p 截断误差的大小直接影响计算结果的精度和计算截断误差的大小直

7、接影响计算结果的精度和计算 工作量，是数值计算中必须考虑的一类误差工作量，是数值计算中必须考虑的一类误差 在数值计算中只能对有限位字长的数值进行 运算 需要对参数、中间结果、最终结果作有限位 字长的处理工作，这种处理工作称作舍入处 理 用有限位数字代替精确数，这种误差叫做舍 入误差，是数值计算中必须考虑的一类误差 舍入误差舍入误差 误差误差误差误差误差误差 例例如在计算时用如在计算时用3.141593.14159近似代替近似代替 ， 产生的误差产生的误差R= R= -3.14159=0.0000026-3.14159=0.0000026 就是舍入误差。就是舍入误差。 上述种种误差都会影响计算结

8、果的准确上述种种误差都会影响计算结果的准确 性，因此需要了解与研究误差，在数值计算性，因此需要了解与研究误差，在数值计算 中将着重研究截断误差、舍入误差，并对它中将着重研究截断误差、舍入误差，并对它 们的传播与积累作出分析们的传播与积累作出分析 二、误差、有效数字二、误差、有效数字 定义定义1 1 绝对误差，绝对误差，简称误差：误差： .* ,*的近似值为准确值其中xxxxe 误差限：误差限：.|*|*的一个上界e 相对误差：相对误差： , * * x e er 相对误差限：相对误差限：.| * 的一个上界 rr e . * * * x e er或 5 . 0765 x例如，毫米尺 5.100

9、0 1,10 yx例如， 0.5%. | %,10 | * * yx y x .000008. 0 ,1416. 3 ,002. 0 ,14. 3 ,1415926. 3 * 5 * 5 * 3 * 3 x x x 取五位 取三位 定义定义2 2 .* ,* 有效数字有效数字位有位，就说的第一位非零数字共有到 该位的半个单位的误差限是某一位数字若近似值 nxnx x 例例1 1 42.195, 0.0375551, 8.00033 8.00033, 2.71828,按四舍五 入写出上述各数具有四位有效数字的近似数. (2.2) 10 2 1 * . 0 (2.1) )1010(10* 1 1

10、) 1(1 21 nm n n m xx a aaax 并且其中 即 例例2 2 考察三位有效数字重力加速度g, 若以m/s2为单位, g9.80m/s2, 若以km/s2为单位, g0.00980km/s2, ,10 2 1 80. 9g 2 3. 0, ) 1 . 2(nm，按 ,10 2 1 00980. 0g 5 3. , 3 ) 1 . 2(nm，按 .10 2 1 2* 1 绝对误差限 .10 2 1 5* 2 绝对误差限 .0.00980/0.0000050.005/9.80 * r 而相对误差限相同： 1 10 2 1 * nm 30 4 1 0.00009260.5 100.

11、5 10 xx 解解1：若取近似值x*=3.1415，绝对误差是0.0000926，有 ， 即m=0,n4，故近似值x*=3.1415只有4位有效数字 解2：x*3.1415的绝对误差限绝对误差限0.0005，它是x的小数后第第3位位 的半个单位，故近似值x*=3.1415准确到小数点后第3位 故近似值x*=3.1415只有4位有效数字 例例3 设x= =3.1415926，求x*=3.1415的近似值及有效数字 1(1) 12 1 *(1) 1 * *10(1010) (2.1) 0 . * 1 10 2 mn n n r x xaaa axn a 设近似数表示为 其中若具有 位有效数字，则

12、其相对误差限为 ； 定理定理 *(1) 1 1 * 10* 2(1) . n r xx a n 反之， 若的相对误差限为，则 至少具有 位有效数字 200.1%要使的相对误差限小于，要取几位有效数字？例例4 4 1 1 1 10 2 n a 1 *11 1 204.4,4 1 100.125 100.1%4 2 nn r a n a 只要取 解：解：设取n位有效数字，相对误差限*r= ， 1 3 1 100.0025 22 16 1 10= 0.000 000 56 29 例例5 指出下列各数具有几位有效数字，及其绝对误差限和相 对误差限： 0.002 009 000.00 解解 因为x1*=

13、0.002 00， m=3 绝对误差限0.000 005= 因为m=3，n=3， x1*= 0.002 00有3位有效数字. a1=2， 相对误差限r= x2*=9 000.00，绝对误差限0.005，因为m=3，n=6，x2*=9 000.00 有6位有效数字，相对误差限为r 如果认为小数点后边的0无用，将9 000.00随便写作9000 9103，那么它的绝对误差就是=0.5=0.51034+1，即m=3， n=4，表明这个数有4位有效数字 可见，小数点之后的0，不是可有可无的，它是有实际 意义的. 53 3 11 0.5 100.5 100.5 10 m n 三、数值运算的误差估计三、数

14、值运算的误差估计 * 1212 ,x xxx四则运算，设为准确值为近似值，则：误差限 . | )(|)(| )/( ),(|)(|)( ),()()( 2* 2 * 1 * 2 * 2 * 1 * 2 * 1 * 1 * 2 * 2 * 1 * 2 * 1 * 2 * 1 * 2 * 1 x xxxx xx xxxxxx xxxx ,*, ,*)(*)*)(*)()( ,*,)( 2 2 )( 之间在 公式由为近似值为准确值，一元函数 xxxxxxxfxfxf Taylorxxxf f *).(|*)(|*)( *)( xxfxf xf 的误差限得 ).(*)( ),( ,),( * 1 *

15、* 1 1 * 11 k n kk n nnn x x f f xxf xxxxxxf 的误差限同理得 的近似值为准确值，多元函数 * (8) ( *)( *)( *). sld ss sld ld 场地面积：书上第 页例例6 6 ABC *(1000.10) , *(1200.10) , *(600.02) ,ABCS o bm cm A 例 设观测数据为 试估计面积 的绝对误差限和相对误差限。 2 1 sin 2 ()( )( )() 11 sin0.1sin0.1 22 1 cos0.0210.57 2180 SbcA SSS SbcA bcA cAbA bcAm 解由则 3 ( )10

16、.57 |( )| |2.035 10 1 sin 2 r s s s bcA 误差分析简介误差分析简介 向后误差分析法 区间分析法 概率分析法 3 误差定性分析、避免误差危害误差定性分析、避免误差危害 ).,( ),( 11 1 nnfl n aagx aagx ， xy yx , 一、病态问题与条件数一、病态问题与条件数 . , , )( )( )( )(*)( 条件数称为计算函数值问题的 考虑计算函数值问题 p p xf xf x x x xf xfxf C C %.24%,2 ,24. 1)02. 1 (, 1) 1 (,10,)( 10 函数值相对误差为误差为 自变量相对例如ffCx

17、xf p .10认为是病态一般 p C .,考虑是否病态条件数其他计算问题也要考虑 二、算法的数值稳定性二、算法的数值稳定性 考虑初始数据误差在计算中的传播问题. . 1 1 0 7 d , 0,1, . nx n Iex ex n 计算并估计误差例例 , ,. 舍入义一个算法若输入数据有误差 而在计算过程中 不增长 则称此算法是数值稳定的 否则是不误差稳定的 定定3 3 , 2 , 1 ,1 1 nnII nn ., 2 , 1 ,1 ,6321. 0 )( 1 0 nInI I A nn .1 1 0 eI . 1 , 8 , 9 ),1 ( ,0684. 0 )( * 1 * 1 * 9

18、 nII I B n n n )0684. 0) 1010 1 ( 2 1 ( 1 9 e I 控制递推公式中误差的传播控制递推公式中误差的传播 对于一个数学问题的求解往往有多种数值方法对于一个数学问题的求解往往有多种数值方法 在选择数值方法时，要注意所用的数值方法不应将在选择数值方法时，要注意所用的数值方法不应将 计算过程中难以避免的误差放大的较快，造成计算计算过程中难以避免的误差放大的较快，造成计算 结果完全失真。结果完全失真。 例例 计算积分计算积分 并估计误差并估计误差 解解 容易得到递推公式容易得到递推公式 1 0 (0,1,2,10) 10 n n x Idxn x 1 . 1ln

19、)10ln( 10 11 0 1 0 0 xdx x I 1.1ln)10ln( 10 11 0 1 0 0 xdx x I 1 0 1 1 0 1 1 0 11 1 0 10 10 10 10 10 1010 10 dx x x dx x xx dx x xxx dx x x I nnnnnnn n 1 1 0 1 1 0 1 10 1 10 10 n n n I n dx x x dxx )10, 2 , 1(n 即即 为为 n I 1 1 1 0(1, 2 ,1 0 ) nn IIn n (1,2,10)n 则准确的理论递推式则准确的理论递推式 实际运算的递推式实际运算的递推式 两式相减

20、有两式相减有 01 101II * 0 * 1 101II )(10)(10 * 0 * 00 * 11 IeIIII *2* 112200 ( )10()( 10) ()( 1) 10 () nn nnnnnnn e IIIIIIIII 这就是说这就是说, ,若若 与与 的误差为的误差为 = = - , ,即即 ，则误差的递推规律为，则误差的递推规律为 0 I * 0 I)( * 0 Ie 0 I * 0 I )( * 0 * 00 IeII 于是于是 )(10)(10)(10)( * 0 10* 8 2* 9 * 10 IeIeIeIe 计算计算 时的误差被扩大了时的误差被扩大了 倍倍,

21、,显然算法是显然算法是 数值不稳定的。数值不稳定的。 如果将递推公式如果将递推公式 变换一种形式变换一种形式 * 10 I 10 10 1 10 1 nn I n I 1010 1 1 n n I n I 准确的理论递推式准确的理论递推式 实际运算的递推式实际运算的递推式 从而有从而有 1010 1 1 n n I n I 1010 1 * * 1 n n I n I )( 10 1 * 11nnnn IIII )( 10 ) 1( )( 10 1 )( 10 1 * 22 2 * 11 * 00nn n n IIIIIIII 即即 )( 10 1 )( 10 1 )( 10 1 )( * 1

22、0 10 * 2 2 * 1 * 0 IeIeIeIe于是有于是有 则这个算法的误差传递规律为则这个算法的误差传递规律为 * * 1 () () 10 n n e I e I 即每计算一步的误差的绝对值是上一步的十分即每计算一步的误差的绝对值是上一步的十分 之一，误差的传播逐步缩小，得到很好的控制，这之一，误差的传播逐步缩小，得到很好的控制，这 个算法是数值稳定的个算法是数值稳定的 算法的数值稳定性 算法优劣的标准 从截断误差观点看,算法必须是截断误差小, 收敛敛速要快。即运算量小,机器用时少. 从舍入误差观点看,舍入误差在计算过程中要 能控制,即算法的数值要稳定. 从实现算法的观点看,算法的

23、逻辑结构不宜太 复杂，便于程序编制和上机实现. 设计算法时应遵循的原则 要有数值要稳定性,即能控制误差的传播. 避免大数吃小数,即两数相加时,防止较小的 数加不到较大的数上. 避免两相近的数相减,以免有效数字的大量丢 失. 避免分母很小(或乘法因子很大),以免产生溢 出. 三、避免误差危害的若干原则三、避免误差危害的若干原则 除了分清问题是否病态和算法是否数值稳定外,还要 考虑避免误差危害和防止有效数字损失的如下原则. 1.避免大数除以小数 例例8 仿计算机，采用3位十进制，用消元法求解方程组 5 1.00 101.001.00 1.001.002.00 xy xy )1000. 100. 2

24、()1000. 100. 1 ( 00. 100. 11000. 1 55 5 y yx x，得消 00. 1 00. 100. 11000. 1 5 y yx 00. 1* ,00. 0* yx 解：解： 错.为什么,怎么办？ 9999899. 0 00001. 1 5 5 5 5 101 102 101 10 y x 5 10) 1 () 2( 减少运算误差原则减少运算误差原则 2 2、两个相近的数相减，会严重损失有效数字、两个相近的数相减，会严重损失有效数字 例如例如x =1958.75x =1958.75，y =1958.32y =1958.32都具有五位都具有五位 有效数字，但有效数

25、字，但x-y=0.43x-y=0.43只有两位有效数字只有两位有效数字 通常采用的方法是改变计算公式通常采用的方法是改变计算公式, ,例如当与例如当与 很接近时很接近时, ,由于由于 2 1 21 lglglg x x xx 用右端代替左端公式计算用右端代替左端公式计算, ,有效数字就不会损失有效数字就不会损失 减少运算误差原则减少运算误差原则 当当x很大时可作相应的变换很大时可作相应的变换 xx xx 1 1 1 ) 1(1 1 ) 1( xx arctgarctgxxarctg 则用右端来代替左端。则用右端来代替左端。 减少运算误差若干原则减少运算误差若干原则 当当x接近接近0 0时时 x

26、 x x x sin1 sin sin cos1 一般情况，当一般情况，当f(x)f(xf(x)f(x* *) )时，可用泰勒展开时，可用泰勒展开 2* )( ! 2 )( )()()(xx xf xxxfxfxf 取右端的有限项近似左端。取右端的有限项近似左端。 如果计算公式不能改变，则可采用增加有效位如果计算公式不能改变，则可采用增加有效位 数的方法保证精度数的方法保证精度 2 12 1610. x863 ,863 xx x 求解例例9 9 7 2 A10 1 cos2 . 1 cos2sin 2 x x 。 计算（）例例1010 xx xx 1 1 1 12301. 001. 001.

27、001. 001. 001. 0123 100100 项项 例例11 仿计算机在3位十进制下， 、防止防止大数大数吃吃小数小数 例 求二次方程x2-105x+1=0的根 解：按二次方程求根公式 x1=(105+(1010-4)1/2)/2 x2=(105-(1010-4)1/2)/2 在8位浮点数计算得 x1=(105+105 )/2=105 (正确）, x2=(105-105 )/2=0 (错误） 产生错误的原因 出现大数1010吃掉小数4的情况 分子部分出现两个相近数相减而丧失有 效数位常称为灾难性的抵消 4、绝对值太小的数不宜做除数 当分母为两个相近数相减时,会丧失有效数字 4 ()()

28、 10 () 0.14560.14550.0001 分子分子 分子 这里分子的误差被扩大这里分子的误差被扩大104104倍倍, ,再如再如 若将分母变为若将分母变为0.0011,0.0011,即分母只有即分母只有0.00010.0001的变化的变化 时时, ,计算结果却有了很大变化计算结果却有了很大变化 减少运算误差若干原则减少运算误差若干原则 3.1415 3141.5 0.001 9 .2855 0011.0 1415.3 例 计算 0135. 00125. 00003. 0 0012. 00143. 00005. 0 D 解: 分子分母分别计算后相除(取9位小数) A=0.0005*0.

29、0143*0.0012=0.00000715*0.0012 =0.000000009(有舍入) B=0.0003*0.0125*0.0135=0.00000375*0.0135 =0.000000051(有舍入) D=A/B=0.17647 真值为0.16948148，所以D只准确到小数后一位 减少运算误差若干原则减少运算误差若干原则 算法2。分成三组因子。每组只取六位小数计算 a=0.0005/0.0003=1.666667(有舍入) b=0.0143/0.0125=1.144000 c=0.0012/0.0135=0.088889 (有舍入) D=a*b*c=1. 666667* 1.144000* 0.088889 =0.169482,准确到小数后5位。 0135.00125.00003.0 0012.00143.00005.0 D b bc ca a 减少运算误差若干原则减少运算误差若干原则 5、简化计算步骤，减少运算次数减少运算次数可 以不但节省时间，而且减少舍入误差 例：x255=xx2x4x8x16x32x64x128 原先要做254次乘法现只需14次即可 例 如计算多项式 p(x)=anxn an-1xn-1 a1x a0 的值 若直接计算ak