数值分析第四章数值积分

1、数值分析第四章数值积分 第四章第四章 数值积分与数值微分数值积分与数值微分 /* Numerical Integration and differentiation*/ 近似计算近似计算 b a dxxfI)( 1 引言引言 数值分析第四章数值积分 对对f( )采用不同的近似计算方法，从而得到各采用不同的近似计算方法，从而得到各 种不同的求积公式。种不同的求积公式。 数值分析第四章数值积分 数值分析第四章数值积分 以上三种方法都是用被积函数值的线性组合来表示积以上三种方法都是用被积函数值的线性组合来表示积 分值分值。推广，一般地有推广，一般地有 0 ( )() n b kk a k f x d

2、xA f x 求积节求积节 点点 求积系数，与被求积系数，与被 积函数无关积函数无关 像这样，将积分用若干节点上被积函数值的线性组合来表示像这样，将积分用若干节点上被积函数值的线性组合来表示 的数值积分公式称为机械求积公式的数值积分公式称为机械求积公式。 0 ( )() n b kk a k R ff x dxA f x 求积误差求积误差 机械型求积公式的构造归结为，确定求积节点机械型求积公式的构造归结为，确定求积节点xk和求积系和求积系 数数Ak，使在某种意义下精确度较高。总之，要解决三个问，使在某种意义下精确度较高。总之，要解决三个问 题：题： 精确度的度量标准；精确度的度量标准； 如何构

3、造具体的求积公式；如何构造具体的求积公式； 1. 具体求积公式构造出来后，误差如何估计？具体求积公式构造出来后，误差如何估计？ 数值分析第四章数值积分 定义：定义：代数精度代数精度 若某个求积公式对次数若某个求积公式对次数 m 阶阶的多项式准确成立，而对的多项式准确成立，而对 m+1 阶阶的多项式不一定准确成立。即对应的误差满足：的多项式不一定准确成立。即对应的误差满足： R Pk =0 对任意对任意 k m 阶阶的多项式成立，且的多项式成立，且 R Pm+1 0 对某对某 个个 m+1 阶多项式成立，则称此求积公式的代数精度为阶多项式成立，则称此求积公式的代数精度为 m 。 代数精度与误差的

4、关系：代数精度越高，求积误差越小。代数精度与误差的关系：代数精度越高，求积误差越小。 结论：结论： 问题问题1 数值分析第四章数值积分 数值分析第四章数值积分 由上面代数精度条件确定求积公式可分两种情形：由上面代数精度条件确定求积公式可分两种情形： 若事先给定求积节点若事先给定求积节点xk(k=0,n),例如被积函数以表的形式例如被积函数以表的形式 给出时给出时xk确定，可令确定，可令m=n,由上式确定由上式确定n+1个系数个系数Ak即可即可- 待定系数法和插值法。待定系数法和插值法。 1. 若若xk和和Ak都可选择，令都可选择，令m=2n +1，确定，确定xk和法和法Ak -Gauss法法

5、要使求积公式具有要使求积公式具有m阶代数精度，则它对阶代数精度，则它对1,x,xm均准确成立，均准确成立， 即即 0 22 0 11 0 1 2 1 1 n k k n kk k n mmm kk k Aba A xba A xba m m+1个方程，个方程， 2n+2个未知数个未知数 问题问题2 数值分析第四章数值积分 Case 1-方法方法1 数值分析第四章数值积分 数值分析第四章数值积分 1 插值型求积插值型求积 公式公式 思思 路路 利用插值多项式利用插值多项式 则积分易算。则积分易算。 )()(xfxP n 在在a, b上取上取 a x0 x1 xn b，做，做 f 的的 n 次插值

6、次插值 多项式多项式 ，即得到，即得到 n k kkn xlxfxL 0 )()()( b a b a k n k k dxxlxfdxxf)()()( 0 Ak b a kj xx xx k dxA jk j )( )(由由 决定，决定， 与与 无关。无关。 节点节点 f (x) 插值型积分公式插值型积分公式 /*interpolatory quadrature*/ b a n k k x n b a n b a n b a n k kk dxxx n f dxxRdxxLxf xfAdxxf fR 0 )1( 0 )( )!1( )( )()()( )()( 误差误差 Case 1-方法方

7、法2 数值分析第四章数值积分 1 Newton-Cotes Formulae 例：对于例：对于a, b上上1次插值，有次插值，有)()()( 1 bfafxL ab ax ba bx )()()( 2221 bfafdxxfAA ab b a ab 考察其代数精度。考察其代数精度。f(x) ab f(a) f(b) 梯形公式梯形公式 /* trapezoidal rule*/ 解：逐次检查公式是否精确成立解：逐次检查公式是否精确成立 代入代入 P0 = 1： b a abdx111 2 ab = 代入代入 P1 = x ：= 代入代入 P2 = x2 ： 2 22 ab b a dxx 2 b

8、a ab 3 2 33 ab b a dxx 22 2 ba ab 代数精度代数精度 = 1 数值分析第四章数值积分 1 Newton-Cotes Formulae Th1.形如形如 的求积公式至少有的求积公式至少有 n 次代数精度次代数精度 该该 公式为插值型（即：公式为插值型（即： ） n k kk xfA 0 )( b a kk dxxlA)( 数值分析第四章数值积分 数值分析第四章数值积分 当节点等距分布时：当节点等距分布时： ni n ab hhiaxi,., 1, 0, dx xx xx A n x x ij ji j i 0)( )( n ji in n ji dtjt inin

9、 ab dth hji hjt 00 )( )!( ! )1)( )( )( 令令htax Cotes系数系数 )(n i C 注：注：Cotes 系数仅取决于系数仅取决于 n 和和 i， 可查表得到。与可查表得到。与 f (x) 及区及区 间间a, b均无关。均无关。 2 Newton-Cotes 公式公式 ( ) 0 0 ( )() n b n k a k f x dxbaCf xkh NewtonCotes formula 数值分析第四章数值积分 1 Newton-Cotes Formulae 2 1 , 2 1 )1( 1 )1( 0 CCn = 1: )()( 2 )(bfaf ab

10、 dxxf b a Trapezoidal Rule dxbxax f fR b a x )( !2 )( /* 令令 x = a+th, h = b a, 用中用中 值定理值定理 */ 1 , , )( 12 1 3 ab hbafh 代数精度代数精度 = 1 n = 2: 6 1 , 3 2 , 6 1 )2( 2 )2( 1 )2( 0 CCC )()(4)( 6 )( 2 bffaf ab dxxf ba b a Simpsons Rule 代数精度代数精度 = 3 2 ,),(,)( 90 1 )4(5 ab hbafhfR 数值分析第四章数值积分 n = 4: Cotes Rule

11、, 代数精度代数精度 = 5,)( 945 8 )6(7 fhfR 01234 ( )7 () 32 ( ) 12 () 32 ( )7 () 90 b a b a f x dxf xf xf xf xf x 偶数阶偶数阶N-C公式具公式具 有有n+1阶代数精度阶代数精度 n = 3: Simpsons 3/8-Rule, 代数精度代数精度 = 3,)( 80 3 )5(5 fhfR 数值分析第四章数值积分 对称节点的系数相同对称节点的系数相同 Cotes公式是公式是 用不同节点用不同节点 的函数值的函数值 （高度）的（高度）的 加权平均来加权平均来 近似区间的近似区间的 平均高度平均高度 注

12、：当注：当n 8时，时，Cotes系数有负，造成公式不稳定，因此常用系数有负，造成公式不稳定，因此常用 低阶低阶Cotes公式。公式。 数值分析第四章数值积分 (1) 00 2 00 0 0 /2 2 /2 0 ( ) ()() (1)! , () even, /2 integer, let /2, we have (/2) n nn bb x kk aa kk n n n k k n n n n k f R fx x dxx x dx n xxjh xxthR fht k dt nntu n R fhu nk du 证明：只需证明n为偶数时，为偶数时， N-C公式对公式对f(x)=xn+1的

13、余项的余项 R(f)=0即可。即可。 因因 f(n+1)(x)=(n+1)!, 由余项公式得由余项公式得 Th2. n为偶数时为偶数时， N-C公式至少具有公式至少具有n+1阶代数精度。阶代数精度。 数值分析第四章数值积分 00 /2 0/2 /2/2 1 /2/2 /2/2 /2/2 ( )(/2)(/2) (/2) ( /2) ()1 ( ) ( ) odd 0. nn kk nn kjn nn n jnjn nn jnjn let H uunkukn uknujlet jkn Huujuj ujujH u H uR f 注：当注：当n 为偶数时，为偶数时，Cotes公式具有公式具有n+1

14、阶精度，与阶精度，与n+1阶阶 Cotes公式精度相同，但少计算一个节点上的函数值，公式精度相同，但少计算一个节点上的函数值， 因此一般常用偶数阶因此一般常用偶数阶Cotes公式。公式。 数值分析第四章数值积分 偶数阶偶数阶N-C公式具公式具 有有n+1阶代数精度阶代数精度 N-C公式具有公式具有n阶代数精度阶代数精度 余项余项R=o(h n+2) 数值分析第四章数值积分 数值分析第四章数值积分 数值分析第四章数值积分 数值分析第四章数值积分 Hint：construct a interpolation polynomial of order 5, H(x), satisfying H(a)=

15、f(a), H(b)=f(b), H (k)(a+b)/2) = f (k)(a+b)/2). 数值分析第四章数值积分 HW: p.151-152 #1-6 数值分析第四章数值积分 数值稳定性的一般概念数值稳定性的一般概念 数值分析第四章数值积分 N-C的稳定性的稳定性 数值分析第四章数值积分 数值分析第四章数值积分 3 复合求积复合求积 /* Composite Quadrature */ Havent we had enough formulae? Whats up now? Oh come on, you dont seriously consider h=(b a)/2 accepta

