牛顿的插值多项​​式[python]

Question

我想使用牛顿的插值多项​​式来计算下面数组的有限分割差异以确定x = 8时的y。阵列是

x = 0 1 2 5.5 11 13 16 18 

y= 0.5 3.134 5.9 9.9 10.2 9.35 7.2 6.2 

我有的伪代码是在http://imgur.com/gallery/Lm2KXxA/new。是否有任何可用的伪代码，算法或库可以用来告诉我答案？

另外我相信这是如何在matlab http://imgur.com/gallery/L9wJaEH/new程序。我只是无法弄清楚如何在Python中做到这一点。

Answer 1

这是Python代码。函数coef计算有限分割差分系数，函数Eval计算给定节点处的插值。

import numpy as np 
import matplotlib.pyplot as plt 

def coef(x, y): 
    '''x : array of data points 
     y : array of f(x) ''' 
    x.astype(float) 
    y.astype(float) 
    n = len(x) 
    a = [] 
    for i in range(n): 
     a.append(y[i]) 

    for j in range(1, n): 

     for i in range(n-1, j-1, -1): 
      a[i] = float(a[i]-a[i-1])/float(x[i]-x[i-j]) 

    return np.array(a) # return an array of coefficient 

def Eval(a, x, r): 

    ''' a : array returned by function coef() 
     x : array of data points 
     r : the node to interpolate at ''' 

    x.astype(float) 
    n = len(a) - 1 
    temp = a[n] 
    for i in range(n - 1, -1, -1): 
     temp = temp * (r - x[i]) + a[i] 
    return temp # return the y_value interpolation 

Answer 2

@Ledruid提出的解决方案是最优的。它不需要2维数组。分化差异树就像2D数组。更原始的方式（从@可以获得Leudruid算法）正在考虑一个“矩阵$ F_ {IJ} $对应的树的节点。这样的算法将是。

import numpy as np 
from numpy import * 

def coeficiente(x,y) : 
    ''' x: absisas x_i 
     y : ordenadas f(x_i)''' 

    x.astype(float) 
    y.astype(float) 
    n = len(x) 
    F = zeros((n,n), dtype=float) 
    b = zeros(n) 
    for i in range(0,n): 
     F[i,0]=y[i] 



    for j in range(1, n): 
     for i in range(j,n): 
      F[i,j] = float(F[i,j-1]-F[i-1,j-1])/float(x[i]-x[i-j]) 


    for i in range(0,n): 
     b[i] = F[i,i] 

    return np.array(b) # return an array of coefficient 

def Eval(a, x, r): 

    ''' a : retorno de la funcion coeficiente() 
     x : abcisas x_i 
     r : abcisa a interpolar 
    ''' 

    x.astype(float) 
    n = len(a) - 1 
    temp = a[n] 
    for i in range(n - 1, -1, -1): 
     temp = temp * (r - x[i]) + a[i] 
    return temp # return the y_value interpolation