Ch10：數(shù)值計(jì)算方法之插值方法

1、第10章 插值方法我們?cè)谛蜓灾性?jīng)提到過(guò)，計(jì)算方法研究的最基本問(wèn)題是如何把復(fù)雜的數(shù)學(xué)問(wèn)題求解有效地轉(zhuǎn)化為對(duì)有限數(shù)位的數(shù)進(jìn)行有限次的四則運(yùn)算問(wèn)題?？梢赃@樣認(rèn)為，插值方法是計(jì)算方法成為一門(mén)獨(dú)立的數(shù)學(xué)分支的重要標(biāo)志。實(shí)際上，在計(jì)算機(jī)問(wèn)世以前，人們正是利用插值方法從根本上解決了高等數(shù)學(xué)中的的各種數(shù)值算問(wèn)題。早期的插值方法主要應(yīng)用于計(jì)算復(fù)雜的函數(shù)值，或者說(shuō)制造數(shù)學(xué)用表。比如我們很容易制造1到10的具有6位數(shù)字的3次方表，反過(guò)來(lái)我們可以利用這個(gè)3次方表借助插值的方法簡(jiǎn)單地制造出1到1000以?xún)?nèi)的數(shù)的具有6位數(shù)字的3次方根表。第10章 插值方法對(duì)于現(xiàn)代的計(jì)算工具來(lái)說(shuō)，插值方法早期的應(yīng)用領(lǐng)域已經(jīng)大大縮小了，但

2、它解決問(wèn)題的原理，思想，方法仍然是我們今天的計(jì)算方法的精神支柱。如果說(shuō)早期的插值方法主要是利用有理函數(shù)的可計(jì)算性來(lái)解決非有理函數(shù)的計(jì)算問(wèn)題，那么今天的插值方法基于同樣的思路：利用初等函數(shù)的可計(jì)算性解決非初等函數(shù)的計(jì)算問(wèn)題。由于非初等函數(shù)的計(jì)算問(wèn)題大量出現(xiàn)在數(shù)值積分以及求微分方程數(shù)值解中，所以我們這一章的學(xué)習(xí)是直接為后面的課程打基礎(chǔ)。10.1 插值問(wèn)題概述假設(shè)f(x)是某個(gè)表達(dá)式很復(fù)雜,甚至根本寫(xiě)不出來(lái)的實(shí)函數(shù),且已知f(x)在某個(gè)區(qū)間a,b上的n+1個(gè)互異的點(diǎn)x0,x1,xn處的函數(shù)值f(x0),f(x1),f(xn)，我們希望找到一個(gè)簡(jiǎn)單的函數(shù)y=P(x),使得 P(xk)=f(xk),k=

3、0,1,n.注釋?zhuān)喝绻覀冋业搅诉@樣的函數(shù)y=P(x),我們就可以在一定范圍內(nèi)利用P(x)近似表示f(x),從而解決了相應(yīng)的計(jì)算問(wèn)題。1.利用函數(shù)值列表來(lái)表示插值問(wèn)題對(duì)于一個(gè)插值問(wèn)題來(lái)說(shuō)，我們的已知條件就是n+1個(gè)互異的點(diǎn)處的函數(shù)值.回顧高等數(shù)學(xué)中學(xué)習(xí)過(guò)的函數(shù)的表示方法，我們可用下面表1的形式列出已知的函數(shù)值，并簡(jiǎn)稱(chēng)為由表1給出的插值問(wèn)題。表1：插值問(wèn)題的函數(shù)值列表k01nxx0 x1xnf(x)f(x0)f(x1)f(xn)2.重要術(shù)語(yǔ)對(duì)于n+1個(gè)基點(diǎn)的插值問(wèn)題，我們稱(chēng)：f(x)為被插值函數(shù);P(x)為插值函數(shù)；x0,x1,xn為插值基點(diǎn)或插值節(jié)點(diǎn);P(xk)=f(xk),k=0,1,n為插

4、值條件；a,b為插值區(qū)間。對(duì)于早期的插值問(wèn)題來(lái)說(shuō)，f(x)通常是已知的，比如對(duì)數(shù)函數(shù)，指數(shù)函數(shù)，三角函數(shù)等，這些問(wèn)題現(xiàn)在已經(jīng)不用插值法來(lái)解決了。對(duì)于現(xiàn)在的許多實(shí)際問(wèn)題來(lái)說(shuō)，我們并不知道f(x)的具體形式，所對(duì)應(yīng)的函數(shù)值可能是由測(cè)量?jī)x器或其他物理設(shè)備中直接讀出來(lái)的，f(x)只是一個(gè)概念中的函數(shù)。3.重要提示：假如我們得到了某個(gè)函數(shù)y=f(x)在n+1個(gè)互異的點(diǎn)x0,x1,xn處的函數(shù)值yk=f(xk)，k=0,1,n，而對(duì) f(x)的其他特征一無(wú)所知，我們同樣可以得到一個(gè)函數(shù)值列表，從而得到一個(gè)插值問(wèn)題。表2：插值問(wèn)題的（函數(shù)）觀測(cè)值列表在這個(gè)問(wèn)題中，我們實(shí)際上看不到被插函數(shù)，或者說(shuō)被插函數(shù)只是

