计算方法ppt课件第一章数值计算方法

Tel：,86613747,E-mail：,lss,zjtcm,.net,授课: 68,学分：4,在数学发展中，理论和计算是紧密联系的。现代计算机的出现为大规模的数值计算创造了条件，集中而系统的研究适用于计算机的数值方法变得十分迫切和必要。数值计算方法正是在大量的数值计算实践和理论分析工作的基础上发展起来的，它不仅仅是一些数值方法的简单积累，而且揭示了包含在多种多样的数值方法之间的相同的结构和统一的原理。数值算法是进行科学计算必不可缺少的起码常识；更为重要的是通过对它们的讨论，能够使人们掌握设计数值算法的基本方法和一般原理，为在计算机上解决科学计算问题打下基础。因此，计算方法已经成为工科大学生必修课程,。,为什么要开设这个课呢？,1. 认识建立算法和对每个算法进行理论分析是基本,任务，主动适应“公式多”的特点；2. 注重各章建立算法的问题的提法，搞清问题的基,本提法，逐步深入；3. 理解每个算法建立的数学背景，数学原理和基本,线索，对最基本的算法要非常熟悉；4. 认真进行数值计算的训练，学习各章算法完全是,为用于实际计算，必须真会算。,如何进行学习？,科学素质：拓宽对21世纪科学的了解； 加深对数学思想的理解； 培养用数学思考世界的习惯数学能力：数学知识的运用能力； 对专业中问题建立数学求解方法与 实际计算能力 应用问题中数学创造性能力计算知识：常用算法的数学理论； 在,“,误差、存贮、速度,”,之下的实 际计算方法； 对结果的数值分析方法,记好课堂笔记,保证课堂纪律,按时完成作业,按时上课，不迟到早退,几点要求,数值分析讲述的基本内容,如何把数学模型归结为数值问题,如何制定快速的算法,如何估计一个给定算法的精度,分析误差在计算过程中的积累和传播,如何构造精度更高的算法,如何使算法较少的占用存储量,如何分析算法的优缺点,本课程的基本要求,掌握数值方法的基本原理,掌握常用的科学与工程计算的基本方法,能用所学方法在计算机上算出正确结果,本章内容,1 引言,2 误差的来源及分类,3 误差的度量,4 误差的传播,5 减少运算误差的原则,第一章计算方法与误差,小结,要求掌握的内容,第一章计算方法与误差,概念,包括有效数字、绝对误差,、,绝对误差,限,、相对误差、相对误差,限等,误差,截断误差、舍入误差的详细内容，误差种类等,分析运算误差的方法和减少运算误差的若干原则,1.1 引言,数值分析又称计算方法, 它是研究各种数,学问题的数值解法及其理论的一门学科。,数值分析的任务,实际问题,数学模型,数值计算方法,程序设计,上机计算,数值结果,根据数学模型提出求解的数值计算方法直到编出程序上机算出结果，这一过程边是数值分析研究的对象,1.,对于要解决的问题建立数学模型,2. 研究用于求解该数学问题近似解的算法和过程,3. 按照2进行计算，得到计算结果,建立数,学模型,转化为,数值公式,进行计算,数值方法解题的一般过程,数值计算以及计算机模拟（包括当前流行的虚拟现实的方法），已经是在工程技术研究和经济、社会科学中广泛应用的方法，带来巨大的经济效益,天气预报与亿次计算机,波音777的无纸设计与有限元,CT、,核磁共振,计算流体力学与爆炸工程,能源问题与大型计算,第一章计算方法与误差,计算作为工程技术研究方法,计算方法课程主要讨论如何构造求数学模型近似解的算法，讨论算法的数学原理、误差和复杂性，配合程序设计进行计算试验并分析试验结果。,与纯数学的理论方法不同，用数值计算方法所求出的结果一般不是解的精确值或者准确的解析表达式，而是所求真解的某些近似值或近似曲线。,第一章计算方法与误差,例如方程,x,2,=2sinx，,在区间(1,2)内有唯一根, 但找不出求根的解析式, 只能用数值计算方法求其近似解。有些数学问题虽有理论上的准确的公式解, 但不一定实用, 例如,行列式解法的,Cramer,法则原则上可用来求解线性方程组,用这种方法解一个,n,元方程组,要算,n,+1,个阶行列式的值,总共需要,n!(n-1)(n+1),次乘法,当,n=20,时,其乘除法运算次数约需10,21,次方,即使用每秒千亿次的计算机也得需要上百年,而用高斯（,Guass,）,消去法约需2660次乘除法运算,并且愈大,相差就愈大。可见研究和选择好的算法是非常重要的。,算法(数值算法):是指有步骤地完成解数值问,题的过程。,数值算法的特点,目的性，条件和结论、输入和输出数据均要有明,确的规定与要求。, 确定性，精确地给出每一步的操作(不一定都是运,算)定义, 不容许有歧义。, 可执行性，算法中的每个操作都是可执行的, 有穷性，在有限步内能够结束解题过程,计算机上的算法，按面向求解问题的不同，,分为数值算法和非数值算法。,第一章计算方法与误差,1.2,误差的来源及分类,早在中学我们就接触过误差的概念，如在做热力学实验中，从温度计上读出的温度是23.4度，就不是一个精确的值，而是含有误差的近似值。事实上，误差在我们的日常生活中无处不在，无处不有。如量体裁衣，量与裁的结果都不是精确无误的，都含有误差。,在用数值方法解题过程中可能产生的误差归纳起来有如下几类：,1. 模型误差,2. 观测误差,3. 截断误差,4. 舍入误差,第一章计算方法与误差,用数学方法解决一个具体的实际问题，首先要建立数学模型，这就要对实际问题进行抽象、简化，因而数学模型本身总含有误差，这种误差叫做模型误差,数学模型是指那些利用数学语言模拟现实而建立起来的有关量的描述,数学模型的准确解与实际问题的真解不同,实际问题的真解,数学模型的真解,为减化模型忽略次要因素,定理在特定条件下建立与实际条件有别,1. 模型误差,在数学模型中通常包含各种各样的参变量，如温度、长度、电压等，这些参数往往是通过观测得到的，因此也带来了误差，这种误差叫观测误差,数学模型中的参数和原始数据，是由观测和试验得到的,由于测量工具的精度、观测方法或客观条件的限制,使数据含有测量误差,这类误差叫做,观测误差或数据误差,根据实际情况可以得到误差上下界,数值方法中需要了解观测误差,以便选择合理的数值方法与之适应,2. 观测误差,精确公式用近似公式代替时,所产生的误差叫,截断误差,例如, 函数,f(x),用泰勒(,Taylor),多项式,3. 截断误差,（,介于0与,x,之间）,近似代替，则数值方法的截断误差是,截断误差的大小直接影响计算结果的精度和计算,工作量，是数值计算中必须考虑的一类误差,在数值计算中只能对有限位字长的数值进行运算,需要对参数、中间结果、最终结果作有限位字长的处理工作，这种处理工作称作舍入处理,用有限位数字代替精确数，这种误差叫做,舍入误差,，是数值计算中必须考虑的一类误差,4. 舍入误差,第一章计算方法与误差,例,如在计算时用3.14159近似代替,，,产生的误差,R=,-3.14159=0.0000026,就是舍入误差。,上述种种误差都会影响计算结果的准确性，因此需要了解与研究误差，在数值计算中将着重研究截断误差、舍入误差，并对它们的传播与积累作出分析,1.3,误差的度量,1.3.1 绝对误差和绝对误差限,定义1.1,设精确值,x,的近似值,x*,，,称差,e(x,*,),=x-x,*,近似值,x,*,的绝对误差，简称误差。,e(x,*,),又记为,e,*,当,e,*,0,时，,x,*,称为弱,近似值，,当,e,*,0,时，,x,*,称为强,近似值|,e,*,|越小，,x,*,的精度越高,由于精确值一般是未知的,因而,e,*,不能求出来, 但可以根据测量误差或计算情况设法估计出它的取值范围，即误差绝对值的一个上界或称误差限。,1.3,误差的度量,定义1.2,设存在一个正数，使,则称为近似值的绝对误差限，简称误差限或精度。,实际应用中经常使用这个量来衡量误差限, 这就是说, 如果近似数 的误差限为 , 则,表明准确值,x,必落在, ,上, 常采用下面的写法,来表示近似值的精度或准确值,x,所在的范围。,1.3,误差的度量,a-,a+,a,A,例,1,设,x,=,=3.1415926,近似值,x,*,=3.14,它的绝,对误差是,0.001 592 6,，有,x,-,x,*,=0.0015926,0.002=0.210,-2,例2,又近似值,x,*,=3.1416,，,它的绝对误差是,0.0000074,，有,x,-,x,*,=0.0000074,0.000008=0.810,-5,例3,而近似值,x,*,=3.1415，,它的绝对误差是,0.0000926，有,x,-,x,*,=0.0000926,0.0001=0.110,-3,可见，,绝对误差限,*,不是唯一的，但,*,越小越好,1.3.2,相对误差和相对误差限,只用绝对误差还不能说明数的近似程度,例如甲打字每100个错一个,乙打字每1000个错一个,他们的误差都是错一个,但显然乙要准确些,这就启发我们除了要看绝对误差外,还必须顾及量的本身。,定义1.3 绝对误差与精确值,x,的比值,称为相对误差。 简记为,1.3.2,相对误差和相对误差限,相对误差越小,精度就越高,实际计算时,x,通常是不知道的,因此可用下列公式计算相对误差,定义1.4 设存在一个正数 ，使,则称 为近似值 的相对误差限。,简记为,1.3.2,相对误差和相对误差限,例4.,甲打字每100个错一个，乙打字每1000个,错一个，求其相对误差,解： 根椐定义:甲打字时的相对误差,乙打字时的相对误差,1.3.3,有效数字,定义1.5 设,x,的近似值,其中 是0到9之间的任一个数,但,n,是正整数,m,是整数,若,则称 为,x,的具有,n,位有效数字的近似值， 准确到第,n,位， 是 的有效数字。,1.3.3,有效数字,例5. 3.142作为,的近似值时有几位有效数字,解： 3.141592= 0.3141592,3.142 = 0.3142,m,= 1,|,-3.142 |=|0.3141592 -0.3142,|, 0.000041 0.0005= ,m,n,=1,n,=-3,所以,n,=4，,具有4位有效数字,例6. 当取3.141作为,的近似值时,-,3.141,=,0.314159210,1,-,0.314110,1,0.0000592,10,1,0.0005=1/2, 10,-2,m,-,n,=1-,n,=-2,所以,n,=3,具,有3位,有效数字,推论,如果,近似数,x,*,误差限是某一位的半个单位,由该位到,x,*,的第一位非零数字一共有,n,位,x,*,就有,n,位有效数字,也就是说准确到该位,再如3.1416,作为,的近似值时, ,-,3.1416,=, 0.314159210,1,-,0.3141610,1,0.00000074,10,1, 0.00000740.00005,0.5, 10,-4,m,-,n,=1-,n,=-4,所以,n,=5,x,*,=,3.1416有5位有效数字,关于有效数字说明, 用,四舍五入取准确值的前,n,位,x,*,作为近似值,则,x,*,必有,n,位有效数字。如3.142作为 的近似值,有4位有效数字，而3.141为3位有效数字, 有效数字相同的两个近似数，绝对误差不一定,相同。例如，设,x,1,*,=12345,设,x,2,*,=12.345,两者,均有5位有效数字但绝对误差不一样,x,-,x,1,*,=,x,- 12345 0.5=,1/2 10,0,x,-,x,2,*,=,x,- 12.3450.0005=,1/210,-3, 把任何数乘以,10,p,(,p,=0,1,),不影响有效位数, 准确值具有无穷多位有效数字,如三角形面积,S=1/2,ah,=0.5,ah,因为0.5是真值,没有误差,*,=0,因此,n,准确值具有无穷位有效数字,1.3.4 有效数字与相对误差,定理1.1 若,近似数,x,*,=0.,x,1,x,2,x,n,10,m,具有,n,位,有效数字，则其相对误差,证: ,x,*,= 0.,x,1,x,2,x,n,10,m,x,*,x,1,10,m-1,又,x,*,具有,n,位有效数字,则,x-,x,*,1/2,10,m - n,一般应用中可以取,r,*,=1/2,x,1,10,-(n-1),n,越大,r,*,越小,有效数字越多，相对误差就越小,例7 取3.14作为,的四舍五入的近似值时，求其,相对误差,解：3.14=0.314,10,1,x,1,=3,m,=1,四舍五入的近似值,其各位都是有效数字,n,=3,r,*,=1/2,x,1,10,-(n-1),=1/2*3 10,-2,=17%,1.3.4 有效数字与相对误差,例8 已知近似数,x,*,有两位有效数字，试求其相,对误差限,解：已知,n,=2,代入公式,r,*,=1/2,x,1,10,-(n-1),得,r,*,=1/2,x,1,10,-1,x,*,的第一位有效数字,x,1,没有给出，可进行如下讨论：当,x,1,=1,r,*,=1/2x,1,10,-1,=1/2*1 10,-1,=5%,x,1,=9,r,*,=1/2x,1,10,-1,=1/2*9 10,-1,=0.56%,取,x,1,=1,时相对误差为最大，即,5%,1.3.4 有效数字与相对误差,1.3.4 有效数字与相对误差,定理1.2 若,近似数,x,*,=0.x,1,x,2,x,n,10,m,相对误差,则该近似数具有,n,位有效数字,证:,x,*,=0.,x,1,x,2,x,n,10,m,x,*, (,x,1,+1) 10,m-1,由有效数字定义可知,x*,具有,n,位有效数字。证毕,例9,已知近似数,x,*,的相对误差限为0.3%，问,x,*,有几位有效数字？,解：由,得,当,x,1,=1,时,3,10,-3,=1/410,-(n-1),12,10,-3,=10,-(n-1),上式两边取以10为底的对数得,lg2,2,+lg3+(-3)=-n+1,lg2=0.3010 lg3=0.4771,2,0.3010+0.4771-4=-n,n=2.9209, 当,x,1,=9,时,3,10,-3,=1/2010,-(n-1),6,10,-3,=10,-n,上式两边取以10为底的对数得,lg2+lg3+(-3)=-n,n=2.2219,x,*,至少有3位有效数字,例10 为使,的近似数的相对误差小于0.1%，,问查开方表时，要取几位有效数字？,解：, 8 9 ,x,1,=8, -(,n-1)lg2+2lg3+(-3),-n1.2552-4,-n2.7448,取,n =3,即查平方表时,8.37取三位有效数字,注意:,已知有效数字,求相对误差用公式,已知相对误差,求具有几位有效数字公式,1.4.1 函数运算误差,函数运算误差可用泰勒展开式来分析,设一元函数,f(x)，,自变量,x,的近似值,x,*,，f(x),的近似值,f(x,*,)，,其误差限记为,f(x,*,), ，对,f(x),在近似值,x,*,附近泰勒展开,1.4,误差的传播,介于,x,x,*,之间,其中,*,为,近似数,x,*,的绝对误差限，设,f(x,*,),与,f,(x,*,),相差不大,可忽略,*,的高次项,于是可得出函数运算的误差和相对误差,多元函数亦类似，用泰勒展开即可推导出来,例11 已测得某场地长,L,的值,L,*,=110m,宽,d,的值,d,*,=80m,已知,L-L,*, 0.2m,d-d,*,0.1m,求场地面积,S=Ld,的,绝对误差限和相对误差限,解：,其中,(,d,*,)=0.1m ,(,L,*,)=0.2m,绝对误差限,(s,*,)(800.2+110 0.1)m,2,=27m,2,相对误差限,1.4.2 算术运算误差,计算机的数值运算主要是加、减、乘、除四则运算，带有误差的数在多次运算过程中会进行传播。使计算结果产生误差。,误差的变化可以用微分简单描述。注意到准确值,x,与其近似值通常很接近，其差可认为是较小的增量，即可以把差看作微分，由此可得误差的微分近似关系式。,即,x,的微分表示,x,的绝对误差，的微分表示,x,的相对误差，利用这两个关系式及微分运算可以得到一系列有关四则运算的误差结果。,1.4.2 算术运算误差,由,d( x,y)=,dx,dy,可得两数之和(差）的误差等于两数的误差之和（差）；,由 可得两数之积的相对误差等于两数的相对误差之和；,由 可得两数商的相对误差可看作是被除数与除数的相对误差之差。,例12 正方形的边长约为100,cm,怎样测量才能使其,面积误差不超过1,cm,2,?,解： 设正方形边长为,x,cm,测量值为,x,*,cm,面积,y,=,f,(,x,)=,x,2,由于,f,(,x,)=2,x,记自变量和函数的绝对误差分别是,e,*,、,e,(,y,*,),则,e,*,=,x,-,x,*,e,(,y,*,)=,y,-,y,*,f,(,x,*,)(,x,-,x,*,)=2x,*,e,*,=200,e,*,现要求 ,e(,y,*,) 200e,*, 1 ,于是,e,*, （1/200）cm=0.005cm,要使,正方形面积误差不超过1,cm,2,，,测量边长时绝对误差应不超过0.005,cm。,1.5 减少运算误差原则,误差是用来衡量数值方法好与坏的重要标志,为此对每一个算法都要进行误差分析,(1)两个相近的数相减，会严重损失有效数字,例如,x =1958.75，y =1958.32,都具有五位,有效数字，但,x-y=0.43,只有两位有效数字,通常采用的方法是改变计算公式,例如当与,很接近时,由于,用右端代替左端公式计算,有效数字就不会损失,1.5 减少运算误差原则,当,x,很大时可作相应的变换,则用右端来代替左端。,1.5 减少运算误差若干原则,当,x,接近0时,一般情况，当,f(x)f(x*),时，可用泰勒展开,取右端的有限项近似左端。,如果计算公式不能改变，则可采用增加有效位数的方法保证精度,（2）防止大数,“,吃掉,”,小数,例 求二次方程,x,2,-10,5,x+1=0,的根,解：按二次方程求根公式,x,1,=(10,5,+(10,10,-4),1/2,)/2,x,2,=(10,5,-(10,10,-4),1/2,)/2,在8位浮点数计算得,x,1,=(10,5,+10,5,)/2=10,5,(正确）,x,2,=(10,5,-10,5,)/2=0 (,错误）,产生错误的原因, 出现大数,10,10,吃掉小数4的情况, 分子部分出现两个相近数相减而丧失有,效数位常称为灾难性的抵消,（,3）绝对值太小的数不宜做除数,当分母为两个相近数相减时,会丧失有效数字,这里分子的误差被扩大104倍,再如,若将分母变为0.0011,即分母只有0.0001的变化时,计算结果却有了很大变化,1.5 减少运算误差若干原则,例1.8 计算,解: 分子分母分别计算后相除(取9位小数),A=0.0005*0.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,只准确到小数后一位,1.5 减少运算误差若干原则,例： 计算,算法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位。,b,c,a,1.5 减少运算误差若干原则,（,4）简化计算步骤，减少运算次数,x,255,=,xx,2,x,4,x,8,x,16,x,32,x,64,x,128,原先要做254次乘法现只需14次即可,又如计算多项式,p,(,x,)=,a,n,x,n,a,n-1,x,n-1,a,1,x,a,0,的值,若直接计算,a,k,x,k,再逐项相加，一共要做,n,+(,n,-1)+,+2+1=,n,(,n,+1)/2,次乘法和,n,次加法,1.5 减少运算误差若干原则,如果将前,n,项提出,x，,则有,p,(,x,)=（,a,n,x,n,-1,a,n-1,x,n-2,a,1,）,x,a,0,=(,a,n,x,n,-2,a,n-1,x,n-3,a,2,),x,a,1,）,x,a,0,=(,(,a,n,x,a,n-1,),x,a,2,),x,a,1,),x,a,0,写成递推公式,1.5 减少运算误差若干原则,于是 ,这种多项式求值的算法称为秦九,韶算法,只做,n,次乘法和,n,次加法,程序实现简单,1.5.5 控制递推公式中误差的传播,对于一个数学问题的求解往往有多种数值方法在选择数值方法时，要注意所用的数值方法不应将计算过程中难以避免的误差放大的较快，造成计算结果完全失真。,例13 计算积分,并估计误差,解 容易得到递推公式,即 为,则准确的理论递推式,实际运算的递推式,两式相减有,这就是说,若 与 的误差为 =,-,即,，则误差的递推规律为,于是,计算 时的误差被扩大了 倍,显然算法是数值不稳定的。,如果将递推公式,变换一种形式,准确的理论递推式,实际运算的递推式,从而有,即,于是有,则这个算法的误差传递规律为,即每计算一步的误差的绝对值是上一步的十分之一，误差的传播逐步缩小，得到很好的控制，这个算法是数值稳定的,本章小结,误差在数值计算中是不可避免的，误差的传播和积累直接影响到计算结果的精度。在研究算法的同时，必须注重误差分析，使建立起来的算法科学有效。,按照误差产生的来源可分为模型误差、观测误差，截断误差、和舍入误差等。,误差的表示法有绝对误差和相对误差两种。,在表示一个近似数时,要用到有效数字的概念,这在数值计算中非常有用,有效数字是由绝对误差决定的,通常用函数的泰勒展开对误差进行估计,作业,习题一1.11.14,