前言
拉格朗日插值其实在初中搞竞赛的时候就学过了，鉴于当时学识浅薄，其实并没有理解其底层的原理。在熬过两年高中、成为苦逼高三生之后，终于有能力、想法和不太充裕的时间来填以前的坑了。
除了高中数学课内的知识外（也不算很课内吧😶🌫️），此篇还杂糅了相当部分的信息学竞赛内容，建议选择性阅读。
高斯消元
高中阶段高斯消元最典型的使用场景大多应用于求解多元一次方程组、待定系数法求函数解析式、解析几何求交点与位置关系等。后文将用一道简单的例子来展示高斯消元的用法。
函数解析式求解
已知二次函数 $f(x)$ 过点 $(1, 2)$、$(2, 9)$、$(3, 22)$，求该函数的解析式。
一般做法是设：
$$f(x) = ax^2 + bx + c$$
将三个点带入方程：
$$\begin{cases} a + b + c = 2 \cr 4a + 2b + c= 9 \cr 9a + 3b + c = 22 \end{cases}$$
通过「加减消元法」求解该三元一次方程组即可。高斯消元则是把方程组改写为「增广矩阵」的形式：
$$\left[ \begin{array}{cccc|c} a_{11} & a_{12} & \cdots & a_{1n} & b_1 \cr a_{21} & a_{22} & \cdots & a_{2n} & b_2\cr \vdots & \vdots & \ddots & \vdots & \vdots \cr a_{m1} & a_{m2} & \cdots & a_{mn} & b_m \end{array} \right]$$
并将该矩阵变成类似如下的「行阶梯形」：
$$\left[ \begin{array}{cccc|c} c_{11} & c_{12} & \cdots & c_{1n} & d_1 \cr 0 & c_{22} & \cdots & c_{2n} & d_2\cr \vdots & \vdots & \ddots & \vdots & \vdots \cr 0 & 0 & \cdots & c_{mn} & d_m \end{array} \right]$$
即对于第 $i$ 行的主元在第 $i$ 列，且主元下面的数都变为 0. 因此上述方程就可以被改写为：
$$\left[ \begin{array}{ccc|c} 1 & 1 & 1 & 2\cr 4 & 2 & 1 & 9\cr 9 & 3 & 1 & 22 \end{array} \right]$$
为了达到目标状态进行如下操作：
$$\xrightarrow{R_2 \leftarrow R_2 - 4R_1} \left[ \begin{array}{ccc|c} 1 & 1 & 1 & 2\cr 0 & -2 & -3 & 1\cr 9 & 3 & 1 & 22 \end{array} \right]$$
$$\xrightarrow{R_3 \leftarrow R_3 - 9R_1} \left[ \begin{array}{ccc|c} 1 & 1 & 1 & 2\cr 0 & -2 & -3 & 1\cr 0 & -6 & -8 & 4 \end{array} \right]$$
$$ \xrightarrow{R_3 \leftarrow R_3 - 3R_2} \left[ \begin{array}{ccc|c} 1 & 1 & 1 & 2\cr 0 & -2 & -3 & 1\cr 0 & 0 & 1 & 1 \end{array} \right]$$
最后再回代求解得 $(a, b, c) = (3, -2, 1)$.
目前来看，高斯消元更像是把方程组写得更整齐、把加减消元的过程做的更规范的工具罢了。
拉格朗日插值
显而易见的是若用待定系数法构造多项式，需要解一个 $n$ 元线性方程组，高斯消元的时间复杂度为 $O(n^3)$，$n$ 稍微大一点开销就爆炸了。拉格朗日插值则提供了一种绕过解方程组、直接构造多项式的方法。首先记一个结论：
对于 $n$ 个点 $(x_i, y_i)$，若 $\forall i \ne j , x_i \neq x_j$，则一定存在唯一一个次数不超过 $n - 1$ 的多项式 $y = f(x)$，满足 $f(x_i) = y_i$
根据因式定理：
若多项式 $f(a) = 0$，则 $f(x)$ 必含有因式 $(x - a)$；反之若 $f(x)$ 含有因式 $(x - a)$，则 $f(a) = 0$
如果一个多项式有 $m$ 个不同的跟，则至少有 $m$ 个因式相乘，次数最小为 $m$. 即一个次数不超过 $m$ 的多项式，最多有 $m$ 个根。
后文将会对其唯一性进行简单证明。
推导
不妨从最简单的情形入手。现在有两个点：
$$(x_0, y_0), (x_1, y_1)$$
两点确定一条直线。因此该直线方程可以用两点式写成：
$$\frac{y - y_0}{y_1 - y_0} = \frac{x - x_0}{x_1 - x_0}$$
若把它写成 $y = L(x)$ 的形式：
$$L(x) = y_0 + \frac{y_1 - y_0}{x_1 - x_0}(x - x_0)$$
这就是一个过 $(x_0, y_0), (x_1, y_1)$ 两点的一次函数。但如果将其推广到更多的点，这样的写法就太不方便了：它把 $y_0$ 和 $y_1$ 混在了一起。
不如换一种整理方式：
$$ \begin{aligned} L(x) &= y_0 + \frac{y_1 - y_0}{x_1 - x_0}(x - x_0) \cr &= y_0 \left( 1 - \frac{x - x_0}{x_1 - x_0} \right) + y_1 \frac{x - x_0}{x_1 - x_0} \cr &= y_0 \frac{x - x_1}{x_0 - x_1} + y_1 \frac{x - x_0}{x_1 - x_0} \end{aligned}$$
令：
$$\ell_0(x) = \frac{x - x_1}{x_0 - x_1}, \ell_1(x) = \frac{x - x_0}{x_1 - x_0}$$
设点 $(x_0, y_0) = (1, 1), (x_1, y_1) = (2, 2)$，并将 $y = y_0\ell_0(x)$ 与 $y = y_1\ell_1(x)$ 表示在图像上：
它们显然满足：
$$\ell_0(x_0) = 1, \ell_0(x_1) = 0$$
$$\ell_1(x_0) = 0, \ell_1(x_1) = 1$$
即 $\ell_0$ 只在 $x = x_0$ 处「打开」，在 $x = x_1$ 处「关闭」。$\ell_1$ 与之相反。即：
$$L(x) = y_0 \ell_0(x) + y_1 \ell_1(x)$$
这个形式就是一次拉格朗日插值，其中 $\ell(x)$ 被称为「开关函数」非权威定义，只是便于理解。
二次函数的推导稍显复杂，其根本是先不处理第三个点，用前两个点做一次插值后构造并加上一个在 $x_0, x_1$ 处为 0 的修成项 $c(x - x_0)(x - x_1)$，再根据第三点的坐标求出 $c$，整理并化为插值的形式。
更高次项的多项式操作类似，感兴趣的读者可以自行推导。现在将其推广到一般形式。
对于已知的 $n + 1$ 个点：
$$(x_0, y_0), (x_1, y_1), \cdots , (x_n, y_n)$$
新的「开关函数」$\ell_i(x)$ 需满足：
- 当 $x = x_i$ 时，$\ell_i(x) = 1$
- 当 $x = x_j$ 且 $i \neq j$ 时，$\ell_i(x) = 0$
显然可以这样构造：
$$\begin{aligned} \ell_i(x) &= \frac{(x - x_0)(x - x_1) \cdots (x - x_{i - 1})(x - x_{i + 1}) \cdots (x - x_n)}{(x_i - x_0)(x_i - x_1) \cdots (x_i - x_{i - 1})(x_i - x_{i + 1}) \cdots (x_i - x_n)} \cr &= \prod_{j\neq i} \frac{x - x_j}{x_i - x_j} \end{aligned}$$
当 $x = x_i$ 时，分子与分母相同，整个式子的值为 1，即开关「开」。
再把所有的「开关」加起来：
$$\begin{aligned} L(x) &= y_0\ell_0(x) + y_1\ell_1(x) \cdots + y_n\ell_n(x) \cr &= \sum_{i = 1}^n y_i \ell_i(x) \end{aligned}$$
唯一性证明
设次数不超过 $n - 1$ 的多项式 $F(x), G(x)$，满足：
$$F(x_i) = y_i, G(x_i) = y_i$$
令：
$$H(x) = F(x) - G(x)$$
因为 $F(x)$ 与 $G(x)$ 的次数均不超过 $n - 1$，所以 $H(x)$ 的次数也不超过 $n - 1$。
对于每一个 $i$：
$$H(x_i) = F(x_i) - G(x_i) = y_i - y_i = 0$$
即 $x_1, x_2 \cdots x_n$ 这 $n$ 个数都是 $H(x)$ 的根。 $H(x)$ 至少有 $n$ 个根。
回顾前文的结论：
一个次数不超过 $m$ 的多项式，最多有 $m$ 个根
但 $H(x)$ 的次数不超过 $n - 1$ 却有 $n$ 个根，这与上述结论矛盾。除非：
$$H(x) \equiv 0$$
即：
$$F(x) - G(x) \equiv 0$$
所以：
$$F(x) = G(x)$$
证毕。
高中阶段所能用到的所有拓展知识到此结束，以下内容则与信息学竞赛强相关，学有余力的读者可以接着往下看
重心拉格朗日插值
这部分的推导相当常规，所以决定增加一点本人对于此概念的碎碎念😗
刚开始看到这个概念时以为是解决高次项插值的的，就是把下图的插值函数 $L_{10}(x)$ 重新拟合到更接近原函数 $f(x) = \frac{1}{1 + (\frac{x}{2})^2}$ 的算法。
注意到 $L_{10}(x)$ 在 $x = 9$ 与 $x = -9$ 附近上下剧烈震荡，与原函数 $f(x)$ 相差甚大，这就是典型的「龙格现象」。。噢你问这个图怎么跟上面不一样因为上面那个是拿 Desmos 画的这个是 Matplotlib，Python 画图还是太优雅了 awa
回到正题。不难看出，在上述插值的做法下对于每一次查询都是 $O(n^2)$ 的，多次查询的时间显然是爆炸。每插入一个值，整个多项式都需要重新构造，因此传统的拉格朗日插值在特定情境下并不优雅。重心拉格朗日插值则提供了一种在 $O(n)$ 内求值与更新多项式的方法。
将 $\ell_i(x)$ 拆开：
$$\ell_i(x) = \frac{\prod\limits_{j \neq i} (x - x_j)}{\prod\limits_{j \neq i} (x_i - x_j)}$$
显然分母部分只与已知点相关，不妨令：
$$w_i = \frac{1}{\prod\limits_{j \neq i} (x_i - x_j)}$$
则：
$$\ell_i(x) = w_i \prod_{j \neq i} (x - x_j)$$
其中， $w_i$ 被称之为「重心权重」。补全连乘，令：
$$\ell(x) = \prod_{j = 1}^n (x - x_j)$$
所以：
$$\begin{aligned} \ell_i(x) &= w_i \frac{\prod\limits_{j = 1}^n (x - x_j)}{x - x_i} \cr &= w_i \frac{\ell(x)}{x - x_i}\end{aligned}$$
$$\begin{aligned}L(x) &= \sum_{i = 1}^n y_i w_i \frac{\ell(x)}{x - x_i} \cr &= \ell(x) \sum_{i = 1}^n \frac{y_i w_i}{x - x_i} \end{aligned}$$
如何消掉这个突兀的 $\ell(x)$ 呢？注意到对于多项式 $1$：
$$\begin{aligned} 1 &= \sum_{i = 1}^n 1 \cdot \ell_i(x) \cr &= \sum_{i = 1}^n \ell_i(x) \cr &= \sum_{i = 1}^n w_i \frac{\ell(x)}{x - x_i} \cr &= \ell(x) \sum_{i = 1}^n \frac{w_i}{x - x_i} \end{aligned}$$
则：
$$\ell(x) = \frac{1}{\sum\limits_{i = 1}^n \frac{w_i}{x - x_i}}$$
所以：
$$L(x) = \frac{\sum\limits_{i = 1}^n \frac{y_i w_i}{x - x_i}}{\sum\limits_{i = 1}^n \frac{w_i}{x - x_i}}$$
至于它为什呢叫「重心」呢是因为最后推导出的公式形似加权平均：
$$L(x) = \frac{\sum{权重}_i \cdot y_i}{\sum{权重_i}}$$
跟「龙格现象」有冇关系。
不嘻嘻。