5、一個(gè)概念上的函數(shù)。k01nxx0 x1xnyy0y1yn4.理論問(wèn)題由于f(x)的表達(dá)式很復(fù)雜或者根本就寫(xiě)不出來(lái)，因此我們的目的是要利用插值函數(shù)p(x)來(lái)近似地表示f(x).對(duì)于早期的插值問(wèn)題來(lái)說(shuō)，我們只是為了得到f(x)的近似值，所以我們要求|p(x)-f(x)|充分小即可。對(duì)于現(xiàn)代的問(wèn)題來(lái)說(shuō)，我們很可能還要求|P(x)-f(x)|以及|P/(x)-f/(x)|都充分小。如果f(x)足夠光滑，那么由泰勒級(jí)數(shù)的理論可以保證當(dāng)區(qū)間充分小，而n充分大時(shí)，結(jié)果一定是有效的。對(duì)于數(shù)值計(jì)算問(wèn)題來(lái)說(shuō)，首先必須有一種方法能算出結(jié)果來(lái)，可以通過(guò)驗(yàn)算來(lái)判定方法的有效性。在我們的課程中，我們?cè)谶m當(dāng)?shù)臅r(shí)候也討論一些

6、理論問(wèn)題，但重點(diǎn)還是算法，還是編程，還是上機(jī)。10.2一般的多項(xiàng)式插值問(wèn)題對(duì)于n+1個(gè)基點(diǎn)的插值問(wèn)題，如果要求插值函數(shù)是次數(shù)不超過(guò)n的多項(xiàng)式，記為Pn(x)，則相應(yīng)的問(wèn)題就是多項(xiàng)式插值，并且把Pn(x)稱(chēng)為插值多項(xiàng)式。由于次數(shù)不超過(guò)n的多項(xiàng)式的一般形式為 Pn(x)=a0+a1x+a2x2+anxn (1) 所以只要確定了n+1個(gè)系數(shù)a0,a1,an，我們便確定了一個(gè)插值多項(xiàng)式。在這一節(jié)中，我們主要解決插值多項(xiàng)式的存在性和唯一性問(wèn)題，為后面的理論分析打基礎(chǔ)，具體的方法留到下面兩節(jié)討論。1多項(xiàng)式插值的一般方法對(duì)于n個(gè)基點(diǎn)的多項(xiàng)式插值問(wèn)題，我們可以把n+1個(gè)插值條件 Pn(xk)=yk,k=0,1

7、,n 分別代入到前面給出的（1）式 Pn(x)=a0+a1x+a2x2+anxn 中，即可得到下面的線(xiàn)性方程組，相對(duì)說(shuō)來(lái)問(wèn)題還算簡(jiǎn)單。 （2）2.唯一性定理. 范德蒙行列式定理1：n+1級(jí)范德蒙（Vandermonde）行列式 不等于零的充要條件是諸x0,x1,xn兩兩互不相同。這是代數(shù)學(xué)中很著名的一個(gè)定理，我們推薦大家閱讀北京大學(xué)數(shù)學(xué)力學(xué)系編高等代數(shù)（人民教育出版社1978年第一版）pp78-79，基本方法是數(shù)學(xué)歸納法。3.唯一性定理. 恒等多項(xiàng)式定理2：如果兩個(gè)次數(shù)都不超過(guò)n的多項(xiàng)式P(x)和Q(x)在n+1個(gè)互不相同的點(diǎn)處的值相同，則這兩個(gè)多項(xiàng)式恒等。這也是代數(shù)學(xué)中很著名的定理，在北京大

8、學(xué)數(shù)學(xué)力學(xué)系編高等代數(shù)（人民教育出版社1978年第一版）pp25-26中可找到定理的證明，基本思路是不恒為零的n次多項(xiàng)式不可能有多于n個(gè)的零點(diǎn)，而P(x)-Q(x)卻有，所以它要么是高于n次的多項(xiàng)式，要么恒等于零。 4.多項(xiàng)式插值的基本結(jié)論由于線(xiàn)性方程組(2)的系數(shù)矩陣的行列式就是范德蒙行列式，再加上我們對(duì)插值基點(diǎn)互異的假設(shè)，上面的定理1表明，對(duì)于給定的插值條件，存在唯一的插值多項(xiàng)式，它的系數(shù)就是線(xiàn)性方程組(2) 的唯一解。定理2進(jìn)一步表明，不管什么形式的多項(xiàng)式，只要次數(shù)不超過(guò)n,而且滿(mǎn)足相同的插值條件，那么它們就是恒等的。從方法論的層面講上講，我們已經(jīng)解決了多項(xiàng)式插值問(wèn)題。但是求解線(xiàn)性方程組

