多項式多點求值|快速插值
多項式的多點求值
描述
給出一個多項式 \(f\left(x\right)\) 和 \(n\) 個點 \(x_{1},x_{2},\dots,x_{n}\)，求
\[
f\left(x_{1}\right),f\left(x_{2}\right),\dots,f\left(x_{n}\right)
\]
解法
考慮使用分治來將問題規模減半。
將給定的點分為兩部分：
\[
\begin{aligned}
X_{0}&=\left\{x_{1},x_{2},\dots,x_{\left\lfloor\frac{n}{2}\right\rfloor}\right\}\\
X_{1}&=\left\{x_{\left\lfloor\frac{n}{2}\right\rfloor+1},x_{\left\lfloor\frac{n}{2}\right\rfloor+2},\dots,x_{n}\right\}
\end{aligned}
\]
構造多項式
\[
g_{0}\left(x\right)=\prod_{x_{i}\in X_{0}}\left(x-x_{i}\right)
\]
則有 \(\forall x\in X_{0}:g_{0}\left(x\right)=0\)。
考慮將 \(f\left(x\right)\) 表示為 \(g_{0}\left(x\right)Q\left(x\right)+f_{0}\left(x\right)\) 的形式，即：
\[
f_{0}\left(x\right)\equiv f\left(x\right)\pmod{g_{0}\left(x\right)}
\]
則有 \(\forall x\in X_{0}:f\left(x\right)=g_{0}\left(x\right)Q\left(x\right)+f_{0}\left(x\right)=f_{0}\left(x\right)\)，\(X_{1}\) 同理。
至此，問題的規模被減半，可以使用分治 + 多項式取模解決。
時間複雜度
\[
T\left(n\right)=2T\left(\frac{n}{2}\right)+O\left(n\log{n}\right)=O\left(n\log^{2}{n}\right)
\]
多項式的快速插值
描述
給出一個 \(n+1\) 個點的集合
\[
X=\left\{\left(x_{0},y_{0}\right),\left(x_{1},y_{1}\right),\dots,\left(x_{n},y_{n}\right)\right\}
\]
求一個 \(n\) 次多項式 \(f\left(x\right)\) 使得其滿足 \(\forall\left(x,y\right)\in X:f\left(x\right)=y\)。
解法
考慮拉格朗日插值公式
\[
f(x) = \sum_{i=1}^{n} \prod_{j\neq i }\frac{x-x_j}{x_i-x_j} y_i
\]
記多項式 \(M(x) = \prod_{i=1}^n (x - x_i)\)，由洛必達法則可知
\[
\prod_{j\neq i} (x_i - x_j) = \lim_{x\rightarrow x_i} \frac{\prod_{j=1}^n (x - x_j)}{x - x_i} = M'(x_i)
\]
因此多項式被表示為
\[
f(x) = \sum_{i = 1}^n \frac{y_i}{M'(x_i)}\prod_{j \neq i}(x - x_j)
\]
我們首先通過分治計算出 \(M(x)\) 的係數表示，接着可以通過多點求值在 \(O(n\log^2 n)\) 時間內計算出所有的 \(M'(x_i)\)。
我們令 \(v_i = \frac{y_i}{M'(x_i)}\)，接下來考慮計算出 \(f(x)\)。對於 \(n = 1\) 的情況，有 \(f(x) = v_1, M(x) = x - x_1\)。否則令
\[
\begin{aligned}
f_0(x) & = \sum_{i = 1}^{\left\lfloor \frac n2 \right \rfloor} v_i\prod_{j \neq i \wedge j \le \left\lfloor \frac n2 \right \rfloor}(x - x_j)\\
M_0(x) & = \prod_{i = 1}^{\left\lfloor \frac n2 \right \rfloor} (x - x_i)\\
f_1(x) & = \sum_{i = \left\lfloor \frac n2 \right \rfloor+1}^n v_i\prod_{j \neq i \wedge \left\lfloor \frac n2 \right \rfloor < j \le n}(x - x_j) \\
M_1(x) & = \prod_{i = \left\lfloor \frac n2 \right \rfloor+1}^n (x - x_i)
\end{aligned}
\]
可得 \(f(x) = f_0(x)M_1(x) + f_1(x)M_0(x), M(x) = M_0(x)M_1(x)\)，因此可以分治計算，這一部分的複雜度同樣是 \(O(n\log^2 n)\)。
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用