第1章 - 数值计算的基本概念

1、121 1 数值计算（分析）的对象与特点数值计算（分析）的对象与特点数值分析：根据实际问题，抽象出数学模型，提出并研究求解数值分析：根据实际问题，抽象出数学模型，提出并研究求解的数值计算方法（算法），计算并进行误差分析。的数值计算方法（算法），计算并进行误差分析。为了更具体地为了更具体地说明数值分析说明数值分析的研究对象，的研究对象，我们考察用计我们考察用计算机解决实际算机解决实际问题时经历的问题时经历的几个过程：几个过程：认识实际问题数值计算方法数学模型程序设计上机计算结果要求要求(特点特点)：实际可行、实际可行、理论可靠、理论可靠、计算复杂性好计算复杂性好3认识实际问题数值计算方法数学模型

2、程序设计上机计算结果观测误差观测误差模型误差模型误差截断误差截断误差舍入误差舍入误差结论：结论：构造算法的基本手段：构造算法的基本手段：近似近似 研究算法的核心问题：近似对计算的影响研究算法的核心问题：近似对计算的影响误差分析误差分析4（2 2）数值计算本身的特点）数值计算本身的特点 离散化：离散化：计算离散点上的近似值；计算离散点上的近似值；有可靠的理论分析；有可靠的理论分析； 算法理论主要是连续系统的离散化数值求解。算法理论主要是连续系统的离散化数值求解。 构造性：构造性：方法的构造，解的存在唯一性的证明。方法的构造，解的存在唯一性的证明。 递推性：递推性：复杂计算过程转化成简单的计算过程

3、的多次复杂计算过程转化成简单的计算过程的多次重复（适合计算机计算）。重复（适合计算机计算）。 近似替代：近似替代：在误差允许的范围内，无限次的计算用有在误差允许的范围内，无限次的计算用有限次计算替代。限次计算替代。 模拟仿真：模拟仿真：可通过计算机的仿真实验验证实际的工程可通过计算机的仿真实验验证实际的工程计算。计算。52 误差与有效数字误差与有效数字误差种类与来源误差种类与来源(以计算地球表面积可以用公式以计算地球表面积可以用公式 为例为例) 模型误差模型误差 数学模型是实际问题的抽象和简化，其间存在误差。数学模型是实际问题的抽象和简化，其间存在误差。( (地球堪称一个圆地球堪称一个圆) )

4、 观测误差观测误差（或称测量误差）（或称测量误差） 由数据观测产生的误差。由数据观测产生的误差。( (地球半径的测量地球半径的测量) ) 截断误差截断误差（或方法误差）（或方法误差）由于问题不能精确求解，近似计算的方法所引起。由于问题不能精确求解，近似计算的方法所引起。( ( 只能截断才能计算只能截断才能计算) ) 舍入误差舍入误差计算机实现计算时，机器的有限字长所造成。计算机实现计算时，机器的有限字长所造成。( (计算中的数据舍入计算中的数据舍入) )24Ar6一、误差的基本概念一、误差的基本概念1. 1. 绝对误差绝对误差定义：定义： 设某量的准确值为设某量的准确值为x， 是是 x 的近似

