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

*,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第一章 数值计算的基本概念,引言,误差与,有效数字,算法的稳定性与病态问题,计算机计算的几个问题,算法设计的原则,1,第一章 数值计算的基本概念引言1,1 引言,一、数值学科的研究内容和特点,解决现代工程技术问题的,基本过程,（如左图）,数值分析是研究适合于在计算机上使用的实际可行、理论可靠、计算复杂性好的数值计算方法的学科。,分析实际问题,数值计算方法,数学模型,机器求解,数值分析研究的,核心：算法。,构造算法的基本手段：,近似,研究算法的核心问题：近似对计算的影响,误差分析,2,1 引言一、数值学科的研究内容和特点解决现代工程技术问题,特点,构造性：,递推性：,离散化：,近似替代：,计算离散点上的近似值；有可靠的理论分析；算法理论主要是连续系统的离散化数值求解。,方法的构造，解的存在唯一性的证明,复杂计算过程转化成简单的计算过程的多次重复（适合计算机计算）,在误差允许的范围内，无限次的计算能用有限次计算替代。,模拟仿真：,可通过计算机的仿真实验验证实际的工程计算,3,特点 构造性：递推性：离散化：近似替代：计算,2 误差与有效数字,一个物理量的真实值和我们算出的值往往不相等，其差称为,误差,。,一、误差定义,定义,热门促销安卓智能手机推荐,4,2 误差与有效数字一个物理量的真实值和我们算出的值往往不相,分析实际问题,数值计算方法,数学模型,机器求解,二、误差种类与来源,观测误差,模型误差,截断误差,舍入误差,数据观测所引入的误差，如电压、天体运行轨道。,数学模型是实际问题的抽象和简化，只是对客观现象的一种近似。其间出现的误差。,近似计算代替精确求解，如此误差称为,截断误差,，本身固有，也称,方法误差,。例如圆周率，自然对数。,计算机数系的有限字长，必须进行四舍五入，称为,舍入误差,。,5,分析实际问题数值计算方法数学模型机器求解二、误差种类与来源观,计算机在处理数据过程中存在计算误差。原因是机器数系所致。这一数系的特点是,有限、离散、支离破碎,；这和数学上常用的实数系,无限、稠密、连续的,特点完全不同。机器数的表示方法通常采用浮点数形式，即：,其中,a,1,0，且,a,1,a,2,a,n,都是整数09中的任一个数。,10,m,称为,尾数,，尾数的位数,n,是有限正整数；,m,称为,阶数,，阶数也是有界的数。所以，机器数中有最大的数，也有最小的数。用机器数表示实数时，很多情况下都带有误差。,附,：计算机数系的特点,6,计算机在处理数据过程中存在计算误差。原因是机,二、误差基本概念,1.绝对误差,绝对误差不是误差的绝对值，即,e,(,x,)可正可负。,通常,x,是未知的，故,e,(,x,)未知，但一般地,已知。,设,x,*,为准确值,x,的近似值，记,称,为,x,*,的,绝对误差限,或,误差限,。,称,e,为近似值,x,*,的,绝对值,或,误差,。,定义,若,例,说明,7,二、误差基本概念1.绝对误差绝对误差不是误差的绝对值，即,2.相对误差,设某量的准确值为,x,，,x,*,是,x,的近似值，称绝对误差与准确值之比,称,为,x,*,的,相对误差限,。,为,x,*,的,相对误差。,定义,若,8,2.相对误差设某量的准确值为 x，x*是 x 的近似值，称,例,：设,估计近似数,x,1,x2的绝对误差与相对误差。,解：,是,x,1,好的近似，,不是,x,2,好的近似。,近似数的相对误差是近似数精确度的基本度量，一个近似数,x,*,的相对误差越小，则近似数越精确。,结论:,9,例：设估计近似数x1,x2的绝对误差与相对误差。解：是x1好,e,r,(,x,)是一个无量纲的数，且,x,一般是未知的，所以,e,r,(,x,)难求。,考察量,较小时,通常将 作为,x,*,的相对误差。,相对误差限,是未知的，但可以确定。,说明,10,er(x)是一个无量纲的数，且 较小时,3.有效数字,若近似值,x,*,的误差限是某一位的半个单位，该位到第一位非零数字,共,n,位，称近似值有,n,位有效数字。,设,x,为准确值，,x,*,为,x,的近似值且,x,*,表示为,换言之，如果,称,x,*,具有,n,位,有效数字。,定义,11,3.有效数字若近似值x*的误差限是某一位的半个单位，该位到,一个十进制数近似值的有效数字，不受单位制的影响。,如,g,*,=9.81,m,/,s,2,作为,g,的近似值，与,g,*,=0.00981,km,/,s,2,，均,为3位有效数字。,在有效数意义下，不同的有效数位数的近似值的近似精度是不同的。如10.4200的精度高于10.42：,前者的绝对误差不超过：,后者的绝对误差不超过：,有效数字与绝对误差有一定的关系。对于某量的近似值，如果有,n,位有效数字，当,m,一定时，,n,越大则相对误差越小。,结论,12,一个十进制数近似值的有效数字，不受单位制的影响。在有效数,定理,(有效数字与相对误差的关系)：,设近似值,x,*,表示为,若,x,*,具有,n,位有效数字，则其相对误差限为,反之，若,x,*,的相对误差限,则,x,*,至少具有,n,位有效数字。,13,定理 (有效数字与相对误差的关系)：设近似值x*表示为若x,证明：,由,x,*,的表达式可得：,又由定义可知,有效数位越多，相对误差越小,所以,反之，则有：,因此，,x,*,具有,n,位有效数字。,14,证明：由x*的表达式可得：又由定义可知有效数位越多，相对误差,为使 近似值的相对误差小于1%，问需要取多少位有效数字？,解：,的近似值的首位数字,a,1,=2,于是由,可解得,因此，可取,n,=3 即,例：,15,为使 近似值的相对误差小于1%，问需要取多少位有效,3 算法的稳定性和病态问题,定义,一个算法如果输入数据有误差，而在计算过程中,舍入误差,不增长，则称此算法是,数值稳定的,，否则称此算法为,不稳定的,。,一、算法稳定性定义,16,3 算法的稳定性和病态问题定义一个算法如果输入数据有误差，,计算下式并估计误差。,由分步积分公式，可得,例,解：,可以计算出下表：,按递推关系,17,计算下式并估计误差。由分步积分公式，可得例解：可以计算出下表,于是，取,n,=9，则有,于是，取,n,=8，则有,而,18,于是，取n=9，则有于是，取n=8，则有而18,现将递推公式改写为：，并且取,因此，可得新的递推公式：,由上面的递推公式，可得到下面的计算结果：,19,现将递推公式改写为：,对于第二种方法，设 ，有,第二种方法比第一种方法计算稳定。,对于第一种方法，设 ，则有,分析：,因此，误差是逐次放大的。,因此，误差是逐次缩小的。,20,对于第二种方法，设,二、病态问题与条件数（针对问题本身）,输入数据的微小变动导致输出数据的较大误差，就被称为,病态问题,。,衡量是否病态的标准：,条件数,不同的问题，条件数具体定义不同。,对于函数值计算问题，条件数定义为：,一般情况下，条件数大于,10,，就认为问题病态。,设,f,(,x,)=,x,n,，则,C,p,=,n,，即对于该函数，误差会被放大,n,倍,通过构造特殊算法来解决,定义,21,二、病态问题与条件数（针对问题本身）输入数据的微小变动导致输,条件数和函数的误差估计,设原始数据,x,1,，,x,2,，,x,n,，,y,与,x,i,有关，是由,x,i,计算所得的解。若,x,1,，,x,2,，,x,n,的近似值为,x,1,*,，,x,2,*,，,x,n,*,，那么相应的解也有一定的误差，记为,y,*,，此时,解的绝对误差为:,e,*,(,y,)=,f,(,x,*,),f,(,x,),e,*,(,x,)=,x,*,x,=,f,(,)(,x,*,x,)(中值定理),一元的情形：,绝对误差条件数,22,条件数和函数的误差估计 设原始数据x1，x2，,x,*,与,x,非常接近时，可认为,f,(,),f,(,x,*,)，则有：,|,e,*,(,y,)|,|,f,(,x,*,)|,|,e,*,(,x,),|,即：,x,*,产生的误差经过,f,作用后被放大/缩小了|,f,(,x,*,)|倍。故称|,f,(,x,*,)|为,放大因子,或,绝对条件数,.,相对误差条件数,23,x*与 x 非常接近时，可认为 f()f,一元的情形,f,的条件数在某一点是,小,大,，则称,f,在该点是,好条件的,坏条件的,.,24,一元的情形 f 的条件数在某一点是小大，则称 f 在该,例(病态问题),设有方程组,A,已知系数,b,测量数据,x,待求数据,其中,如果测量数据不够精确，即测量数据仅保留了2位有效数字，即 ，计算结果为,以上问题称为病态的问题，病态是问题本身固有的。,那么很容易计算,若测量数据为准确数据，,即,25,例(病态问题)设有方程组A已知系数b测量数据x待求数据其中,4 机器计算的几个问题与算法设计原则,数值计算的一般标准：,运算次数的多少(计算效率);,运算过程是否规律(易编程);,需要记录的中间结果的多少(储存量);,运算方案能否控制误差的传播和积累以保证计算结果有足够的精度（数值稳定性）,26,4 机器计算的几个问题与算法设计原则数值计算的一般标准：运,一、减少运算次数,不仅能提高计算精度，而且能减少误差的积累,1、对同一种计算方法，要选用计算量少的运算次序,例,例,：计算多项式 的值。,27,一、减少运算次数 不仅能提高计算精度，而且能减少误差的积累,(,b,)利用秦九韶算法：,解,：,(,a,),直接计算每一项再求和：,计算,p,n,(,x,)的值只需做,n,次乘法,n,次加法。,则,计算,p,n,(,x,)的递推公式：,计算,a,n,x,n,需做,n,次乘法，,计算,p,n,(,x,)的值需做乘法次数：,加法次数：,n,28,(b)利用秦九韶算法：解：(a)直接计算每一项再求和：计,(,a,)利用级数,2、对于不同的算法，要注意收敛速度，讲效率,例,计算 ln2 的近似值，要求误差小于10.,解：,取,x,=1，有,误差,计算量太大,29,(a)利用级数2、对于不同的算法，要注意收敛速度，讲效率例,(,b,)使用级数,则，取,用前 9 项（即取,m,=8）计算就能达到精度要求:,得：,30,(b)使用级数则，取用前 9 项（即取 m=8）计算就,若 用四位有效数字进行计算时：,有理数的有限数集，即浮点数集（参读教材p22-29）,一个好的算法必须是数值稳定的，,否则结果不可靠，计算失败（数值不稳定）。,1.注意计算机数系的运算特点,例,讨论在计算机数系中分别用公式 和,无误差时，必相等；有舍入误差时，可能不相等。,二、数值计算中要构造和使用数值稳定的方法,求,a,b,中点时所得结果是否相同。,31,若 用四位有效数字进行计算时,例,4位有效数字舍入运算：,1234+0.4+0.3+0.2+0.1=1234,0.4+0.3+0.2+0.1+1234=1235,若出现“溢出”应立即中断,应避免出现“大数吃小数”,事先预防、事后解决,例,求,解:设 则,可防溢出,针对计算机的计算特点，必须注意：,解:,计算机算法设计时，必须作到：,32,例 4位有效数字舍入运算：1234+0.4+0.3+0.2+,2.防止两接近的数相减,例,求下列方程的根,解:,(a)用8位浮点数(有效数字)计算,是因为求 的误差(并不大),进行减法后导致不应忽视的后果,准确,不稳定,33,2.防止两接近的数相减例 求下列方程的根解:(a)用8,两接近数相减,损失了有效数字,(b)用4位浮点数(有效数字)计算,(c)数值稳定的方法,改用公式,仍用4 位浮点数计算,当|,x,|1 时：,几种经验技巧,34,两接近数相减(b)用4位浮点数(有效数字)计算(c)数值稳,前面有例题，计算,3.设法控制误差的传播,第二种方法比第一种方法计算稳定。,对于第一种方法，设,，则有,因此，误差是逐次放大的。,对于第二种方法，设,，则有,因此，误差是逐次缩小的。,(当时给出了两种方法),必须小心控制误差的传播,并估计误差。,35,前面有例题，计算3.设法控制误差的传播 第二种方法比第一种,三 计算过程中应十分小心处理病态的数学问题,引起,函数的很大误差,病态问题,病态问题一般要用高精度(双精度)计算或解病态问题的方法解决。,输入的很小 的误差,36,三 计算过程中应十分小心处理病态的数学问题引起函数的很大误差,1.求 的近似值的相对误差不超过0.1%，要取几位有效数字？,作 业,一、教材上的作业,二、补充作业,三、编程作业,教材P.43 1.P.44 5.P.44 8.,2.设,，假定,g,是准确的，而对,t,的测量有,秒的误差，,证明：当t增大时，,S,的绝对误差增大而相对误差却减小。,1.用MATLAB编程实现P44.第7题(,x,=3 时)，写出相应代码。,37,1.求 的近似值的相对误差不超过0.1,