9、(2)的計(jì)算量為O(n3)，存貯量為O(n2)，因此效率不高，而且算法也復(fù)雜，所以我們還要尋找更有效的方法。4重要提示： 上面的兩個(gè)定理已經(jīng)表明，對(duì)于多項(xiàng)式插值問(wèn)題來(lái)說(shuō)，插值多項(xiàng)式由插值條件唯一決定，所以我們?cè)诳谡Z(yǔ)中所講的n+1個(gè)基點(diǎn)的插值問(wèn)題求解指的就是求出由一組插值條件所唯一決定的多項(xiàng)式。我們?cè)试S這個(gè)唯一的插值多項(xiàng)式有不同的數(shù)學(xué)形式，以適應(yīng)不同的問(wèn)題求解。在后面的兩節(jié)中，我們將對(duì)相同的插值條件給出兩種不同的插值多項(xiàng)式，即Lagrange和Newton插值多項(xiàng)式。所以他們應(yīng)該是恒等的，名稱(chēng)不同只是各自的形式有所不同。不管那種插值方法，基本思路都是把插值多項(xiàng)式表示為具有固定形式的基函數(shù)的線(xiàn)性組

10、合，目的是為了簡(jiǎn)化計(jì)算。5.與曲線(xiàn)擬合的差異從形式上看，n+1個(gè)基點(diǎn)的插值問(wèn)題與曲線(xiàn)擬合問(wèn)題基本相同：都是由n+1個(gè)條件決定出一個(gè)多項(xiàng)式，也考慮尋找基函數(shù)的線(xiàn)性組合，但它們的原理，方法，以及應(yīng)用領(lǐng)域都不相同，基本上是兩個(gè)類(lèi)別的問(wèn)題。曲線(xiàn)擬合主要應(yīng)用于誤差分析以及多元回歸，數(shù)學(xué)原理是投影理論，方法是最小二乘法；而插值則應(yīng)用于精確計(jì)算，應(yīng)該說(shuō)只是一種經(jīng)驗(yàn)的方法，理論基礎(chǔ)非常脆弱，可以通過(guò)驗(yàn)算來(lái)證實(shí)結(jié)果的有效性。盡管插值問(wèn)題與曲線(xiàn)擬合問(wèn)題都可以看成是逼近理論的應(yīng)用，因此很多學(xué)者喜歡把他們捆在一起，其實(shí)不值得。10.3 拉格朗日插值方法拉格朗日插值多項(xiàng)式選用的基函數(shù)具有對(duì)稱(chēng)性，所以我們可以從中體驗(yàn)到數(shù)

11、學(xué)的美，事實(shí)上它也是牛頓插值法中證明差商具有對(duì)稱(chēng)性的基礎(chǔ)。正是因?yàn)槔窭嗜詹逯刀囗?xiàng)式所具有的美學(xué)價(jià)值，所以它對(duì)后面的學(xué)習(xí)有很大的影響。拉格朗日插值公式看上去形式較復(fù)雜，但實(shí)際上算法非常簡(jiǎn)單。1.拉格朗日插值公式的構(gòu)造對(duì)于一般的的n+1個(gè)基點(diǎn)的插值問(wèn)題，相應(yīng)的拉格朗日插值公式，我們記為L(zhǎng)n(x)，實(shí)際就是把插值多項(xiàng)式Pn(x)表為基函數(shù)lk(x)|k=0,1,n的線(xiàn)性組合，其中 而且組合系數(shù)實(shí)際就是諸y0,y1,yn，因此我們有 接下來(lái)我們要證明Ln(x)的確是插值多項(xiàng)式，也就是滿(mǎn)足插值條件。2.證明Ln(x)的確是插值多項(xiàng)式 注意到所有的lk(x)都是n次數(shù)多項(xiàng)式，所以L(fǎng)n(x)是次數(shù)不超過(guò)n

12、的多項(xiàng)式。再注意到所以L(fǎng)n(x)滿(mǎn)足插值條件，即Ln(x)的確是插值多項(xiàng)式。3.基函數(shù)的性質(zhì)定理：對(duì)于由前面的表2給出的插值問(wèn)題以及由（1）定義的基函數(shù)lk(x),k=0,1,n，我們有 證明：考慮被插函數(shù)為f(x) 1的特殊的多項(xiàng)式插值問(wèn)題，對(duì)于給定的插值基點(diǎn)x0,x1,xn，對(duì)應(yīng)的函數(shù)值y0,y1,yn均為1，從而相應(yīng)的拉格朗日插值多項(xiàng)式為3.基函數(shù)的性質(zhì)（證明）它滿(mǎn)足插值條件 而f(x)1也是次數(shù)不超過(guò)n的多項(xiàng)式，也滿(mǎn)足插值條件 f(xj)=yj=1，j=0,1,n 由插值多項(xiàng)式的唯一性立即推出我們的結(jié)論。4.計(jì)算基函數(shù)值的方法拉格朗日多項(xiàng)式插值的計(jì)算主要是計(jì)算基函數(shù)的值，作為練習(xí)編程，

