newton插值报告.doc

Newton插值多项式
实验的目的及意义：
为了弥补Lagrange插值的不同，引入插商的概念。对给定(xi,yi)，i=0,1,…,n,构造Newton插值多项式，使得。
数学公式：

算法描述:
Step1:输入m,(xi,yi),i=0,1,…,n；
Step2:fori=j-1;i<N计算f[x,x0,x1,...,xn]的大小。
Step3:forj=2,3,…N计算
。
Step4:输出。

程序原代码如下：
#include"stdio.h"
#defineN3
voidmain()
{
doublea[N][N+1],b[N];
doublem,n,q;
inti,j;
printf("pleaseinputthemvalue:");//m为未知数的大小
scanf("%lf",&m);
printf("pleaseinputthexvalue:");
for(i=0;i<N;i++)
scanf("%lf",&a[i][0]);//输入x的大小
printf("pleaseinputtheyvalue:");
for(i=0;i<N;i++)
scanf("%lf",&a[i][1]);//输入f(X)的大小
for(j=2;j<=N;j++)
{
for(i=j-1;i<N;i++)
{
a[i][j]=(a[i][j-1]-a[i-1][j-1])/(a[i][0]-a[i-j+1][0]);
//计算f[x,x0,x1,...,xn]的大小
}
}
for(i=0;i<N;i++)
b[i]=a[i][i+1];
q=b[0];//f(x0)的大小
for(i=0,n=1.0;i<N-1;i++)
{
n*=(m-a[i][0]);//连乘运算
q+=b[i+1]*n;//连加运算
}
printf("%f\n",q);
}
计算实例：
给定，，，构造Lagrange函数，计算
程序输入输出结果如下：
pleaseinputthemvalue:11.5
pleaseinputthexvalue:111213
pleaseinputthexvalue:0.1908090.2079120.224951
0.199369
Pressanykeytocontinue
对计算结果进行评价分析：
计算结果已经十分准确了，其误差可以由公式

计算得出。它的误差与Lagrange差值多项式的误差相同。它们满足相同的插值条件。Newton差值多项式具有递推性，有如下的递推关系式。
有了这个递推关系式，当我们用n个节点x,x0,x1,...,xn求出n次多项式后，如果再增加一个节点,只需要增加上式右端的第二项，就可以求出n+1次多项式，这样可以提高计算效率。
参考文献：
秦新强，数值逼近，西安：西安理工大学，2010