代數(shù)精度插值求積及復化公式PPT

1、但是，在工程技術(shù)領(lǐng)域，在實際使用上述求積分方法時，往往會遇到下面情況：,1. 函數(shù)f (x)沒有具體的解析表達式，只有一些由實驗測試數(shù)據(jù)形成的表格或 圖形。,關(guān)于定積分的計算，我們知道，只要求出f (x)的一個原函數(shù)F(x)，就可以利用牛頓萊布尼慈（Newton-Leibniz）公式出定積分值：,3. f (x) 的結(jié)構(gòu)復雜，求原函數(shù)困難，即不定積分難求。,2. f (x)的原函數(shù)無法用初等函數(shù)表示出來，如：,由于以上種種原因，因此有必要研究積分的數(shù)值計算方法，進而建立起上機計算定積分的算法。此外，數(shù)值積分也是研究微分方程和積分方程的數(shù)值解法的基礎(chǔ)。,數(shù)值積分,1.1 構(gòu)造數(shù)值求積公式的基本思

2、想,定積分I=ab f (x)dx在幾何上為x=a, x=b, y=0和y=f (x)所圍成的曲邊梯形的面積。定積分計算之所以困難，是不規(guī)則圖形的面積。由積分中值定理，對連續(xù)函數(shù)f (x)，在區(qū)間a, b 內(nèi)至少存在一點，使：,也就是說,曲邊梯形的面積I 恰好等于底為b-a, 高為f ()的規(guī)則圖形矩形的面積(圖7-1), f ()為曲邊梯形的平均高度,然而點的具體位置一般是不知道的,因此難以準確地求出f ()的值。但是,由此可以得到這樣的啟發(fā),只要能對平均高度f ()提供一種近似算法,便可以相應地得到一種數(shù)值求積公式。,如用兩端點的函數(shù)值f (a)與f (b)取算術(shù)平均值作為平均高度f ()

3、的近似值,這樣可導出求積公式：,第七章 數(shù)值積分與微分,7-3,更一般地在區(qū)間a, b 上適當選取某些點xk (k=0,1,n), 然后用f (xk) 的加權(quán)平均值近似地表示f (),這樣得到一般的求積公式：,其中,點xk 稱為求積節(jié)點,系數(shù)Ak 稱為求積系數(shù)，Ak 僅僅與節(jié)點xk 的選取有關(guān),而不依賴于被積函數(shù)f (x)的具體形式。,另一方面定積分的定義，,其中xk是a, b 的每一個分割小區(qū)間的長度,它與f (x)無關(guān),去掉極限,由此得到近似計算公式：,因此，式（7-1）可作為一般的求積公式,其特點是將積分問題歸結(jié)為函數(shù)值的計算,從而避開了使用牛頓一萊布尼慈公式需要求原函數(shù)的困難,適合于函

4、數(shù)給出時計算積分,也非常便于設計算法,便于上機計算。 求積公式（7-1）的截斷誤差為：,Rn也稱為積分余項.,1.2 代數(shù)精度,定義1,如果某個求積公式對所有次數(shù)不大于m的多項式都精確成立，而至少對一個m +1次多項式不精確成，則稱該公式具有m次代數(shù)精度。,一般來說，代數(shù)精度越高，求積公式越好。為了便于應用，由定義1容易得到下面定理。,數(shù)值積分是一種近似計算,但其中有的公式能對較多的函數(shù)準確成立,而有的只對較少的函數(shù)準確成立。為了反映數(shù)值積分公式的準確差別,引入代數(shù)精度的概念。,試驗證梯形公式具有一次代數(shù)精度。,例1,可以證明矩形公式的代數(shù)精度也是一次的。,定理1,一個求積公式具有m次代數(shù)精度