13、編寫(xiě)求單個(gè)的基函數(shù)值的程序還是很有意義的。下面是求基函數(shù)的程序段： double GetG(int k，double u) int n = 0; double y=1.0; for(n=0;nTN;n+) if(n=k) continue; y *= u-Xn; y /= Xk-Xn; return y; 4.計(jì)算表格與算法說(shuō)明應(yīng)該說(shuō)，對(duì)于給定的x,求拉格朗日插值多項(xiàng)式的值還是很簡(jiǎn)單的，直接按公式計(jì)算就成，所以沒(méi)有太大的價(jià)值來(lái)研究算法問(wèn)題。如果用計(jì)算器來(lái)計(jì)算，可以按如下的表格計(jì)算，其中諸Gk為基函數(shù)值。kXkYkGkLk0X0Y0G0L01X1Y1G1L1NXnYnGnLn6.補(bǔ)充說(shuō)明與舉例計(jì)

14、算對(duì)于上面給出的表格，可以按下面的格式計(jì)算：先依次計(jì)算基函數(shù) G0,G1,GTN,接下來(lái)計(jì)算 Lk=Yk*Gk, k=0,1,2,TN.再接下來(lái)對(duì) Lk列元素求和即可.基函數(shù)值計(jì)算完畢后，可作一次檢驗(yàn)，看加起來(lái)是否為1，如果是，則計(jì)算正確；如果不是，則前面的計(jì)算肯定有誤，應(yīng)當(dāng)重新計(jì)算。拉格朗日插值雖然算法很簡(jiǎn)單，但是當(dāng)n較大時(shí)，用計(jì)算器來(lái)算還是有點(diǎn)累贅，大家一定不要再去尋找捷徑，唯一的笨辦法就是老老實(shí)實(shí)地一個(gè)一個(gè)地算，把結(jié)果填在表中。7.完整的子程序double Lagrange(double x,double*X,double*Y,int TN) int k,n; double y=1.0,

15、z=0.0; for(k=0;kTN;k+) y=1.0; for(n=0;nTN;n+) if(n=k)continue; y*=(x-Xn)/(Xk-Xn); z+=y*Yk; return z; 8.基函數(shù)的等價(jià)形式 9插值函數(shù)的等價(jià)形式利用lk(x)的等價(jià)形式，我們可以進(jìn)一步得到Ln(x)的等價(jià)形式：重要結(jié)論：拉格朗日插值多項(xiàng)式的首項(xiàng)的系數(shù)為10.4 差商與牛頓插值公式問(wèn)題的提出：假如我們對(duì)具有n+1個(gè)基點(diǎn)的問(wèn)題得到相應(yīng)的拉格朗日插值函數(shù)值Ln(x),如果它不滿(mǎn)足精度要求，我們當(dāng)然希望增加一個(gè)基點(diǎn)（xn+1,f(xn+1)來(lái)計(jì)算相應(yīng)的n+2個(gè)基點(diǎn)的問(wèn)題的解Ln+1(x)。拉格朗日插值法

16、具有公式優(yōu)美，算法簡(jiǎn)單的特征，但是該方法不具有承襲性。也就是說(shuō)，我們計(jì)算Ln+1(x)不太好利用前面得到的結(jié)果Ln(x)，而是一切都要重新計(jì)算。牛頓插值公式，我們通常記為Nn(x)是一個(gè)具有承襲性的方法，也就是說(shuō)，我們可直接以利用xn+1,f(xn+1) 以及Nn(x)來(lái)計(jì)算Nn+1(x)。1.牛頓插值公式的基函數(shù)對(duì)于一般形式的n+1個(gè)基點(diǎn)的差值問(wèn)題，牛頓插值公式采用的基函數(shù)集合為k(x)|k=0,1,n,其中： 0(x)1k(x)= (x-x0)(x-x1)(x-xk-1),k=1,2,n (1)不難看出，對(duì)任意k=1,2,n, k(x)僅與前面的k-1個(gè)插值基點(diǎn)x0,x1,xk-1有關(guān)，且

17、 k(xj)=0,j=0,1,k-1k(xk) 0k(x) = (x-xk-1)k-1(x)2牛頓插值公式的一般形式牛頓插值公式就是利用上面給出的一組基函數(shù)的線(xiàn)性組合并利用插值條件確定組合系數(shù)所得到的插值多項(xiàng)式，其數(shù)學(xué)形式為 Nn(x)=c00(x)+ c11(x)+ cnn(x) 或 Nn(x)=c0+ c11(x)+ cnn(x) （2） 其中c0,c1,cn為待定常數(shù)。對(duì)任意0kn,利用基函數(shù)的性質(zhì), 我們不難得到 k(xj)=0,j=0,1,k-1 從而對(duì)任意j=0,1,n,我們有： Nn(xj)= c0+ c11(xj)+ cjj(xj) （3）3.組合系數(shù)的確定為了使（2）式真正成

