第五章数值积分及微分1.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,华长生制作,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,华长生制作,*,*,第五章 数值积分和数值微分,函数无解析表达式或表达式过于复杂时,定积分问题的数值解法,主要内容,导数或微分数值计算,华长生制作,1,传统方法的困境,数值积分的基本思想,数值积分的一般形式,代数精度问题,求函数,f,(,x,),在区间,a,b,上的定积分,是微积分学中的基本问题。,5.1,数值积分概述华长生制作,2,对于积分,但是在工程技术和科学研究中,常会见到以下现象,:,传统方法的困境,华长生制作,3,以上这些现象,Newton-Leibniz,很难,发挥作用,!,只能建立积分的近似计算方法,-,数值积分,正是为解决这样的困难而提出来的，,不仅如此，数值积分也是微分方程数值解法的,工具之一。,华长生制作,4,数值积分的基本思想,数值积分,-,指计算定积分近似值的各种计算方法。常用一个简单函数代替原来的复杂函数求积分。,从几何上看，就是计算曲边梯形面积的近似值。,最简单的办法，是用,直线,、,抛物线,等代替曲边，使得面积容易计算。,华长生制作,5,f,(,x,),a,b,f,(,a,)f,(,x,),a,b,f,(,x,),a,b,f,(,b,),f,(,a,),(a+b)/2,左矩公式,中矩公式,梯形公式,用,直线,代替曲边,华长生制作,6,抛物线公式,用,抛物线,代替曲边,又称辛普森公式,数值积分的一般形式,正是由于权系数的构造方法不同，从而决定了数值积分的不同方法。,上述的近似求积公式都是取,a,b,上若干点 处的高度通过加权 后再进行求和得到积分的近似值,，写成一般形式：,或写为：,其中，,-,称为,求积节点,A,k,-,称为节点,x,k,上的,权系数,。,-,是函数,f,(,x,),在节点,x,k,上的函数值，,-,称为求积公式的,截断误差或余项,。,华长生制作8,利用插值多项式来构造数值求积公式,具体步骤如下,:,不同的,插值方法,有不同的,基函数,插值型求积公式,思路,利用,插值多项式,则积分易算。,以拉格朗日插值多项式为例,华长生制作,9,A,k,由 决定，,与 无关。,节点,f,(,x,),称为,求积系数。,定义,其系数,，为拉各朗日插值基函数,这种求积公式称为,插值型积分公式,华长生制作,10,插值型的,求积公式余项,为了保证数值求积公式的精度,我们自然希望求积公式能够对尽可能多的函数,f(x,),都准确成立,这在数学上常用,代数精度,这一概念来说明。,插值型的,求积公式余项,华长生制作,11,解：,逐次检查公式是否精确成立,代入,f(x),=1,：,=,代入,f(x,),=,x,：,=,代入,f(x,),=,x,2,：,例：,对于,a,b,上,1,次插值，有,考察 时其求积误差。,梯形公式,因此梯形公式只对一次多项式精确成立。,华长生制作,12,代数精度,定义,如果某个求积公式对于次数不超过,m,的一切多项式都准确成立,而对 某个,m+1,次多项式并不准确成立，则称该求积公式的代数精度为,m,。,显然，梯形公式与中矩形公式均具有一次代数精度。,一般来说，代数精度越高，求积公式越精确。,定理,对于,n+1,节点的插值型求积公式,至少具有,n,次代数精度。,代数精度,华长生制作,13,例,试确定下面积分公式中的参数使其代数精确度尽量高,.,解:,华长生制作,14,因此,所以该积分公式具有,3,次代数精确度,华长生制作,15,5.2,牛顿柯特斯求积公式,Newton-Cotes,公式是指,等距节点,下使用,Lagrange,插值,多项式建立的数值求积公式,各节点为,一、公式推导：,，,以此分点为节点,构造出的插值型求积公式。,牛顿柯特斯求积公式,华长生制作,16,注意是等距节点,华长生制作,17,所以,Newton-Cotes,公式为,Cotes,系数,注：,Cotes,系数仅取决于,n,和,k,，可查表得到。与,f,(,x,),及区间,a,b,均无关。,华长生制作,18,二、低,阶,Newton-Cotes,公式及其余项,在,Newton-Cotes,公式中,n=1,2,4,时的公式是最常用也,最重要三个公式,称为低阶公式,(1).,梯形公式及其余项,Cotes,系数为,低阶,Newton-Cotes,公式及其余项,华长生制作,19,上式即为,梯形求积公式,也称,两点公式,，记为,梯形公式的余项为,求积公式为,华长生制作,20,广义积分,中值定理,故,华长生制作,21,(2).,辛卜生公式及其余项,Cotes,系数为,求积公式为,华长生制作,22,上式称为,辛卜生求积公式,，也称,三点公式或抛物线公式,记为,Simpson,公式的余项为,华长生制作,23,(3).,柯特斯,公式,上式特别称为,柯特斯求积公式,，也称,五点公式,柯特斯系数可由柯特斯系数表得到（,P153,）。由此可以得到任意阶数的牛顿柯特斯求积公式。但实际计算时一般不用高阶的公式，因为高次插值有,Runge,现象。,华长生制作,24,由此可自然会得出以下结论：,梯形规则简单，有,1,阶代数精度；,再增加一个节点，就是具有,3,阶代数精度的辛卜生规则；,三、牛顿科特斯公式的代数精度,牛顿科特斯公式实际上是插值求积公式，因此,n,阶牛顿科特斯公式至少有,n,次代数精度。,由于牛顿科特斯公式是等距插值，因此，有定理：,当,n,为偶数时，牛顿科特斯公式有,n,1,次代数精度,。,华长生制作,25,四、复化求积法,直接使用,NewtonCotes,公式的余项将会较大,。,公式的舍入误差又很难得到控制,为了提高公式的精度,往往使用,复化求积法,。,然后在每个小区间上使用低阶,Newton-Cotes,公式,最后将每个小区间上的积分的近似值相加,复化求积法,华长生制作,26,复化梯形公式,：,在每个 上用梯形公式：,=,T,n,/*,中值定理*,/,复合梯形公式,华长生制作,27,复化,Simpson,公式,：,4,4,4,4,4,=,S,n,复化,Simpson,公式,华长生制作,28,求积公式的余项比较,我们知道,两个求积公式的余项分别为,单纯的求积公式,复化求积公式的每个小区间,复化求积公式精度提高。,华长生制作,29,2 Composite Quadrature,Lab 13.,Composite Trapezoidal Rule,Use the Composite Trapezoidal rule with a given,n,0 to approximate a given integral .,You are supposed to write a function,double CTR(int n,double a,double b,double(*f)(),to approximate the integral from,a,to,b,of the function,f,using the trapezoidal rule on,n,equal-length subintervals.,Input,There is no input file.Instead,you must hand in your function in a,*.h,file.The rule of naming the*.h file is the same as that of naming the*.c or*.cpp files.,Output,For each test case,you are supposed to return the approximation of the integral.,华长生制作,30,Sample Judge Program,#include,#include,#include 98115001_13.h,double f1(double x),return(1.0/(1.0+sin(x)*sin(x);,double f2(double x),return(x*log(x);,void main(),FILE*outfile=fopen(out.txt,w);,int n;,double a,b;,a=0.0;b=1.0;n=10;,fprintf(outfile,%lfn,CTR(n,a,b,f1);,a=1.0;b=2.0;n=4;,fprintf(outfile,%lfn,CTR(n,a,b,f2);,fclose(outfile);,Sample Output,0.809093,0.639900,华长生制作,31,比较两种复合公式的的余项,为此介绍收敛阶的概念,!,华长生制作,32,定义,1.,不难知道,复合梯形、,Simpson,公式的收敛阶分别为,2,阶、,4,阶,华长生制作,33,复化求积法通过将积分区间分成,n,等份，来减小截断误差，因此,n,越大积分精度越高。但,n,太大，运算量也增大，舍入误差也增大；,n,太小，精度可能达不到。如何确定适当的,使得计算结果达到预选给定的精度要求呢？,在实际计算中,常采用积分步长的自动选择。具体地讲,就是在求积过程中,将步长逐次折半,反复利用复合求积公式,直到相邻两次的计算结果之差的绝对值小于允许误差为止。这实际上是一种事后估计误差的方法,变步长求积算法,。,5.3,变步长求积和龙贝格算法,问题,5.3,变步长求积和龙贝格算法,华长生制作,34,综合前几节的内容,我们知道,梯形公式,Simpson,公式,Cotes,公式的代数精度分别为,1,次,3,次和,5,次,复化梯形、复化,Simpson,、,复化,Cotes,公式的收敛阶分别为,2,阶、,4,阶和,6,阶,35,5.3.1,变步长梯形求积法,对于复合梯形公式，若将积分区间,a,bn,等分,积分近似值记为,T,n,积分精确值记为,I,则有,:,把每个子区间分半,也就是将积分区间,a,b,2n,等分,则有,则有,当 在连续,且函数值变化不大时,即有,给定求积精度,，如何取,n,?,5.3.1,变步长梯形求积法,36,可用来判断迭代,是否停止。,变步长梯形法计算过程,37,可以看到,每次都是在前一次的基础上将子区间再对分。原分点上的函数值不需要重复计算,只需计算新分点上的函数值即可,一般地计算公式为：,38,由上节,变步长,梯形公式,得到的积分,近似值的误差大致是,因此人们期望,如果用这个误差作为对,的一种补偿,则得到的求积公式的代数精度会有所提高。,（,1,）,5.3.2,龙贝格公式,龙贝格算法是在复化梯形公式误差估计的基础上，应用线性外推的方法构造出的加速算法。,5.3.2,龙贝格公式,39,通过直接验证可知,也就是说,用梯形公式二分前后的两个积分值,与,按照公式,(1),做线形组合,其结果正好是用抛物线公式得到的积分值,。,(2),即,40,同理可知,用,抛物线公式,得到的积分近似值,的误差大致是,因此对抛物线公式进行修正,得到,(3),也就是说,用抛物线公式二分前后的积分值,与,按照公式,(3),作线形组合,其结果正好是用柯特斯公式得到的积分值,。,通过直接验证可知,(4),41,同理可知，,用柯特斯公式得到的积分近似值,的误差大致是,因此,对柯特斯公式进行修改,得到求积公式,(5),为此,构造求积公式,(6),称,(6),式为,龙贝格,(,Romberg,),公式。,42,龙贝格公式是一种计算积分的方法。在变步长的求积过程中,运用,(2),(4),(6),式可以将精度低的梯形值 逐步加工成精度较高的抛物线,柯特斯值 与龙贝格值 。,总之有：,Romberg,序列,43,计算,f,(a,),f,(b,),算出,。,(2),把,a,b 2,等分,计算,算出,与,。,(3),把,a,b 4,等分,计算,算出,与,。,龙贝格求积的计算步骤如下：,44,(4),把,a,b 8,等分,计算,算出,与,与,。,(5),把,a,b 16,等分,计算,算出,与,与,继续重复进行,直到,时停止计算,就是所求的积分值,.,(,允许误差,),45,Romberg,算法,：,?,?,?,T,1,=,),0,(,0,T,T,8,=,),3,(,0,T,T,4,=,),2,(,0,T,T,2,=,),1,(,0,T,S,1,=,),0,(,1,T,R,1,=,),0,(,3,T,S,2,=,),1,(,1,T,C,1,=,),0,(,2,T,C,2,=,),1,(,2,T,S,4,=,),2,(,1,T,Romberg,算法,46,要求,熟练掌握,的内容,：,能灵活运用梯形公式和辛普生公式计算数值积分,求积公式的代数精度的定义，能判断求积公式的代数精度；,能灵活运用复化梯形公式和复化辛普生公式计算数值积分,要求,掌握,的内容,：,插值求积公式和牛顿科特斯公式的导出、系数的性质特点,变步长法则和龙贝格算法。,本章要求,本章要求,华长生制作,47,华长生制作,48,时，即为常用的积分中值定理。,可以看出,广义积分中值定理,设函数,及乘积 在 可积，,上不变号，,在,上连续，则,在,华长生制作,49,