數值分析數值積分

1、會計學1數值分析數值積分數值分析數值積分 對對f( )采用不同的近似計算方法，從而得到各種不同的求積公式。采用不同的近似計算方法，從而得到各種不同的求積公式。 以上三種方法都是用被積函數值的以上三種方法都是用被積函數值的線性組合線性組合來表示積來表示積分值分值。推廣，一般地有推廣，一般地有0( )()nbkkakf x dxA f x求積節(jié)求積節(jié)點點求積系數，與被求積系數，與被積函數無關積函數無關像這樣，將積分用若干節(jié)點上被積函數值的像這樣，將積分用若干節(jié)點上被積函數值的線性組合線性組合來表示來表示的數值積分公式稱為的數值積分公式稱為機械求積公式機械求積公式。0 ( )()nbkkakR ff

2、 x dxA f x 求積誤差求積誤差 機械型求積公式的構造歸結為，確定求積節(jié)點機械型求積公式的構造歸結為，確定求積節(jié)點xk和求積系和求積系數數Ak，使在某種意義下精確度較高?？傊?，要解決三個問，使在某種意義下精確度較高?？傊鉀Q三個問題：題：1. 精確度的度量標準；精確度的度量標準；2. 如何構造具體的求積公式；如何構造具體的求積公式；3. 具體求積公式構造出來后，誤差如何估計？具體求積公式構造出來后，誤差如何估計？定義：定義：代數精度代數精度若某個求積公式對次數若某個求積公式對次數 m 階階的多項式準確成立，而對的多項式準確成立，而對m+1 階階的多項式不一定準確成立。即對應的誤差滿足

3、：的多項式不一定準確成立。即對應的誤差滿足：R Pk =0 對對任意任意 k m 階階的多項式成立，且的多項式成立，且 R Pm+1 0 對對某個某個 m+1 階多項式成立，則稱此求積公式的階多項式成立，則稱此求積公式的代數精度代數精度為為 m 。代數精度與誤差的關系代數精度與誤差的關系：代數精度越高，求積誤差越小。：代數精度越高，求積誤差越小。結論：結論：問題問題1由上面代數精度條件確定求積公式可分兩種情形：由上面代數精度條件確定求積公式可分兩種情形：1. 若事先給定求積節(jié)點若事先給定求積節(jié)點xk(k=0,n),例如被積函數以表的形式例如被積函數以表的形式給出時給出時xk確定，可令確定，可令

4、m=n,由上式確定由上式確定n+1個系數個系數Ak即可即可-待定系數法和插值法待定系數法和插值法。2. 若若xk和和Ak都可選擇，令都可選擇，令m=2n +1，確定，確定xk和法和法Ak -Gauss法法要使求積公式具有要使求積公式具有m階代數精度，則它對階代數精度，則它對1,x,xm均準確成立均準確成立，即，即02201101211nkknkkknmmmkkkAbaA xbaA xbamm+1個方程，個方程，2n+2個未知數個未知數問題問題2Case 1-方法方法11 插值型求積插值型求積 公式公式思思路路利用利用插值多項式插值多項式 則積分易算。則積分易算。)()(xfxPn 在在a, b

5、上取上取 a x0 x1 xn b，做，做 f 的的 n 次插次插值多項式值多項式 ，即得到，即得到 nkkknxlxfxL0)()()( babaknkkdxxlxfdxxf)()()(0Ak bakjxxxxkdxAjkj)()(由由 決定，決定，與與 無關。無關。節(jié)點節(jié)點 f (x)插值型積分公式插值型積分公式/*interpolatory quadrature*/ bankkxnbanbanbankkkdxxxnfdxxRdxxLxfxfAdxxffR0)1(0)()!1()()()()()()( 誤差誤差Case 1-方法方法21 Newton-Cotes Formulae例：例：對

6、于對于a, b上上1次插值，有次插值，有)()()(1bfafxLabaxbabx )()()(2221bfafdxxfAAabbaab 考察其代數精度。考察其代數精度。f(x)abf(a)f(b)梯形公式梯形公式/* trapezoidal rule*/解：解：逐次檢查公式是否精確成立逐次檢查公式是否精確成立代入代入 P0 = 1： baabdx111 2 ab=代入代入 P1 = x ：=代入代入 P2 = x2 ： 222abbadxx 2baab 3233abbadxx 222baab 代數精度代數精度 = 11 Newton-Cotes FormulaeTh1.形如形如 的求積公式至

7、少有的求積公式至少有 n 次代數精度次代數精度 該該公式為公式為插值型插值型（即：（即： ） nkkkxfA0)( bakkdxxlA)( 當節(jié)點當節(jié)點等距分布等距分布時：時：ninabhhiaxi,., 1, 0, dxxxxxAnxxijjiji 0)()( njiinnjidtjtininabdthhjihjt00)()!( !)1)()()(令令htax Cotes系數系數)(niC注：注：Cotes 系數僅取決于系數僅取決于 n 和和 i，可查表得到。與，可查表得到。與 f (x) 及區(qū)間及區(qū)間a, b均無關。均無關。 2 Newton-Cotes 公式公式( )00( )()nbn

8、kakf x dxbaCf xkhNewtonCotes formula1 Newton-Cotes Formulae21,21)1(1)1(0 CCn = 1:)()(2)(bfafabdxxfba Trapezoidal RuledxbxaxffRbax)(!2)( /* 令令 x = a+th, h = b a, 用中用中值定理值定理 */1, , )(1213abhbafh 代數精度代數精度 = 1n = 2:61,32,61)2(2)2(1)2(0 CCC)()(4)(6)(2bffafabdxxfbaba Simpsons Rule代數精度代數精度 = 32,),(,)(901)4

