牛頓插值法原理及應(yīng)用

1、文檔牛頓插值法插值法是利用函數(shù)f (x)在某區(qū)間中若干點(diǎn)的函數(shù)值，作出適當(dāng)?shù)奶囟ê瘮?shù)，在這些點(diǎn)上取已知值，在區(qū)間的其他點(diǎn)上用這特定函數(shù)的值作為函數(shù)f (x)的近似值。如果這特定函數(shù)是 多項(xiàng)式，就稱它為插值多項(xiàng)式。當(dāng)插值節(jié)點(diǎn)增減時全部 插值基函數(shù)均要隨之變化，這在實(shí)際計算中很不方便。為了克服這一缺點(diǎn)，提出 了牛頓插值。牛頓插值通過求各階差商，遞推得到的一個公式：f(x)=fx0+fx0,x1(x-x0)+fx0,x1,x2(x-x0)(x-x1)+.fx0,.x n(x-x0 ).(x-x n-1)+R n(x)。插值函數(shù)插值函數(shù)的概念及相關(guān)性質(zhì)乩 定義：設(shè)連續(xù)函數(shù)y-f(x) 在區(qū)間a,b上有

2、定義，已知在n+1個互異的點(diǎn)x0,x1,xn上取值分別為y0,y1,yn (設(shè)a x1 x2 -*wi - w- . P|gJ!W- g ：r程序框圖 #includevoid mai n()float x11,y1111,xx,temp, newto n;int i,j, n;printf(Newton插值:n請輸入要運(yùn)算的值:x=);sca nf(%f, &xx);printf(請輸入插值的次數(shù)(n11):n=);sca nf(%d,&n);printf(請輸入 d組值:n,n+1);for(i=0;i n+1;i+) prin tf(x%d=,i);sca nf(%f, &xi);pri

3、n tf(y%d=,i);sca nf(%f, &y0i);XO=OMHUOW 匚 LHdlu9a巨 A-=uv&=)主dWL-=x-mx)、(D-=D.M-nKL.MHm=M S05 -mxgD-mL-M-mDMHnKM(LAW 7(+r L+uvrHD04(+土=+uvud04a-=x sa)OOH (匚 Lo_(x)llo)u -H u(A)6U2 hh (x)6u一)七】siuAs(oxsx)uoweN H 4 uoloua ftqewlAIw迴B犀 eow u-xx-=uJ6&Ha 寸& )M 滅撫旨e=)匕 d宀CLlu &=二 A+uo g u H u o g u二 L.vxxh

4、dlu 晉 dlu2 (+土=+uvU_)O4disp('x 和 y 的維數(shù)不相等！ ');return;endf = y(1);y1 = 0;l = 1;for(i=1:n-1)for(j=i+1:n)y1(j) = (y(j)-y(i)/(x(j)-x(i);endc(i) = y1(i+1);l = l*(t-x(i);f = f + c(i)*l;simplify(f);y = y1;if(i=n-1)if(nargin = 3)f = subs(f,'t',x0);elsef = collect(f);%將插值多項(xiàng)式展開f = vpa(f, 6

5、);endend牛頓插值法摘 要：值法利用函數(shù) f (x) 在某區(qū)間中若干點(diǎn)的函數(shù)值，作出 適當(dāng)?shù)奶囟ê瘮?shù)， 在這些點(diǎn)上取已知值， 在區(qū)間的其他點(diǎn)上用這特定 函數(shù)的值作為函數(shù) f (x) 的近似值。如果這特定函數(shù)是多項(xiàng)式，就稱 它為插值多項(xiàng)式。利用插值基函數(shù)很容易得到拉格朗日插值多項(xiàng)式， 公式結(jié)構(gòu)緊湊， 在理論分析中甚為方便， 但當(dāng)插值節(jié)點(diǎn)增減時全部插 值基函數(shù)均要隨之變化，整個公式也將發(fā)生變化， 這在實(shí)際計算中 是很不方便的，為了克服這一缺點(diǎn)，提出了牛頓插值。 牛頓插值通過求各階差商，遞推得到的一個公式： f(x)=fx0+fx0,x1(x-x0)+fx0,x1,x2(x-x0)(x-x1)

6、+.fx0,.xn(x-x0).(x-xn-1)+Rn(x)關(guān)鍵詞 ：牛頓插值法 流程圖 程序?qū)崿F(xiàn)一、插值法的由來在許多實(shí)際問題及科學(xué)研究中， 因素之間往往存在著函數(shù)關(guān)系， 然而，這種關(guān)系經(jīng)常很難有明顯的解析表達(dá)， 通常只是由觀察與測試 得到一些離散數(shù)值。有時， 即使給出了解析表達(dá)式，卻由于表達(dá)式過 于復(fù)雜，不僅使用不便，而且不易于進(jìn)行計算與理論分析。解決這類 問題的方法有兩種：一種是插值法 , 另一種是擬合法。插值法是一種 古老的數(shù)學(xué)方法，它來自生產(chǎn)實(shí)踐，早在一千多年前，我國科學(xué)家在 研究歷法上就應(yīng)用了線性插值與二次插值， 但它的基本理論卻是在微 積分產(chǎn)生之后才逐漸完善的， 其應(yīng)用也日益增多