5、值，称的近似值，称x( )e xxx若，x称 为 的绝对误差限绝对误差限。.xxxx x 即，在应用上常记为例例3.14159263.1416( ),e41( )10 .2e通常通常x是未知的，故是未知的，故 未知未知 ，但一般地，但一般地 已知。已知。 )(xe绝对误差不是误差的绝对值，即绝对误差不是误差的绝对值，即 可正可负。可正可负。)(xex为为 的的绝对误差绝对误差。( )e xxx7例：设例：设 ，估计，估计近似数近似数 的绝对误差与相对误差。的绝对误差与相对误差。解：解：但是但是 是是 的一个好的近似，的一个好的近似， 不是不是 的一个好的近似。的一个好的近似。定义：设某量的准确

6、值为定义：设某量的准确值为x， 是是x 的近似值，则的近似值，则称绝对误差称绝对误差与准确值之比与准确值之比 为为 的相对误差。的相对误差。若若 ，称，称 为为 的相对误差限。的相对误差限。2. 2. 相对误差相对误差x( )( )re xxxe xxx( )rxxe xxxx12121.234,0.002,1.233,0.001xxxx12,x x33111222()10()10 ,e xxxe xxx，1x1x2x2x33121010()0.81%()50%.1.2340.002rre xe x，8 是一个无量纲的数，是一个无量纲的数， ，x一般是未知一般是未知 的，所以的，所以 难求。难

7、求。 考察量考察量 近似数的相对误差是近似数精确度的基本度量，一个近似近似数的相对误差是近似数精确度的基本度量，一个近似数的相对误差越小，则近似数越精确。数的相对误差越小，则近似数越精确。结论结论: :( )( )re xxxe xxx( )re x( )( )re xxxe xxx( )rex*2*( )( )( )( )( )( )( )( )rre xe xx e xxe xexe xe xxxx xxxe x 较小时较小时)(xer 22*( )()( )0( )1( )1rre xe xxe xe xx 通常将通常将 作为作为 的相对误差。的相对误差。( )( )re xxxe xx

8、xx 相对误差限相对误差限是未知的，但可以确定是未知的，但可以确定9 浮点数浮点数根据国际标准根据国际标准IEEE 754IEEE 754，任意一个二进制浮点数，任意一个二进制浮点数V V可以可以表示成下面的形式：表示成下面的形式： V = (-1)aM2s（1）(-1)a表示符号位，当表示符号位，当a=0，V为正；当为正；当a=1，V为负。为负。（2）M=d1d2dt表示有效数字，大于等于表示有效数字，大于等于1，小于，小于2。（3）2s表示指数位。表示指数位。例：十进制的例：十进制的5.0，写成二进制是，写成二进制是101.0，相当于，相当于1.0122。那么，按照上面那么，按照上面V的格

9、式，可以得出的格式，可以得出s=0，M=1.01，s=2。 3 3 浮点数与舍入误差浮点数与舍入误差10 浮点数浮点数Matlab Matlab 中使用中使用IEEE IEEE 双精度二进制数，用双精度二进制数，用6464位存贮一个数位存贮一个数对于对于64位的浮点数，最高的位的浮点数，最高的1位是符号位位是符号位a，接着的，接着的11位位是指数阶码是指数阶码s，剩下的，剩下的52位为有效数字位为有效数字M（尾数）。（尾数）。 111) 1) 浮点数浮点数 前面说过，1M2，也就是说，M可以写成1.xxxxxx的形式，其中xxxxxx表示小数部分。IEEE 754规定，在计算机内部保规定，在计

10、算机内部保存存M时，默认这个数的第一位总是时，默认这个数的第一位总是1，因此可以被舍去，只保，因此可以被舍去，只保存后面的存后面的xxxxxx部分。部分。比如保存1.01的时候，只保存01，等到读取的时候，再把第一位的1加上去。这样做的目的，是节省1位有效数字。IEEE标准的双精度：其中：指数满足：5252121,01;02210221023exfMfffe 122) 2) 舍入误差舍入误差 实数中的绝大部分在计算机上总不能精确表出，总要实数中的绝大部分在计算机上总不能精确表出，总要“舍舍”或或“入入”而由一个与之相近的浮点数表示，由此而而由一个与之相近的浮点数表示，由此而引起的误差称为引起的

11、误差称为舍入误差。舍入误差。 真正理解舍入误差，特别是它在算法中的传播及最终真正理解舍入误差，特别是它在算法中的传播及最终对计算结果的影响，是初步具备科学计算能力的重要标志。对计算结果的影响，是初步具备科学计算能力的重要标志。 随着符合运算的发展特别是软件工具的日趋普及，微随着符合运算的发展特别是软件工具的日趋普及，微分的计算有了新的有力工具，但数值微分的地位并没有因分的计算有了新的有力工具，但数值微分的地位并没有因此而有任何下降。对一些大规模的问题，特别是函数关系此而有任何下降。对一些大规模的问题，特别是函数关系不是直接由解析表达式给出时，数值微分更是不可替代的。不是直接由解析表达式给出时，

12、数值微分更是不可替代的。13212!nxxxexn 4 截断误差截断误差 在计算过程中，用有限的查分替代无限的极限过程，在计算过程中，用有限的查分替代无限的极限过程，称为算法的截断误差。称为算法的截断误差。例如，在计算指数函数例如，在计算指数函数的值时，常用到如下幂级数展开的值时，常用到如下幂级数展开式：式：这是一个无穷级数。计算时，只能取有限项。这是一个无穷级数。计算时，只能取有限项。2( )12!nnxxSxxn 用有限项逼近无穷级数，会产生一个误差，这个误差用有限项逼近无穷级数，会产生一个误差，这个误差就是一种截断误差。就是一种截断误差。14则从最后一位则从最后一位 到第一位非零数字到第