18、為插值多項(xiàng)式,還需要根據(jù)插值條件確定組合系數(shù)c0,c1,cn.利用插值條件以及上面的（3）式，我們不難得到牛頓插值多項(xiàng)式的系數(shù)c0,c1,cn就是下面的線(xiàn)性方程組的解： (4)這是一個(gè)下三角形的線(xiàn)性方程組,直接求它的數(shù)值解也很容易,至少比本章第2節(jié)中的線(xiàn)性方程組（2）容易得多。4.差商的定義為了深入研究線(xiàn)性方程組(4)的解的特性，并得到更緊湊的計(jì)算格式，我們需要引進(jìn)一個(gè)新的數(shù)學(xué)概念：差商。設(shè)f(x)是定義在某區(qū)間內(nèi)取連續(xù)變量值或離散變量值的實(shí)值函數(shù),且已知f(x)在n+1個(gè)互異的離散點(diǎn)x0,x1,xn 處的函數(shù)值f(x0),f(x1),f(xn),稱(chēng) fxk=f(xk), k=0,1,n 為f

19、(x)在xk處的零階差商;稱(chēng) fxi,xj=( fxj- fxi)/( xj- xi) , ij,0i,jn 為f(x)在xi,xj處的一階差商;5.高階差商的遞歸定義 （1）假如我們定義了f(x)在x0,x1,xk和x1,x2,xk+1處的k階差商fx0,x1,xk和fx1,x2,xk+1，定義f(x)在x0,x1,xk,xk+1處的k+1差商fx0,x1,xk+1為 這里,k可取值 1,2,n-1.注釋?zhuān)哼@是目前普遍采用的定義，它有利于用手工計(jì)算差商，但不利于許多重要結(jié)論的推導(dǎo)，也不利于利用機(jī)器計(jì)算。6. 差商的遞歸定義 （2）為了完善有關(guān)結(jié)論的證明，我們給出差商的一個(gè)等價(jià)定義如下：零階和

20、一階差商的定義不變；假如我們定義了f(x)在x0,x1,xk-1,xk和x0,x1,xk-1,xk+1處的k階差商fx0,x1,xk-1,xk和fx0,x1,xk-1,xk+1，定義f(x)在x0,x1,xk,xk+1處的k+1差商fx0,x2,xk+1為 (5) 這里,k可取值 1,2,n-1.提示：凡是需要進(jìn)行理論分析的時(shí)候，我們都采用這里的定義更為方便。7.差商的計(jì)算格式（1）根據(jù)差商的定義1，如果手工在草稿紙上計(jì)算f(x)的各階差商，一般教科書(shū)中推薦按下面的格式計(jì)算：注意：我們將要用到的是主對(duì)角線(xiàn)上的元素，因此如果利用機(jī)器計(jì)算，存貯效率不高。 7.差商的計(jì)算格式（2）根據(jù)差商的定義2，

21、如果手工在草稿紙上計(jì)算f(x)的各階差商，我們推薦按下面的格式計(jì)算：注意：計(jì)算方法是從第2行開(kāi)始，逐行從上向下計(jì)算；每一行從主對(duì)角線(xiàn)上的元素開(kāi)始，從左向右計(jì)算；每個(gè)元素都是利用上一行主對(duì)角線(xiàn)上的元素與“頂頭上司”元素計(jì)算。這種方法特別適用于編程計(jì)算，無(wú)需保留中間結(jié)果。7.差商的計(jì)算算法（3）如果編程計(jì)算差商，采用下面的程序段比較好：假如在程序外定義數(shù)組XN,YN,FN,其中YK=f(Xk),K=0,1,N-1;FN用來(lái)存放fx0,fx0,x1,fx0,x1,xN-1，則相應(yīng)的c語(yǔ)言程序段為： void GetDQTF() int i,j; for(i=0;iN;i+) Fi=Yi; for(j

22、=0;ji;j+) Fi=(Fi-Fj)/(XI-Xj) return;8重要結(jié)論定理1: 設(shè)f(x)是定義在某區(qū)間內(nèi)取連續(xù)變量值或離散變量值的實(shí)值函數(shù),對(duì)該區(qū)間內(nèi)任意k+1個(gè)互異的離散點(diǎn)x0,x1,xk以及任意異于所有x0,x1,xk的x，我們有 (6)作為課外練習(xí)，我們鼓勵(lì)大家勇敢地用數(shù)學(xué)歸納法完成這個(gè)定理的證明。如果一時(shí)完成不了，就記住這個(gè)結(jié)論。提示：不要看其他參考書(shū)，幾乎所有的參考書(shū)關(guān)于這個(gè)定理的表述或者是含糊其辭，或者有錯(cuò)誤沒(méi)有實(shí)際意義。9.確定組合系數(shù)現(xiàn)在，我們只要把差商的定義以及上面的定理1與表1所確定的n+1個(gè)基點(diǎn)的插值問(wèn)題聯(lián)系起來(lái)，即可導(dǎo)出具有承襲性的牛頓插值多項(xiàng)式。定理2：

