newton.cpp

经典的牛顿插值算法Demo

#include "newton.h"
#include "assert.h"
#include "math.h"
#ifndef NULL
#define NULL 0
#endif

CNewton::CNewton(int MaxN)
{
	max=MaxN+1;
	n=0;
	x=new double[max];
	f[0]=new double[max];
	f[1]=new double[max];
	assert(x!=NULL);
	assert(f[0]!=NULL);
	assert(f[1]!=NULL);
}

CNewton::~CNewton()
{
	if(x)
		delete[]x;
	if(f[0])
		delete[]f[0];
	if(f[1])
		delete[]f[1];
}

void CNewton::InsertPoint(double X,double Y)
{
	int i;
	double fw;
	assert(n<max);
	//重复点检查
	for(i=0;i<n;++i)
		if(fabs(X-x[i])<1e-5)
			return;
		//如果确保不会有重复点可删去上面语句
		x[n]=X;
		fw=Y;
		for(i=1;i<=n;++i)
		{
			double tmp=fw;
			fw=(fw-f[1][i-1])/(x[n]-x[n-i]);
			f[1][i-1]=tmp;
		}
		f[0][n]=f[1][n]=fw;
		n++;
}
double CNewton::GetValue(double X)
{
	if(n==0)
		return 0.0;
	double s=f[0][n-1];
	for(int i=n-2;i>=0;--i)
	{
		s=s*(X-x[i])+f[0][i];
	}
	return s;
}