牛顿插值法的C语言实现

《牛顿插值法的C语言实现》由会员分享，可在线阅读，更多相关《牛顿插值法的C语言实现（13页珍藏版）》请在装配图网上搜索。

1、牛顿插值法的C语言实现摘要：拉格朗日插值法具有明显的对称性，公式中的每一项与所 有的插值节点有关。因此，如果需要增加一个插值节点，则拉格朗日 插值公式中的每一项都要改变，在有的应用中就显得不太方便。因此, 可以利用另外一种差值方法来弥补这种缺陷， 就牛顿插值法。本文通 过对牛顿插值法的数学分析，主要给出其 c语言实现方法。关键字：差商差分c语言算法1差商及其牛顿插值公式i.i差商及其主要性质定义 若已知函数f(x)在点Xi(i =0,1,2,n)处的函数值f(x)。则称:f X0 = f(X0)为函数f (x)在点X0的0阶差商；f X0, Xi =f一地立为函数f(x)过点X0,Xi的1阶差

2、商；X0 -Xif x0, x1,x2 = f X0, Xl fX0, X2为函数 f (x)过点 X0, Xi,X2 的 2阶差商；Xi -X2以此类推，一般地称fx0,Xi,X2,XkAXkln fX0,Xi, 一，口x- fX0,Xi, k 为函数 f(x)过 Xk J -Xk点X0,Xi, Xk的k阶差商。性质i阶差商表示为函数值 f(x0), f(x1)，f (xk)的线性组合。即Jf(Xj)fX0,Xi,X2, ；Xk= -；jz0(Xj X。)(Xj Xj)(Xj - Xj .1)(Xj - Xk)_ef(Xj)一 kji【(Xj -Xi)i =0 i二j性质2若函数f(x)在包

3、含节点的区间a,b上存在k阶导数，则k阶差商与导数的关 系为f (k)( )fXo,Xi,Xk,a, bk!1.2牛顿插值公式通过n +1个互异点上的次数不超过 n的插值多项式Pn(x)可以表示如下形式:Pn(X)= fXo fXo,Xi(Xo -Xi) fXo,Xi,X2(X-Xo)(X-Xi) fXo,Xi,Xn(X -Xo) (X -Xn)这种形式的插值多项式称为牛顿插值多项式，一般记为Nn(X) = f% fXo,Xi(Xo -为)fXo,Xi,X2(X-Xo)(X-Xi)fXo, X), ,Xn(X-X0) (X -Xn)由牛顿插值多项式可以看出， 当增加一个插值点时， 当前已有的各

