newton插值多项式

Newton 插值的算法实现Lagrange 插值公式结构紧凑，便于理论分析。

利用插值基函数也容易到插值多项式的值。

Lagrange 插值公式的缺点是，当插值节点增加，或其位置变化时，全部插值基函数均要随之变化，从而整个插值公式的结构也发生变化，这在实际计算中是非常不利的。

下面引入的Newton 插值公式可以克服这个缺点。

1、问题描述当n=1时，由点斜式直线方程知，过两点00(,())x f x 和11(,())x f x 的直线方程为1010010()()()()().f x f x N x f x x x x x −=+−−若记 100110()()[,],f x f x f x x x x −=−则可把1()N x 写成10010()()[,]().N x f x f x x x x =+−显然，1()N x 就是一次Lagrange 插值多项式1()L x 。

由于1()y N x =表示通过两点00(,())x f x 和11(,())x f x 的直线，因此一次插值亦称为线性插值。

当n=2时，进而记120121*********[,][,]()()[,],[,,]f x x f x x f x f x f x x f x x x x x x x −−==−−类似地，构造不超过二次的多项式2001001201()()[,]()[,,]()().N x f x f x x x x f x x x x x x x =+−+−−容易检验，这样的2()N x 满足插值条件200211222()(),()(),()().N x f x N x f x N x f x ===因此，2()N x 就是二次Lagrange 插值多项式2()L x 。

二次插值的几何解释是，用通过三点00(,())x f x ，11(,())x f x ，22(,())x f x 的抛物线2()y N x =来近似所考察的曲线()y f x =，因此这类插值亦称为抛物线插值。

数学与软件科学学院实验报告学期：至第学期年月日课程名称:___计算机数值方法_ 专业:信心与计算科学 08 级 6班实验编号：3 实验项目Newton插值多项式指导教师__张莉_姓名：田文晓学号：2008060632 实验成绩：一、实验目的及要求实验目的：掌握Newton插值多项式的算法，理解Newton插值多项式构造过程中基函数的继承特点，掌握差商表的计算特点。

实验要求：1. 给出Newton插值算法2. 用C语言实现算法二、实验内容1. 用下列插值节点数据，构造Newton插值多项式，并计算2. 用下列插值节点数据，构造一个三次Newton插值多项式，并计算f(1.2)的值。

三、实验步骤(该部分不够填写.请填写附页)步骤1：算法描述：输入n值，及（x_i,y_i）,i=0,1,2,…n;记f(x_i)=y_i;For i=0,1,2…n计算差商f[x0,x1,x2,…x_k]=(f[x1,x2,…x_k]-f[x0,x1,x_k-1])/(x_k-x0) 其中 f[x_i]=f(x_i);对给定的x ,由N_n(x)=f(x0)+(x-x0)f[x0,x1]+(x-x0)(x-x1)f[x0,x1.x2]+...(x-x0)(x-x 1)(x-x2)...(x-x_n-1)f[x0,x1,...x_n]计算出N_n(x)的值输出N_n(x)的值步骤2：程序代码如下：#include<stdio.h>#define MAX_N 30typedef struct tagPOINT /*the structer of point */{double x;double y;}POINT;int main(){int n,i,j;POINT points[MAX_N+1];double tmp,newton=0;double diff[MAX_N+1];double x;clrscr();printf("\nInput n value :"); /*the number of the points inserted*/scanf("%d",&n);if(n>MAX_N){printf("The input n is larger than MAX_N,please redefine the MAX_N.\n");return 1;}if(n<=0){printf("Please input a number between 1 and %d.\n",MAX_N);return 1;}printf("Now input the (x_i,y_i),i=0,...%d:\n",n);for(i=0;i<=n;i++)scanf("%lf %lf",&points[i].x,&points[i].y);printf("Now input the x value:"); /*the value of x*/scanf("%lf",&x);for(i=0;i<=n;i++) diff[i]=points[i].y;for(i=0;i<n;i++){for(j=n;j>i;j--){diff[j]=(diff[j]-diff[j-1])/(points[j].x-points[j-1-i].x); }}tmp=1;newton=diff[0];for(i=0;i<n;i++){tmp=tmp*(x-points[i].x);newton=newton+tmp*diff[i+1];}printf("newton(%f)=%f\n",x,newton);return 0;}四，实验结果与分析：当输入x=0.9时，利用牛顿二次插值得到结果如下：Input n value :2Now input the (x_i,y_i),i=0,...2:0 11 22 19Now input the x value:0.9newton(0.900000)=1.180000当输入x=0.9时，利用牛顿三次插值得到结果如下：Input n value :3Now input the (x_i,y_i),i=0,...3:-2 170 12 191 2Now input the x value:0.9newton(0.900000)=1.303750输入当x=1.2时，得到结果如下：Input n value :3Now input the (x_i,y_i),i=0,...3:-1.00 3.002.00 5.003.00 7.004.005.00Now input the x value:1.2newton(1.200000)=2.401600注:实验成绩等级分为(90-100分)优,(80-89分)良,(70-79分)中,(60-69分)及格,(59分)不及格。

