Lagrange 插值是一种用于计算通过一组 n 个点的多项式的技术。
将向量插值为多项式
示例
通过两点的直线
考虑如果我们有两个点，可以用一条直线来插值它们。例如，给定 (1,1) 和 (2,2)，我们可以画一条穿过这两个点的直线，它将是一个 1 次多项式 y=x。
单点
现在考虑如果我们有一个点，可以通过这个点画一条 0 次多项式的直线。例如，如果点是 (3,5)，我们可以通过它画一条直线 y=5（这是一个 0 次多项式）。
三个点和一个抛物线
我们可以用至多 n-1 次多项式“通过”n 个点的模式适用于任意数量的点。例如，点 (0,0),(1,1),(2,4) 可以用 y=x² 插值。如果这些点恰好是一条直线，例如 (0,0),(1,1),(2,2)，那么我们可以用 1 次多项式 y=x 通过 (1,1) 和 (2,2) 画一条直线，但通常情况下，三个点不会共线，因此我们需要一个 2 次多项式来穿过所有点。
用于 Lagrange 插值的 Python 代码
出于我们的目的，了解如何计算这个多项式并不重要，因为有数学库可以为我们完成。最常用的算法是 Lagrange 插值，我们展示了如何在 Python 中实现它。
浮点数示例
我们可以使用 Lagrange 插值计算一个多项式 p(x)，它通过点 (1,4),(2,8),(3,2),(4,1)。
from scipy.interpolate import lagrange
x_values = [1, 2, 3, 4]
y_values = [4, 8, 2, 1]
print(lagrange(x_values, y_values))
## 3 2
## 2.5 x - 20 x + 46.5 x - 25
有限域示例
让我们使用与之前相同的多项式，但这次我们将使用有限域 F17 而不是浮点数。
import galois
import numpy as np
GF17 = galois.GF(17)
xs = GF17(np.array([1,2,3,4]))
ys = GF17(np.array([4,8,2,1]))
p = galois.lagrange_poly(xs, ys)
assert p(1) == GF17(4)
assert p(2) == GF17(8)
assert p(3) == GF17(2)
assert p(4) == GF17(1)
插值多项式的唯一性
回到我们之前的点 (1,1),(2,2) 的示例，插值它们的最低次多项式是 y=x。一般来说，
对于一组 n 个点，存在一个唯一的最低次多项式，其次数最多为 n-1，可以插值这些点。
插值这些点的最低次多项式有时称为 Lagrange 多项式。
其结果是，
如果我们使用点 (1,2,…,n) 作为 x 值，通过 Lagrange 插值将一个长度为 n 的向量转换为多项式，那么所得到的多项式是唯一的。
换句话说，给定一个一致的 x 值基来插值一个向量，存在一个唯一的多项式来插值给定的向量。换句话说，每个长度为 n 的向量都有一个唯一的多项式表示。
非正式地，每个 n 次向量都有一个唯一的 n-1 次多项式“表示”它。如果点共线等，次数可能会更少，但向量将是唯一的。
“最低次”部分非常重要。给定两个点，有极多的多项式通过这两个点——但最低次多项式是唯一的。
