This is one of my favorites. It takes a sequence of (x, y) coordinates and builds a serial of polynomials for which one can then use to interpolate or extrapolate values.
def lagrange_build_basis_poly(x, y):
"""Build the basis polynomials for lagrange interpolation.
The points (x_i, y_i) represent the known values. The output
polynomials will calculate a best fit interpolation between
these points when evaluated.
"""
polys = []
k = len(x)
for j in range(k):
num_terms = []
den_terms = []
for m in range(k):
if m == j:
continue
num_terms.append((None, x[m]))
den_terms.append(x[j] - x[m])
# coefficient, numerator, denomenator_result
polys.append((y[j], num_terms, np.prod(den_terms)))
# sum polynomials for L(x)
return polys
def lagrange_eval_basis_poly(polys, arbitrary_x):
"""Evaluate the basis polynomials for an arbitrary x.
"""
y_at_x = 0.0
for poly in polys:
num_result = [arbitrary_x - num_term[1] for num_term in poly[1]]
num_result = np.prod(num_result)
den_result = poly[2]
y_at_x += num_result / den_result * poly[0]
return y_at_x