/**
牛顿插值法
牛顿递推公式:Nk(x) = Nk-1(x) + tk(x) / f [x0,x1,..,xk]
基函数递推公式: ti (x) = (x - x i ) * ti-1 (x)
属性:插值计算法
《数值计算方法与算法》第二版 - 科学出版社 P25
代码维护:2007.04.18 pengkuny
**/
#include <iostream>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
float NewtonInterpolate(float px[], float py[], int n, float x)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{//px,py;插值点(Xi,Yi) n:插值点个数 x:待计算的点
float *g = new float[n+1];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
//计算差商表个g[k],k=0,1,
,n
for (int i=0; i<n+1; i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
g[i] = py[i];
}
for (int k=1; k<n+1; k++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for (int i=n; i>=k; i--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
g[i] = (g[i] - g[i-1]) / (px[i] - px[i-k]);//g[i]用来暂时存放f[X(i-k), X(i)]
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
float t = 1;//基函数
float newton = py[0];
for (int i=1; i<n; i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
t = (x - px[i-1]) * t;//基函数的递推式
newton = newton + t * g[i];
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
delete g;
return newton;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
float x;//插值
float px[10];//已知(x0,y0),(x1,y1)
float py[10];
int n;//输入已知插值组数
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
cout<<"输入插值组数:"<<endl;
cin>>n;
cout<<"输入"<<n<<"组已知插值数(X,Y)"<<endl;
for(int i=0; i<n; i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
cin>>px[i]>>py[i];
}
cout<<"输入插值:"<<endl;
cin>>x;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
cout<<"牛顿插值结果:"<<NewtonInterpolate(px, py, n, x)<<endl;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
system("pause");
return 0;
}
posted on 2007-04-20 10:55
哈哈 阅读(3446)
评论(5) 编辑 收藏 引用