23、對(duì)于表1所確定的n+1個(gè)基點(diǎn)的多項(xiàng)式插值問(wèn)題，對(duì)任意k=0,1,n-1，我們有 (7)證明：在（6）式中令x=xk+1立即得證。定理3：對(duì)于表1所確定的n+1個(gè)基點(diǎn)的多項(xiàng)式插值問(wèn)題，我們有 ck=fx0,x1,xk, k=0,1,n 為線(xiàn)性方程組（4）的解。提示：這個(gè)定理實(shí)際上是上面的定理2的推論.10. 重要提示：為了完成上面定理的證明，我們可以這么干： 首先一行寫(xiě)：fx0=fx0 接下來(lái)再按k=0,1,n-1的順序把上面的（7）式重寫(xiě)一遍，每遍占一行，再與(4)式對(duì)比，利用解的唯一性以及fxk=f(xk),k=0,1,n即可完成證明。 這個(gè)思路類(lèi)似于中學(xué)里用同一法做幾何證明題。話(huà)已說(shuō)到這個(gè)

24、份上，如果還做不出來(lái)，那就根據(jù)差商的定義直接用數(shù)學(xué)歸納法證明，難度也不是很大。11.牛頓插值公式在（7）式中，取xk+1為任意異于x0,x1,xk的x,我們有 f(x)=fx0+fx0,xkk(x)+ fx0,xk,xk+1(x) 記 Nk(x)=fx0+fx0,xkk(x) Rk(x)= fx0,xk,xk+1(x) 則有 f(x)=Nk(x)+Rk(x) 特別地在取k=n，我們有它們分別稱(chēng)為牛頓插值多項(xiàng)式、插值余項(xiàng)和牛頓插值公式。12.計(jì)算表格與計(jì)算方法說(shuō)明對(duì)于給定的n+1個(gè)基點(diǎn)的插值問(wèn)題以及自變量的任意取值x,我們建議按如下的表格計(jì)算牛頓插值多項(xiàng)式的系數(shù)以及多項(xiàng)式的值。表中Xk列和yk列

25、為函數(shù)值列表，F(xiàn)k存放fx0,x1,xk,Pk存放(x-x0)(x-x1) (x-xk),Nk存放Fk*Pk,最后對(duì)Nk列求和即可。kXkYkFkPkNk0X0Y0F0P0N01X1Y1F1P1N1NXNYNFNPNNN10.5插值余項(xiàng)與差商的性質(zhì)討論插值余項(xiàng)簡(jiǎn)單說(shuō)來(lái)就是插值函數(shù)與被插函數(shù)之間的差，實(shí)際也就是誤差。對(duì)于一般的n+1個(gè)基點(diǎn)的多項(xiàng)式插值問(wèn)題，我們?cè)谇懊娴娜?jié)中分別給出了三種不同的方法：一般方法、拉格朗日插值法和牛頓插值法。由唯一性定理可知，不同的方法得到的不同形式的不超過(guò)n次的多項(xiàng)式由于在n+1個(gè)不同的點(diǎn)處的值相同，所以它們實(shí)際上是恒等的。所以本節(jié)關(guān)于插值余項(xiàng)討論對(duì)前面三節(jié)給出的插

26、值公式都適用。1.插值余項(xiàng)的定義定義：對(duì)于一般的n+1個(gè)基點(diǎn)的多項(xiàng)式插值問(wèn)題，設(shè)f(x)為被插值函數(shù),Pn(x)為相應(yīng)的插值多項(xiàng)式,記Rn(x)為f(x)與Pn(x)的差,即 f(x)= Pn(x)+ Rn(x) （1） 則Rn(x)就是用Pn(x)近似替代f(x)的誤差,我們稱(chēng)它為插值余項(xiàng).結(jié)論：由插值多項(xiàng)式的唯一性可以導(dǎo)出插值余項(xiàng)的唯一性。2. 插值余項(xiàng)的估計(jì)定理1：設(shè)f(x)是定義在a,b上的n+1階連續(xù)可導(dǎo)的被插值函數(shù),又假設(shè)n+1個(gè)插值基點(diǎn)滿(mǎn)足ax0 x1xnb，Pn(x)為相應(yīng)的插值多項(xiàng)式，Rn(x)為插值余項(xiàng)，則對(duì)任意x(a,b)，我們有: （2）提示：把x看作是(任意)固定的點(diǎn)

27、，作輔助函數(shù) (3) 則g(t)有n+2個(gè)零點(diǎn)，n+1次應(yīng)用羅爾定理，則存在使得g(n+1)()=0,注意到x是常數(shù)，Pn(t),n+1(t)是多項(xiàng)式，所以推出我們的結(jié)果并不難。3.差商與導(dǎo)數(shù)的關(guān)系在牛頓插值公式一節(jié)中，我們?cè)o出了多項(xiàng)式插值余項(xiàng)的數(shù)學(xué)形式。對(duì)(a , b)內(nèi)任意異于x0,x1,xn的x,我們有 Rn(x)=fx0,x1,xn,x n+1(x) （4） 把它與上面的（2）式對(duì)比即可看出 （5）4.多項(xiàng)式的差商利用牛頓插值公式以及余項(xiàng)的數(shù)學(xué)形式，我們還可以推出許多有意義的結(jié)果，比如：任何n次多項(xiàng)式的n+1階差商均為零。由n次多項(xiàng)式的n+1個(gè)互異的基點(diǎn)的牛頓插值公式的余項(xiàng)Rn(x)