13、一位非零数字 为为 的有效数字（共的有效数字（共n n位）位）二、有效数字二、有效数字x设设 x 为准确值，为准确值， 为为 x 的近似值且的近似值且 表示为表示为 xx，是是整整数数）（)(10). 0(11maaxmn 的绝对误差的绝对误差满足满足x其中其中 为为 0, 1, , 9 0, 1, , 9 中的一个数字。中的一个数字。120,naaanmxx 10212 ）（误差不超过误差不超过m-n位的半个单位位的半个单位na1a15有效数字有效数字 我们还可以用有效数字的概念来说明一个近似值的我们还可以用有效数字的概念来说明一个近似值的准确程度。准确程度。 我们先介绍我们先介绍“四舍五入

14、四舍五入”的概念，四舍五入是数值的概念，四舍五入是数值计算时，取近似值的一种方法。若被舍去部分的头一位计算时，取近似值的一种方法。若被舍去部分的头一位大于等于大于等于5时，就在所取数的末位加时，就在所取数的末位加1；小于；小于5时，就舍去。时，就舍去。 用四舍五入方法得到的近似值，称为有效数字。用四舍五入方法得到的近似值，称为有效数字。 有效数字的末位到第一位非零数字的个数，称为该有有效数字的末位到第一位非零数字的个数，称为该有效数字的位数。效数字的位数。 有效数字可用来表示一个近似值的准确程度，一个近有效数字可用来表示一个近似值的准确程度，一个近似值的有效位数越多，这个近似值就越逼近真值似值

15、的有效位数越多，这个近似值就越逼近真值。161)3.14 2)3.1416 3)3.1415 0.00159260.005 2) 0.000007ee 1解：） 是按四舍五入原则得到的，有三位有效数字。 小于百分位上的半个单位。准确到百分位。从这一位到个位（第一位非零数字）有三位。 有三位有效数字。30.00005 小于万分位上的半个单位。准确到万分位。从万分位 到个位有五位。有五位有效数字。例：圆周率例：圆周率是一个无理数，是一个无理数，=3.14159265358979323，考察下列近似值的有效位数。，考察下列近似值的有效位数。17 3 3） 的万分位不是按四舍五入规则得到的，因此的万分

16、位不是按四舍五入规则得到的，因此有四位有效数字，而不是五位有效数字。有四位有效数字，而不是五位有效数字。0.00009260.0005e小于千分位上的半个单位，从千分位到个位有四小于千分位上的半个单位，从千分位到个位有四位。位。精确到千分位。精确到千分位。3.14163.1416有五位有效数字有五位有效数字，准准确到万分位。确到万分位。3.1415有四位有效数字，准确到千分有四位有效数字，准确到千分位。这就是位。这就是的近似值采用的近似值采用3.1416而不采用而不采用3.1415的原因。的原因。18 一个十进制数近似值的有效数字，不受单位制的影响。如一个十进制数近似值的有效数字，不受单位制的

17、影响。如29.81gm s作为作为g的近似值，与的近似值，与20.00981gkm s均为均为3 3位有效数字。位有效数字。有效数字与绝对误差有一定的关系。对于某量的近似值，当有效数字与绝对误差有一定的关系。对于某量的近似值，当一定时，越大，有效位数越多，则绝对误差限越小。一定时，越大，有效位数越多，则绝对误差限越小。80000.8*2*1 xx，例例 设设 考虑考虑44110.33 10102xx，8.000033x 4210.33 102xx( 在有效数意义下，不同的有效数位数的近似值的近似精度是在有效数意义下，不同的有效数位数的近似值的近似精度是不同的。如不同的。如10.4200的精度高

18、于的精度高于10.42)19定理（有效数字与相对误差的关系）：定理（有效数字与相对误差的关系）：*121210(101010 )mnnxaaa 设近似值设近似值x*表示为表示为若若x*具有具有n位有效数字，则其相对误差限为位有效数字，则其相对误差限为*(1)11102nrreexa反之，若反之，若x*的相对误差限的相对误差限*(1)111021nrea则则x*至少具有位有效数字。至少具有位有效数字。201*11110(1) 10mmaxa*(1)111110*1210*102m nnrmxxxaa*1(1)111*(1) 10102(1)mnrxxxaa1102m n 证明证明：由由x*的表达

