多项式插值法

多项式插值法，指的是给出一些离散的数据点，通过插值法，找到这些点的曲线（使离散点变平滑）的一种方法

拉格朗日插值法

比如有N个数据点，先计算第一个点的构造一个独立的多项式，使多项式在第一个点这一项的值为1，其他项的值都是0。再基于第二个点构造第二个多项式，依然让第二个点的值为1，其余项为0，以此类推，一直到最后一个数据点位置。之后整体函数，则为每一项的值，乘以每一个多项式（因为每一个多项式都是1，乘以值，就是该项的值，其余项都是0）。

示例：假设我们有 3 个点：((1, 2)), ((2, 3)), ((4, 1))。我们可以用拉格朗日插值法来构造插值多项式 (P(x))

首先构造每个基函数：

• (L_0(x)) 是通过点 (x_0 = 1) 构造的基函数：

  $$L_0(x) = \frac{(x - 2)(x - 4)}{(1 - 2)(1 - 4)} = \frac{(x - 2)(x - 4)}{3}$$
• (L_1(x)) 是通过点 (x_1 = 2) 构造的基函数：

  $$L_1(x) = \frac{(x - 1)(x - 4)}{(2 - 1)(2 - 4)} = \frac{(x - 1)(x - 4)}{-2}$$
• (L_2(x)) 是通过点 (x_2 = 4) 构造的基函数：

  $$L_2(x) = \frac{(x - 1)(x - 2)}{(4 - 1)(4 - 2)} = \frac{(x - 1)(x - 2)}{6}$$

然后，插值多项式 (P(x)) 为：

$$P(x) = 2 \cdot L_0(x) + 3 \cdot L_1(x) + 1 \cdot L_2(x)$$

拉格朗日插值法的原理在于使用特定构造的基函数 (L_i(x)) 使得多项式 (P(x)) 能够精确通过给定的插值点。每个基函数在某个点处取值为 1，而在其他点处取值为 0，这保证了插值多项式能在每个给定点上准确取值。

所以从这个示例上，就能看出：拉格朗日插值法，得到的函数的阶数，如果N个样本点，则阶数最多是 N - 1 阶。如果数据量很大的话，速度会很慢.

拉格朗日插值法的复杂度是 $O(n^2)$