5、的充分必要條件是該求積公式對 1,x,x2,xm 精確成立，而對xm+1不精確成立。,第七章 數(shù)值積分與微分,7-6,上述過程表明,可以從代數(shù)精度的角度出發(fā)來構(gòu)造求積公式. 如,對于求積公式（7-1）,若事先選定一組求積節(jié)點xk (k=0,1,n,), xk可以選為等距點,也可以選為非等距點,令公式對f(x)=1,x,xn 精確成立,即得：,這是關(guān)于A0、A1、An的線性方程組,系數(shù)行列式為范德蒙行列式,其值不等于零,故方程組存在唯一的一組解。,求解方程組(7-2)確定求積系數(shù)Ak,這樣所得到的求積公式(7-1)至少具有n次代數(shù)精度.,例2,確定求積公式,使其具有盡可能高的代數(shù)精度。,解：求積

6、公式中含有三個待定參數(shù),可假定近似式（7-3）的代數(shù)精度為m =2,則當f (x)=1，x，x2時，式（7-3）應準確成立，即有：,代回去可得：,檢查（7-4）對 m = 3 是否成立,為此,令 f(x)=x3 代入（7-4）,此時左邊,第七章 數(shù)值積分與微分,7-8,再檢查（7-4）對m=4是否成立,令f(x)=x4代入(7-4),此時:,因此近似式（7-4）的代數(shù)精度為m=3.,由待定系數(shù)法確定的求積公式?jīng)]有確切的誤差估計式，只能從其所具有的代數(shù)精度去判定求積公式的準確程度。,上述方法稱為待定系數(shù)法，在具有盡可能高的代數(shù)精度的要求下，利用它可以得出各種求積公式。,1.3 插值型求積公式,設

7、給定一組節(jié)點a x0 x1 xn-1xn b，且已知f (x) 在這些節(jié)點上的函數(shù)值，則可求 得f (x)的拉格朗日插值多項式：,其中l(wèi)k(x) 為n次插值基函數(shù)。取f (x) Ln(x)，則有：,記：,則有：,這種求積系數(shù)由式（7-5）所確定的求積公式稱為插值型求積公式.,根據(jù)插值余項定理，插值型求積公式的求積余項為：,其中a,b 與x有關(guān).,關(guān)于插值型求積公式的代數(shù)精度，有如下定理。,具有n +1個節(jié)點的數(shù)值求積公式（7-1）是插值型求積公式的充分必要條件是該公式至少具有n次代數(shù)精度。,定理2,定理2說明,當求積公式（7-1）選定求積節(jié)點xk后,確定求積系數(shù)Ak有兩條可供選擇的途徑：求解線

8、性方程 組（7-2）或者計算積分（7-5）,即利用n次代數(shù)精度或插值型積分來確定求積系數(shù). 由此得到的求積公式都是插值型的,其代數(shù)精度均不小于n次.,證：(充分性) 設求積公式（7-1）至少具有n次代數(shù)精度,那么,由于插值基函數(shù) li(x) (i=0,1,n)均是次數(shù)為n的多項式,故式（7-1）對li(x)精確成立,即:,(必要性) 設求積公式（7-1）是插值型的，則對所有次數(shù)不大于n的多項式f (x)，按（7-6）其求積余項Rn = 0，即這時插值型求積公式是精確成立的。由定義1,n+1個節(jié)點的插值型求積公式至少具有n次代數(shù)精度。（證畢）,例3,考察求積公式：,具有幾次代數(shù)精度.,注：n+1

9、個節(jié)點的求積公式不一定具有n次代數(shù)精度.其原因是此求積公式不一定是插值型的。 例：,2 牛頓一柯特斯(Newton-Cotes)公式,本節(jié)介紹節(jié)點等距分布時的插值型求積公式，即牛頓一柯特斯（Newton-Cotes）公式。,2.1 牛頓一柯特斯（Newton-Cotes）公式,設將積分區(qū)間a, b 劃分為n等分,步長h=(b-a)/n,求積節(jié)點取為xk = a+kh(k=0,1,n),由此構(gòu)造插值型求積公式,則其求積系數(shù)為:,記：,稱之為n階牛頓一柯特斯（Newton-Cotes）公式簡記為N-C公式， 稱 為柯特斯系數(shù)。顯然，柯特斯系數(shù)與被積函數(shù)f (x) 和積分區(qū)間a, b 無關(guān)，且為多項

