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^2$ 进行插值。如果这些点恰好在一条直线上，例如 $(0, 0), (1, 1), (2, 2)$，那么我们可以用次数为 1 的多项式 $y = x$ 画一条穿过 $(1, 1)$ 和 $(2, 2)$ 的直线，但通常情况下，三个点不会共线，因此我们需要一个次数为 2 的多项式来穿过所有点。

Lagrange 插值的 Python 代码

就我们的目的而言，了解如何计算这个多项式并不重要，因为有数学库可以替我们完成计算。最常用的算法是 Lagrange 插值，下面我们将展示如何在 Python 中实现它。

浮点数示例

我们可以使用 Lagrange 插值计算一个穿过点 $(1,4), (2,8), (3,2), (4,1)$ 的多项式 $p(x)$。

Copy
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

有限域示例

让我们使用与之前相同的多项式，但这次我们将使用有限域 $\mathbb{F}_{17}$ 而不是浮点数。

Copy
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$ 的多项式来“表示”它。次数可能会更低（例如，如果这些点共线），但向量的表示将是唯一的。

“最低次”这一属性非常重要。给定两个点，有极大量的多项式可以穿过这两个点——但最低次的多项式是唯一的。