1、牛頓插值法的C語言實現摘要：拉格朗日插值法具有明顯的對稱性，公式中的每一項與所有的插值節點有關。因此，如果需要增加一個插值節點，則拉格朗日插值公式中的每一項都要改變，在有的應用中就顯得不太方便。因此，可以利用另外一種差值方法來彌補這種缺陷，就牛頓插值法。本文通過對牛頓插值法的數學分析，主要給出其C語言實現方法。關鍵字：差商 差分 C語言算法1差商及其牛頓插值公式1.1 差商及其主要性質定義 若已知函數在點處的函數值。則稱：為函數在點的階差商；為函數過點的階差商；為函數過點的階差商；以此類推，一般地稱為函數過點的階差商。性質1 階差商表示為函數值的線性組合。即 性質2 若函數在包含節點的區間上存

2、在階導數，則階差商與導數的關系為 1.2 牛頓插值公式通過個互異點上的次數不超過的插值多項式可以表示如下形式： 這種形式的插值多項式稱為牛頓插值多項式，一般記為 由牛頓插值多項式可以看出，當增加一個插值點時，當前已有的各項不變，只需要在后面增加一項即可。并且，在牛頓插值公式中，每一項的系數就是各階差商，比拉格朗日插值公式計算量小，且便于程序設計。根據差商性質2，即就可以將拉格朗日插值公式的余項轉化成牛頓插值公式的余項，即 牛頓插值公式余項更具有一般性，它對于列表函數或者導數不存在的情形都適用。2 差分與等距結點插值公式2.1 差分及其主要性質 定義 設函數在等距結點上的函數值為其中，為常熟，稱

3、為步長。則 稱為函數在處以為步長的一階向前差分，并簡記為；稱為函數在處以為步長的一階向后差分，并簡記為稱為函數在處以為步長的一階向中心差分，并簡記為性質1 各階差分可以表示成函數值的線性組合。即 性質2 差商與差分具有如下關系： 2.2 等距結點插值公式2.2.1 牛頓前插公式 其余項公式為 2.2.2 牛頓后插公式 其余項公式為 在用牛頓前插和后插公式計算時候，要涉及到各階前插和后插計算，下面是各階向前和向后差分 的計算格式，如下圖所示。表1 各階向前差分和向前差分的計算公式1階差分2階差分3階差分4階差分用于前插公式用于后插公式3 牛頓差值公式的C程序設計和應用實例3.1 牛頓差值法的應用

4、步驟步驟 首先我們按照表1，求得各點的差商.然后利用牛頓前差或后差公式，把數值帶入.即可以求得n次多項式。 它在計算機上的應用步驟如下： 步驟1 輸入所要求的牛頓多項式的次數，并依次輸入個節點. for : i=0 to n+1scanf("%f",&xi) scanf("%f",&y0i);步驟2 計算各階差商 for : i=1 to n+1 for : j=i to n+1 if(i>1) yij=(yi-1j-yi-1j-1)/(xj-xj-i); else yij=(yi-1j-yi-1j-1)/(xj-xj-1); 步驟

5、3 代入牛頓插值公式,可計算得出結果。 for：i=1 to n+1 temp=temp*(xx-xi-1); 牛頓=牛頓+yii*temp;3.2 利用牛頓插值法程序的實例為了更方便的應用牛頓插值法，我們進行了與計算機的結合，下面我們將展示幾個例子。例2.1 已知的一組數據為xsinx（1） 構造牛頓插值函數并作圖分析。（2） 并分別利用程序估計，的估計值。 分析 首先我們可以通過程序求出差商表：一階差商二階差商三階差商四階差商帶入定義1.5中可求得如下牛頓插值多項式如下 (2.1) (2.2) 第二步 利用C+程序計算和的值。步驟如下：利用C程序：首先輸入所要求的牛頓多項式的次數n，然后輸

6、入n+1個節點的值.即可以得出和的值為0.2586和0.0804；例2.2 設的函數表如下：0.250.300.360.390.450.2231440.2623640.3074850.3293040.371564試計算，分析：同上題步驟我們先求差商表，進而代入公式可得 利用C程序我們可以得到計算結果 ： ，從上述兩個例子我們可以看出,多項式在區間周圍與原函數逼近的較好。離這個區間越遠與原函數的誤差越大在處時，該圖像就已經開始背離圖像了.所以該多項式只能在一個小的區間里可以逼近原函數,不適合作為原函數的逼近函數.也可以看出多項式在區間的周圍逼近的較好，但是處時，該圖像就離原圖像誤差較大.多項式在

7、區間0,2.5都逼近的挺好，從圖中我們看出在遠離這個區間的圖像誤差相對較大，但是在這三個多項式中是逼近最好的。于是可以得出節點越多，函數逼近的相對較好.在節點附近逼近的越好，越遠離節點誤差越大，所以公式適用于計算節點附近的值于是為了減小誤差，在下一節的等距節點下的插值公式根據所求的點的函數值的不同分別采取了前插和后插公式。3.4等距節點下的牛頓插值算法與程序設計前面我們講述了一般節點下的牛頓插值公式，為了計算方便于是有了對等距節點下的牛頓多項式的研究，本節將對等距節點下的插值多項式進行總結討論.3.4.1 等距節點下的牛頓插值法的程序算法步驟步驟先求差分.然后利用牛頓前插公式或牛頓后插公式并把

