牛顿插值法原理及应用

1、文档牛顿插值法插值法是利用函数f (x)在某区间中若干点的函数值，作出适当的特定函数，在这些点上取已知值，在区间的其他点上用这特定函数的值作为函数f (x)的近似值。如果这特定函数是 多项式，就称它为插值多项式。当插值节点增减时全部 插值基函数均要随之变化，这在实际计算中很不方便。为了克服这一缺点，提出 了牛顿插值。牛顿插值通过求各阶差商，递推得到的一个公式：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)。插值函数插值函数的概念及相关性质乩 定义：设连续函数y-f(x) 在区间a,b上有

2、定义，已知在n+1个互异的点x0,x1,xn上取值分别为y0,y1,yn (设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请输入要运算的值:x=);sca nf(%f, &xx);printf(请输入插值的次数(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 的维数不相等！ ');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);%将插值多项式展开f = vpa(f, 6

5、);endend牛顿插值法摘 要：值法利用函数 f (x) 在某区间中若干点的函数值，作出 适当的特定函数， 在这些点上取已知值， 在区间的其他点上用这特定 函数的值作为函数 f (x) 的近似值。如果这特定函数是多项式，就称 它为插值多项式。利用插值基函数很容易得到拉格朗日插值多项式， 公式结构紧凑， 在理论分析中甚为方便， 但当插值节点增减时全部插 值基函数均要随之变化，整个公式也将发生变化， 这在实际计算中 是很不方便的，为了克服这一缺点，提出了牛顿插值。 牛顿插值通过求各阶差商，递推得到的一个公式： f(x)=fx0+fx0,x1(x-x0)+fx0,x1,x2(x-x0)(x-x1)

6、+.fx0,.xn(x-x0).(x-xn-1)+Rn(x)关键词 ：牛顿插值法 流程图 程序实现一、插值法的由来在许多实际问题及科学研究中， 因素之间往往存在着函数关系， 然而，这种关系经常很难有明显的解析表达， 通常只是由观察与测试 得到一些离散数值。有时， 即使给出了解析表达式，却由于表达式过 于复杂，不仅使用不便，而且不易于进行计算与理论分析。解决这类 问题的方法有两种：一种是插值法 , 另一种是拟合法。插值法是一种 古老的数学方法，它来自生产实践，早在一千多年前，我国科学家在 研究历法上就应用了线性插值与二次插值， 但它的基本理论却是在微 积分产生之后才逐渐完善的， 其应用也日益增多

7、， 特别是在计算机软 件中，许多库函数，如等的计算实际上归结于它的逼近函数的计算。 逼近函数一般为只含有算术运算的简单函数， 如多项式、有理分式(即 多项式的商)。在工程实际问题当中，我们也经常会碰到诸如此类的 函数值计算问题。 被计算的函数有时不容易直接计算， 如表达式过于 复杂或者只能通过某种手段获取该函数在某些点处的函数值信息或 者导数值信息等。因此，我们希望能用一个“简单函数”逼近被计算 函数，然后用该简单函数的函数值近似替代被计算函数的函数值。 这 种方法就叫插值逼近或者插值法。逐次线性插值法优点是能够最有效地计算任何给定点的函数值， 而不需要写出各步用到的插值多项式的表达式。 但如

8、果解决某个问题 时需要插值多项式的表达式， 那么，它的这个优点就成了它的缺点了。 能不能根据插值条件构造一个插值多项式， 它既有具体的表达式， 又 很容易用它计算任何点的函数值呢？牛顿插值法能作到这一点。二、牛顿插值法的概念牛顿插值多项式的表达式设Nn c0c1(xx0)c2(xx0)(xx1)cn(xx0)(xx1)(xxn 1)问题是如何根据插值条件N n xi yi ,i=0,1,2 n来计算待定系数 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*称为函数f（X）在Xo,Xi点的一阶商。由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。*称为函数f （X）在X，XiX点的二阶差商。实际上，它是一阶差商的差商。一般地，如果已知一阶差商fXii

10、,Xi,fXi,Xi 1,那么就可以计算二阶差商fXi i，Xi，Xi 1fXXi 1fXi 1，XX 1 Xi 1类似于上述过程不断地推导下去，可得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，分别称为函数f （x）在相应点处的三阶差商，四阶差商和 n阶差商。实际上,Co，

11、Cl，C2 Cn的计算可通过以下简易地构造函数的差商来完成。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.按上述方式构造插值多项式的方法叫做牛顿插值法。 根据插值多项式的惟一性知，其截断误差与拉格朗日插值法相同，即：1(n 1)Rn (n 1)! f ()nn i(x)但也可以表示成差商形式。这是因为以IX0XX2刈为节点的多项式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)顺便指出，因为牛顿插值多项式具有性质：Nn(X) Nni(X)fX0，Xl Xn(X X)(X X2)(X X)所以，类似于逐次线性插值法，也可以把上述和式中的第二项fXo，Xl Xn(X X1)(X X2) (X Xn 1)看成是估计 Nn1(X)的一种实用误差估计式。与差商概念密切联系的另一个概念是差分，它是指在等距节点上函数值的差。所谓等距节点，是指对给定的常数 h (称为步长)，节点 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,转步骤4。三、牛顿插值法的实现1、【算法】步骤 1：输入节点( xj ，yj )，精度 ，计值点 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|,结果 Ni-1(x)，余项 Ri-1= fx0,xi(xx-xi-1)T 。(2)、否则(xx-xi-1)*T T, p+ fx0,xi*T步骤 4：若 in ,则 i+1 i ,转步骤 2；否则终止2、【流程图】NOJLqk gkkq(xx-Xn-i)*T RSTOP 23 、【程序清单】 #includestdio.h#define n 4/ 牛顿插值的次数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( 输出牛顿插值表达式 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( 输入插值点 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. 【程序实现】刀用各帅均罟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参考文献 :Richard L. Burden, J. Douglas Faires, Numerical Analysis(Seventh Edition), Brooks Pub. Co.,2001.2. 蔡大用，白峰杉 . 高等数值分析 . 清华大学， 1998.3. 邓建中，之行 . 计算方法(第二版) . 交通大学， 2001.4. 韩旭里. 数值分析. 中南大学， 2003.致谢本文得以顺利完成，非常感谢我的指导教师。从论文的选题直到论文的最终完成，他都给予我尽心尽力的指导。老师严谨的治学态度深深地影响着我， 对我今后