计算机数值方法第四章-数值积分与微分.ppt

延安大学 数学与计算机科学学院,计算机数值方法,Numerical Analysis,本章要点:,牛顿柯特斯积分 复合积分 龙贝格积分 高斯求积公式,第4章 数值积分,1 牛顿柯特斯积分公式 2 复合求积公式 3 龙贝格积分方法 4 高斯求积公式 5 数值微分,一、 引言,对于定积分,以上这些现象,牛顿-莱布尼兹很难发挥作用,只能建立积分的近似计算方法,但是在工程技术和科学研究中,常会见到以下现象:,则积分值 I 对应于曲边梯形的面积。,这样导出的求积公式,近似地取代平均高度,某种线性组合，作为原定积分的近似值，,在区间a,b内取n+1个点,利用被积函数f(x)在这 n+1 个点的函数值的,这样的方法称为数值积分，,相应的公式称为数值积分公式。,这类数值积分公式通常称为机械求积公式。,定义1. 若求积公式,则称该求积公式具有m次的代数精度,二、代数精度,梯形公式和矩形公式均具有一次代数精度。,要使求积公式具有m次代数精度，只要令它对于,都能准确成立，这就要求,例：,三、插值型的求积公式,积分数值计算的方法很多, 最常用的一种 方法是利用插值多项式来构造数值求积公式,具体步骤如下:,求积公式,由插值型的求积公式的余项可推得,由插值余项定理即知，对于插值型的求积公式，其余项,代数精度的充分必要条件是，它是插值型求积公式.,四、求积公式的收敛性与稳定性,牛顿柯特斯公式是指等距节点下使用 拉格朗日插值多项式建立的数值求积公式。,各节点为,1 牛顿柯特斯求积公式,一、牛顿柯特斯求积公式,而,因此对于定积分,有,即有,n阶牛顿柯特斯求积公式,牛顿柯特斯公式的余项,等距节点时,所以牛顿-柯特斯公式化为,称为Cotes系数,二、 偶数阶求积公式的代数精度,定理 当阶数n为偶数时，牛顿柯特斯公式 至少有n+1次代数精度。,在牛顿柯特斯公式中，n=1,2,4 时的 公式是最常用、也最重要的三个公式； 通常称为低阶公式。,三、低阶牛顿柯特斯公式及其余项,1.梯形公式及其余项,柯特斯系数为,上式称为梯形求积公式,也称两点公式，记为,求积公式为,梯形公式具有1次代数精度,梯形公式的余项为,2.辛普森公式及其余项,柯特斯系数为,求积公式为,称为辛普森求积公式，也称三点公式或抛物线公式,辛普森公式的余项为,辛普森公式具有3次代数精度,3.柯特斯公式及其余项,柯特斯系数为,求积公式为,上式称为柯特斯求积公式，也称五点公式,柯特斯公式的余项为,柯特斯公式具有5次代数精度.,例: 用n=2和n=3的牛顿-柯特斯公式,解：,1. n=2时：,2. n=3时,（ 的精确值为0.7668010）,2 复合求积法,Newton-Cotes积分公式,低阶Newton-Cotes积分公式,n=1, 2, 4 时的Newton-Cotes公式称为低阶公式,n=1：梯形公式及其余项,梯形公式具有1次代数精度,低阶Newton-Cotes积分公式,n=2：辛普森公式及其余项,辛普森公式具有3次代数精度,低阶Newton-Cotes积分公式,n=4：柯特斯公式及其余项,柯特斯公式具有5次代数精度,Newton-Cotes积分法的稳定性,因此，实际应用中常用低阶Newton-Cotes公式，,即：梯形公式、辛普森公式、柯特斯公式。,高阶公式稳定性不好，低阶公式精度不高,问 题,b,=xn,函数y=f(x)上的数据点,a,=x0,f(a),x1,y1,f(b),y=f(x),x2,xi,xi+1,y2,yi,yi+1,复合求积法,将积分区间a , b分成若干个子区间，在每个子区间上用低阶公式计算 ，然后对所有子区间上的计算结果求和，即得到原定积分的近似值，这种方法称为复合求积法。,1. 复合求积公式,1.1 复合求积公式,由定积分的区间可加性得：,1.1 复合求积公式,x0,x1,xk,xk+1,xn,1.2 复合梯形求积公式,复合梯 形公式,1.2 复合梯形求积公式,b,=xn,a,=x0,f(a),x1,y1,f(b),y=f(x),x2,xi,xi+1,y2,yi,yi+1,1.3 复合辛普森求积公式,复合辛普森公式,1.3 复合辛普森求积公式,xi+1/2,=xn,xi,xi+1,x1,b,a,=x0,f(a),y1,f(b),y=f(x),yi,yi+1,1.3 复合辛普森求积公式,1.4 复合柯特斯求积公式,2. 复合求积法的余项及收敛阶,2.1 复合求积公式的收敛阶,定义.,1, 2, 4 阶牛顿-柯特斯积分公式的余项分别为：,积分区间 a, b上：,积分区间 xk , xk+1上：,2.2 复合梯形公式的余项及收敛阶,R1(f ) 是h的2阶无穷小量，所以,因此复合梯形公式是2阶收敛的。,于是复化梯形公式余项为：,2.2 复合梯形公式的余项及收敛阶,因此复合辛普森公式是4阶收敛的。,2.3 复合辛普森公式的余项及收敛阶,R2(f ) 是h的4阶无穷小量，所以,因此复合柯特斯公式是6阶收敛的。,2.4 复合柯特斯公式的余项及收敛阶,R4(f ) 是h的6阶无穷小量，所以,2.5 三种复合求积公式比较,例1.,分别用8阶复合梯形公式、4阶复合辛普森公式和,并对结果进行比较分析。,n=8 时的函数数据表,分别由复合梯形、辛普森、柯特斯公式得：,比较三个复合公式的计算结果：,积分的精确值为,精度最高,精度最低,3. 步长的自动选择,通常情况下,定积分的结果只要满足所要求的精度即可,1.变步长公式 在实际计算中，借助于计算机来完成积分步长 h 的自动选择，即采用变步长求积公式。具体地讲，就是将步长逐次折半，反复利用复合求积公式，直到满足精度要求为止。,2.变步长复合辛普森公式 逐次将区间a，b分成21，22，2m等份，并按复合抛物线公式逐次计算积分得到S1，S2，Sm，而,其中,2.变步长复合辛普森公式,再把每个子区间分成两半,用,作步长,按复合抛物线公式计算出积分的近似值S2m。,对于相邻两次的积分近似值Sm、S2m，考察,2.变步长复合辛普森公式,设给定的精度为，若 d 则以S2m作为所要求的积分近似值，否则继续将区间分半，利用复合抛物线公式求积分，直到满足给定的精度为止。,4.自动选择步长的算法步骤,依此类推,以上这种方法称为自适应求积法。,有时去掉后 精度会更高,不同的方法 P取不同值,3 龙贝格积分方法,梯形公式,Simpson公式,Cotes公式的代数精度分别为,1次,3次和5次,复合梯形、复合Simpson、复合Cotes公式的收敛阶分别为,2阶、4阶和6阶,在代数精度和收敛速度方面, 梯形公式都较差,但梯形公式形式简单、计算量小,有没有办法改善梯形公式呢?,1. 复合梯形公式的递推化,由前面讨论可知，加密节点可以提高求积公式的精度，复合求积方法对提高精度是行之有效的，但选择合适的步长（即n的选取）是个问题。,上节的变步长方法解决了这个问题，即把区间逐次二分，反复利用复合求积公式进行计算，直到二分前后两次积分近似值之差符合精度要求为止。,各节点为,复合梯形公式为,-(1),经过二分只增加了一个分点,-(3),-(2),用复化梯形公式求得该子区间上的积分值为,这里h仍为二分前的步长.将每个子区间上的积分值相加得,由(1)(2)两式可,(3)式称为递推的梯形公式,递推梯形公式加上一个控制精度,即可成为自动选取步长的复化梯形公式,优点：梯形法计算简单,缺点：收敛慢，为了达到要求的精度，需要二分区间 多次，分点大量增加，计算量很大,2. 龙贝格算法,根据复化梯形公式的余项表达式可知,即,复合辛普森公式,也就是，相邻的两个梯形值的外推，,即,却得到了辛普森公式的值。,简单的组合，改变了近似值的代数精度和收敛阶。,同理，由复合辛普森公式的余项,可得,由复合柯特斯公式的余项,得,通常，取m3即可。因为当m较大时，校正的效果已经很微小了。,T数表,例2 用龙贝格积分公式求,龙贝格积分值R1=0.9460831的每位数字都是有效数字,解：由龙贝格公式得如下T-数表：,3. 算法设计,Romberg 序列, ?, ?, ?, ,Romberg 算法,引言 求积公式 (1) 当求积系数 、求积节点 都可以自由选取时，其代数精确度最高可以达到多少次? 下面的引理可以回答上述问题。,4 Gauss求积公式,引理1 当求积系数 和求积节点 都可以自由选取时，n点的求积公式(1)的代数精确度 最高可以达到2n-1次。 证 假设求积公式(1)具有m次代数精确度, 即对任意的m次代数多项式 求积公式(1)都精确成立。于是成立等式,即 (2) 若记,则(2)式成为 (3),由于系数 的任意性，故使(3)式 成为恒等式的充要条件是 (4) (4)式的待定系数有2n个，所以确定待定系数的独立条件至多给出2n个，从而可知m至多为2n-1。,定义1 n点的求积公式(1)具有2n-1次代数精确度(或称为 具有最高的代数精确度)时，称为Gauss型求积公式。 Gauss型求积公式的求积节点 ，称为 Gauss点，它们可以通过求区间a,b上带权(x)的n次 正交多项式 的n个根获得。 所以先介绍正交多项式及其性质。 然后讨论Gauss型求积公式的构造。,正交多项式及其性质 定义2 若 (1) ，则称函数f(x)和g(x)在区间 a,b上正交。 (2) ，则称函数f(x)和g(x)在区 间a,b上带权(x)正交。,(3) 代数多项式序列 (下标k为多项式 的次数, 表示k次多项式)，在区间a,b上满足 当mn 当m=n 则称多项式序列 为区间a,b上带权(x)的正交多项式序列。,定义3 若n次多项式 中含 项的系 数为 ，则称 为 的首次系数； 时，称 为首次系数为1的n次多项式。,正交多项式有如下性质: 性质1 若 是区间a,b上带权(x)的正 交多项式序列，则它们线性无关。 证 对任意的xa,b,若 ，在式子 两边同乘(x)gl(x)(l=0,1,n), 并从a到b积分, 由 的正交性定义2中的(3)可知必有 l=0,1,n. 故正交多项式序列 线性无关。,由性质1可知,若 为a,b上带权(x)的 正交多项式序列，则序列 可以作为空间 的一组基函数,即 中的任一元素 可由它们线性表示： 其中 为组合系数。,性质2 若 为a,b上带权(x)的正交多 项式序列,且 ,则,(1) (2) 事实上,由性质1, . 由 的正交性定义容易证得(1). 证(2)也是类似的.,Gauss型求积公式 由引理1和定义1可知，n点的求积 公式(1)若具有最高的代数精确度，即 具有2n-1次的代数精确度，为Gauss型 求积公式. 求积公式(1)的求积节点 和 求积系数 如何选取,才能使之 成为Gauss型求积公式?,定理1 求积公式(1)中的n个求积节点 ,取为 区间a,b上带权函数(x)的n次正交多项式 的n个根，则求积公式(1)为Gauss型求积公式。 证 设 。a,b上带权函数(x)的,n次正交多项式 的n个根记为 ,记 其首项系数为 .由定义3有 因此, (5) 其中 .,在(5)式两边同乘 (x),并从a到b积分. 由正交多项式的性质可知,含 项的积分为零,所以 (6) 注意到当 作为插值节点时建立的n点插值,求积公式 至少具有n-1次代数精确度,而 , 所以 (7),又由(5)式可知 , 即 (8) 综合(6),(7),(8)式可知,当 时,求积 公式(1) 成立. 因此公式(1)具有2n-1次代数精度，为Gauss型求积公式。,用n点Gauss求积公式 (9) 之值近似积分值 ，有下面的误差估计. 定理2 若 ,则Gauss型求积 公式(1)的误差估计R(,f)为 其中 定理3 Gauss型求积公式的求积系数 大于零.,前面讨论了复合求积公式的收敛性问题 Gauss型求积公式的收敛性由下面的定理给出. 定理4 若f(x)a,b,则Gauss型求积公式 所求积分值序列 收敛于积分值I(f),即,Gauss型求积公式的构造与应用 定理1实际上给出了构造Gauss型求积公式的一种方法。 给定 a,b和(x) ，构造n个点的Gauss求积公式： 先求出区间a,b上带权函数(x)的n次正交多项式 , 然后用多项式求根的方法求出 的n个根 , 从而获得了求积节点,为了求得求积系数 ,将n个求积节点 代入方程组(4)中的前n个方程并加以求解, 即解线性代数方程组,求得系数 ,完成Gauss型求积公式的构造.,例1 求 使求积公式 具有三次代数精确度. 问题是构造区间0,1上带权函数 的两点Gauss型求积公式. 解 方法1 容易计算出当 时 的积分值分别为 所求 公式具有3次代数精确度.,故可得 为未知数的方程组为 (1) (2) (3) (4) 又因为 为Gauss型求积公式的求积节点, 所以它们是区间0,1上带权函数 且 首项系数为1的二次正交多项式 的两个根.,不妨记 ,为此 又因为 必须满足方程(2)(3)(4),所以,由 可得关于p,q的方程组为,解此方程组得,将所求 p, q 代入 ,求得其根为,再将所求 代入方程(1)(2),联立解得 为此,公式 为所求具有3次代数精确度的求积公式.,例1 方法2 求出区间0,1上带权函数 的二次正交多项式 ,并求出其根 , 获得求积节点.再求方程组(4)前两个方程组成 的方程组获得求积系数 .,第二种方法与第一种方法求出的 是一样 的,后面的求解过程相同. 方法2是一种将一组线性无关函数组 正交化而得到正交多项式 的方法.高于2次