"""Compute the Newton's Interpolation Polynomial"""
def newtonPolValue(n, nodesX, coeffs, t):
'''
Value of Newton interpolation polynomial in point t
n Number of nodes (degree of polynomial = n-1)
nodesX Nodes of interpolation: x0, x1, ..., xn
coeffs Coefficients of Newton polynomial
t Point of interpolation
'''
s = coeffs[0]
p = 1.
for i in range(1, n+1):
p *= (t - nodesX[i-1]);
s += coeffs[i] * p;
return s
def computeNewtonPol(nodes):
'''
Compute the coefficients of Newton
interpolation polynomial
n Number of nodes - 1 == degree of polynomial
nodes Nodes of interpolation:
[(x0, y0), ..., (xn, yn)]
Return:
coeffs Coefficients of Newton polynomial
'''
n = len(nodes) - 1 # Degree of polynomial
coeffs = [0.0]*(n + 1)
nodesX = [t[0] for t in nodes]
coeffs[0] = nodes[0][1]
for i in range(1, n + 1):
p = 1.
for j in range(0, i):
p *= (nodes[i][0] - nodes[j][0])
coeffs[i] = (
(nodes[i][1] -
newtonPolValue(i-1, nodesX, coeffs, nodes[i][0])) / p
)
return coeffs