插值

引入

插值是一种通过已知的、离散的数据点推算一定范围内的新数据点的方法。插值法常用于函数拟合中。

例如对数据点：

\(x\)	\(0\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)
\(f(x)\)	\(0\)	\(0.8415\)	\(0.9093\)	\(0.1411\)	\(-0.7568\)	\(-0.9589\)	\(-0.2794\)

其中 \(f(x)\) 未知，插值法可以通过按一定形式拟合 \(f(x)\) 的方式估算未知的数据点。

例如，我们可以用分段线性函数拟合 \(f(x)\)：

这种插值方式叫做 线性插值。

我们也可以用多项式拟合 \(f(x)\)：

这种插值方式叫做 多项式插值。

多项式插值的一般形式如下：

多项式插值

对已知的 \(n+1\) 的点 \((x_0,y_0),(x_1,y_1),\dots,(x_n,y_n)\)，求 \(n\) 阶多项式 \(f(x)\) 满足

\[ f(x_i)=y_i,\qquad\forall i=0,1,\dots,n \]

下面介绍多项式插值中的两种方式：Lagrange 插值法与 Newton 插值法。不难证明这两种方法得到的结果是相等的。

Lagrange 插值法

由于要求构造一个函数 \(f(x)\) 过点 \(P_1(x_1, y_1), P_2(x_2,y_2),\cdots,P_n(x_n,y_n)\). 首先设第 \(i\) 个点在 \(x\) 轴上的投影为 \(P_i^{\prime}(x_i,0)\).

考虑构造 \(n\) 个函数 \(f_1(x), f_2(x), \cdots, f_n(x)\)，使得对于第 \(i\) 个函数 \(f_i(x)\)，其图像过 \(\begin{cases}P_j^{\prime}(x_j,0),(j\neq i)\\P_i(x_i,y_i)\end{cases}\)，则可知题目所求的函数 \(f(x)=\sum\limits_{i=1}^nf_i(x)\).

那么可以设 \(f_i(x)=a\cdot\prod_{j\neq i}(x-x_j)\)，将点 \(P_i(x_i,y_i)\) 代入可以知道 \(a=\dfrac{y_i}{\prod_{j\neq i} (x_i-x_j)}\)，所以

\[ f_i(x)=y_i\cdot\dfrac{\prod_{j\neq i} (x-x_j)}{\prod_{j\neq i} (x_i-x_j)}=y_i\cdot\prod_{j\neq i}\dfrac{x-x_j}{x_i-x_j} \]

那么我们就可以得出 Lagrange 插值的形式为：

\[ f(x)=\sum_{i=1}^ny_i\cdot\prod_{j\neq i}\dfrac{x-x_j}{x_i-x_j} \]

朴素实现的时间复杂度为 \(O(n^2)\)，可以优化到 \(O(n\log^2 n)\)，参见 多项式快速插值。

Luogu P4781【模板】拉格朗日插值

给出 \(n\) 个点对 \((x_i,y_i)\) 和 \(k\)，且 \(\forall i,j\) 有 \(i\neq j \iff x_i\neq x_j\) 且 \(f(x_i)\equiv y_i\pmod{998244353}\) 和 $\deg(f(x))

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：AtomAlpaca, billchenchina, caibyte, Chrogeek, Early0v0, EndlessCheng, Enter-tainer, Henry-ZHR, hly1204, hsfzLZH1, Ir1d, Ghastlcon, kenlig, Marcythm, megakite, Peanut-Tang, qwqAutomaton, qz-cqy, StudyingFather, swift-zym, swiftqwq, Tiphereth-A, TrisolarisHD, Watersail2005, x4Cx58x54, Xeonacid, xiaopangfeiyu, YanWQ-monad
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用