标签：拉格朗 limits 插值法 dfrac sum prod neq

拉格朗日插值法

引入

拉格朗日插值法是一种解决多项式插值的方法。

多项式插值：

已知 \(n + 1\) 个点 \((x_i, y_i)\)， 求一个多项式函数 \(f(x)\) 使得其图像经过这 \(n + 1\) 个点。

其中 \(f(x)\) 被称为插值多项式。

可以证明 \(n + 1\) 个点可以唯一确定一个最高 \(n\) 次的插值多项式。

结论

\[f(k) = \sum\limits_{i = 0}^n y_i \prod\limits_{j \neq i} \dfrac{k - x_j}{x_i - x_j} \]

可以发现对于一个点 \((x_a, y_a)\)，当 \(i \neq a\) 时，\(\prod\) 部分会有一个 \(\dfrac{x_a - x_a}{x_i - x_a}\)，此时该式子值为 \(0\)。而当 \(i = a\) 时，\(\prod\) 部分的值为 \(1\)。故 \(f(x_a) = y_a\)。

求某一点的值的复杂度为 \(O(n^2)\)。

取值连续时的优化

当 \(x\) 的取值连续，即 \(x_i = i\) 时，可以将复杂度优化到 \(O(n)\)。

\[\begin{align*} f(k) &= \sum\limits_{i = 0}^n y_i \prod\limits_{j \neq i} \dfrac{k - x_j}{x_i - x_j} \\ &= \sum\limits_{i = 0}^n y_i \prod\limits_{j \neq i} \dfrac{k - j}{i - j} \end{align*} \]

令 \(pre_i = \prod\limits_{j = 0}^i (k - j), suf_i = \prod\limits_{j = i}^n (k - j)\)。

则

\[f(k) = \sum\limits_{i = 0}^n y_i \dfrac{pre_{i - 1} \times suf_{i + 1}}{i! \times (n - i)!} \times (-1)^{n - i} \]

重心拉格朗日插值法

一种可以 \(O(n)\) 插入一个点，\(O(n)\) 查询的拉格朗日插值法。

依然考虑这个式子：

\[\begin{align*} f(k) &= \sum\limits_{i = 0}^n y_i \prod\limits_{i \neq j} \dfrac{k - x_j}{x_i - x_j} \\ &= \sum\limits_{i = 0}^n y_i \dfrac{\prod\limits_{j \neq i} k - x_j}{\prod\limits_{j \neq i} x_i - x_j} \\ &= \sum\limits_{i = 0}^n \dfrac{y_i}{k - x_i} \dfrac{\prod\limits_{j = 0}^n k - x_j}{\prod\limits_{j \neq i} x_i - x_j} \\ \end{align*} \]

设 \(g(k) = \prod\limits_{i = 0}^n k - x_i, t_i = \dfrac{y_i}{\prod\limits_{j \neq i} x_i - x_j}\)。

则

\[\begin{align*} f(k) &= \sum\limits_{i = 0}^n \dfrac{g(k)t_i}{k - x_i} \\ &= g(k) \sum\limits_{i = 0}^n \dfrac{t_i}{k - x_i} \end{align*} \]

于是每次插入只需要更新之前的所有 \(t_i\) 并计算当前点的 \(t_i\) 即可，时间复杂度为 \(O(n)\)。

由于 \(g(k)\) 和 \(\sum\limits_{i = 0}^k \dfrac{t_i}{k - x_i}\) 都可以 \(O(n)\) 求得，故询问复杂度也是 \(O(n)\)。

标签：拉格朗,limits,插值法,dfrac,sum,prod,neq
From： https://www.cnblogs.com/mk-oi/p/lagrange.html