牛顿插值法原理及应用

实用文档牛顿插值法插值法是利用函数f(x)在某区间中若干点的函数值，作出适当的特定函数，在这些点上取已知值，在区间的其他点上用这特定函数的值作为函数f(x)的近似值。如果这特定函数是多项式，就称它为插值多项式。当插值节点增减时全部插值基函数均要随之变化，这在实际计算中很不方便。为了克服这一缺点，提出了牛顿插值。牛顿插值通过求各阶差商，递推得到的一个公式：f(x)=f[x0]+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)+...f[x0,...xn](x-x0)...(x-xn-1)+Rn(x)。插值函数插值函数的概念及相关性质[1]定义：设连续函数y-f(x)在区间[a,b]上有定义，已知在n+1个互异的点x0,x1,…xn上取值分别为y0,y1,…yn（设a≤x1≤x2……≤xn≤b)。若在函数类中存在以简单函数P(x)，使得P(xi)=yi,则称P(x)为f(x)的插值函数.称x1,x2,…xn为插值节点，称[a,b]为插值区间。定理：n次代数插值问题的解存在且唯一。实用文档牛顿插值法C程序程序框图#includestdio.hvoidmain(){floatx[11],y[11][11],xx,temp,newton;inti,j,n;printf(Newton插值:\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,&x[i]);printf(y%d=,i);scanf(%f,&y[0][i]);实用文档}for(i=1;in+1;i++)for(j=i;jn+1;j++){if(i1)y[i][j]=(y[i-1][j]-y[i-1][j-1])/(x[j]-x[j-i]);elsey[i][j]=(y[i-1][j]-y[i-1][j-1])/(x[j]-x[j-1]);printf(%f\n,y[i][i]);}temp=1;newton=y[0][0];for(i=1;in+1;i++){temp=temp*(xx-x[i-1]);newton=newton+y[i][i]*temp;}printf(求得的结果为:N(%.4f)=%9f\n,xx,newton);牛顿插值法Matlab程序functionf=Newton(x,y,x0)symst;if(length(x)==length(y))n=length(x);c(1:n)=0.0;else实用文档disp('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);endend实用文档牛顿插值法摘要：值法利用函数f(x)在某区间中若干点的函数值，作出适当的特定函数，在这些点上取已知值，在区间的其他点上用这特定函数的值作为函数f(x)的近似值。如果这特定函数是多项式，就称它为插值多项式。利用插值基函数很容易得到拉格朗日插值多项式，公式结构紧凑，在理论分析中甚为方便，但当插值节点增减时全部插值基函数均要随之变化，整个公式也将发生变化，这在实际计算中是很不方便的，为了克服这一缺点，提出了牛顿插值。牛顿插值通过求各阶差商，递推得到的一个公式：f(x)=f[x0]+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)+...f[x0,...xn](x-x0)...(x-xn-1)+Rn(x)关键词：牛顿插值法流程图程序实现一、插值法的由来在许多实际问题及科学研究中，因素之间往往存在着函数关系，然而，这种关系经常很难有明显的解析表达，通常只是由观察与测试得到一些离散数值。有时，即使给出了解析表达式，却由于表达式过于复杂，不仅使用不便，而且不易于进行计算与理论分析。解决这类问题的方法有两种：一种是插值法,另一种是拟合法。插值法是一种古老的数学方法，它来自生产实践，早在一千多年前，我国科学家在实用文档研究历法上就应用了线性插值与二次插值，但它的基本理论却是在微积分产生之后才逐渐完善的，其应用也日益增多，特别是在计算机软件中，许多库函数，如等的计算实际上归结于它的逼近函数的计算。逼近函数一般为只含有算术运算的简单函数，如多项式、有理分式（即多项式的商）。在工程实际问题当中，我们也经常会碰到诸如此类的函数值计算问题。被计算的函数有时不容易直接计算，如表达式过于复杂或者只能通过某种手段获取该函数在某些点处的函数值信息或者导数值信息等。因此，我们希望能用一个“简单函数”逼近被计算函数，然后用该简单函数的函数值近似替代被计算函数的函数值。这种方法就叫插值逼近或者插值法。逐次线性插值法优点是能够最有效地计算任何给定点的函数值，而不需要写出各步用到的插值多项式的表达式。但如果解决某个问题时需要插值多项式的表达式，那么，它的这个优点就成了它的缺点了。能不能根据插值条件构造一个插值多项式，它既有具体的表达式，又很容易用它计算任何点的函数值呢？牛顿插值法能作到这一点。二、牛顿插值法的概念牛顿插值多项式的表达式设)())(())(()(110102010xxxxxxcxxxxcxxccNnnn问题是如何根据插值条件yxNiin,i=0,1,2n来计算待定系数ccccn210,,？实用文档由)()(000xyxNfn知，)(000xycf。由)()(111xyxNfn知yxxcc10110)(因而xxxxxxxxyycfff10010101011,)()(，其中xxf10,称为函数f(x)在xx10,点的一阶商。由)()(222xyxNfn知yxxxxcxxcc2120220110))(()(因而实用文档],,[)(],[],[)(],[))(()](,[)](,[))(()](,[))(()](,[210021021021012121202021001101212020210011212020210022xxxxxxxxxxxxxxxyyxxxxxxxxxxxxyyxxxxxxxxyyyyxxxxxxxxyycffffffff其中],,[210xxxf称为函数f(x)在xxx210,,点的二阶差商。实际上，它是一阶差商的差商。一般地，如果已知一阶差商],[],,[11xxxxiiiiff，那么就可以计算二阶差商xxxxxxxxxiiiiiiiiifff111111_],[],[],,[类似于上述过程不断地推导下去，可得],,,[)(],,[],[],,,,,[)(],,,[],,,[],,,,[)(],,[],,[2100121021443210043210432143210032103213xxxxxxxxxxxxxcxxxxxxxxxxxxxxxcxxxxxxxxxxxxcnnnnfffffffff其中，],,,,[3210xxxxf],,,,,[43210xxxxxf],,,,,,[543210xxxxxxf分别称为函数f(x)在相应点处的三阶差商，四阶差商和n阶差商。实际上，实用文档ccccn210,,的计算可通过以下简易地构造函数的差商来完成。x0cxf00)(x1)(1xfcxxf110],[x2)(2xf],[21xxfcxxxf2210],,[x3)(3xf],[32xxf],1[32,xxxfcxxxxf33210],,,[x4)(4xf],[43xxf],,[432xxxf],,1[432,xxxxfcxxxxxf443210],,,,[..................按上述方式构造插值多项式的方法叫做牛顿插值法。根据插值多项式的惟一性知，其截断误差与拉格朗日插值法相同，即：)()()!1(1π1)1(xnnnnfR但也可以表示成差商形式。这是因为以xxxxn210,,为节点的多项式)(],[)()(11101xxxxNNnnnnfxx从而)(],[)()()(111101111xxxxxNxNxnnnnnnnnff实用文档于是)(xNn的截断误差可表为)(],,,[)(1110xfxnnnxxxxR顺便指出，因为牛顿插值多项式具有性质：)())(](,[)()(121101xxxxxxxxxNNnnnnfxx所以，类似于逐次线性插值法，也可以把上述和式中的第二项)())(](,[12110xxxxxxxxxnnf看成是估计)(1xNn的一种实用误差估计式。与差商概念密切联系的另一个概念是差分，它是指在等距节点上函数值的差。所谓等距节点，是指对给定的常数h（称为步长），节点)2,1,0(,0niihxxi称fxxkiiff)()(1为xi处的一阶向前差分；称fxxiiiff)()(1为xi处的一阶向后差分；称fxxihihiff)1()(22为xi处的中心差分。一阶差分的差分称为二阶差分，即fffiii21称为xi处的二阶向前差分。一般地，m阶向前和向后差分可定义如下：3,2,,111111mmmffffffimimiimimi实用文档三、牛顿插值法的实现1、【算法】步骤1：输入节点（xj，yj），精度，计值点xx，f0p，1T，1i；步骤2：对k=1，2，……，i依次计算k阶均差f[xi-k,xi-k+1,…,xi]=(f[xi-k+1,…,xi]-f[xi-k,…,xi])/(xi-xi-k)步骤3：（1）、若|f[x1,…,xi]-f[x0,…,xi-1]|，则p为最终结果Ni-1(x)，余项Ri-1=f[x0,…,xi](xx-xi-1)T。（2）、否则(xx-xi-1)*TT，p+f[x0,…,xi]*Tp，转步骤4。步骤4：若in，则i+1i，转步骤2；否则终止。实用文档2、【流程图】i+1iYESNO开始输出，xx，n及（xj，yj）f0g0，fiq0k=1，2，……，i（qk-1－gk-1）（xi－xi-k）qkk|gi-1-qi-1|qi(xi-xi-1)TR输出p，r，iSTOP1(xi-xi-1)TTp+qi*Tpk=1，2，……，i实用文档YESi+1iNOqkgkkknqi(xx-xn-1)*TR输出P，R，nSTOP2实用文档3、【程序清单】#includestdio.h#definen4//牛顿插值的次数voidmain(){floata[n+1][n+2]={0},s=0,t=1,x;inti,j;printf(请输入xi及yi的值//要求先输入xi再输入yi然后输入下一组\n);for(i=0;in+1;i++)for(j=0;j2;j++)scanf(%f,&a[i][j]);for(j=1;jn+2;j++)//计算各阶均差for(i=j;in+1;i++)a[i][j+1]=(a[i][j]-a[i-1][j])/(a[i][0]-a[i-j][0]);p