Newton插值法

Newton插值法的基函数非常的容易记:

Nn(x) = A0 + A1(x – x0) + A2(x – x0)(x – x1) + … + An(x – x0)…(x – xn-1)

系数Ai也非常容易求,是一个递推的过程:

A0 = [x0]f (x = x0处的零阶差商)
A1 = [x0,x1]f (x = x0,x1处的一阶差商)
A2 = [x0,x1,x2]f (x = x0,x1,x2处的二阶差商)
…………………………
An = [x0,x1,x2,…,xn]f (x =x0,x1,x2,…,xn处的n阶差商)

其中差商的递推关系是:

[xi]f = f(xi)

[x0,x1,x2,…,xk]f = ([x1,x2,…,xk]f – [x0,x1,x2,…,xk-1]f)/(xk – x0)

所以,整个过程就很轻易咯。。

另:当每个插值点是等距的时候,过程将大大简化。。。

放代码:

//一共有n个点,数组x,y存放函数表格,aim为插值点
//d[i]存放第i阶差商(i = 0, 1, 2,..., n-1)
double Newton(int n, double* x, double* y, double aim){
double tnew, *d = new double[n];
for(int i = 0; i < n; i++)
d[i] = *(y + i);
for(int i = 1; i < n; i++)
for(int j = n - 1; j >= i; j--)
d[j] = (d[j] - d[j-1])/(*(x + j) - *(x + j - i));
tnew = d[n - 1];
for(int i = n - 2; i >= 0; i--)
tnew = d[i] + tnew * (aim - *(x+i));
return tnew;
}