第四章N-C公式

1、第四章 數(shù)值積分與數(shù)值微分Newton-CotesNewton-Cotes公式公式nkknknxfCabI0)()()(badxxfA)(120001)2)12(2)1(21)(kjkkabjafabkTkT微積分學微積分學- “- “人類精神的卓越勝利人類精神的卓越勝利”微積分就是微分運算和積分運算這兩種互逆運算方法微積分就是微分運算和積分運算這兩種互逆運算方法的合稱，就像加法與減法，乘法與除法是互逆運算一的合稱，就像加法與減法，乘法與除法是互逆運算一樣，但微積分的運算法則要比加減乘除，乘方，開方樣，但微積分的運算法則要比加減乘除，乘方，開方等運算復雜得多，現(xiàn)在已成為高等數(shù)學的核心內容。等運

2、算復雜得多，現(xiàn)在已成為高等數(shù)學的核心內容。 為什么要數(shù)值積分？為什么要數(shù)值積分？在微積分里，按在微積分里，按Newton-LeibnizNewton-Leibniz公式求定積分公式求定積分( )( )( )( )baI ff x dxF bF aWhy do we do numerical integral? f(x)沒有解析表達式，只有數(shù)表形式?jīng)]有解析表達式，只有數(shù)表形式x12345f(x)44.5688.5 f(x)有表達式，但原函數(shù)不是初等函數(shù)有表達式，但原函數(shù)不是初等函數(shù)210 xedx10(arctan)x x dx它們的原函它們的原函數(shù)都不是初數(shù)都不是初等函數(shù)等函數(shù). . f(x)

3、原函數(shù)表達式很復雜，計算量很大原函數(shù)表達式很復雜，計算量很大討論數(shù)值積討論數(shù)值積分的必要性分的必要性更一般地，我們可以在區(qū)間更一般地，我們可以在區(qū)間a,ba,b上選取某些節(jié)點上選取某些節(jié)點4.-(1.3)P98-99)()()(2221bfafdxxfAAabbaab 考察其代數(shù)精度?？疾炱浯鷶?shù)精度。f(x)abf(a)f(b)梯形公式梯形公式/* trapezoidal rule*/解：解：逐次檢查公式是否精確成立逐次檢查公式是否精確成立代入代入 P0 = 1： baabdx111 2 ab=代入代入 P1 = x ：=代入代入 P2 = x2 ： 222abbadxx 2baab 3233

