Python中的拉格朗日插值

Question

我想用拉格朗日方法来插值一个多项式，但这段代码不管用：

def interpolate(x_values, y_values):
    def _basis(j):
        p = [(x - x_values[m])/(x_values[j] - x_values[m]) for m in xrange(k + 1) if m != j]
        return reduce(operator.mul, p)

    assert len(x_values) != 0 and (len(x_values) == len(y_values)), 'x and y cannot be empty and must have the same length'

    k = len(x_values)
    return sum(_basis(j) for j in xrange(k))

我参考了维基百科上的内容，但运行时在第3行遇到了索引错误！

谢谢

Answer 1

我虽然晚了快十年才来了解这个，但我在寻找简单的拉格朗日插值实现时找到了这个。@smichr的回答很好，不过Python的代码有点过时了，我还想要一些能和np.ndarrays很好配合的东西，这样我就可以方便地绘图了。也许其他人会觉得这个有用：

import numpy as np
import matplotlib.pyplot as plt


class LagrangePoly:

    def __init__(self, X, Y):
        self.n = len(X)
        self.X = np.array(X)
        self.Y = np.array(Y)

    def basis(self, x, j):
        b = [(x - self.X[m]) / (self.X[j] - self.X[m])
             for m in range(self.n) if m != j]
        return np.prod(b, axis=0) * self.Y[j]

    def interpolate(self, x):
        b = [self.basis(x, j) for j in range(self.n)]
        return np.sum(b, axis=0)


X  = [-9, -4, -1, 7]
Y  = [5, 2, -2, 9]

plt.scatter(X, Y, c='k')

lp = LagrangePoly(X, Y)

xx = np.arange(-100, 100) / 10

plt.plot(xx, lp.basis(xx, 0))
plt.plot(xx, lp.basis(xx, 1))
plt.plot(xx, lp.basis(xx, 2))
plt.plot(xx, lp.basis(xx, 3))
plt.plot(xx, lp.interpolate(xx), linestyle=':')
plt.show()

Answer 2

试试看

def interpolate(x, x_values, y_values):
    def _basis(j):
        p = [(x - x_values[m])/(x_values[j] - x_values[m]) for m in xrange(k) if m != j]
        return reduce(operator.mul, p)
    assert len(x_values) != 0 and (len(x_values) == len(y_values)), 'x and y cannot be empty and must have the same length'
    k = len(x_values)
    return sum(_basis(j)*y_values[j] for j in xrange(k))

你可以这样确认：

>>> interpolate(1,[1,2,4],[1,0,2])
1.0
>>> interpolate(2,[1,2,4],[1,0,2])
0.0
>>> interpolate(4,[1,2,4],[1,0,2])
2.0
>>> interpolate(3,[1,2,4],[1,0,2])
0.33333333333333331

所以结果是根据通过给定点的多项式计算出的插值。在这个例子中，这三个点定义了一个抛物线，前面三个测试显示，对于给定的x值，返回的y值是正确的。

Answer 3

检查一下索引，维基百科上说“k+1个数据点”，但是你把 k = len(x_values) 设置成了这个，实际上应该是 k = len(x_values) - 1，如果你严格按照公式来做的话。