实验目的：掌握Newton均差插值算法的基本原理，理解均差的概念，掌握均差表的计算方法。学习用计算机语言编写程序实现算法。

[参考程序]

#include "stdio.h"

#define N 10                 //设置表示均差表的二维数组的最大值为10

//定义插值节点及所求点数据，根据题目不同而修改

double x[]={0.4,0.55,0.65,0.80,0.90,1.05};

double y[]={0.41075,0.57815,0.69675,0.88811,1.02652,1.25382};

// 数据读入及参数设置函数。

void ReadPara(double *xx,int *n,double f[N][N])

{

       printf("Please input xx:");

       scanf("%lf",xx);                   //设置例题数据xx=0.596;

       printf("Please input n:");

       scanf("%d",n);                            //设置例题数据n=4;

       //初始化均差表

       int loopi;

       for(loopi=0;loopi<=*n;loopi++)

       {

              //零阶均差作为均差表二维数组的第0列

              f[loopi][0]=y[loopi];

       }

}

//计算单个均差的函数

double fx(int i,int j,double f[N][N])

{

       if(j==0)

       {

              return f[i][j];

       }

       else

       {

             

              //这种表示方法需要注意两个x的下标

              return (fx(i,j-1,f)-fx(i-1,j-1,f))/(x[i]-x[i-j]);

       }

}

//由初始值计算整个均差表

void CaculateNewton(int n,double f[N][N])

{

       int loopi,loopj;

       for(loopi=1;loopi<=n;loopi++)

       {

          for(loopj=1;loopj<=loopi;loopj++)

          {

                     //调用计算均差的函数计算均差表里的每个均差值

                     f[loopi][loopj]=fx(loopi,loopj,f);

          }

       }

}

 

//用秦九韶算法计算插值多项式结果

double S(int start,int end,double xx,double f[N][N])

{

       if(start==end)

       {

              return f[end][end];

       }

       else

       {

             

              //递归计算

              return (S(start+1,end,xx,f)*(xx-x[start])+f[start][start]);

       }

}

 

//程序主函数

void main()

{

       double f[N][N];            //用来记录均差表中各个数据

       int n;                            //插值多项式次数

       double xx;                   //需要计算的插值函数值

       double result;              //保存最终插值计算结果

 

       //输入算法所需数据及参数

       ReadPara(&xx,&n,f);

       //循环计算均差表中的其他所有数据

       CaculateNewton(n,f);

       //通过秦九韶法计算Newton均差插值多项式值

       result=S(0,n,xx,f);

       //输出插值结果

       printf("Result is: %f",result);

}