19、式可得：的表达式可得：又由定义可知又由定义可知1102m nxx有效数位越多，相有效数位越多，相对误差越小对误差越小所以所以反之，则有：反之，则有：因此，因此， x*具有具有n位有效数字。位有效数字。21例：为使的近似值例：为使的近似值 的相对误差小于的相对误差小于1%，问需要取多少位，问需要取多少位有效数字？有效数字？5解：解：5的近似值的首位数字的近似值的首位数字12,a于是由于是由11100.0122nre可解得可解得2.4n 。因此，可取因此，可取 即即3,n 52.24。22小结：概念小结：概念 模型误差模型误差 观测误差观测误差 截断误差截断误差 舍入误差舍入误差 绝对误差绝对误差

20、 相对误差相对误差 绝对误差限绝对误差限 相对误差限相对误差限 浮点数浮点数 有效数字（与四舍五入的关系）有效数字（与四舍五入的关系） 有效数字的绝对误差有效数字的绝对误差 有效数字与相对误差的关系有效数字与相对误差的关系越多越小越多越小23例计算，例计算， 并估计误差。并估计误差。3 算法的稳定性与病态问题算法的稳定性与病态问题一个算法如果输入数据有误差，而在计算过程中舍一个算法如果输入数据有误差，而在计算过程中舍入误差不增长，则称此算法是数值稳定的，否则称入误差不增长，则称此算法是数值稳定的，否则称此算法为不稳定的。此算法为不稳定的。一、算法稳定性定义一、算法稳定性定义1111100()1

21、(1,2,)nxnxnnIex enxe dxnIn 1110010.6321xIee dxe 110(0,1,)nxnIex e dx n由分步积分公式，可得由分步积分公式，可得24nn00.632150.148010.367960.112020.264270.216030.20748-0.718040.170497.552可以计算出下表：可以计算出下表：按递推关系按递推关系010.63211nnIInI25111110001011(min)(max)11xnxnnxxeeex dxIeex dxnn 1911010eI1*9911()0.064842 1010eII现将递推公式改写为现将递

22、推公式改写为： ，并且取，并且取11(1)nnIIn于是，取于是，取n=9，则有，则有因此，可得新的递推公式：因此，可得新的递推公式：于是，取于是，取n=8，则有，则有18199eI8=-0.7180I9=7.552I*9*10.064841(1)nnIIIn26nn00.632150.145510.367960.126820.264370.112130.207380.103540.170890.0684由上面的递推公式，可得到下面的计算结果：由上面的递推公式，可得到下面的计算结果： 第二种方法比第一种方法计算稳定。第二种方法比第一种方法计算稳定。对对比比结结论论与与分分析析nnnEII1nn

23、EnE *nnnEII*11nnEEn 对于第一种方法，设对于第一种方法，设，则有，则有因此，误差是逐次放大的因此，误差是逐次放大的。 对于第二种方法，设对于第二种方法，设，则有，则有因此，误差是逐次缩小的因此，误差是逐次缩小的。27nn00.632150.148010.367960.112020.264270.216030.20748-0.718040.170497.552nn00.632150.145510.367960.126820.264370.112130.207380.103540.170890.068428设设 ，则，则 ，即对于该函数，误差会被放大，即对于该函数，误差会被放大n

24、 n倍。倍。二、病态问题与条件数（针对问题本身）二、病态问题与条件数（针对问题本身）*( )( )()( )( )pxfxf xf xxCf xxf x定义：输入数据的微小变动导致输出数据的较大误差，定义：输入数据的微小变动导致输出数据的较大误差，就被称为病态问题。就被称为病态问题。衡量是否病态的标准：条件数衡量是否病态的标准：条件数 对于函数值计算问题，条件数定义为：对于函数值计算问题，条件数定义为： 不同的问题，条件数具体定义不同。不同的问题，条件数具体定义不同。一般情况下，条件数大于一般情况下，条件数大于1010，就认为问题病态。，就认为问题病态。( )nfxxpCn通过构造特殊算法来解

25、决通过构造特殊算法来解决2911123111234111345A例例 设有方程组设有方程组AxbAb已知系数已知系数x测量数据测量数据待求数据待求数据其中其中A为为 ，若测量数据为准确数据，若测量数据为准确数据，即即 ，那么很容易计算，那么很容易计算4711 13,6 12 60Tb1231xxx如果测量数据不够精确，即测量数据仅保留了如果测量数据不够精确，即测量数据仅保留了2 2位有效数字，位有效数字，即即 ，计算结果为，计算结果为1.8 1.1 0.78Tb 0, 6,3.6Tx 以上问题称为病态的问题，病态是问题本身固有的。以上问题称为病态的问题，病态是问题本身固有的。304 4 计算机