9、(5abhbafhfR n = 4: Cotes Rule, 代數精度代數精度 = 5,)(9458)6(7 fhfR 01234( )7 () 32 ( ) 12 () 32 ( )7 ()90bab af x dxf xf xf xf xf x偶數階偶數階N-C公式具公式具有有n+1階代數精度階代數精度n = 3: Simpsons 3/8-Rule, 代數精度代數精度 = 3,)(803)5(5 fhfR 對稱節(jié)點的系數相同對稱節(jié)點的系數相同Cotes公式公式是用不同節(jié)是用不同節(jié)點的函數值點的函數值（高度）的（高度）的加權平均來加權平均來近似區(qū)間的近似區(qū)間的平均高度平均高度注：當注：當n

10、 8時，時，Cotes系數有負，造成公式不穩(wěn)定，因此常系數有負，造成公式不穩(wěn)定，因此常用低階用低階Cotes公式。公式。(1)0020000/22/20( ) ()()(1)!, () even, /2 integer, let /2, we have (/2)nnnbbxkkaakknnnkknnnnkfR fx x dxx x dxnxxjh xxthR fht k dtnntu nR fhu nk du 證明：只需證明n為偶數時，為偶數時， N-C公式對公式對f(x)=xn+1的余項的余項R(f)=0即可。即可。因因 f(n+1)(x)=(n+1)!, 由余項公式得由余項公式得Th2.

11、n為偶數時為偶數時， N-C公式至少具有公式至少具有n+1階代數精階代數精度。度。00/20/2/2/21/2/2/2/2/2/2 ( )(/2)(/2)(/2) ( /2)()1( )( ) odd 0.nnkknnkjnnnnjnjnnnjnjnlet H uunkuknuknujlet jknHuujujujujH uH uR f 注：當注：當n 為偶數時，為偶數時，Cotes公式具有公式具有n+1階精度，與階精度，與n+1階階Cotes公式精度相同，但少計算一個節(jié)點上的函數值，公式精度相同，但少計算一個節(jié)點上的函數值，因此一般常用偶數階因此一般常用偶數階Cotes公式。公式。偶數階偶數

12、階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)=f(a), H(b)=f(b), H (k)(a+b)/2) = f (k)(a+b)/2).HW: p.151-152 #1-6數值穩(wěn)定性的一般概念數值穩(wěn)定性的一般概念N-C的穩(wěn)定性的穩(wěn)定性3 復合求積復合求積 /* Composite Quadrature */Havent we had enough formulae?

13、 Whats up now?Oh come on, you dont seriously consider h=(b a)/2 acceptable, 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 復合復合求積公式求