7、， 特別是在計算機(jī)軟 件中，許多庫函數(shù)，如等的計算實(shí)際上歸結(jié)于它的逼近函數(shù)的計算。 逼近函數(shù)一般為只含有算術(shù)運(yùn)算的簡單函數(shù)， 如多項(xiàng)式、有理分式(即 多項(xiàng)式的商)。在工程實(shí)際問題當(dāng)中，我們也經(jīng)常會碰到諸如此類的 函數(shù)值計算問題。 被計算的函數(shù)有時不容易直接計算， 如表達(dá)式過于 復(fù)雜或者只能通過某種手段獲取該函數(shù)在某些點(diǎn)處的函數(shù)值信息或 者導(dǎo)數(shù)值信息等。因此，我們希望能用一個“簡單函數(shù)”逼近被計算 函數(shù)，然后用該簡單函數(shù)的函數(shù)值近似替代被計算函數(shù)的函數(shù)值。 這 種方法就叫插值逼近或者插值法。逐次線性插值法優(yōu)點(diǎn)是能夠最有效地計算任何給定點(diǎn)的函數(shù)值， 而不需要寫出各步用到的插值多項(xiàng)式的表達(dá)式。 但如

8、果解決某個問題 時需要插值多項(xiàng)式的表達(dá)式， 那么，它的這個優(yōu)點(diǎn)就成了它的缺點(diǎn)了。 能不能根據(jù)插值條件構(gòu)造一個插值多項(xiàng)式， 它既有具體的表達(dá)式， 又 很容易用它計算任何點(diǎn)的函數(shù)值呢？牛頓插值法能作到這一點(diǎn)。二、牛頓插值法的概念牛頓插值多項(xiàng)式的表達(dá)式設(shè)Nn c0c1(xx0)c2(xx0)(xx1)cn(xx0)(xx1)(xxn 1)問題是如何根據(jù)插值條件N n xi yi ,i=0,1,2 n來計算待定系數(shù) c0,c1,c2 cn ？由Nn（X。）y。f（X。） 知，C0 y0 f（x。）。由Nn（0 yi f（Xl）知co e（xi X。）yi因而yi yo f（Xi）f（Xo）f Cif

9、Xo, XiXi XoXi Xo其中 fxo*稱為函數(shù)f（X）在Xo,Xi點(diǎn)的一階商。由Nn（X2）丫2 f（X2）知Co Ci（Xi X。）C2（X2 Xo）（X2 Xi） y2因而y? y。3，劉心2 X。）c（X2 xo）（X2 X1）y? % % y。，為映 X。）a xo）（x2 X1）2 % fXo，Xi（Xi X。）fXo，Xi（X2 X。）（X2 Xo）（X2 X1）y y %，為X2 Xi（X2 X。）fXi，X2 fXo，Xi f（）5。，為用（X2 X。）其中fix。*稱為函數(shù)f （X）在X，XiX點(diǎn)的二階差商。實(shí)際上，它是一階差商的差商。一般地，如果已知一階差商fXii

10、,Xi,fXi,Xi 1,那么就可以計算二階差商fXi i，Xi，Xi 1fXXi 1fXi 1，XX 1 Xi 1類似于上述過程不斷地推導(dǎo)下去，可得C3C4fXi，X2，X3fXo，Xi，X2（X3 X。）fXo，Xi，X2，X3，fXi，X2，X3，X4fXo，Xi，X2，X3（X4 X。）fXo，Xi，X2，X3，X4，C4fXo，Xi，X2fXi，X2Xn fXo，Xi，X2Xn 1（Xn X。）其中,f【X。，Xi, X2, X3，f【X。，X，X2，X3，X4，f 氐。，為，X2，X3, X4, X5，分別稱為函數(shù)f （x）在相應(yīng)點(diǎn)處的三階差商，四階差商和 n階差商。實(shí)際上,Co，

11、Cl，C2 Cn的計算可通過以下簡易地構(gòu)造函數(shù)的差商來完成。Xof(Xo)CoX1f(X1)fXo，X1 C1X2f(X2)fX1，X2fXo，X1，X2 C2X3f(X3)fX2，X3fX1，X2，X3fX0，X1，X2，X3 C3X4J)fX3，X4fX2，X3，X4fX1,X2，X3，X4fX0，X1，X2，X3，X4 C4.按上述方式構(gòu)造插值多項(xiàng)式的方法叫做牛頓插值法。 根據(jù)插值多項(xiàng)式的惟一性知，其截斷誤差與拉格朗日插值法相同，即：1(n 1)Rn (n 1)! f ()nn i(x)但也可以表示成差商形式。這是因?yàn)橐訧X0XX2刈為節(jié)點(diǎn)的多項(xiàng)式Nn 1(X) Nn(X)fXo，Xl