10、式積分，其值可以事先求出備用。表7-1中給了了部分柯特斯系數(shù)。,柯特斯系數(shù),表7-1,經(jīng)計算或查表得到柯特斯系數(shù)后，便可以寫出對應的牛頓一柯特斯（Newton-Cotes）公式。,當n =1時,按公式（7-7）有：,得求積公式：,即梯形公式,當n =2時,第七章 數(shù)值積分與微分,7-15,相應的求積公式：,稱為辛卜生(Simpson)公式.,當n=4時，所得的公式稱作柯特斯公式，它有五個節(jié)點，其系數(shù)：,所以柯特斯公式是：,柯特斯系數(shù)的性質(zhì),1、與積分區(qū)間無關(guān):當n確定后,其系數(shù)和都等于1,即,2、對稱性：,此特性由表7-1很容易看出，對一般情況可以證明。(略),3、柯特斯系數(shù)并不永遠都是正的。

11、 表7-1看出當n = 8時,出現(xiàn)了負系數(shù),在實際計算中將使舍入誤差增大,并且往往難以估計, 從而牛頓一柯特斯公式的收斂性和穩(wěn)定性得不到保證,因此實際計算中不用高階的。,第七章 數(shù)值積分與微分,7-17,第七章 數(shù)值積分與微分,7-18,2n階Newton-Cotes公式至少具有2n+1次代數(shù)精度。,我們知道，由n次插值多項式導出的n次牛頓一柯特斯公式至少具有n次代數(shù)精度. 由于節(jié)點等距，更進一步有以下結(jié)論：,定理3,證：計算知由2n次插值多項式導出的求積公式 的截斷誤差為0即可.,例4,驗證辛卜生(Simpson)公式:,具有三次代數(shù)精度。（定理3直接得到）,解：由定理2, 3個節(jié)點的插值積

12、分公式辛卜生公式至少具有二次代數(shù)精度,因此只需檢查對f (x)=x3成立否。當f (x)=x3時：,所以I = S，表明辛卜生公式對于次數(shù)不超過三次的多項式準確成立，用同樣的方法可以驗證對于f (x)=x4，辛卜生公式不成立，因此辛卜生公式的代數(shù)精度可以達到三次。 在幾種低階N-C公式中, 感興趣的是梯形公式（最簡單,最基本）辛卜生公式和柯特斯公式。,例5,解：由梯形公式（7-9）：,由辛卜生公式（7-10）得：,由柯特斯公式（7-11）得：,事實上，積分的精確值：,與之相比可以看到，柯特斯公式的結(jié)果最好，具有七位有效數(shù)字；辛卜生公式的結(jié)果次之，具有四位有效數(shù)字；而梯形公式的結(jié)果最差,只有兩位

13、有效數(shù)字。,分別用梯型公式、辛卜生公式和柯特斯公式計算積分：,2.2 幾種低價N-C求積公式的余項,考察梯形公式,按N-c的截斷誤差知,梯形公式（7-9） 的余項：,這里被積函數(shù)中的因子t(t1)在區(qū)間0, 1 上不變號（非正），故由積分中值定理，在0, 1 內(nèi)至少存在一點，使：,2. 對于辛卜生公式,需要注意的是，關(guān)于牛頓-科特斯公式的收斂性，可以證明，并非對一切連續(xù)函數(shù)f (x),都有： , 也就是說牛頓柯特斯公式的收斂性沒有保證。當n趨于無窮時，它的穩(wěn)定性也沒有保證，因此，在實際計算中，一般不采用高階(n 8) 的牛頓-柯特斯公式。,3. 柯特斯公式（6-10）的余項為：,在實際計算中常

