有限域内的拉格朗日插值法python源代码

在Python中，我们可以使用numpy库来实现有限域内的拉格朗日插值。下面是一个简单的示例，假设我们有一个列表`points`，包含每个点的坐标和对应的y值：

import numpy as np

def lagrange_interpolation(points):
    # 点的坐标和y值
    x, y = zip(*points)
    
    # 计算阶乘模n，因为拉格朗日插值涉及除法运算，这里是取模操作
    def factorial_modulo(n, mod):
        fact = 1
        for i in range(1, n+1):
            fact = (fact * i) % mod
        return fact
    
    # 计算拉格朗日基本多项式
    def lpolynomial(x_value, points):
        prod = 1
        for point, other_x in zip(points, x):
            if point[0] != x_value:
                prod *= (x_value - other_x) % mod
        return prod
    
    # 根据最后一个点作为基准，计算插值多项式
    mod = points[-1][0]
    lpolynomial_func = lambda x: sum(y_val * lpolynomial(x, points[:index]) for index, (x_val, y_val) in enumerate(zip(x, y)))
    
    return lpolynomial_func, mod

# 使用示例
points = [(413, 25439), (432, 14847), (451, 24780), (470, 5910), (489, 12734)]
interpolator, mod = lagrange_interpolation(points)

这个函数返回两个值：一个是插值函数`interpolator`，另一个是模数`mod`。你可以使用`interpolator(x)`来获取在给定`x`值下的插值结果。