python-3.x - 高效的插值实现

Question

我正在编写一个插值方法，而不使用直接执行它的库函数。该函数的签名是：

def interpolate(self, f: callable, a: float, b: float, n: int) -> callable:
        """
        Parameters
        ----------
        f : callable. it is the given function
        a : float
            beginning of the interpolation range.
        b : float
            end of the interpolation range.
        n : int
            maximal number of points to use.

        Returns
        -------
        The interpolating function.
        """

现在我的实现是直截了当的“拉格朗日插值”，如下所述：https ://www.codesansar.com/numerical-methods/python-program-lagrange-interpolation-method.htm

但是，这种实现是 O(n^2)，我正在寻找一种在 O(n) 中运行的更有效的解决方案。

（也许贝塞尔曲线可以在这里提供帮助？）

Answer 1

我也在做同样的事情，我想到了 NumPy elementwise 计算，这是我的代码行，可以解决你的问题：

对于 xi, yi in zip(x,y): yp += yi*np.prod((xp-x[x!=xi])/(xi-x[x!=xi]))