代数精度插值求积及复化公式.ppt

但是，在工程技术领域，在实际使用上述求积分方法时，往往会遇到下面情况：,1.函数f(x)没有具体的解析表达式，只有一些由实验测试数据形成的表格或 图形。,关于定积分的计算，我们知道，只要求出f(x)的一个原函数F(x)，就可以利用牛顿莱布尼慈（Newton-Leibniz）公式出定积分值：,3.f(x)的结构复杂，求原函数困难，即不定积分难求。,2.f(x)的原函数无法用初等函数表示出来，如：,由于以上种种原因，因此有必要研究积分的数值计算方法，进而建立起上机计算定积分的算法。此外，数值积分也是研究微分方程和积分方程的数值解法的基础。,数值积分,1.1 构造数值求积公式的基本思想,定积分I=ab f(x)dx在几何上为x=a,x=b,y=0和y=f(x)所围成的曲边梯形的面积。定积分计算之所以困难，是不规则图形的面积。由积分中值定理，对连续函数f(x)，在区间a,b 内至少存在一点，使：,也就是说,曲边梯形的面积I 恰好等于底为b-a,高为f()的规则图形矩形的面积(图7-1),f()为曲边梯形的平均高度,然而点的具体位置一般是不知道的,因此难以准确地求出f()的值。但是,由此可以得到这样的启发,只要能对平均高度f()提供一种近似算法,便可以相应地得到一种数值求积公式。,如用两端点的函数值f(a)与f(b)取算术平均值作为平均高度f()的近似值,这样可导出求积公式：,第七章 数值积分与微分,7-3,更一般地在区间a,b 上适当选取某些点xk(k=0,1,n),然后用f(xk)的加权平均值近似地表示f(),这样得到一般的求积公式：,其中,点xk 称为求积节点,系数Ak 称为求积系数，Ak 仅仅与节点xk 的选取有关,而不依赖于被积函数f(x)的具体形式。,另一方面定积分的定义，,其中xk是a,b 的每一个分割小区间的长度,它与f(x)无关,去掉极限,由此得到近似计算公式：,因此，式（7-1）可作为一般的求积公式,其特点是将积分问题归结为函数值的计算,从而避开了使用牛顿一莱布尼慈公式需要求原函数的困难,适合于函数给出时计算积分,也非常便于设计算法,便于上机计算。求积公式（7-1）的截断误差为：,Rn也称为积分余项.,1.2 代数精度,定义1,如果某个求积公式对所有次数不大于m的多项式都精确成立，而至少对一个m+1次多项式不精确成，则称该公式具有m次代数精度。,一般来说，代数精度越高，求积公式越好。为了便于应用，由定义1容易得到下面定理。,数值积分是一种近似计算,但其中有的公式能对较多的函数准确成立,而有的只对较少的函数准确成立。为了反映数值积分公式的准确差别,引入代数精度的概念。,试验证梯形公式具有一次代数精度。,例1,可以证明矩形公式的代数精度也是一次的。,定理1,一个求积公式具有m次代数精度的充分必要条件是该求积公式对 1,x,x2,xm 精确成立，而对xm+1不精确成立。,第七章 数值积分与微分,7-6,上述过程表明,可以从代数精度的角度出发来构造求积公式.如,对于求积公式（7-1）,若事先选定一组求积节点xk(k=0,1,n,),xk可以选为等距点,也可以选为非等距点,令公式对f(x)=1,x,xn 精确成立,即得：,这是关于A0、A1、An的线性方程组,系数行列式为范德蒙行列式,其值不等于零,故方程组存在唯一的一组解。,求解方程组(7-2)确定求积系数Ak,这样所得到的求积公式(7-1)至少具有n次代数精度.,例2,确定求积公式,使其具有尽可能高的代数精度。,解：求积公式中含有三个待定参数,可假定近似式（7-3）的代数精度为m=2,则当f(x)=1，x，x2时，式（7-3）应准确成立，即有：,代回去可得：,检查（7-4）对 m=3 是否成立,为此,令 f(x)=x3 代入（7-4）,此时左边,第七章 数值积分与微分,7-8,再检查（7-4）对m=4是否成立,令f(x)=x4代入(7-4),此时:,因此近似式（7-4）的代数精度为m=3.,由待定系数法确定的求积公式没有确切的误差估计式，只能从其所具有的代数精度去判定求积公式的准确程度。,上述方法称为待定系数法，在具有尽可能高的代数精度的要求下，利用它可以得出各种求积公式。,1.3 插值型求积公式,设给定一组节点a x0 x1 xn-1xn b，且已知f(x)在这些节点上的函数值，则可求 得f(x)的拉格朗日插值多项式：,其中lk(x)为n次插值基函数。取f(x)Ln(x)，则有：,记：,则有：,这种求积系数由式（7-5）所确定的求积公式称为插值型求积公式.,根据插值余项定理，插值型求积公式的求积余项为：,其中a,b 与x有关.,关于插值型求积公式的代数精度，有如下定理。,具有n+1个节点的数值求积公式（7-1）是插值型求积公式的充分必要条件是该公式至少具有n次代数精度。,定理2,定理2说明,当求积公式（7-1）选定求积节点xk后,确定求积系数Ak有两条可供选择的途径：求解线性方程 组（7-2）或者计算积分（7-5）,即利用n次代数精度或插值型积分来确定求积系数.由此得到的求积公式都是插值型的,其代数精度均不小于n次.,证：(充分性)设求积公式（7-1）至少具有n次代数精度,那么,由于插值基函数 li(x)(i=0,1,n)均是次数为n的多项式,故式（7-1）对li(x)精确成立,即:,(必要性)设求积公式（7-1）是插值型的，则对所有次数不大于n的多项式f(x)，按（7-6）其求积余项Rn=0，即这时插值型求积公式是精确成立的。由定义1,n+1个节点的插值型求积公式至少具有n次代数精度。（证毕）,例3,考察求积公式：,具有几次代数精度.,注：n+1个节点的求积公式不一定具有n次代数精度.其原因是此求积公式不一定是插值型的。例：,2 牛顿一柯特斯(Newton-Cotes)公式,本节介绍节点等距分布时的插值型求积公式，即牛顿一柯特斯（Newton-Cotes）公式。,2.1 牛顿一柯特斯（Newton-Cotes）公式,设将积分区间a,b 划分为n等分,步长h=(b-a)/n,求积节点取为xk=a+kh(k=0,1,n),由此构造插值型求积公式,则其求积系数为:,记：,称之为n阶牛顿一柯特斯（Newton-Cotes）公式简记为N-C公式，称 为柯特斯系数。显然，柯特斯系数与被积函数f(x)和积分区间a,b 无关，且为多项式积分，其值可以事先求出备用。表7-1中给了了部分柯特斯系数。,柯特斯系数,表7-1,经计算或查表得到柯特斯系数后，便可以写出对应的牛顿一柯特斯（Newton-Cotes）公式。,当n=1时,按公式（7-7）有：,得求积公式：,即梯形公式,当n=2时,第七章 数值积分与微分,7-15,相应的求积公式：,称为辛卜生(Simpson)公式.,当n=4时，所得的公式称作柯特斯公式，它有五个节点，其系数：,所以柯特斯公式是：,柯特斯系数的性质,1、与积分区间无关:当n确定后,其系数和都等于1,即,2、对称性：,此特性由表7-1很容易看出，对一般情况可以证明。(略),3、柯特斯系数并不永远都是正的。表7-1看出当n=8时,出现了负系数,在实际计算中将使舍入误差增大,并且往往难以估计,从而牛顿一柯特斯公式的收敛性和稳定性得不到保证,因此实际计算中不用高阶的。,第七章 数值积分与微分,7-17,第七章 数值积分与微分,7-18,2n阶Newton-Cotes公式至少具有2n+1次代数精度。,我们知道，由n次插值多项式导出的n次牛顿一柯特斯公式至少具有n次代数精度.由于节点等距，更进一步有以下结论：,定理3,证：计算知由2n次插值多项式导出的求积公式 的截断误差为0即可.,例4,验证辛卜生(Simpson)公式:,具有三次代数精度。（定理3直接得到）,解：由定理2,3个节点的插值积分公式辛卜生公式至少具有二次代数精度,因此只需检查对f(x)=x3成立否。当f(x)=x3时：,所以I=S，表明辛卜生公式对于次数不超过三次的多项式准确成立，用同样的方法可以验证对于f(x)=x4，辛卜生公式不成立，因此辛卜生公式的代数精度可以达到三次。在几种低阶N-C公式中,感兴趣的是梯形公式（最简单,最基本）辛卜生公式和柯特斯公式。,例5,解：由梯形公式（7-9）：,由辛卜生公式（7-10）得：,由柯特斯公式（7-11）得：,事实上，积分的精确值：,与之相比可以看到，柯特斯公式的结果最好，具有七位有效数字；辛卜生公式的结果次之，具有四位有效数字；而梯形公式的结果最差,只有两位有效数字。,分别用梯型公式、辛卜生公式和柯特斯公式计算积分：,2.2 几种低价N-C求积公式的余项,考察梯形公式,按N-c的截断误差知,梯形公式（7-9）的余项：,这里被积函数中的因子t(t1)在区间0,1 上不变号（非正），故由积分中值定理，在0,1 内至少存在一点，使：,2.对于辛卜生公式,需要注意的是，关于牛顿-科特斯公式的收敛性，可以证明，并非对一切连续函数f(x),都有：,也就是说牛顿柯特斯公式的收敛性没有保证。当n趋于无穷时，它的稳定性也没有保证，因此，在实际计算中，一般不采用高阶(n 8)的牛顿-柯特斯公式。,3.柯特斯公式（6-10）的余项为：,在实际计算中常用前面三种低价N-C公式，但若积分区间比较大，直接使用以上三种低阶求积公式，则精度难以保证；若增加节点，就要使用高阶的N-C公式，然而前面已指出，当n 8时，由于N-C公式的收敛性和稳定性得不到保证，因此不能采用高阶的公式。事实上，增加节点，从插值的角度出发，必然会提高插值多项式的次数，Runge现象表明，一般不采用高次插值，亦即不用高阶N-C公式。为提高精度，当增加求积节点时，考虑对被积函数用分段低次多项式近似，由此导出复化求积公式。,3 复化求积公式,3.1 复化梯形公式,用分段线性插值函数来近似被积函数,等于把积分区间分成若干小区间,在每个小区间上以梯形面积近似曲边梯形面积,即用梯形公式求小区间上积分的近似值.这样求得的近似值显然比整区间上用梯形公式计算精度高。,式（7-15）称为复化梯形公式。,因为f(x)在a,b 连续，由介值定理，存在(a,b)，使得：,从而有：,这就是复化梯形公式的截断误差.,3.2 复化Simpson公式和复化Cotes公式,如果用分段二次插值函数近似被积函数，即在小区间上用Simpson公式计算积分近似值，就导出复化Simpson公式。,如果f(x)C(4)a,b,由式（7-13）可得复化Simpson公式的截断误差为：,整理得：,式（7-17）称为复化Simpson公式。,因为f(4)(x)连续，故存在(a,b)，使得：,若用复化求积公式计算积分:,的近似值，要求计算结果有四位有效数字，n应取多大？,例,解 因为当0 x1时有0.3e-1e-x1于是：,要求计算结果有四位有效数字,即要求误差不超过10-4/2.又因为:,由复化梯形公式误差估计式：,式（7-18）表明,步长h越小,截断误差越小.与复化梯形公式的分析相类似,可以证明,当n 时,用复化Simpson公式所求得的近似值收敛于积分值,而且算法具有数值稳定性.,例子的计算结果表明，为达到相同的精度，用复化Simpson公式所需的计算量比复化梯形公式少，这也说明了复化Simpson公式的精度较高，实际计算时多采用复化Simpson公式。,复化求积方法又称为定步长方法。复化求积公式,根据预先给定的精度能估计出合适的步长或 n,进而确定对积分区间的等分数,如同例7一样.然而当被积函数稍复杂一些，要由误差估计式给出合适的步长，就要估计被积函数导数的上界值，而这一点是相当困难的。,因此若用复化梯形公式求积分,n应等于41即41等分才能达到精度.若用复化Simpson公式,由式（7-18）,即得n 1.6.故应取n=2即4等分.,h=1/n,h=1/2n,复化Cotes公式,将区间a,b分成n 等分,分点为：,用Cotes公式得到复化Cotes公式：,复化Cotes公式的截断误差为：,要使截断误差不超过10-3/2，h应取多大？辛普生公式又怎么样？,用复化梯形求积公式计算积分:,作业,第七章 数值积分与微分,7-32,4 逐次分半算法(变步长方法),基于复化求积公式（定步长方法）的缺点，常采用变步长方法，即逐步缩小步长，每次将步长缩小一半，或者说逐次等分区间,反复利用复化求积公式，直到相邻两次计算结果相差不大为止或者满足给定精度为止。,第七章 数值积分与微分,7-33,梯形法的递推公式,第七章 数值积分与微分,7-34,因此计算梯形序列T2m可按:,第七章 数值积分与微分,7-35,此为复化梯形公式的递推公式,第七章 数值积分与微分,7-36,第七章 数值积分与微分,7-37,第七章 数值积分与微分,7-38,若f(x)在a,b 的二阶导数连续，则当m较大时：,以此作为停止计算的控制。,而由前面的推导可知，下面公式具有如下规律性：,并且是利用控制结束的误差式，构成新的、收敛更快的公式，,