16、ble, do you? Why cant you simply refine the partition if you have to be so picky? Dont you forget the oscillatory nature of high- degree polynomials! Uh-oh 高次插值有高次插值有Runge 现象，故采用分段低次插值现象，故采用分段低次插值 分段低次合成的分段低次合成的 Newton-Cotes 复合求积公式。复合求积公式。 复合梯形公式：复合梯形公式：),., 0(,nkhkax n ab h k 在每个在每个 上用梯形公式：上用梯形公式：

17、, 1kk xx nkxfxf xx dxxf kk x x kk k k ,., 1,)()( 2 )( 1 1 1 1 1 )()(2)( 2 n k k bfxfaf h b a n k kk xfxf h dxxf 1 1 )()( 2 )( = Tn ),(),()( 12 )( )( 12 )( 12 2 1 2 1 3 bafab h n f ab h f h fR n k k n k k /*中值定理中值定理*/ 数值分析第四章数值积分 数值分析第四章数值积分 2 Composite Quadrature 复化复化 Simpson 公式：公式： ),., 0(,nkhkax n

18、 ab h k )()(4)( 6 )( 1 2 1 1 k k k x x xfxfxf h dxxf k k k x 2 1 k x 1 k x4 4 4 4 4 )()(2)(4)( 6 )( 1 0 1 0 1 2 1 n k n k k k b a bfxfxfaf h dxxf = Sn )( 2180 )4( 4 f hab fR 注：为方便编程，可采用另一记法：令注：为方便编程，可采用另一记法：令 n = 2n 为偶数，为偶数， 这时这时 ，有，有hkax h n ab h k , 2 )()(2)(4)( 3 koddkeven kkn bfxfxfaf h S 数值分析第四

19、章数值积分 数值分析第四章数值积分 2 Composite Quadrature 收敛速度与误差估计：收敛速度与误差估计： 定义定义 若一个复化积分公式的误差满足若一个复化积分公式的误差满足 且且C 0， 则则称该公式是称该公式是 p 阶收敛的。阶收敛的。 C h fR p h lim 0 32 1 01 2 : ()() 1212 11 ( )( )( ) 1212 nn kk kk b a hh R ffhf R f fx dxfbfa h 复化梯形公式 /*中值定理中值定理*/ 类似的，可得类似的，可得 44 (5)(5) 66 1 :( )( ) 1802 2 :( )( ) 9454

20、 R f fbfa h R f fbfa h 复化Simpson公式 复化Cotes公式 2阶收敛阶收敛 4阶收敛阶收敛 6阶收敛阶收敛 数值分析第四章数值积分 例例1：计算：计算dx x 1 0 1 4 2 解：解： )1()(2)0( 16 1 7 1 8 fxffT k k 8 k xk 其中其中 = )1()(2)(4)0( 24 1 oddeven 4 fxfxffS kk 8 k xk 其中其中 = 502 运算量基运算量基 本相同本相同 数值分析第四章数值积分 Q: 给定精度给定精度 ，如何取，如何取 n ? 例如：要求例如：要求 ，如何判断，如何判断 n = ？ | n TI

21、2 ( )( ) 12 h R ffbfa 上例中若要求上例中若要求 ，则，则 6 10| n TI 6 22 10 6 | )0() 1 (| 12 | | h ff h fRn 00244949.0 h 即：取即：取 n = 409 数值分析第四章数值积分 数值分析第四章数值积分 数值分析第四章数值积分 数值分析第四章数值积分 数值分析第四章数值积分 数值分析第四章数值积分 2 Composite Quadrature 数值分析第四章数值积分 事后误差估事后误差估 计式，可用计式，可用 来判断迭代来判断迭代 是否停止。是否停止。 始步长始步长h 数值分析第四章数值积分 数值分析第四章数值积

22、分 数值分析第四章数值积分 0.5 10-2 数值分析第四章数值积分 4 龙贝格积分龙贝格积分 /* Romberg Integration */ 复化梯形公式算法简单，但精度较差，收敛速度（复化梯形公式算法简单，但精度较差，收敛速度（2阶收敛）阶收敛） 较慢，如何提高收敛速度？较慢，如何提高收敛速度？ 数值分析第四章数值积分 数值分析第四章数值积分 注：按上面规律，可以构造线性组合系数为注：按上面规律，可以构造线性组合系数为 的新的积分公式，但当的新的积分公式，但当m 4时，前一个系数接近于时，前一个系数接近于1，后一个，后一个 系数接近于系数接近于0，这样构造出的新公式与前一个公式结果差别不，这样构造出的新公式与前一个公式结果差别不 大，反而增加计算量，因此实际上常做到大，反而增加计算量，因此实际上常做到Romberg公式为止。公式为止。 41 , 41 41 m mm 数值分析第四章数值积分 数值分析第四章数值积分 数值分析第四章数值积分 数值分析第四章数值积分 数值分析第四章数值积分 例：计算例：计算 dx x 1 0 1 4 2