拉格朗日插值法【python，算法】

拉格朗日插值是一种在数值分析中用来构建通过一系列已知数据点的多项式插值的方法。这种方法以 18 世纪的法国数学家约瑟夫·拉格朗日命名。当给定一组离散的数据点(?_0,?_0),(?_1,?_1),...,(?_?,?_?)，其中每个?_?是唯一的，拉格朗日插值法能够找到一个最高次幂为?的多项式?(?)，使得对于所有?=0,1,...,?，都有?(?_?)=?_?。

拉格朗日插值公式为：

$$L_x=\sum _{i=0}^n{y}_i{P}_i$$

其中$P_i$称为基多项式，其表达式如下：

$$P_i=\prod _{j=0,j!=i}^n\frac{x-x_j}{x_i-x_j}$$

下面是 Python 实现的拉格朗日插值算法：

def lagrange_interpolation(x_points, y_points, target_x):
    if len(x_points) != len(y_points) or len(x_points) < 2:
        raise ValueError("Input data must contain at least two points.")
    n = len(x_points)
    target_y = 0
    for i in range(n):
        p_i = 1
        for j in range(n):
            if i != j:
                p_i *= (target_x - x_points[j]) / (x_points[i] - x_points[j])
        target_y += p_i * y_points[i]
    return target_y


# 测试
x_points = [1, 2, 3, 4]
y_points = [2, 4, 6, 8]
print(lagrange_interpolation(x_points, y_points, 5))