牛頓插值法原理及應用

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

2、+1個互異的點x0,x1,xn上取值分別為y0,y1,yn （設a x1x2xnb)。若在函數(shù)類中存在以簡單函數(shù)P(x) ，使得P(xi)=yi,則稱P(x) 為f(x)的插值函數(shù).稱x1,x2,xn 為插值節(jié)點，稱a,b為插值區(qū)間。定理：n次代數(shù)插值問題的解存在且唯一 。牛頓插值法C程序程序框圖#includevoid main() float x11,y1111,xx,temp,newton; int i,j,n; printf(Newton插值:n請輸入要運算的值:x=); scanf(%f,&xx); printf(請輸入插值的次數(shù)(n11):n=); scanf(%d,&n); pr

3、intf(請輸入%d組值:n,n+1); for(i=0;in+1;i+) printf(x%d=,i); scanf(%f,&xi); printf(y%d=,i); scanf(%f,&y0i); for(i=1;in+1;i+) for(j=i;j1) yij=(yi-1j-yi-1j-1)/(xj-xj-i); else yij=(yi-1j-yi-1j-1)/(xj-xj-1); printf(%fn,yii); temp=1;newton=y00; for(i=1;in+1;i+) temp=temp*(xx-xi-1); newton=newton+yii*temp; print

4、f(求得的結果為:N(%.4f)=%9fn,xx,newton);牛頓插值法Matlab程序function f = Newton(x,y,x0) syms t; if(length(x) = length(y) n = length(x); c(1:n) = 0.0; else disp('x和y的維數(shù)不相等！'); return; end f = 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); end c(i) = y1(i+1); l = l*(t-x(i);

5、f = f + c(i)*l; simplify(f); y = y1; if(i=n-1) if(nargin = 3) f = subs(f,'t',x0); else f = collect(f); %將插值多項式展開 f = vpa(f, 6); end end牛頓插值法摘 要：值法利用函數(shù)f (x)在某區(qū)間中若干點的函數(shù)值，作出適當?shù)奶囟ê瘮?shù)，在這些點上取已知值，在區(qū)間的其他點上用這特定函數(shù)的值作為函數(shù)f (x)的近似值。如果這特定函數(shù)是多項式，就稱它為插值多項式。利用插值基函數(shù)很容易得到拉格朗日插值多項式，公式結構緊湊，在理論分析中甚為方便，但當插值節(jié)點增減時全

6、部插值基函數(shù)均要隨之變化，整個公式也將發(fā)生變化， 這在實際計算中是很不方便的，為了克服這一缺點，提出了牛頓插值。 牛頓插值通過求各階差商，遞推得到的一個公式： f(x)=fx0+fx0,x1(x-x0)+fx0,x1,x2(x-x0)(x-x1)+.fx0,.xn(x-x0).(x-xn-1)+Rn(x)關鍵詞：牛頓插值法 流程圖 程序實現(xiàn)一、 插值法的由來 在許多實際問題及科學研究中，因素之間往往存在著函數(shù)關系，然而，這種關系經(jīng)常很難有明顯的解析表達，通常只是由觀察與測試得到一些離散數(shù)值。有時，即使給出了解析表達式，卻由于表達式過于復雜，不僅使用不便，而且不易于進行計算與理論分析。解決這類問

7、題的方法有兩種：一種是插值法,另一種是擬合法。插值法是一種古老的數(shù)學方法，它來自生產(chǎn)實踐，早在一千多年前，我國科學家在研究歷法上就應用了線性插值與二次插值，但它的基本理論卻是在微積分產(chǎn)生之后才逐漸完善的，其應用也日益增多，特別是在計算機軟件中，許多庫函數(shù)，如等的計算實際上歸結于它的逼近函數(shù)的計算。逼近函數(shù)一般為只含有算術運算的簡單函數(shù)，如多項式、有理分式（即多項式的商）。在工程實際問題當中，我們也經(jīng)常會碰到諸如此類的函數(shù)值計算問題。被計算的函數(shù)有時不容易直接計算，如表達式過于復雜或者只能通過某種手段獲取該函數(shù)在某些點處的函數(shù)值信息或者導數(shù)值信息等。因此，我們希望能用一個“簡單函數(shù)”逼近被計算函