4、项不变， 只需要在后面增 加一项即可。并且，在牛顿插值公式中，每一项的系数就是各阶差商， 比拉格朗日插值公式 计算量小，且便于程序设计。根据差商性质2,即fXo，Xi， ,%f (n )( )(n i)!, a,b就可以将拉格朗日插值公式的余项转化成牛顿插值公式的余项，即f(n，jRn(X) = - = fXo,Xi, ,Xn (n i)!牛顿插值公式余项更具有一般性，它对于列表函数或者 f (X)导数不存在的情形都适用。2差分与等距结点插值公式2.i差分及其主要性质定义 设函数y = f (x )在等距结点Xk =Xo kh,k = 0,i, , n上的函数值为fk 二 f Xk , k =

5、0,i, ,n其中，为常熟，h称为步长。则f(Xk) = f (XkQ-f(Xk)称为函数f(x)在处以h为步长的一阶向前差分，并简记为f k =fk4- fk；f(Xk)= f(Xk) f (Xk)称为函数f(x)在处以h为步长的一阶向后差分，并简记为%，fk = fk -fkj6 f (Xk) = f(Xk和2) f(Xkq2)称为函数f(X)在处以h为步长的一阶向中心差分，并间记为 C. % =。1/2 - fkj/2性质1各阶差分可以表示成函数值的线性组合。即n(1). nfi C(.1)kCnk fj:；n*k z0n(2)、nfj(-1)kCkfj 上k z0n(3)、八(-1)C

6、f.k 王j 2 上性质2差商与差分具有如下关系：. n f 上 n ffX0M 二木一篇2.2等距结点插值公式2.2.1 牛顿前插公式Nn(X) = fo一 ML) (t - n D-f。n!n=k =0t(t -1) (t -k 1)k!，kf0其余项公式为f(n 书)()Rn(X) =Rn(X。+th) = j t(t-1) (t -n)hn+1, 士X。, Xn(n 1.2.2.2 牛顿后插公式Nn(X) = fn -tfn + t(-1)nt(t -1) (t-n 1)n!fnnc (-1)kk z0t(t -1) (t -k 1)k!其余项公式为Rn(X)= Q(Xn -th) =

7、f(n 1)( )(n 1)t (t -1) (-1) . (t n)h ，x0, xn在用牛顿前插和后插公式计算时候，要涉及到各阶前插和后插计算，下面是各阶向前和向后差分的计算格式，如下图所示。表1各阶向前差分和向前差分的计算公式Xkfk1阶差分2阶差分3阶差分4阶差分附十前插公式Xof0 2fo 3fo 4foUlLX1f1A2f3f1Illi 1X2f2f22f2Illi 1X3f3颂U1LX4f4U1LULLIlli 1Xn工fn工U1LXn工fn J3，n J2UlLXn2fn J2*n/V2 fTn_2Illi 1Xn .1fnfn靖fv fnV3fV TnIlli 1Xnfnfn

8、2f573f1 nV4f1 n用于后插公式3牛顿差值公式的C程序设计和应用实例3.1牛顿差值法的应用步骤步骤 首先我们按照表1,求得各点的差商.然后利用牛顿前差或后差公式，把数值带入即可以求得n次多项式。它在计算机上的应用步骤如下：步骤1输入所要求的牛顿多项式的次数n,并依次输入n+1个节点（Xi,yj .for : i=0 to n+1scanf(%f,&xi)scanf(%f,&y0i);步骤2计算各阶差商for : i=1 to n+1for: j=i to n+1if(i1)yij=(yi-ij-yi-ij-i)/(xj-xj-i)；elseyij=(yi-ij-yi-ij-i)/(x

9、j-xj-i)；步骤3代入牛顿插值公式，可计算得出结果。for : i=1 to n+1temp=temp*(xx-xi-1);牛顿=牛顿 +yii*temp;3.2利用牛顿插值法程序的实例为了更方便的应用牛顿插值法，我们进行了与计算机的结合，下面我们将展示几个例 子。例2.1已知y =sin x的一组数据为x07T6了31 万JI 万sinx012V22正21(1)构造牛顿插值函数并作图分析。14(2)并分别利用程序估计 sin , sin* 的估计值。分析首先我们可以通过程序求出差商表：xkf(xk)一阶差商二阶差商三阶差商四阶差商006120.954929268冗 彳火-2-0.7910

10、89631-2.086076213第 20.607024424-0.35153865-0.13648909Jt210.25587263-0.44710035-0.091254700.028797106带入定义1.5中可求得如下牛顿插值多项式如下N2(x) = 0.95492926X -0.2086076x(x-)6(2.(1)JITE 31N3(x) =0.95492926x-0.2086076x(x-石)-0.13648909x(x-)(x-)(2.(2)313131N4(x) =0.95492926x -0.2086076x(x -) - 0.13648909x(x -)(x -)664i

11、t je je0.028797106x(x 一一)(x 一)(x - 一)643第二步 利用C+锂序at算sina和sin篝 的值。步骤如下：利用 C程序：首先输入14二所要求的牛顿多项式的次数n,然后输入n+1个节点的值.即可以得出sinsin 的值为 0.2586 和 0.0804 ;例2.2设f(x) =ln(1 +x)的函数表如下:x0.250.300.360.390.45f(x0.2231440.2623640.3074850.3293040.371564试计算 ln(1.275) , f (x) =ln 2.3分析：同上题步骤我们先求差商表，进而代入公式可得M(x) =0.2231

12、4 0.7844(x - 0.25) - 0.294393939(x - 0.25)(x - 0.30) 0.1411736357(x-0.25)(x -0.30)(x - 0.36) 0.057720032 (x -0.25)(x-0.30)(x-0.36)(x -0.39)Na(x) =0.22314 0.7844(x - 0.25) - 0.294393939(x - 0.25)(x -0.30) 0.1411736357(x -0.25)(x -0.30)(x- 0.36)。(x) =0.22314 0.7844(x-0.25)-0.294393939(x-0.25)(x-0.30)利

13、用C程序我们可以得到计算结果：M (0.275) =0.242946,M(0.275) = 0.242945,N2 (0.275) =0.2429383(1.3)=0.928823,&(1.3) = 0.877002,电(0.275) =0.737653从上述两个例子我们可以看出，多项式在区间0,工周围与原函数逼近的较好。离这个4区间越远与原函数的误差越大在 x =1.5处时，该图像就已经开始背离图像了 .所以该多项式 只能在一个小的区间里可以逼近原函数，不适合作为原函数的逼近函数.也可以看出多项式在0,3区间的周围逼近的较好，但是x =2处时，该图像就离原图像误差较大.多项式在区3间0,2.

14、5都逼近的挺好，从图中我们看出在远离这个区间的图像误差相对较大，但是在这三个多项式中是逼近最好的。于是可以得出节点越多，函数逼近的相对较好.在节点附近逼近的越好，越远离节点误差越大，所以公式适用于计算节点附近的值于是为了减小误差，在下一节的等距节点下的插值公式根据所求的点的函数值的不同分别采取了前插和后插公式。3.4等距节点下的牛顿插值算法与程序设计前面我们讲述了一般节点下的牛顿插值公式，为了计算方便于是有了对等距节点下的牛顿多项式的研究，本节将对等距节点下的插值多项式进行总结讨论3.4.1 等距节点下的牛顿插值法的程序算法步骤步骤先求差分.然后利用牛顿前插公式或牛顿后插公式并把数值带入.即可

15、以求得n次多项式。它在计算机上的应用步骤如下：步骤1输入所要求的牛顿多项式的次数n,步长h ,并依次输入n+1个节点(x，yi)。for : i=0 to n+1scanf(%f,&xi)scanf(%f,&y0i);步骤2求得各界差分for : i=1 to n+1 for : j=i to n+1yij=(yi-1j+1-yi-1j-1)/(xj-xj);/ 求向前差分for : i=1 to n+1 for : j=i to n+1yij=(yi-ij-yi-ij-i)/(xj-xj-i);/ 求向后差分步骤3代入牛顿插值公式，可计算得出结果for(i=1;in+1;i+)temp=te

16、mp*(t-i+1)/i);牛顿=牛顿 +yii*temp;printf(求得的结果为：N(%.4f)=%9fn,xx,牛顿);/求得运用前插公式的值for(i=n;i0;i-)temp=temp*(t-i+1)/i);牛顿=牛顿 +yn-in-i*temp;printf( 求得的结果为：N(%.4f)=%9fn,xx,牛顿)；/求得运用后插公式的值3.4.2 等距节点下牛顿插值的实例例 已知tan x的值列表如下:x1.31.311.321.33tanx3.60213.74713.90334.0723近似计算 tan1.325, tan1.305。P3(x)= 4.0723 0.1690t0

17、.01280.0016t(t 1)2!3!t(t 1)(t 2).采用牛顿向后插公式.为此，做差分表xifi2fi叫1.33.60210.14500.01120.00161.313.74710.15620.01281.323.90330.16901.334.0723从而，有将t =1.325 T33 = 0.5代入上式，得0.01tan1.325 电 p3(1.325) = 3.9869 。1.305-1.33001=-2.5带入后插多项式中可以得到tan1.305 : p3(1.305) =3.0797现在我们利用C程序 首先输入所求插值的次数3和步长0.01.然后输入各个节点，并输入所要求

18、的点1.325既可以求出该点的函数值。即f (1.325) =3.9869。 f (1.26)上 p3(1.26) = 3.0797例 设函数在各节点的取值如下x00.20.40.60.81.0f(x)1.00.8187310.6703200.5488120.4493290.367879试利用插值公式求f (0.3)的值。采用牛顿向前插公式，同上题我们先做差分表，然后相应带入到差分公式.中求得后插公式。利用C语言程序步骤如下：首先输入所求插值的次数 5和步长0.2。然后输入各个节点，并输入所要求的点0.3既可以求出该点的函数值。即 f(0.3) =0.7880。由以上例子我们看到例 1用了牛顿

19、后插公式，例2用了牛顿前插公式，我们该怎样选取。 这个经过验证得出，如果所要求的点较靠近节点为，则采用前插公式；如果靠近xn,则采用牛顿后插公式。4结束语用牛顿差值方法处理测量数据，具有使差值多项式通过选定测量值的特点，所以在数 据处理中有一定的应用场合。当测量值较多、较密时，为了减轻计算工作量及提高准确性， 应选取合适的测量值作为差商计算的依据求得 Nn (x)。参考文献1李庆扬等编.数值分析.华中科技大学出版社,19892储钟武等编译.数值分析.黑龙江科学技术出版社，19873徐士良编.数值分析与算法.机械工业出版社,2007附录A:牛顿插值法的程序#includeNewtonvoid m

20、ain()float x11,y1111,xx,temp,牛顿;int i,j,n；printf(牛顿插值：n请输入要运算的值：x=);scanf(%f,&xx);printf(请输入插值的次数(n11):n=);scanf(%d,&n);printf(请输入 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-ij-yi-ij-i)/(xj-xj-i)；elseyij=(yi-ij-yi-ij-i)/(

21、xj-xj-i)； printf(%fn,yii);temp=1; 牛顿=y00;for(i=1;in+1;i+) temp=temp*(xx-xi-1); 牛顿=牛顿 +yii*temp;printf( 求得的结果为：N(%.4f)=%9fn,xx,牛顿);C语言程序附录B:等距节点下的前插公式的#includevoid main()int i,j,n；printf(牛顿插值：n请输入要运算的值：x=);scanf(%f,&xx);printf(请输入插值的次数(n11):n=);scanf(%d,&n);printf(步长:n请输入要运算的值：h=);scanf(%f,&h);printf

22、(请输入 d组值:n,n+1);for(i=0;in+1;i+) printf(x%d=,i);scanf(%f,&xi);printf(y%d=,i);scanf(%f,&y0i);t=(xx-x0)/h;for(i=1;in+1;i+) for(j=i;jn+1;j+) yij=(yi-ij+i-yi-ij);printf(%fn,yii); temp=1; 牛顿=y00; for(i=1;in+1;i+) temp=temp*(t-i+1)/i);牛顿=牛顿 +yii*temp;printf(求得的结果为：N(%.4f)=%9fn,xx,牛顿)；附录C:等距节点下的后插公式的C语言程序#

23、include void main() float x11,y1111,xx,temp,牛顿,t,h;int i,j,n; printf(牛顿插值：n请输入要运算的值：x=);scanf(%f,&xx); printf(请输入插值的次数(n11):n=);scanf(%d,&n); printf(步长:n请输入要运算的值：h=);scanf(%f,&h);printf( 请输入 d组值:n,n+1);for(i=0;in+1;i+)printf(x%d=,i);scanf(%f,&xi);printf(y%d=,i);scanf(%f,&y0i);t=(xx-xn-1)/h;for(i=1;in+1;i+)for(j=i;jn+1；j+)yij=(yi-ij-yi-ij-i);printf(%fn,yii);temp=1; 牛顿=yn-1n-1;for(i=n;i0;i-)temp=temp*(t-i+1)/i);牛顿=牛顿 +yn-in-i*temp;printf( 求得的结果为：N(%.4f)=%9fn,xx, 牛顿);附录D:牛顿插值法的流程图