牛顿插值法原理及应用.doc

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

2、) 在区间 a,b 上有定义，已知在 n+1 个互异的点 x0,x1, xn 上取值分别为 y0,y1, yn （设 a x1 x2 xnb) 。若在函数类中存在以简单函数 P(x) ，使得 P(xi)=yi, 则称 P(x) 为 f(x) 的插值函数 .称 x1,x2, xn 为插值节点，称 a,b 为插值区间。定理： n 次代数插值问题的解存在且唯一 。牛顿插值法C 程序程序框图 #includevoid main()float x11,y1111,xx,temp,newton;int i,j,n;printf(Newton插值 :n 请输入要运算的值 :x=);scanf(%f,&xx)

3、;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-1j-yi-1j-1)/(xj-xj-i);elseyij=(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-

4、1);newton=newton+yii*temp;printf(求得的结果为 :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;elsedisp('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(

5、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);endend牛顿插值法摘 要：值法利用函数 f (x) 在某区间中若干点的函数值，作出适当的特定函数， 在这些点上取已知值， 在区间的其他点上用这特定函数的值作为函数 f (x) 的近似值。如果这特定函数是多项式， 就称它为插值多项式。利用插值基函数很容易得到拉格朗日插值多项式， 公式结构紧凑，在理论分析中

6、甚为方便， 但当插值节点增减时全部插值基函数均要随之变化，整个公式也将发生变化， 这在实际计算中是很不方便的，为了克服这一缺点，提出了牛顿插值。牛顿插值通过求各阶差商，递推得到的一个公式：f(x)=fx0+fx0,x1(x-x0)+fx0,x1,x2(x-x0)(x-x1)+.fx0,.xn(x-x0).(x-xn-1)+Rn(x)关键词：牛顿插值法流程图程序实现一、 插值法的由来在许多实际问题及科学研究中， 因素之间往往存在着函数关系，然而，这种关系经常很难有明显的解析表达， 通常只是由观察与测试得到一些离散数值。 有时，即使给出了解析表达式， 却由于表达式过于复杂，不仅使用不便， 而且不易

7、于进行计算与理论分析。 解决这类问题的方法有两种：一种是插值法 ,另一种是拟合法。插值法是一种古老的数学方法， 它来自生产实践， 早在一千多年前， 我国科学家在研究历法上就应用了线性插值与二次插值， 但它的基本理论却是在微积分产生之后才逐渐完善的， 其应用也日益增多， 特别是在计算机软件中，许多库函数，如等的计算实际上归结于它的逼近函数的计算。逼近函数一般为只含有算术运算的简单函数， 如多项式、有理分式（即多项式的商）。在工程实际问题当中，我们也经常会碰到诸如此类的函数值计算问题。 被计算的函数有时不容易直接计算， 如表达式过于复杂或者只能通过某种手段获取该函数在某些点处的函数值信息或者导数值

8、信息等。因此，我们希望能用一个“简单函数”逼近被计算函数，然后用该简单函数的函数值近似替代被计算函数的函数值。 这种方法就叫插值逼近或者插值法。逐次线性插值法优点是能够最有效地计算任何给定点的函数值，而不需要写出各步用到的插值多项式的表达式。 但如果解决某个问题时需要插值多项式的表达式， 那么，它的这个优点就成了它的缺点了。能不能根据插值条件构造一个插值多项式， 它既有具体的表达式， 又很容易用它计算任何点的函数值呢？牛顿插值法能作到这一点。二、牛顿插值法的概念牛顿插值多项式的表达式设Nn c0 c1(x x0) c2(x x0)(x x1)cn(x x0)(x x1) (x xn 1)问题是

9、如何根据插值条件N nxiyi ,i=0,1,2 n来计算待定系数 c0 ,c1 , c2cn ？由知，由知N n ( x0)c0y0N n ( x1)y0f ( x0)f ( x0) 。y1f ( x1)c0 c1 ( x1 x0)y1因而c1y1y0f ( x1)f ( x0)f x0 , x1x1x0x1x0，其中f x0 , x1 称为函数 f(x) 在 x0 , x1点的一阶商。由N n ( x2)y2f (x2)知c0 c1 ( x1x0)c2 ( x2 x0)( x2 x1) y2因而c2y2 y0f x0 , x1( x2x0)( x2x0)( x2 x1)y2 y1y1 y0

10、f x0 , x1( x2 x0)y2 y1y2y1x2 x1( x2x0)( x2x1)f x0 , x1( x1x0)( x2 x0)( x2 f x0 , x1f x , x ( xx )0120x1)( x2f x1 , x2 ( x2x0)f x0 , x1f x0 , x1, x2x0 )其中 f x0 , x1 , x2 称为函数 f (x) 在 x0 , x1 , x2 点的二阶差商。实际上，它是一阶差商的差商。一般地，如果已知一阶差商f xi 1 , xi , f xi , xi 1 ，那么就可以计算二f xi 1 , xif xi , xi 1 f xi 1 , xi, x

11、i 1阶差商xi 1 _ xi 1类似于上述过程不断地推导下去，可得c3f x1 , x2 , x3f x0 , x1 , x2f x0 ,x1 , x2 , x3,(x3x0)c4f x1 , x2 , x3 , x4f x0 , x1 , x2 , x3f x0 , x1 , x2 , x3 , x4,( x4x0)c4f x1 , x2 xnf x0 , x1, x2 xn 1xn ,( xnx0 )f x0 , x1 , x2其中，f x , x , x , x ,f x , x , x , x , x , f x , x , x , x , x , x , 分别称为函数0123012

12、34012345f (x) 在相应点处的三阶差商，四阶差商和n 阶差商。实际上，c0 ,c1 ,c2cn的计算可通过以下简易地构造函数的差商来完成。x0f ( x0) c0x1x2x3x4.f ( x )1f ( x2) f ( x3) f ( x4).f x0 , x1 c1f x1, x2f x0 , x1 , x2 c2f 2 ,3f , x2 ,x3f 0 ,1, 2,3 3xx1xx xxcxf 3 ,x4f 2 , 3 ,x4f 1, x2 , x3 , x4f 0 , 1 , 2 , 3 ,x44xx xxx x x xc.按上述方式构造插值多项式的方法叫做牛顿插值法。根据插值多

13、项式的惟一性知，其截断误差与拉格朗日插值法相同，即：1( n 1)n1)!f ( )n 1( x)R (n但也可以表示成差商形式。这是因为以x0 , x1 , x2xn 为节点的多项式Nn 1 (x)Nn ( x)f x0, x1 xn 1 n 1 (x )从而f (xn 1)N n 1 ( xn 1)Nn (xn 1)f x0 , x1xn 1n 1 ( xn 1)于是 Nn (x) 的截断误差可表为R (x)f x , x ,x , x ( x)n01n 1n 1顺便指出，因为牛顿插值多项式具有性质：Nn (x)Nn 1 ( x) f x0 , x1 xn ( x x1)( x x2) (

14、 x xn 1)所以，类似于逐次线性插值法，也可以把上述和式中的第二项f x0 , x1xn( x x1)( x x2) ( x xn 1)看成是估计N n 1 ( x) 的一种实用误差估计式。与差商概念密切联系的另一个概念是差分，它是指在等距节点上函数值的差。所谓等距节点，是指对给定的常数h（称为步长），节点xix0 ih,(i 0,1,2 n) 称 f ( xi 1) f ( xi ) f k 为 xi 处的一阶向前差分；称f ( xi)f ( xi 1)f i为 xi 处的一阶向后差分；称f ( xih 2 )f ( xi 1h 2 )f i为 xi 处的中心差分。一阶差分的差分称为二阶

15、差分，即f i 1 f i2 f i称为 xi 处的二阶向前差分。一般地， m 阶向前和向后差分可定义如下：mmffm 1im 1iffm 1i1m 1i 1ff,im2,3,i11三、牛顿插值法的实现1、【算法】步骤 1：输入节点（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) ，余项 Ri-1= fx0,xi

