WayToFFT Part 0
从拉格朗日插值法到 FFT. Part-0.
系数表示法和点值表示法
系数表示法
多项式可定义为形如
$$ \sum_{i=0}^{n} a_{i}x^{i} $$的有限和式，记作
$$ f(x) = \sum_{i=0}^{n} a_{i}x^{i} $$
其中 $a_i$ 称为 $i$ 次项的系数。
这种表示方法称为系数表示法。
点值表示法
将 $x = t_i$ 代入，得到序列 $(t_i, y_i)$。当此序列满足 $0 \le i \le n$ 且 $t_i$ 互不相等时，可以唯一确定一个次数不超过 $n$ 的多项式，这种描述方法称为点值表示法。
在给定 $n$ 个点值 $(t_0, y_0), (t_1, y_1), \dots, (t_{n-1}, y_{n-1})$ 且 $t_i$ 互不相等时，唯一确定的多项式次数至多为 $n-1$。
证明：考虑 $n$ 阶 Vandermonde 方阵
$$ V = \begin{bmatrix} 1 & t_0 & t_0^2 & \cdots & t_0^{n-1} \\\\ 1 & t_1 & t_1^2 & \cdots & t_1^{n-1} \\\\ 1 & t_2 & t_2^2 & \cdots & t_2^{n-1} \\\\ \vdots & \vdots & \vdots & \ddots & \vdots \\\\ 1 & t_{n-1} & t_{n-1}^2 & \cdots & t_{n-1}^{n-1} \end{bmatrix}, \quad \mathbf{a} = \begin{bmatrix} a_0 \\\\ a_1 \\\\ a_2 \\\\ \vdots \\\\ a_{n-1} \end{bmatrix} $$由于 $t_i$ 互不相同，$\det V \ne 0$，故方程有唯一解，从而唯一确定系数向量 $\mathbf{a}$。
- 系数表示 $\to$ 点值表示：求值（evaluation)
- 点值表示 $\to$ 系数表示：插值（interpolation)
拉格朗日插值
定义
对于某个次数不超过 $n$ 的多项式 $f$，已知点值表示 $(t_i, y_i)$，其拉格朗日插值公式为：
$$ \mathscr{L}(x) := \sum_{i=0}^{n} y_{i} \,\ell_{i}(x) $$其中 $\ell_i(x)$ 称为拉格朗日基本多项式（插值基函数）：
$$ \ell_{i}(x) := \prod_{\substack{m=0 \\ m \ne i}}^{n} \frac{x - t_{m}}{t_{i} - t_{m}} $$存在性
由点值表示知，目标多项式一定存在。对于 $\ell_i(x)$，在 $x = t_s$ 时：
$$ \ell_{i}(t_s) = \begin{cases} 1, & s = i, \\ 0, & s \ne i. \end{cases} $$于是：
$$ \mathscr{L}(t_s) = \sum_{i=0}^{n} y_{i} \,\ell_{i}(t_s) = y_s $$唯一性
次数不超过 $n$ 的拉格朗日多项式 $\mathscr{L}(x)$ 至多只有一个。
设 $P_1$ 与 $P_2$ 均为满足插值条件的多项式，作差：
则 $\Delta(x)$ 在 $n+1$ 个互异点 $t_0,\dots,t_n$ 上为零，故：
$$ \Delta(x) = k \prod_{i=0}^{n} (x - t_i) $$若 $k = 0$，则 $P_1 \equiv P_2$；若 $k \ne 0$，则 $\deg \Delta > n$，与已知矛盾。
对应到 Vandermonde 矩阵：
- $\operatorname{rank} V = n+1$ 时有唯一解
- $\operatorname{rank} V < n+1$ 时有无穷多解
向量空间观点
设 $\mathbb{K}_{n}[X]$ 表示系数域为 $\mathbb{K}$、次数不超过 $n$ 的多项式空间。
由 ${\ell_0, \ell_1, \dots, \ell_n}$ 构成的集合为该空间的一组基，因为：
- 它们线性无关
- 元素个数为 $n+1$（等于空间维数）
核心思想总结
利用点值的可加性：每次构造一个多项式在某个插值点处取所需值、在其他插值点处取 0，然后将这些多项式相加。
插值公式可写为：
$$ f(x) = \sum_{i=0}^{n} y_{i} \prod_{\substack{m=0 \\ m \ne i}}^{n} \frac{x - t_{m}}{t_{i} - t_{m}} $$为了得到 $f$ 的系数，需要 $O(n^2)$ 时间计算
$$ F(x) = \prod_{i=0}^{n} (x - t_i) $$然后可通过解线性方程组（Vandermonde 系数矩阵）得到多项式系数。
范德蒙矩阵与拉格朗日逆
范德蒙行列式
定义 $n \times n$ 的 Vandermonde 矩阵：
$$ V = \begin{bmatrix} 1 & a_1 & a_1^2 & \cdots & a_1^{n-1} \\\\ 1 & a_2 & a_2^2 & \cdots & a_2^{n-1} \\\\ \vdots & \vdots & \vdots & \ddots & \vdots \\\\ 1 & a_n & a_n^2 & \cdots & a_n^{n-1} \end{bmatrix} $$其行列式为：
$$ \det V = \prod_{1 \le j < i \le n} (a_i - a_j) $$只要 $a_i$ 两两不同，该行列式非零，矩阵可逆。
克拉默法则
若 $A\mathbf{x} = \mathbf{b}$ 且 $\det A \ne 0$，则唯一解为：
$$ x_j = \frac{\det A_j}{\det A}, \quad j = 1, \dots, n $$其中 $A_j$ 为将 $A$ 的第 $j$ 列替换为列向量 $\mathbf{b}$ 后得到的矩阵。
多项式与对称多项式
设多项式
$$ f(x) = \sum_{i=0}^{n} a_i x^i $$若为首一多项式（最高次项系数 $a_n = 1$），根据代数基本定理：
$$ f(x) = \prod_{i=1}^{n} (x - r_i) $$韦达定理给出系数与根的关系：
$$ a_{n-k} = (-1)^k \,\sigma_k(r_1, r_2, \dots, r_n), \quad k=1,\dots,n $$其中 $\sigma_k$ 为第 $k$ 阶初等对称多项式。
拉格朗日逆矩阵形式
设 $V$ 为由插值点 $t_0,\dots,t_n$ 构成的 $(n+1) \times (n+1)$ Vandermonde 矩阵：
$$ V_{ij} = t_i^{\,j}, \quad 0 \le i,j \le n $$插值过程等价于解：
$$ V \mathbf{a} = \mathbf{y} $$其中 $\mathbf{a} = (a_0, \dots, a_n)^\mathrm{T}$，$\mathbf{y} = (y_0, \dots, y_n)^\mathrm{T}$。
由克拉默法则：
$$ a_j = \frac{\det V_j}{\det V} $$展开可得：
$$ f(x) = \sum_{j=0}^{n} \frac{\det V_j}{\det V} \, x^j $$进一步化简后，$V^{-1}$ 的第 $(j,i)$ 元素正是 $\ell_i$ 展开式中 $x^j$ 的系数，从而：
$$ \ell_i(x) = \frac{\prod_{\substack{m=0 \\ m \ne i}}^{n} (x - t_m)}{\prod_{\substack{m=0 \\ m \ne i}}^{n} (t_i - t_m)} $$矩阵形式：
$$ \mathbf{a} = V^{-1} \mathbf{y} $$即给出了 拉格朗日逆矩阵 的具体含义。