14、用前面三種低價N-C公式，但若積分區(qū)間比較大，直接使用以上三種低階求積公式，則精度難以保證； 若增加節(jié)點，就要使用高階的N-C公式，然而前面已指出，當n 8時，由于N-C公式的收斂性和穩(wěn)定性得不到保證，因此不能采用高階的公式。事實上，增加節(jié)點，從插值的角度出發(fā)，必然會提高插值多項式的次數(shù)，Runge現(xiàn)象表明，一般不采用高次插值，亦即不用高階N-C公式。 為提高精度，當增加求積節(jié)點時，考慮對被積函數(shù)用分段低次多項式近似，由此導出復化求積公式。,3 復化求積公式,3.1 復化梯形公式,用分段線性插值函數(shù)來近似被積函數(shù),等于把積分區(qū)間分成若干小區(qū)間,在每個小區(qū)間上以梯形面積近似曲邊梯形面積,即用梯形

15、公式求小區(qū)間上積分的近似值.這樣求得的近似值顯然比整區(qū)間上用梯形公式計算精度高。,式（7-15）稱為復化梯形公式。,因為f (x) 在a, b 連續(xù)，由介值定理，存在(a, b)，使得：,從而有：,這就是復化梯形公式的截斷誤差.,3.2 復化Simpson公式和復化Cotes公式,如果用分段二次插值函數(shù)近似被積函數(shù)，即在小區(qū)間上用Simpson公式計算積分近似值，就導出復化Simpson公式。,如果f (x)C(4)a, b,由式（7-13）可得復化Simpson公式的截斷誤差為：,整理得：,式（7-17）稱為復化Simpson公式。,因為f (4)(x) 連續(xù)，故存在(a, b)，使得：,若

16、用復化求積公式計算積分:,的近似值，要求計算結(jié)果有四位有效數(shù)字，n應取多大？,例,解 因為當0 x1時有0.3e-1e-x1于是：,要求計算結(jié)果有四位有效數(shù)字,即要求誤差不超過10-4 / 2.又因為:,由復化梯形公式誤差估計式：,式（7-18）表明,步長h越小,截斷誤差越小.與復化梯形公式的分析相類似,可以證明,當n 時,用復化Simpson公式所求得的近似值收斂于積分值,而且算法具有數(shù)值穩(wěn)定性.,例子的計算結(jié)果表明，為達到相同的精度，用復化Simpson公式所需的計算量比復化梯形公式少，這也說明了復化Simpson公式的精度較高，實際計算時多采用復化Simpson公式。,復化求積方法又稱為

17、定步長方法。復化求積公式,根據(jù)預先給定的精度能估計出合適的步長或 n,進而確定對積分區(qū)間的等分數(shù),如同例7一樣. 然而當被積函數(shù)稍復雜一些，要由誤差估計式給出合適的步長，就要估計被積函數(shù)導數(shù)的上界值，而這一點是相當困難的。,因此若用復化梯形公式求積分,n應等于41即41等分才能達到精度. 若用復化Simpson公式,由式（7-18）,即得n 1.6.故應取n = 2即4等分.,h=1/n,h=1/2n,復化Cotes公式,將區(qū)間a, b分成n 等分,分點為：,用Cotes公式得到復化Cotes公式 ：,復化Cotes公式的截斷誤差為：,要使截斷誤差不超過10-3 / 2，h應取多大？辛普生公式又怎么樣？,用復化梯形求積公式計算積分:,作業(yè),第七章 數(shù)值積分與微分,7-32,4 逐次分半算法(變步長方法),基于復化求積公式（定步長方法）的缺點，常采用變步長方法，即逐步縮小步長，每次將步長縮小一半，或者說逐次等分區(qū)間,