8、數值帶入.即可以求得n次多項式。 它在計算機上的應用步驟如下： 步驟1 輸入所要求的牛頓多項式的次數，步長，并依次輸入個節點。 for : i=0 to n+1 scanf("%f",&xi) scanf("%f",&y0i);步驟2 求得各界差分for : i=1 to n+1 for : j=i to n+1 yij=(yi-1j+1-yi-1j-1)/(xj-xj); /求向前差分 for : i=1 to n+1 for : j=i to n+1 yij=(yi-1j-yi-1j-1)/(xj-xj-i); /求向后差分步驟3 代

9、入牛頓插值公式,可計算得出結果 for(i=1;i<n+1;i+) temp=temp*(t-i+1)/i); 牛頓=牛頓+yii*temp; printf("求得的結果為:N(%.4f)=%9fn",xx,牛頓); /求得運用前插公式的值for(i=n;i<0;i-) temp=temp*(t-i+1)/i); 牛頓=牛頓+yn-in-i*temp; printf("求得的結果為:N(%.4f)=%9fn",xx,牛頓); /求得運用后插公式的值3.4.2 等距節點下牛頓插值的實例例 已知的值列表如下： 1. 3 1.31 1.32 1.3

10、3 3.6021 3.7471 3.9033 4.0723近似計算,。采用牛頓向后插公式.為此，做差分表 1.3 3.6021 0.1450 0.0112 0.0016 1.31 3.7471 0.1562 0.0128 1.32 3.9033 0.1690 1.33 4.0723從而，有將代入上式，得。將帶入后插多項式中可以得到現在我們利用C程序 首先輸入所求插值的次數3和步長0.01.然后輸入各個節點，并輸入所要求的點1.325既可以求出該點的函數值。即 。 例 設函數在各節點的取值如下00.20.40.60.81.01.00.8187310.6703200.5488120.4493290

11、.367879試利用插值公式求的值。采用牛頓向前插公式，同上題我們先做差分表，然后相應帶入到差分公式.中求得后插公式。利用C語言程序步驟如下:首先輸入所求插值的次數5和步長0.2。然后輸入各個節點，并輸入所要求的點0.3既可以求出該點的函數值。即。由以上例子我們看到例1用了牛頓后插公式，例2用了牛頓前插公式，我們該怎樣選取。這個經過驗證得出，如果所要求的點較靠近節點，則采用前插公式；如果靠近，則采用牛頓后插公式。4 結束語 用牛頓差值方法處理測量數據，具有使差值多項式通過選定測量值的特點，所以在數據處理中有一定的應用場合。當測量值較多、較密時，為了減輕計算工作量及提高準確性，應選取合適的測量值

12、作為差商計算的依據求得。參考文獻1 李慶揚等編.數值分析.華中科技大學出版社,1989 2 儲鐘武等編譯.數值分析.黑龍江科學技術出版社,1987 3 徐士良編.數值分析與算法.機械工業出版社,2007附錄A：牛頓插值法的程序#include<stdio.h>Newtonvoid main() float x11,y1111,xx,temp,牛頓; int i,j,n; printf("牛頓插值:n請輸入要運算的值:x="); scanf("%f",&xx); printf("請輸入插值的次數(n<11):n=&quo

13、t;); scanf("%d",&n); printf("請輸入%d組值:n",n+1); for(i=0;i<n+1;i+) printf("x%d=",i); scanf("%f",&xi); printf("y%d=",i); scanf("%f",&y0i); 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); else y

14、ij=(yi-1j-yi-1j-1)/(xj-xj-1); printf("%fn",yii); temp=1;牛頓=y00; for(i=1;i<n+1;i+) temp=temp*(xx-xi-1); 牛頓=牛頓+yii*temp; printf("求得的結果為:N(%.4f)=%9fn",xx,牛頓); 附錄B：等距節點下的前插公式的C語言程序#include<stdio.h>void main() float x11,y1111,xx,temp,牛頓,t,h; int i,j,n; printf("牛頓插值:n請輸入要

15、運算的值:x="); scanf("%f",&xx); printf("請輸入插值的次數(n<11):n="); scanf("%d",&n);printf("步長:n請輸入要運算的值:h="); scanf("%f",&h); printf("請輸入%d組值:n",n+1); for(i=0;i<n+1;i+) printf("x%d=",i); scanf("%f",&xi);

16、printf("y%d=",i); scanf("%f",&y0i); t=(xx-x0)/h; for(i=1;i<n+1;i+) for(j=i;j<n+1;j+) yij=(yi-1j+1-yi-1j); printf("%fn",yii); temp=1;牛頓=y00; for(i=1;i<n+1;i+) temp=temp*(t-i+1)/i); 牛頓=牛頓+yii*temp; printf("求得的結果為:N(%.4f)=%9fn",xx,牛頓);附錄C：等距節點下的后插公式的

17、C語言程序#include<stdio.h>void main() float x11,y1111,xx,temp,牛頓,t,h; int i,j,n; printf("牛頓插值:n請輸入要運算的值:x="); scanf("%f",&xx); printf("請輸入插值的次數(n<11):n="); scanf("%d",&n);printf("步長:n請輸入要運算的值:h="); scanf("%f",&h); printf("請輸入%d組值:n",n+1); for(i=0;i<n+1;i+) printf("x%d=",i); scanf("%f",&xi); printf("y%d=",i); scanf("%f",&y0i); t=(xx-xn-1)/h; for(i=1;i<n+1;i+) for(j=i;