14、積公式。 復合梯形公式：復合梯形公式：),., 0(,nkhkaxnabhk 在每個在每個 上用梯形公式：上用梯形公式：,1kkxx nkxfxfxxdxxfkkxxkkkk,., 1,)()(2)(111 11)()(2)(2nkkbfxfafh bankkkxfxfhdxxf11)()(2)(= Tn),(),()(12)()(12)(1221213bafabhnfabhfhfRnkknkk /*中值定理中值定理*/2 Composite Quadrature 復化復化 Simpson 公式：公式：),., 0(,nkhkaxnabhk )()(4)(6)(1211 kkkxxxfxfxf

15、hdxxfkkkx21 kx1 kx44444 )()(2)(4)(6)(1010121 nknkkkbabfxfxfafhdxxf= Sn)(2180)4(4 fhabfR 注：注：為方便編程，可采用另一記法：令為方便編程，可采用另一記法：令 n = 2n 為偶數為偶數， 這時這時 ，有，有hkaxhnabhk ,2 )()(2)(4)(3 koddkevenkknbfxfxfafhS2 Composite Quadrature 收斂速度與誤差估計：收斂速度與誤差估計：定義定義 若一個復化積分公式的誤差滿足若一個復化積分公式的誤差滿足 且且C 0，則，則稱該公式是稱該公式是 p 階收斂階收斂

16、的。的。 ChfRphlim0321012: ()()1212 11( )( )( )1212nnkkkkbahhR ffhfR ffx dxfbfah 復化梯形公式/*中值定理中值定理*/類似的，可得類似的，可得44(5)(5)66 1:( )( )1802 2:( )( )9454R ffbfahR ffbfah 復化Simpson公式復化Cotes公式2階收斂階收斂4階收斂階收斂6階收斂階收斂例例1：計算計算dxx 10142 解：解： )1()(2)0(161718fxffTkk8kxk 其中其中= 3.138988494 )1()(2)(4)0(241oddeven4fxfxffSk

17、k8kxk 其中其中= 3.141592502運算量基運算量基本相同本相同Q: 給定精度給定精度 ，如何取，如何取 n ?例如：要求例如：要求 ，如何判斷，如何判斷 n = ？ |nTI2 ( )( )12hR ffbfa 上例中若要求上例中若要求 ，則，則610| nTI622106| )0() 1 (|12| | hffhfRn00244949. 0 h即：取即：取 n = 4092 Composite Quadrature事后誤差估事后誤差估計式，可用計式，可用來判斷迭代來判斷迭代是否停止。是否停止。始步長始步長h0.5 10-24 龍貝格龍貝格積分積分 /* Romberg Integ

18、ration */復化梯形公式算法簡單，但精度較差，收斂速度（復化梯形公式算法簡單，但精度較差，收斂速度（2階收斂）階收斂）較慢，如何提高收斂速度？較慢，如何提高收斂速度？注：按上面規(guī)律，可以構造線性組合系數為注：按上面規(guī)律，可以構造線性組合系數為的新的積分公式，但當的新的積分公式，但當m 4時，前一個系數接近于時，前一個系數接近于1，后一，后一個系數接近于個系數接近于0，這樣構造出的新公式與前一個公式結果差，這樣構造出的新公式與前一個公式結果差別不大，反而增加計算量，因此實際上常做到別不大，反而增加計算量，因此實際上常做到Romberg公式公式為止。為止。41,41 41mmm例：例：計算計

19、算dxx 10142 已知對于已知對于 = 10 6 須將區(qū)間對分須將區(qū)間對分 9 次，得到次，得到 T512 = 3.14159202由由 來計算來計算 I 效果是否好些效果是否好些？nnnnTTTTI313414422 考察考察412 nnTITI483134TT = 3.141592502= S4一般有：一般有：nnnSTT 1442nnnCSS 144222nnnRCC 144323Romberg 序列序列 Romberg 算法：算法： ? ? 0, k=0,1,n定理定理()()22202:( )( )2( )( ), ( )( )0jkjx xkxxj kknbki kikikiaibkkaproofl xGaussLagrangel xnl x dxAl xl xl x dxA設是以點為節(jié)點的插值基函數，則是一個 次多項式，因此求積公式對它準確成立，即又求積系數的求積系數的另一種計算另一種計算方法方法結論：結論：Gauss型積分公式是數值穩(wěn)定型積分公式是數值穩(wěn)定的。（穩(wěn)定性分析類似于的。（穩(wěn)定性分析類似于n 7的的N-C公公式）式）6 Numerical Differentiationh=0.8，精，精度度像這樣，將微分的計算歸結為在若干節(jié)點上函數值的像這樣，將微分的計算歸結為在若干節(jié)點上函數值的線性組線性組合合的數值微分方法稱為的數值微分方法稱為機械