4、abbadxx 222baab 代數(shù)精度代數(shù)精度 = 1( )1( )1baf xI fdxba時，3( )(14 1)()6baIfba22( )( )2baf xxI f時，223( )(22)62babaIfaabb332( )( )3baf xxI f時，332223( )()63babaIfaabb443( )( )4baf xxI f時，344333()( )()624baabbaIfab554( )( )5baf xxI f時，4443()( )()( )64baabIfabI f試確定下面積分公式中的參數(shù)使其代數(shù)精確度盡量高.220)()0()()0(2)(Ihffahhffh

5、dxxfIhhdxxI00222hI 202232hahhI0)(xxf對于hI 2hhdxxI011)(xxf對于22hhdxxI022)(xxf對于33h3)221(ha2II 令121a3022242hahhIhdxxI033)(xxf對于44h44h4023252hahhIhdxxI044)(xxf對于55h65h3 ,2 , 1 , 0)()(2jxIxIjj)()(424xIxI,)(baCxf設函數(shù)等份分割為將積分區(qū)間nba,nkkhaxk, 1 ,0,為步長其中nabh各節(jié)點為Cotes系數(shù)系數(shù))(niC 注：注：Cotes 系數(shù)僅取決于系數(shù)僅取決于 n 和和 i，可查表得到。

6、與可查表得到。與 f (x) 及區(qū)及區(qū)間間a, b均無關。均無關。)()(2bfafab)(1fI10)1()()(kkkxfCab)()(210 xfxfab)(1fI即132321883838( )()( )()()( )baa babf x dxb af afff b 3n 時，時，3/8公式公式例例 用用n=6的牛頓柯特斯公式計算定積分值的牛頓柯特斯公式計算定積分值101.dxIx 解：解：將積分區(qū)間將積分區(qū)間0,1劃分為劃分為n份，得到節(jié)點列為份，得到節(jié)點列為100 1 266, , ,ixii在這些節(jié)點處的函數(shù)值為在這些節(jié)點處的函數(shù)值為160 1 2616(), , ,iif xi

7、xi 則則n=6的牛頓柯特斯公式為的牛頓柯特斯公式為01230124199341 084035280105419984035280() ()( )()()()( )()If xf xf xf xf xf xf x 41 69 69634 64169696840 6 35 7 280 8 105 9 840 10 35 11 280 12 0 6931. (1) ( ) 0 bnnaf xn(x) I(f) (x)dx , nfP當為次多項式時從而至少有次代數(shù)精確度。2,2,2210abhbxabxaxn則取Cotes系數(shù)為系數(shù)為dtttC20)2(0)2)(1(4161dtttC20)2(1)

8、2(2164dtttC20)2(2)1(4161求積公式為求積公式為2I20)2()()(kkkxfCab)(61)(64)(61)(210 xfxfxfab)()2(4)(6bfbafafab)(2fI上式稱為Simpson求積公式，也稱三點公式或拋物線公式記為)(2fIS Simpson公式的余項為公式的余項為)()(2IRSRbadxxR)(2)()2(180)4(4fababSimpson公式具有公式具有3次代數(shù)精度次代數(shù)精度4,4 , 1 , 0, 4abhkkhaxnk則取dtttttC)4)(3( )2)(1(! 44140)4(0907dtttttC)4)(3( )2(! 34

9、140)4(19032dtttttC)4)(3( )1(! 2! 24140)4(29012dtttttC)4)(2( )1(! 34140)4(39032dtttttC)3)(2( )1(! 44140)4(4907)(4fI40)4()()(kkkxfCab)(907)(9032)(9012)(9032)(907)(43210 xfxfxfxfxfab)(7)(32)(12)(32)(79043210 xfxfxfxfxfab上式稱為上式稱為Cotes求積公式，也稱也稱五點公式記為)(4fIC )()(4IRCRbadxxR)(4)()4(945)(2)6(6fabab使用使用n次次Lag

10、range插值多項式的插值多項式的Newton-Cotes公式至少具有公式至少具有n次代數(shù)精度次代數(shù)精度,并且并且n為偶數(shù)時至為偶數(shù)時至少具有少具有n+1次代數(shù)精度次代數(shù)精度.n=n=偶數(shù)時偶數(shù)時Newton-Cotes Newton-Cotes 求積公式的代數(shù)精確度求積公式的代數(shù)精確度bqx bn)(nknkk)!(n(x)q(x)n11101 1則次多項式對dt)t ()t ( t)thax(dx)x(wdx)x(wdx)x(dx)x(nnnbanbabanbahbb)!n()(qPq)n(n1 102111令積分誤差：次代數(shù)精確度。有為偶數(shù)時至少求積公式當即即：，為偶數(shù)時，上式積分為當

11、1n n CotesNewton )()( 0n dxxdxxbanbaPqk)dt)(tk(t)kk)(t(t)(ttn)dt(t)(tt kn212111200k)du)(uk(u)u(u)k(uk)(ukt ukk111 令分為零！點上的對稱區(qū)間上的積奇函數(shù)在以零點為對稱令H(u)H(u)(k)u)(ku()uu)()kuk)(u(u) H(k)(uk(u)u(u)kk)(u(uH(u)k1111111 12dtjtknknCnkjnjknnk 00)()()!( !)1(無關與函數(shù)的劃分有關的節(jié)點只與積分區(qū)間)(,xfxbaj因此用因此用Newton-CotesNewton-Cotes

12、公式計算積分的舍入誤差主要由公式計算積分的舍入誤差主要由的計算引起函數(shù)值)(kxf其值可以精確給定其值可以精確給定響的舍入誤差對公式的影只需討論)(kxf)()()(,)(計算值的近似值作為而以為精確值假設kkkxfxfxf為誤差)()(kkkxfxfnInkknkxfCab0)()()(記)(計算值的近似值為nI而理論值為nInkknkxfCab0)()()(的誤差為與nnIInnIInkkknkxfxfCab0)()()()(nnIInkkknkxfxfCab0)()()()(nkknkCab0)()(nkkCab0)()()(kkkxfxfkmax設10nkkC, 1, 0, 70nkk

13、kCCn)(ab的增大而增大且隨有正有負nCCnnkkk, 1, 80定義定義2 2 在機械求積公式中，若在機械求積公式中，若00lim()( )nbkkankhA f xf x dx其中其中11max()iii nhxx 則稱機械求積公式是則稱機械求積公式是的。的。使用機械求積公式計算使用機械求積公式計算()kf x得到的近似值記為得到的近似值記為kf記記kkkfxf)(為誤差為誤差0( )()nnkkkIfA f x0( )nnkkkIfA f舍入誤差舍入誤差nkkknkkkknnAfxfAfIfI00)()()(這表明求積公式計算是穩(wěn)定的。這表明求積公式計算是穩(wěn)定的。定義定義3 3 對任

14、給對任給只要只要成立，就稱機械求積公式是成立，就稱機械求積公式是的。的。0若若0kkfxf)(就有就有nkkknkkkknnAfxfAfIfI00)()()(),1 , 0(0nkAk知，由穩(wěn)定性定義的條件取ab, 0kkfxf)(nkkknkkkknnAfxfAfIfI00)()()()(0abAnkkHavent we had enough formulae? Whats up now?Oh come on, you dont seriously consider h=(b a)/2 acceptable, do you?Why cant you simply refine the par

15、tition if you have to be so picky?Dont you forget the oscillatory nature of high-degree polynomials!Uh-oh固定時而節(jié)點個數(shù)的長度較大當積分區(qū)間1,nba直接使用直接使用Newton-CotesNewton-Cotes公式的余項將會較大公式的余項將會較大增加時即而如果增加節(jié)點個數(shù)1,n公式的舍入誤差又很難得到控制公式的舍入誤差又很難得到控制為了提高公式的精度為了提高公式的精度, ,又又使算法簡單易行使算法簡單易行, ,往往使用往往使用復化方法復化方法分成若干個子區(qū)間即將積分區(qū)間,ba然后然后在

16、每個小區(qū)間上使用低階在每個小區(qū)間上使用低階Newton-CotesNewton-Cotes公式公式最后將每個小區(qū)間上的積分的近似值最后將每個小區(qū)間上的積分的近似值相加相加 復化復化 Simpson 公式：公式：),., 0(,nkhkaxnabhk )()(4)(6)(1211 kkkxxxfxfxfhdxxfkkkx21 kx1 kx44444 )()(2)(4)(6)(1010121 nknkkkbabfxfxfafhdxxf= Sn注：注：為方便編程，可采用另一記法：令為方便編程，可采用另一記法：令 n = 2n 為偶數(shù)，為偶數(shù)， 這時這時 ，有，有hkaxhnabhk ,2 )()(2

17、)(4)(3 koddkevenkknbfxfxfafhS復化求積公式的余項和收斂的階復化求積公式的余項和收斂的階我們知道,三個求積公式的余項分別為)(TR)(12)(3fab )(SR)()2(180)4(4fabab)(CR)()4(945)(2)6(6fabab單純的求積公式單純的求積公式復化求積公式的每個小區(qū)間)(122kfhh )(2180)4(4kfhh)(49452)6(6kfhh )(12103 nkkfh,)(. 12baCxf設被積函數(shù)則復合梯形公式的余項為nTI 103)(12nkkfh)(max)()(min10 xfnfxfbxankkbxa 由于使得由介值定理,ba

18、)()(10fnfnkk 即有即有)(12)(2fhab nTI 103)(12nkknfnh)(123fnh 10)4(45)(2180nkkfh,)(. 24baCxf若被積函數(shù)nSI 公式的余項為復合足夠大時則Simpsonn,)(2180)4(4fhabnTI nSI 階無窮小量，的分別是42h)(2ho)(4ho)(12)(2fhab )(2180)4(4fhab 例例1 對于函數(shù)對于函數(shù)f(x)=sinx/x，給出，給出n=8的函數(shù)表，的函數(shù)表，試用復化梯形公式和復化辛普森公式試用復化梯形公式和復化辛普森公式 計算積分計算積分 10.sindxxxIxf(x)01/81/43/81

19、/25/83/47/8110.99739780.98961580.97672670.95885100.93615560.90885160.87719250.8414709 解解 將積分區(qū)間將積分區(qū)間0,1劃分為劃分為8等分，用復化梯形公式求得等分，用復化梯形公式求得.9456909. 08 T而將積分區(qū)間而將積分區(qū)間0, 1劃分為劃分為24等等分，用復化辛普森公式求得分，用復化辛普森公式求得.9460832. 04 S 比較上面兩個計算結果比較上面兩個計算結果T8與與S4，它們都需要提供，它們都需要提供9個點上的函數(shù)值，然而精度卻差別很大，同積分準個點上的函數(shù)值，然而精度卻差別很大，同積分準確

20、值確值I=0.9460831比較，應用復化梯形公式計算的結比較，應用復化梯形公式計算的結果果T8=0.9456909只有只有2位有效數(shù)字，而應用復化辛普位有效數(shù)字，而應用復化辛普森公式計算的結果森公式計算的結果S4= 0.9460832卻有卻有6位有效數(shù)字位有效數(shù)字. 為了利用余項公式估計誤差，要求為了利用余項公式估計誤差，要求f(x)=sinx/x的的高階導數(shù)，由于高階導數(shù)，由于.)cos(sin)(10 dtxtxxxf所以有所以有.2cos)cos()(1010)( dtkxttdtxtdxdxfkkkk 于是于是.112cos)(max10)(10 kdtkxttxfkkx 復化梯形公

21、式誤差復化梯形公式誤差為為.000434. 03181121)(max12)(210288 xfhTIfRx復化辛普森公式誤差復化辛普森公式誤差為為.10271. 0514128801)(6444 SIfR 例例2 利用復利用復化梯形公式化梯形公式計算計算 使其誤使其誤差限為差限為0.5*10-6，應將區(qū)間，應將區(qū)間0, 1幾等分幾等分?,sin10 dxxxI 解解 利用例利用例1的結果的結果取取n=236可滿足要求可滿足要求.由由復化梯形公式的余項得復化梯形公式的余項得.11)(max)(10 kxfkx222410111()10.12122136nR Thfhh 6因此只需將區(qū)間因此只需

22、將區(qū)間0, 1四等分，即取四等分，即取9個點個點42 h444611( )101802900 22nbahhISf n3.4取取n=4 使用復合使用復合Cotes公式，只需要將區(qū)間公式，只需要將區(qū)間1等分，即四小等等分，即四小等分，五個點。分，五個點。 前面用復化梯形公式計算此題，滿足相同的精度前面用復化梯形公式計算此題，滿足相同的精度需要將區(qū)間需要將區(qū)間0, 1劃分劃分17等分，可見復化辛普森公式的等分，可見復化辛普森公式的精度的確比復化梯形公式精度高同樣也可用精度的確比復化梯形公式精度高同樣也可用| S4m- -S2m |來控制計算的精度來控制計算的精度. 這就是下面要介紹的這就是下面要介

23、紹的龍貝格求積龍貝格求積公式公式.例例 用復化用復化Simpson公式計算積分公式計算積分 的近似值，的近似值，并估計誤差。（取并估計誤差。（取n=5）101dxIx 解：解：n=5，h=(1-0)/n=0.2，節(jié)點列為，節(jié)點列為0 10 110., ,ixii 則復化則復化Simpson公式為公式為11111121 0 1 11 02 1 04 1 06 1 080264444441 01 1 03 1 05 1 07 1 09.I 截斷誤差估計：截斷誤差估計：44450 145454242412100 1241 3 10180180( )( ) , ( ),max( )()()( / )(

24、).xfxmfxxba hmR 1 052 083333 071429 062500 055560033334 090909 076923 066667 058824 052632(. )( .).( .) 0 03333 20 79450 69315. 理查德森理查德森外推法外推法 /* Richardsons extrapolation */利用利用低低階公式產(chǎn)生階公式產(chǎn)生高高精度的結果。精度的結果。設對于某一設對于某一 h 0，有公式，有公式 T0(h) 近似計算某一未知值近似計算某一未知值 I。由。由Taylor展開得到：展開得到： T0(h) I = 1 h + 2 h2 + 3 h

25、3 + i 與與 h 無關無關現(xiàn)將現(xiàn)將 h 對分，得：對分，得：( () )( () )( () ).)(3232222120 hhhhIT Q：如何將公式精度由如何將公式精度由 O(h) 提高到提高到 O(h2) ？.432112)()(23322020 hhIhTTh 即：即：.12)()(2)(32210201 hhIhTThTh .)(42312 hhIhT 12)()(221212 hTTh.)(2211 mmmhhIhT 12)()(2121 mmhmmhTT求積公式 (1)當求積系數(shù) 、求積節(jié)點 都可以自由選取時,其代數(shù)精確度最高可以達到多少次? 1( )( ) ( )()( ,

26、)nbkkakI fx f x dxA f xRf1nkkA1nkkx4.5 高斯型積分高斯型積分 /* Gaussian Quadrature */bankkkxfAdxxfx0)()()(構造具有構造具有2n+1次代數(shù)精度的求積公式次代數(shù)精度的求積公式將節(jié)點將節(jié)點 x0 xn 以及系數(shù)以及系數(shù) A0 An 都作為待定系數(shù)。都作為待定系數(shù)。令令 f (x) = 1, x, x2, , x2n+1 代入可求解，得到的公式代入可求解，得到的公式具有具有2n+1 次代數(shù)精度。這樣的節(jié)點稱為次代數(shù)精度。這樣的節(jié)點稱為Gauss 點點，公式稱為公式稱為Gauss 型求積公式型求積公式。例：例：求求 的

27、的 2 點點 Gauss 公式。公式。dxxfx)(10解：解：設設 ，應有，應有 3 次代數(shù)精度。次代數(shù)精度。 101100)()()(xfAxfAdxxfx代入代入 f (x) = 1, x, x2, x3 31130092211200721100521032xAxAxAxAxAxAAA2776. 03891. 02899. 08212. 01010 AAxx不是線性方程組，不是線性方程組，不易求解。不易求解。正交多項式正交多項式證明：證明： “” 對任意次數(shù)對任意次數(shù)不大于不大于n 的多項式的多項式 Pm(x)， Pm(x) w(x)的次數(shù)的次數(shù)不大于不大于2n+1，則代入公式應則代入公

28、式應精確成立精確成立： nkkkmkbamxwxPAdxxwxPx0)()()()()( 0= 0 x0 xn 為為 Gauss 點點, 則公式則公式 bankkkxfAdxxfx0)()()( 至少有至少有2 2n n+1+1次代數(shù)精度。次代數(shù)精度。與任意次數(shù)不大于與任意次數(shù)不大于n 的多項式的多項式 P(x) （帶權）正交（帶權）正交。 nkkxxxw0)()(P119;Th5 x0 xn 為為 Gauss 點點 0)()()(1dxxxwxPnba“” 要證明要證明 x0 xn 為為 Gauss 點，即要證公式對點，即要證公式對任意次數(shù)任意次數(shù)不大于不大于2n+1 的多項式的多項式 Pm

29、(x) 精確成立，精確成立，即證明：即證明： nkkmkbamxPAdxxPx0)()()( 設設)()()()(xrxqxwxPm bababamdxxrxdxxqxwxdxxPx)()()()()()()( 0 nkkkxrA0)( nkkmkxPA0)( n n次多項式次多項式)( 0 )()()()(kkkkkmxrxrxqxwxPTH5TH5表明，在表明，在a,ba,b上帶權的上帶權的n+1n+1次正交多項式次正交多項式的零點就是求積公式的高斯點。的零點就是求積公式的高斯點。 如何通過正交多項式求高斯點？如何通過正交多項式求高斯點？& 正交多項式族正交多項式族 0, 1, , n,

30、有性質：有性質：任意次數(shù)不大于任意次數(shù)不大于n 的多項式的多項式 P(x) 必與必與 n+1 正交。正交。若取若取 w(x) 為其中的為其中的 n+1則則 n+1的根的根就是就是 Gauss 點。點。再解上例：再解上例： 101100)()()(xfAxfAdxxfxStep 1：構造正交多項式構造正交多項式 2設設cbxxxaxxx 2210)(,)(, 1)( 53 a0)(10 dxaxx0),(10 1021102100)(53(0),(0)(0),(dxcbxxxxdxcbxxx 215910 cb即：即：215910)(22 xxx Step 2：求求 2 = 0 的的 2 個根，即為個根，即為 Gauss 點點 x0 ，x1221/20)9/10(9/1021;0 xStep 3：代入代入 f (x) = 1, x