12、Xn 1 n 1(X )從而f (Xn1)Nn1(XnJ N n(Xn1)f X。，為 Xn1n 1(Xn1)于是Nn(X)的截斷誤差可表為Rn (X)fXo，Xl，Xn 1, X n 1(X)順便指出，因?yàn)榕ｎD插值多項(xiàng)式具有性質(zhì)：Nn(X) Nni(X)fX0，Xl Xn(X X)(X X2)(X X)所以，類似于逐次線性插值法，也可以把上述和式中的第二項(xiàng)fXo，Xl Xn(X X1)(X X2) (X Xn 1)看成是估計 Nn1(X)的一種實(shí)用誤差估計式。與差商概念密切聯(lián)系的另一個概念是差分，它是指在等距節(jié)點(diǎn)上函數(shù)值的差。所謂等距節(jié)點(diǎn)，是指對給定的常數(shù) h (稱為步長)，節(jié)點(diǎn) Xi X。

13、ih，(i 0,1,2 n)稱 f(Xi 丿 f(Xi) f k 為 X 處的一階向前差 分；稱f(X)f(Xi1) f i為X處的一階向后差分；稱f(Xi h2) f(Xi1。 fi為x處的中心差分。一階差分的差分稱為二階差分，即f i 1 f i f i稱為Xi處的二階向前差分。一般地，m階向前和向后差分可定義如下：m2,31T， 1 i ；,xi)/( xi則 p 為最終p,轉(zhuǎn)步驟4。三、牛頓插值法的實(shí)現(xiàn)1、【算法】步驟 1：輸入節(jié)點(diǎn)( xj ，yj )，精度 ，計值點(diǎn) xx，f0p，步驟2：對k=1, 2,i依次計算k階均差fxi-k,xi-k+1, ,xi = (fxi-k+1,xi

14、- fxi-k,-xi-k )步驟 3: (1)、若 | fx1,，刈-fx0,xi-1|,結(jié)果 Ni-1(x)，余項(xiàng) Ri-1= fx0,xi(xx-xi-1)T 。(2)、否則(xx-xi-1)*T T, p+ fx0,xi*T步驟 4：若 in ,則 i+1 i ,轉(zhuǎn)步驟 2；否則終止2、【流程圖】NOJLqk gkkq(xx-Xn-i)*T RSTOP 23 、【程序清單】 #includestdio.h#define n 4/ 牛頓插值的次數(shù)void main()float an+1n+2=0,s=0,t=1,x;int i,j;printf( 請輸入 xi 及 yi 的值 / 要求

15、先輸入 xi 再輸入 yi 然后輸入 下一組 n);for(i=0;in+1;i+)for(j=0;j2;j+)scanf(%f,&aij);for(j=1;jn+2;j+)/ 計算各階均差for(i=j;in+1;i+) aij+1=(aij-ai-1j)/(ai0-ai-j0);printf( 輸出 xi ， yi 及各階均差 n);for(i=0;in+1;i+)for(j=0;jn+2;j+)printf(%6.5f ,aij);printf(n);printf( 輸出牛頓插值表達(dá)式 n);printf(N%d(x)=,n);for(i=0;in+1;i+)printf(%6.5f,a

16、ii+1);for(j=0;ji;j+)printf(x-%3.2f),aj0);if(i=n)break;printf(+);printf(n);printf( 輸入插值點(diǎn) x=);scanf(%f,&x);for(i=0;in+1;i+)/ 計算插值點(diǎn)的近似值for(j=0;ji;j+)t*=(x-aj0);s+=aii+1*t;printf(N%d(%4.3f)=%6.5fn,n,x,s);4. 【程序?qū)崿F(xiàn)】刀用各帥均罟0.41fT7SS0-69675102&52fkfWf伽0.S60B00-00S00 U.1?732 3.21298pi. snappi&.Q00G0 B.28368 0

17、.358V3 取43347可jmjj ”訂邂愛篆話逬邈穗菲廳魏遊證喙:翌總靈移$；;腮凳煞翅逐鶴遨0：量器燒變袋婕荻鮭:熒謖煌録泌埶11.1I6B01.275731.3841B9. 00900 e.eaaeo 0.UM0UM 0.03132參考文獻(xiàn) :Richard L. Burden, J. Douglas Faires, Numerical Analysis(Seventh Edition), Brooks Pub. Co.,2001.2. 蔡大用，白峰杉 . 高等數(shù)值分析 . 清華大學(xué)， 1998.3. 鄧建中，之行 . 計算方法(第二版) . 交通大學(xué)， 2001.4. 韓旭里. 數(shù)值分析. 中南大學(xué)， 2003.致謝本文得以順利完成，非常感謝我的指導(dǎo)教師。從論文的選題直到論文的最終完成，他都給予我盡心盡力的指導(dǎo)。老師嚴(yán)謹(jǐn)?shù)闹螌W(xué)態(tài)度深深地影響著我， 對我今后