Lagrange插值与Newton插值算法编程

专业：电路与系统 姓名：邹鑫 学号：2012021716

1. 程序流程

用C++编程实现函数的插值计算，由用户依次输入节点个数（设为20个节点以内）以及各个节点对应的x值和y值来描述已知函数的插值，最后输入所求的x值，程序就分别用公式计算出所求插值x对应的函数y值。

2. Lagrange插值

2.1. 源程序：

#include

#include

typedef struct data

{

float x;

float y;

1

}

Data;

Data d[20]; //创建一个元素为20的d数组

float lagrange(float x, int count)

{

float y=0.0; //先清零y

for(int k=0;k{

float p=1.0;

for(int j=0;j{

if(k==j)

continue;

p=p*(x-d[j].x)/(d[k].x-d[j].x);

2

}

y=y+p*d[k].y; //y求和

}

return y; //返回y的值

}

//===主函void main()

{

float x,y;

int count;

cout<<\"请输入x[i],y[i]的组数，不得超过20组:\";//要求输入数据组数

cin>>count; //获得总共有几组的组数

for(int i=0;i{

3

数

===================================================

cout<<\"请输入第\"<cin>>d[i].x;

cout<<\"请输入第\"<cin>>d[i].y;

}

cout<<\"请输入x的值:\"; //获得插入变量x的值

cin>>x;

cout<<\"拉格朗日插值计算结果为:\"<y=lagrange(x,count);

cout<<\"x=\"<}

2.2. 运行结果：

输入函数f(x)=x2的5个节点值，求x=3.73时的拉格郎日插值：

4

3. Newton插值

3.1. 源程序：

#include

#include

typedef struct data

{

float x;

float y;

5

}Data;

Data d[20]; //创建一个元素为20的d数组

float f(int s,int t) //牛顿插值法，用以返回插商

{

if(t==s+1)

return (d[t].y-d[s].y)/(d[t].x-d[s].x);

else

return (f(s+1,t)-f(s,t-1))/(d[t].x-d[s].x);

}

float Newton(float x,int count)

{

int n;

cout<<\"请输入n值(即n次插值):\"; //获得插值次数

cin>>n;

6

float t=1.0;

float y=d[0].y;

float yt=0.0;

for(int j=1;j<=n;j++)

{

t=(x-d[j-1].x)*t;

yt=f(0,j)*t;

y=y+yt; //y求和

}

return y; //返回y的值

}

//========================================================

void main()

{

7

float x,y;

int count;

cout<<\"请输入x[i],y[i]的组数，不得超过20组:\";//要求用户输入数据组数

cin>>count;

for(int i=0;i{

cout<<\"请输入第\"<cin>>d[i].x;

cout<<\"请输入第\"<cin>>d[i].y;

}

cout<<\"请输入x的值:\"; //获得插入变量x的值

cin>>x;

y=Newton(x,count);

8

cout<<\"Newton插值计算结果为:\"<cout<<\"x=\"<3.2. 运行结果：

输入函数f(x)=x2的5个节点值，求x=3.73时的牛顿3次插值：

9