数值计算方法实验报告实验报告题目：newton插值多项式实验要求用mat1ab解析Newton插值多项式的程序二、实验分析(包括数学原理，小组分析讨论后确定实验方案和实现思路)根据经过n+1个不同的差值点x1,x2,…，x(n+1),构造牛顿插值公式∕V(x)=y[x1,x2](x-Λ1)+∕[x1,x2,x3](x-Jc1)(x-x2)+∙∙∙+∕[x1,Λ2∕∙∙xn+1](x-x1)(x-x 2)∙∙∙(x-xn)三、实脸步骤(过程)(包括程序及上机的实现的结果)function[p2,z]=newton(x,y,t)n=1ength(x);chaS(1)=y(1);for i=2:nx1=x;y1=y;x1(i+1:n)=[];y1(i+1：n)=[];n1=1ength(x1);s1=0;for j=1:n1t1=1;for k=1:n1if k==j continue;e1set1=t1*(x1(j)-x1(k));ehdehds1=s1+y1(j)∕t1;end chaS(i)=s1;ehd b(1,:)=[zeros(1,n-1)chaS(1)];c1=ce11(1,n-1);for i=2:nυ1=1;for j=1:i-1u1=conv(u1,[1-x(j)]);c1{i-1}=u1;end c1{i-1}chaS(i)*c1{i-1);b(i,:)=[zeros(1,n-i)z c1{i-1}];end四、总结（包括实脸过程遇到的情况等，组长总结组员在整个过程的参与情况）实验过程中大家都积极参与，搞明白了牛顿插值多项式的程序。

有不明白的地方，也通过询问同班学霸，或是网页查询得到了解决。

第三节 牛顿插值多项式拉格朗日插值的优点是插值多项式特别容易建立，缺点是增加节点时原有多项式不能利 用，必须重新建立，即所有基函数都要重新计算，这就造成计算量的浪费；牛顿(Newton )插值多项式是代数插值的另一种表现形式，当增加节点时它具有所谓的“承袭性”，这 要用到差商的概念。

5.3.1 差商的定义与性质定义 已知函数f(x)的n+1个插值点为),(j i y x ，i y =f(i x )，i=0,1, …,n ，ji j i x x x f x f --)()(称为f(x)在点),(j i y x 的一阶差商，记为f ［ji y x ,］，即f ［j i y x ,］=j i j i x x x f x f --)()( (5.3.1)一阶差商的差商k i k j j i x x x x f x x f ---],[][称为f(x) 在点kj i x x x ,,的二阶差商，记为f ［k j i xx x ,,］，即f ［kj i x x x ,,］=ki k j j i x x x x f x x f ---],[][(5.2.2) 一般地，k-1阶差商的差商kk k x x x x x f x x x f ---021110],...,[],...,,[称为f(x)在点k x x x ,...,,10的k 阶差商，记为f ［k x x x ,...,,10］，即f ［k x x x ,...,,10］=kk k x x x x x f x x x f ---021110],...,[],...,,[ (5.3.3)差商具有以下性质：性质1 n 阶差商可以表示成n+1个函数值)(),...,(),(10n x f x f x f 的线 性组合，即f ［k x x x ,...,,10］=∑=+-----ni n i i i i i i i x x x x x x x x x f 0110))...()()...(()( 事实上，由式(1)当n=1时，011100101010)()()()(],[x x x f x x x f x x x f x f x x f -+-=--=当n=2时，))(()())(()())(()())(()()11()())(()())()((1))()((1],[],[],[],[],,[12022210112010012022210120120100122211020111002002211010212110210x x x x x f x x x x x f x x x x x f x x x x x f x x x x x x x f x x x x x f x x x f x x x f x x x x x f x x x f x x x x x x f x x x x f x x x x f x x f x x x f --+--+--=--+----+--=-+--+-+--=-+-=--=一般地有f ［k x x x ,...,,10］=∑=+-----ni n i i i i i i i x x x x x x x x x f 0110))...()()...(()( 性质2(对称性) 差商与节点的顺序无关，如],,[],,[],,[],[],[1202012100110x x x f x x x f x x x f x x f x x f === 这一点可以从性质1看出。