标签：拉格朗 aligned frac 插值 sum times le prod

拉格朗日插值

普通拉格朗日插值

众所周知，\(n + 1\) 个横坐标互不相同的点可以确定出唯一的最高次为 \(n\) 的多项式。当给定你 \(n\) 个点并要求你求出横坐标为 \(x\) 的点的纵坐标，高斯消元虽是个选择，但是 \(O(n^3)\) 的时间复杂度显然不优。于是我们选择用 \(O(n^2)\) 的拉格朗日插值解决这类问题。

我们先来考虑构造一个函数 \(L(x)\)，我们希望这个函数在 \(x = x_i\) 时等于 \(1\)，在 \(x = x_j(0 \le j \le n, j \not= i)\) 时等于 \(0\)。

我们想达到这个目的，不难想到去令多个式子相乘，这样的话只要有一项等于 \(0\)，则总的式子就等于 \(0\)。

所以我们先设 \(\displaystyle L(x) = \prod_{0 \le j \le n} (x - x_j)\)，但是我们发现当 \(x = x_i\) 时也等于 \(0\)。

所以我们再设 \(\displaystyle L(x) = \prod_{0 \le j \le n 且i \not= j} (x - x_j)\)，但是我们发现当 \(x = x_i\) 时不等于 \(1\)。

所以我们设 \(\displaystyle L(x) = \prod_{0 \le j \le n 且i \not= j} \frac{x - x_j}{x_i - x_j}\)。

然后就得到了一个非常巧的函数。

然后就有：

\[\begin{aligned} f(x) &= \sum_{i = 0}^n y_i L(x)\\ &= \sum_{i = 0}^n y_i \prod_{j \not= i} \frac{x - x_j}{x_i - x_j} \end{aligned}\]

这个式子显然是可以在 \(O(n^2)\) 的时间复杂度内算出来的。

在横坐标连续的情况下的拉格朗日插值

当横坐标连续时，我们可以将 \(x_i\) 看作 \(i\)，\(x_j\) 看作 \(j\)，所以原式变成：

\[\begin{aligned} f(x) = \sum_{i = 0}^n y_i \prod_{j \not= i} \frac{x - j}{i - j} \end{aligned}\]

现在的重点在于如何快速算出 \(\displaystyle \prod_{j \not= i} \frac{x - j}{i - j}\)

我们发现分子可以写成前缀积和后缀积相乘的形式，所以设 \(\displaystyle pre_i = \prod_{j = 0}^i (x - j), suf_i = \prod_{j = i}^n (x - j)\)，然后分子就可以写成 \(pre_{i - 1} \times suf_{i + 1}\)。

但是我们发现，分子好像也可以不写成前缀积和后缀积相乘的形式。我们直接预处理出 \(prod = \displaystyle \prod_{j = 0}^n (x - j)\)，然后分子就是 \(\displaystyle \frac{prod}{x - i}\)，我们把 \(x - i\) 移到分母上即可。

我们发现分母可以写成阶乘的形式，所以设 \(fac_i\) 为 \(i\) 的阶乘，然后分母就可以写成 \(fac_{i - 1} \times fac_{n - i}\)。

但是我们发现，当 \(i < j\) 时有可能会使原式变为负数。我们考虑什么时候会出现这种情况。

对于 \(m\) 个负数相乘，当 \(m\) 为偶数时结果为正，\(m\) 为奇数时结果为负。对于一个 \(i\)，大于 \(i\) 的 \(j\) 的个数为 \(n - i\)，所以我们让分母再乘上 \((-1)^{n - i}\) 即可。

所以整合一下：

\[\begin{aligned} f(x) &= \sum_{i = 0}^n \frac{y_i \times pre_{i - 1} \times suf_{i + 1}}{(-1)^{n - i} \times fac_{i - 1} \times fac_{n - i}}\\ &= \sum_{i = 0}^n \frac{y_i \times prod}{(x - i) \times (-1)^{n - i} \times fac_{i - 1} \times fac_{n - i}}\\ \end{aligned}\]

我们发现这个式子是 \(O(n)\) 的。

重心拉格朗日插值

如果我们需要计算多次拉格朗日插值，那每一次都跑一边 \(O(n^2)\) 这个过程是很不优的，因为我们重复算了很多东西。

所以我们考虑重写一下原式。

\[\begin{aligned} f(x) &= \sum_{i = 0}^n y_i \prod_{j \not= i} \frac{x - x_j}{x_i - x_j}\\ &= \sum_{i = 0}^n y_i \prod_{j \not= i} (x - x_j) \prod_{p \not= i}\frac{1}{x_i - x_p}\\ &= \sum_{i = 0}^n \prod_{j \not= i} (x - x_j) \frac{y_i}{\prod_{p \not= i}(x_i - x_p)}\\ &= \prod_{j = 0}^n (x - x_j) \sum_{i = 0}^n \frac{y_i}{\prod_{p \not= i}(x_i - x_p)} \times \frac{1}{x - x_i}\\ \end{aligned}\]

然后我们设 \(\displaystyle prod_i = \frac{y_i}{\prod_{p \not= i}(x_i - x_p)}, g_x = \prod_{j = 0}^n (x - x_j)\)。

所以有：

\[\begin{aligned} f(x) &= g(x) \sum_{i = 0}^n \frac{prod_i}{x - x_i}\\ \end{aligned}\]

在 \(O(n^2)\) 预处理出 \(prod\) 后，这个式子可以 \(O(n)\) 计算。

标签：拉格朗,aligned,frac,插值,sum,times,le,prod
From： https://www.cnblogs.com/Meteor-streaking/p/17772886.html