26、计算的几个问题与算法设计原则计算机计算的几个问题与算法设计原则一、减少运算次数一、减少运算次数 不仅能提高计算精度，而且能减少误差的积累不仅能提高计算精度，而且能减少误差的积累1 1、对同一种算法（计算方法），要选用计算量少的运算次序、对同一种算法（计算方法），要选用计算量少的运算次序例如例如(),abacada bcd32axbxcxd4. 4. 运算方案能否控制误差的传播和积累以保证计算结果有足够运算方案能否控制误差的传播和积累以保证计算结果有足够的精度（数值稳定性）的精度（数值稳定性）. .数值计算的一般标准：数值计算的一般标准：2. 2. 运算过程是否规律（易编程）；运算过程是否规律（

27、易编程）；3. 3. 需要记录的中间结果的多少（储存量）；需要记录的中间结果的多少（储存量）；(),axb xc xd1. 1. 运算次数的多少（计算效率）；运算次数的多少（计算效率）；31例题：计算多项式例题：计算多项式 的值。的值。nna xn计算需作 次乘法，(1)( )(1)21;2nn npxnn 计算的值需作乘法次数：. n加法次数：(b) 利用秦九韶算法：利用秦九韶算法：解：解：(a)直接计算每一项再求和：直接计算每一项再求和：,1, 2,111;( ), ().nnnkn nkkkSap xSxSa计算的递推公式：0( ),nSp x则( )npxnn计算的值只需作次乘法 次加

28、法。110( ) () nnnp xx xx a xaaa1110( )nnnnnpxa xaxa xa32(a) 用级数用级数 来计算来计算231ln(1) 1( 1)( 1,1)23nnxxxxxn 2、对于不同的算法，要注意收敛速度，讲效率、对于不同的算法，要注意收敛速度，讲效率1111ln21123nnSn 71ln210 ,1nSn例例 计算计算 ln2 ln2 的近似值，要求误差小于的近似值，要求误差小于1010 . .解：解：取取x=1，则得，则得误差误差7101.n计算量太大计算量太大33(b) 用级数用级数 来计算来计算221ln2 (1)(1)1321mxxxxxxm242

29、131 11 1112ln21( )( )( ),33 35 321 3mxm，241681 11 1112ln21( )( )( ),33 35 317 3S则，取则，取用前用前 9 项（即取项（即取 m = 8）计算就能达到精度要求）计算就能达到精度要求:78ln210 .S得：得：34有理数的有限数集，即浮点数有理数的有限数集，即浮点数集（参读教材集（参读教材p22-29p22-29）二、二、 数值计算中要构造和使用数值计算中要构造和使用数值稳定数值稳定的计算方法的计算方法一个好的算法必须是数值稳定的一个好的算法必须是数值稳定的否则结果不可靠，计算失败否则结果不可靠，计算失败（数值不稳定

30、）。（数值不稳定）。1. 1. 注意计算机数系的运算特点注意计算机数系的运算特点例例 讨论在计算机数系中分别用公式讨论在计算机数系中分别用公式 和和 求求a,ba,b中点时所得结果是否相同。中点时所得结果是否相同。12abm22bama5.243,8.355ab a b m m 准确值准确值 5.243 5.243 8.3558.355 6.8001.556 6.7991.557 6.7991.556若若 用四位有效数字进行计算时：用四位有效数字进行计算时：无误差时，必相等；无误差时，必相等；有舍入误差时，可有舍入误差时，可能不相等。能不相等。35例例 4 4位有效数字舍入运算：位有效数字舍入

31、运算：1234+0.4+0.3+0.2+0.1=12340.4+0.3+0.2+0.1+1234=1235若出现若出现“溢出溢出”应立即中应立即中断断应避免出现应避免出现“大数吃小数大数吃小数”事先预防、事先预防、 事后解决事后解决 例例 求求1222() .ab解解: :设设 ，则，则 max,cab，12122222()( )( ).ababccc可防溢出可防溢出针对计算机的计算特点，必须注意：针对计算机的计算特点，必须注意：解解: :计算机算法设计时，必须作到：计算机算法设计时，必须作到：362 2防止两接近的数相减防止两接近的数相减21810.xx 例例 求下列方程的根求下列方程的根解解: :12980,980 .xx用用8 8位