牛頓插值法原理及應(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)式，就稱(chēng)它為插值多項(xiàng)式。當(dāng)插值節(jié)點(diǎn)增減時(shí)全部插值基函數(shù)均要隨之變化，這在實(shí)際計(jì)算中很不方便。為了克服這一缺點(diǎn)，提出了牛頓插值。 牛頓插值通過(guò)求各階差商，遞推得到的一個(gè)公式：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ù)的概念及相關(guān)性質(zhì)1 定義：設(shè)連續(xù)函數(shù)y-f(x) 在區(qū)間

2、a,b上有定義，已知在n+1個(gè)互異的點(diǎn)x0,x1,xn上取值分別為y0,y1,yn （設(shè)a x1x2xnb)。若在函數(shù)類(lèi)中存在以簡(jiǎn)單函數(shù)P(x) ，使得P(xi)=yi,則稱(chēng)P(x) 為f(x)的插值函數(shù).稱(chēng)x1,x2,xn 為插值節(jié)點(diǎn)，稱(chēng)a,b為插值區(qū)間。 定理：n次代數(shù)插值問(wèn)題的解存在且唯一 。牛頓插值法C程序 程序框圖#include<stdio.h>void main()    float x11,y1111,xx,temp,newton;    int i,j,n;  &#

3、160; printf("Newton插值:n請(qǐng)輸入要運(yùn)算的值:x=");    scanf("%f",&xx);    printf("請(qǐng)輸入插值的次數(shù)(n<11):n=");    scanf("%d",&n);    printf("請(qǐng)輸入%d組值:n",n+1);    for(i=0;i<n+1;i+)

4、0;      printf("x%d=",i);        scanf("%f",&xi);        printf("y%d=",i);        scanf("%f",&y0i);     

5、60;  for(i=1;i<n+1;i+)        for(j=i;j<n+1;j+)           if(i>1)                yij=(yi-1j-yi-1j-1)/(xj-xj-i);   &#

6、160;        else            yij=(yi-1j-yi-1j-1)/(xj-xj-1);                    printf("%fn",yii);  &#

7、160;      temp=1;newton=y00;        for(i=1;i<n+1;i+)       temp=temp*(xx-xi-1);        newton=newton+yii*temp;        printf("求得的結(jié)果為:N(%.4f)=%9fn"

8、,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(&apos;x和y的維數(shù)不相等！&apos;);     return; end f = y(1); y1 = 0; l  = 1; for(i=1:n-1)      

9、; 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);       f = f + c(i)*l;     simplify(f);  

10、0;  y = y1;     if(i=n-1)         if(nargin = 3)             f = subs(f,&apos;t&apos;,x0);         else        &

11、#160;    f = collect(f);                %將插值多項(xiàng)式展開(kāi)             f = vpa(f, 6);         end     end 牛頓插

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

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

14、。逼近函數(shù)一般為只含有算術(shù)運(yùn)算的簡(jiǎn)單函數(shù)，如多項(xiàng)式、有理分式（即多項(xiàng)式的商）。在工程實(shí)際問(wèn)題當(dāng)中，我們也經(jīng)常會(huì)碰到諸如此類(lèi)的函數(shù)值計(jì)算問(wèn)題。被計(jì)算的函數(shù)有時(shí)不容易直接計(jì)算，如表達(dá)式過(guò)于復(fù)雜或者只能通過(guò)某種手段獲取該函數(shù)在某些點(diǎn)處的函數(shù)值信息或者導(dǎo)數(shù)值信息等。因此，我們希望能用一個(gè)“簡(jiǎn)單函數(shù)”逼近被計(jì)算函數(shù)，然后用該簡(jiǎn)單函數(shù)的函數(shù)值近似替代被計(jì)算函數(shù)的函數(shù)值。這種方法就叫插值逼近或者插值法。逐次線性插值法優(yōu)點(diǎn)是能夠最有效地計(jì)算任何給定點(diǎn)的函數(shù)值，而不需要寫(xiě)出各步用到的插值多項(xiàng)式的表達(dá)式。但如果解決某個(gè)問(wèn)題時(shí)需要插值多項(xiàng)式的表達(dá)式，那么，它的這個(gè)優(yōu)點(diǎn)就成了它的缺點(diǎn)了。能不能根據(jù)插值條件構(gòu)造一個(gè)插值

