Newton 插值
Newton 插值函数 Newton 插值函数是用差商作为系数，对于01,,,n x x x …这1n +个点，其一般形式为：
00100120101011()[][,]()[,,]()()[,,,]()()()
n n n N x f x f x x x x f x x x x x x x f x x x x x x x x x −=+−+−−++−−−…………对于011,,,n x x x −…这n 个点，
100100120101012()[][,]()[,,]()()[,,,]()()()
n n n N x f x f x x x x f x x x x x x x f x x x x x x x x x −−=+−+−−++−−−…………差商的定义 若已知函数()f x 在点(0,1,2,,)i x i n =⋅⋅⋅处的函数值()i f x 。

则称：
00[]()f x f x =为函数()f x 在点0x 的0阶差商；
100110
[][]
[,]f x f x f x x x x −=
−为函数()f x 关于01,x x 的1阶差商；
120101220
[,][,]
[,,]f x x f x x f x x x x x −=
−为函数()f x 过点012,,x x x 的2阶差商；
依此类推，一般地称
121012101210
[,,,,][,,,,]
[,,,,,]k k k k k k k f x x x x f x x x x f x x x x x x x −−−−⋅⋅⋅−⋅⋅⋅⋅⋅⋅=
−为函数()f x 关于01,,,k x x x ⋅⋅⋅的
k 阶差商。

表1 差商表
i x ()i f x 1阶差商 2阶差商
3阶差商
4阶差商
0x 1x 2x 3x 4x
……
0()f x 1()f x 2()f x 3()f x 4()
f x ……
01[,]f x x
12[,]f x x 23[,]f x x 34[,]f x x
……
012[,,]f x x x 123[,,]f x x x 234[,,]
f x x x ……
0123[,,,]f x x x x 1234[,,,]
f x x x x ……
01234[,,,,]f x x x x x
……
根据Newton 插值函数编写的C 语言编程
根据Newton 插值函数并对照上面的差商表，可编写出Newton 插值法的C 语言程序如下： #include<stdio.h> #include<iostream.h> #include <stdlib.h>
double NewtonInterpolation(double *x,double *y,int n,double xx,double *pyy) {
double *f=(double *)malloc(n*sizeof(double));
int i,k;
for(i=1;i<=n-1;i++)
f[i]=y[i];
for(k=1;k<=n-1;k++)
for(i=k;i<=n-1;i++)
{f[i]=(y[i]-y[i-1])/(x[i]-x[i-k]);
if(i==n-1)
for(i=k;i<n;i++)
y[i]=f[i];
}
*pyy=y[n-1];
for(i=n-2;i>=0;i--)
*pyy=(*pyy)*(xx-x[i])+y[i];
free(f);
return 0;
}
void main()
{
int n=5;
double x[5]={1.0,2.7,3.2,4.8,5.6},y[5]={14.2,17.8,22.0,38.3,51.7},xx=3,yy; NewtonInterpolation(x,y,n,xx,&yy);
printf("%lf\n",yy);
}。