16、(xx-xi-1)T 。（2）、否则 (xx-xi-1)*TT ，p+ fx0,xi*Tp，转步骤 4。步骤 4：若 in ，则 i+1i ，转步骤 2；否则终止。122、【流程图】开始i+1i输出，xx，n 及（xj ，yj ）f 0g0，f iq0k= 1 ，2， ， i（qk-1g）（xxi-k）qk-1ikkqi (x i -x i-1 )TR输出 p，r ，iYESSTOP 113|g i-1 -q i-1 |NO(x i -x i-1 )TTp+qi *Tpk = 12iqkgkkYESi+1iknNOqi (xx-x n-1 )*TR14输出 P，R，nSTOP 23、【程序清单

17、】 #includestdio.h#define n 4/牛顿插值的次数void main()float an+1n+2=0,s=0,t=1,x;int i,j;15printf( 请输入 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

18、;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,aii+1);for(j=0;ji;j+)printf(x-%3.2f),aj0);16if(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.【程序实现】17参考文献 :Richard L. Burden, J. Douglas Faires, Numerical Analysis(Seventh Edition), Brooks Pub. Co.,2001.2. 蔡大用，白峰杉 . 高等数值分析 . 清华大学出版社，北京， 1998.3. 邓建中，刘之行 . 计算方法（第二版）.西安交通大学出版社， 2001.4. 韩旭里 . 数值分析 . 中南大学出版社， 2003.18致谢本文得以顺利完成，非常感谢我的指导教师。从论文的选题直到论文的最终完成，他都给予我尽心尽力