(x_i,y_i)的牛顿插值多项式.cpp

一个在C++做的(x_i,y_i)的牛顿插值多项式的程序,也可以在C中运行.

///////////////////////////////////////////////
//     (x_i,y_i)的牛顿插值多项式             //
///////////////////////////////////////////////
#include "stdio.h"
#define MAX_N 20 //	定义(x_i,y_i)的最大维 (x_i,y_i)的牛顿插值多项式数
typedef struct tagPOINT//点的结构
{
	double x;
	double y;
}POINT;
int main()
{
	int n;
	int i,j;
	POINT points[MAX_N+1];double diff[MAX_N+1];
	double x, tmp,newton=0;
	printf("\nInput n value:");// 输入被插值点的数目
	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;
	}
	  //输入配插值的点(x_i,y_j)
	printf("Now input the (x_i,y_j),i=0,...,%d:\n",n);
	for(i=0;i<=n;i++)
		scanf("%lf%lf",&points[i].x,&points[i].y);
	printf("INput the x value");//输入计算牛顿插值多项式的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);
		}//计算f(x_0,...,x_n)的差商
	}
	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)=%lf\n",x,newton);
	return 0;

}