28、=0,立即推得fx0,x1,xn,x=0.這個(gè)結(jié)論也可以由上面的（4）式立即推出。任何n次多項(xiàng)式的n階差商均為常數(shù)?？疾靚次多項(xiàng)式P(x)的任意的n+1個(gè)基點(diǎn)的牛頓插值多項(xiàng)式Nn(x)，顯然它們恒等，從而首項(xiàng)系數(shù)相同，所以Px0,x1,xn為常數(shù)。4.多項(xiàng)式的差商差商具有對(duì)稱(chēng)性，也就是說(shuō)，如果z0,z1,zn是x0,x1,xn的任意一個(gè)排列，那么fz0,z1,zn= fx0,x1,xn. 證明：僅改變插值基點(diǎn)的排列順序所得到的兩個(gè)牛頓插值多項(xiàng)式是恒等的，所以他們的最高次項(xiàng)的系數(shù)也相等。提示：插商的對(duì)稱(chēng)性視察上的重要性直之一，至少我們不難利用插商的對(duì)稱(chēng)性證明前面給出的關(guān)于插上的兩個(gè)定義是等價(jià)的。

29、10.6 靈活應(yīng)用插值方法舉例1 反(函數(shù))插值在高等數(shù)學(xué)中我們已注意到這樣一個(gè)事實(shí)：有時(shí)候求直接函數(shù)值比較容易，但是求反函數(shù)值卻比較麻煩。我們可以巧妙地利用插值方法來(lái)解決這個(gè)問(wèn)題。對(duì)于多項(xiàng)式插值來(lái)說(shuō)，求反函數(shù)插值與求直接函數(shù)插值是完全一樣的容易：我們只要簡(jiǎn)單地把直接函數(shù)的函數(shù)值列表的兩行互換一下，即可得到相應(yīng)的反函數(shù)的函數(shù)值列表，再利用反函數(shù)的函數(shù)值列表我們即可簡(jiǎn)單地計(jì)算反函數(shù)值，我們稱(chēng)之為反插值。我們無(wú)需編寫(xiě)反插值程序，在調(diào)用Lagrange插值的c語(yǔ)言函數(shù)時(shí)簡(jiǎn)單地互換數(shù)組X和Y的位置即可得到反差知結(jié)果。2 利用 反插值解非線(xiàn)性方程作為數(shù)值計(jì)算問(wèn)題來(lái)說(shuō)，求反函數(shù)值與解非線(xiàn)性方程實(shí)際上有異曲

