插值

引入

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

例如对数据点：

$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,\mathrm{\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{array}{l}{P}_j^{\prime }(x_j,0),(j\ne i)\\ P_i(x_i,y_i)\end{array}$，则可知题目所求的函数 $f(x)=\sum _{i=1}^n{f}_i(x)$.

那么可以设 $f_i(x)=a\cdot \prod _{j\ne i}(x-x_j)$，将点 $P_i(x_i,y_i)$ 代入可以知道 $a={\displaystyle \frac{y_i}{\prod _{j\ne i}(x_i-x_j)}}$，所以

$$f_i(x)=y_i\cdot {\displaystyle \frac{\prod _{j\ne i}(x-x_j)}{\prod _{j\ne i}(x_i-x_j)}}=y_i\cdot \prod _{j\ne i}{\displaystyle \frac{x-x_j}{x_i-x_j}}$$

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

$$f(x)=\sum _{i=1}^n{y}_i\cdot \prod _{j\ne i}{\displaystyle \frac{x-x_j}{x_i-x_j}}$$

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

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

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

---

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