8、數(shù)，然后用該簡單函數(shù)的函數(shù)值近似替代被計算函數(shù)的函數(shù)值。這種方法就叫插值逼近或者插值法。逐次線性插值法優(yōu)點是能夠最有效地計算任何給定點的函數(shù)值，而不需要寫出各步用到的插值多項式的表達式。但如果解決某個問題時需要插值多項式的表達式，那么，它的這個優(yōu)點就成了它的缺點了。能不能根據(jù)插值條件構造一個插值多項式，它既有具體的表達式，又很容易用它計算任何點的函數(shù)值呢？牛頓插值法能作到這一點。 2、 牛頓插值法的概念牛頓插值多項式的表達式設問題是如何根據(jù)插值條件 ,i=0,1,2n 來計算待定系數(shù)？由 知， 。由 知 因而 ，其中 稱為函數(shù)f(x)在點的一階商。由 知 因而 其中稱為函數(shù)f (x)在點的二階

9、差商。實際上，它是一階差商的差商。一般地，如果已知一階差商，那么就可以計算二階差商 類似于上述過程不斷地推導下去，可得 其中，分別稱為函數(shù)f (x)在相應點處的三階差商，四階差商和n 階差商。實際上， 的計算可通過以下簡易地構造函數(shù)的差商來完成。 .按上述方式構造插值多項式的方法叫做牛頓插值法。根據(jù)插值多項式的惟一性知，其截斷誤差與拉格朗日插值法相同，即： 但也可以表示成差商形式。這是因為以為節(jié)點的多項式 從而 于是 的截斷誤差可表為 順便指出，因為牛頓插值多項式具有性質(zhì)： 所以，類似于逐次線性插值法，也可以把上述和式中的第二項看成是估計 的一種實用誤差估計式。與差商概念密切聯(lián)系的另一個概念是

10、差分，它是指在等距節(jié)點上函數(shù)值的差。所謂等距節(jié)點，是指對給定的常數(shù)h（稱為步長），節(jié)點稱為 處的一階向前差分；稱 為 處的一階向后差分；稱 為 處的中心差分。一階差分的差分稱為二階差分，即 稱為 處的二階向前差分。一般地，m 階向前和向后差分可定義如下：3、 牛頓插值法的實現(xiàn)1、【算法】步驟1：輸入節(jié)點（xj，yj），精度，計值點xx，f0p，1T，1i；步驟2：對k=1，2，i依次計算k階均差fxi-k,xi-k+1,xi = (fxi-k+1,xi- fxi-k,xi)/( xi -xi-k )步驟3：（1）、若| fx1,xi- fx0,xi-1| ，則p為最終結果Ni-1(x)，余項R

11、i-1= fx0,xi(xx-xi-1)T。 （2）、否則(xx-xi-1)*TT，p+ fx0,xi*Tp，轉步驟4。步驟4：若in，則i+1i，轉步驟2；否則終止。 2、【流程圖】STOP 1輸出p，r，iqi(xi-xi-1)TRk= 1，2，ik（qk-1gk-1）（xixi-k）qkf0g0，fiq0輸出，xx，n及（xj，yj）開始 i+1i YES|gi-1-qi-1| NO(xi-xi-1)TTp+qi*Tp k = 1，2，iqkgkk YESkn i+1 i qi(xx-xn-1)*TR NO 輸出P，R，nSTOP 2 3、【程序清單】#includestdio.h#de

12、fine n 4/牛頓插值的次數(shù)void main() float an+1n+2=0,s=0,t=1,x; int i,j; printf(請輸入xi及yi的值/要求先輸入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)

13、; printf(n); printf(輸出牛頓插值表達式n); printf(N%d(x)=,n); for(i=0;in+1;i+) printf(%6.5f,aii+1); for(j=0;ji;j+) printf(x-%3.2f),aj0); if(i=n) break; printf(+); printf(n); printf(輸入插值點x=); scanf(%f,&x); for(i=0;in+1;i+)/計算插值點的近似值 for(j=0;ji;j+) t*=(x-aj0);s+=aii+1*t; printf(N%d(%4.3f)=%6.5fn,n,x,s);4.【程序實現(xiàn)】

14、參考文獻:Richard L. Burden, J. Douglas Faires, Numerical Analysis (Seventh Edition), Brooks Pub. Co.,2001.2. 蔡大用，白峰杉. 高等數(shù)值分析. 清華大學出版社，北京，1998.3. 鄧建中，劉之行. 計算方法（第二版）.西安交通大學出版社，2001.4. 韓旭里. 數(shù)值分析. 中南大學出版社，2003.致謝本文得以順利完成，非常感謝我的指導教師 。從論文的選題直到論文的最終完成，他都給予我盡心盡力的指導。老師嚴謹?shù)闹螌W態(tài)度深深地影響著我，對我今后的學習，工作，生活必將產(chǎn)生影響。借此機會，特向老師表示最誠摯的感謝。感謝南昌工程學院理學系的所有