15、多項(xiàng)式，它既有具體的表達(dá)式，又很容易用它計(jì)算任何點(diǎn)的函數(shù)值呢？牛頓插值法能作到這一點(diǎn)。 2、 牛頓插值法的概念牛頓插值多項(xiàng)式的表達(dá)式設(shè)問(wèn)題是如何根據(jù)插值條件 ,i=0,1,2n 來(lái)計(jì)算待定系數(shù)？由 知， 。由 知 因而 ，其中 稱(chēng)為函數(shù)f(x)在點(diǎn)的一階商。由 知 因而 其中稱(chēng)為函數(shù)f (x)在點(diǎn)的二階差商。實(shí)際上，它是一階差商的差商。一般地，如果已知一階差商，那么就可以計(jì)算二階差商 類(lèi)似于上述過(guò)程不斷地推導(dǎo)下去，可得 其中，分別稱(chēng)為函數(shù)f (x)在相應(yīng)點(diǎn)處的三階差商，四階差商和n 階差商。實(shí)際上， 的計(jì)算可通過(guò)以下簡(jiǎn)易地構(gòu)造函數(shù)的差商來(lái)完成。 .按上述方式構(gòu)造插值多項(xiàng)式的方法叫做牛頓插值法。

16、根據(jù)插值多項(xiàng)式的惟一性知，其截?cái)嗾`差與拉格朗日插值法相同，即： 但也可以表示成差商形式。這是因?yàn)橐詾楣?jié)點(diǎn)的多項(xiàng)式 從而 于是 的截?cái)嗾`差可表為 順便指出，因?yàn)榕ｎD插值多項(xiàng)式具有性質(zhì)： 所以，類(lèi)似于逐次線性插值法，也可以把上述和式中的第二項(xiàng)看成是估計(jì) 的一種實(shí)用誤差估計(jì)式。與差商概念密切聯(lián)系的另一個(gè)概念是差分，它是指在等距節(jié)點(diǎn)上函數(shù)值的差。所謂等距節(jié)點(diǎn)，是指對(duì)給定的常數(shù)h（稱(chēng)為步長(zhǎng)），節(jié)點(diǎn)稱(chēng)為 處的一階向前差分；稱(chēng) 為 處的一階向后差分；稱(chēng) 為 處的中心差分。一階差分的差分稱(chēng)為二階差分，即 稱(chēng)為 處的二階向前差分。一般地，m 階向前和向后差分可定義如下：3、 牛頓插值法的實(shí)現(xiàn)1、【算法】步驟1：

17、輸入節(jié)點(diǎn)（xj，yj），精度，計(jì)值點(diǎn)xx，f0p，1T，1i；步驟2：對(duì)k=1，2，i依次計(jì)算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為最終結(jié)果Ni-1(x)，余項(xiàng)Ri-1= fx0,xi(xx-xi-1)T。 （2）、否則(xx-xi-1)*TT，p+ fx0,xi*Tp，轉(zhuǎn)步驟4。步驟4：若i<n，則i+1i，轉(zhuǎn)步驟2；否則終止。 2、【流程圖】STOP 1輸出p，r，iqi(xi-xi-1)TRk= 1，2，ik（qk-1gk-1）（xi

18、xi-k）qkf0g0，fiq0輸出，xx，n及（xj，yj）開(kāi)始 i+1i YES|gi-1-qi-1|< NO(xi-xi-1)TTp+qi*Tp k = 1，2，iqkgkk YESk<n i+1 i qi(xx-xn-1)*TR NO 輸出P，R，nSTOP 2 3、【程序清單】#include"stdio.h"#define n 4/牛頓插值的次數(shù)void main() float an+1n+2=0,s=0,t=1,x; int i,j; printf("請(qǐng)輸入xi及yi的值/要求先輸入xi再輸入yi然后輸入下一組n"); for

19、(i=0;i<n+1;i+) for(j=0;j<2;j+) scanf("%f",&aij); for(j=1;j<n+2;j+)/計(jì)算各階均差 for(i=j;i<n+1;i+) aij+1=(aij-ai-1j)/(ai0-ai-j0); printf("輸出xi，yi及各階均差n"); for(i=0;i<n+1;i+) for(j=0;j<n+2;j+) printf("%6.5f ",aij); printf("n"); printf("輸出牛頓插值表達(dá)式n"); printf("N%d(x)=",n); for(i=0;i<n+1;i+) printf("%6.5f",aii+1); for(j=0;j<i;j+) printf("(x-%3.2f)",aj0); if(i=n) break; printf("+"); printf("n"); printf("輸入插值點(diǎn)x="); scanf("%f",&x); for(i=