30、同工之妙：y=f(x)的反函數(shù)當(dāng)y=y0時(shí)的函數(shù)值x0實(shí)際上也是非線(xiàn)性方程f(x)=y0的解。注意到反函數(shù)當(dāng)自變量取零時(shí)的函數(shù)值就是直接函數(shù)的零點(diǎn)，所以我們可以利用反插值求函數(shù)的零點(diǎn)。我們無(wú)需編寫(xiě)利用 反插值方法解非線(xiàn)性方程的程序，既然可以直接利用Lagreange插值的程序進(jìn)行反函數(shù)插值，所以直接取(反）插值點(diǎn)為0即可。一般很少有專(zhuān)門(mén)利用反插值方法解非線(xiàn)性方程的，主要原因是數(shù)字性能得不到保證。但是與一些具體方法結(jié)合起來(lái)實(shí)用，效果都是不錯(cuò)的。3.反插值與二分法集成求解非線(xiàn)性方程現(xiàn)代數(shù)值計(jì)算的一個(gè)基本方法是首先找出問(wèn)題的一個(gè)精確度不太高的近似解，然后利用一個(gè)迭代過(guò)程得到一個(gè)比一個(gè)更精確的解。在這

31、個(gè)過(guò)程中，利用已經(jīng)得到的結(jié)果靈活應(yīng)用插值方法計(jì)算，插值的計(jì)算量可忽略不計(jì)，通?？梢缘玫礁玫慕Y(jié)果。假如用二分法求f(x)在a,b上的解，可以利用a,b,以及中點(diǎn)x0這三個(gè)點(diǎn)處的函數(shù)值做一次反插值，也可以得到一個(gè)近似解。當(dāng)區(qū)間長(zhǎng)度不太大時(shí)，用這種方法得到的解通常更精確一些。在二分法中，隨著計(jì)算區(qū)間長(zhǎng)度趨近于零，用反插值方法得到的近似解序列通常會(huì)更快地收斂于零。反插值與二分法集成的好處是，如果區(qū)間長(zhǎng)度較大，二分法得到的結(jié)果更好一些；當(dāng)區(qū)間長(zhǎng)度較小時(shí)，3個(gè)基點(diǎn)的反插值方法的性能可叫板牛頓法。實(shí)際上也容易利用4個(gè)(足矣）基點(diǎn)反插，效果還要好一些。4.拋物線(xiàn)插值與黃金分割法集成假設(shè)用黃金分割法求函數(shù)的極

32、值點(diǎn)，我們實(shí)際上可以知道4個(gè)點(diǎn)x0,x1,x2,x3處的函數(shù)值。其中x0和x1委區(qū)間的端點(diǎn)，x1,x2每為區(qū)間上的兩個(gè)黃金分割點(diǎn)。一次迭代即可去掉一個(gè)點(diǎn)，利用保留下來(lái)的三個(gè)點(diǎn)做拋物線(xiàn)，從而可以直接寫(xiě)出這個(gè)拋物線(xiàn)的極值點(diǎn)。在黃金分割法中隨著迭代的繼續(xù)，我們也可以得到插值結(jié)果的序列，他們通常會(huì)更快地收斂于問(wèn)題的解?？梢跃帉?xiě)一個(gè)c語(yǔ)言函數(shù)(見(jiàn)教材第292頁(yè)程序10.09)，直接算出經(jīng)過(guò)(x0,y0)、 (x1,y1)和 (x2,y2)的拋物線(xiàn)的極值點(diǎn)，這樣可以簡(jiǎn)化程序的編寫(xiě)。10.7分段Hermit插值利用插值的方法進(jìn)行有關(guān)計(jì)算，基本要求就是誤差應(yīng)盡可能小，通常的想法是，我們可以通過(guò)增加插值基點(diǎn)從而

33、提高插值多項(xiàng)式的次數(shù)來(lái)提高插值的精度，但這并不是最有效的方法。當(dāng)插值多項(xiàng)式的次數(shù)較高時(shí)，可能會(huì)產(chǎn)生意想不到的龍格現(xiàn)象，此時(shí)，次數(shù)的增高反而產(chǎn)生不利影響。理論分析和數(shù)值試驗(yàn)表明，采用低次的多項(xiàng)式插值，并輔之以縮短插值區(qū)間長(zhǎng)，通常能得到更好的效果，分段三次Hermit插值就是這種思想的最好體現(xiàn)。1.多項(xiàng)式插值的龍格現(xiàn)象設(shè)被插函數(shù)為f(x)=1/(1+x2)，插值區(qū)間為-5,5,把插值區(qū)間n等分，插值基點(diǎn)為區(qū)間的等分點(diǎn)。我們會(huì)發(fā)現(xiàn)，隨著n的增大，插值多項(xiàng)式在區(qū)間端點(diǎn)附近發(fā)生激烈的震蕩，這就是龍格現(xiàn)象克服的辦法：減小插值區(qū)間，降低多項(xiàng)式的次數(shù)，要求插值函數(shù)與被插函數(shù)在基點(diǎn)處的導(dǎo)數(shù)值相同。圖7.1 多項(xiàng)

34、式插值的龍格現(xiàn)象示意圖2.Hermit插值（問(wèn)題）問(wèn)題：已知f(x)在x0,x1,xn處的函數(shù)值y0,y1,yn和導(dǎo)數(shù)值z(mì)0,z1,zn,我們可以構(gòu)造一個(gè)2n+1次多項(xiàng)式H(x),滿(mǎn)足這2n+2個(gè)條件，即 這就是Hermit插值問(wèn)題。提示：分段插值重點(diǎn)應(yīng)解決的問(wèn)題是插值函數(shù)在段與段的分界點(diǎn)處的光滑性問(wèn)題，所以Hermit插值是分段插值的基礎(chǔ)。類(lèi)似地我們還可以要求插值函數(shù)滿(mǎn)足在節(jié)點(diǎn)處高階導(dǎo)數(shù)值的要求。2.Hermit插值（方法）仿照拉格朗日插值公式的構(gòu)造方法，我們也可以把H(x)表為基函數(shù)k(x),k=0,1,n和k(x), k=0,1,n的線(xiàn)性組合，且組合系數(shù)相應(yīng)地分別為y0,y1,yn和z0,z1,zn，則有：顯然，H(x)是2n+1次多項(xiàng)式，它由2n+2個(gè)常數(shù)確定，而則2n+2個(gè)常數(shù)正好由2n+2個(gè)插值條件確定。2.Hermit插值（插值條件）不難看出，對(duì)任意給定的j=0,1,n,可以證明，對(duì)任意給定的j=0,1,n及k=0,1,n所以H(x)的確滿(mǎn)值插值條件。3三次Hermit插值問(wèn)題：已知f(x)在x0,x1處的函數(shù)值y0,y1和導(dǎo)數(shù)值z(mì)0,z1,求三次多項(xiàng)式H(x),滿(mǎn)足相應(yīng)的插值條件。顯然，這是最簡(jiǎn)單的Hermi