物理

多项式插值

题目应该是：《多项式插值与泰勒展开》

注：$i$ 默认不表示虚数单位。

多项式插值是一个非常有用的东西。

假设有人问你：$1$，$3$，$5$，下一个数是什么？

你可以直接回答：$114514$。

如果你觉得它太臭了，你也可以回答：$998244353$。

为什么？请读者自己去插值，就明白了。

$\Huge{\text{1：待定系数法}}$

先说一个结论：解 $n$ 元一次方程需要 $n$ 个方程才可能有唯一解。

设 $f(x)=ax^3+bx^2+cx+d$。

显然你需要让 $f(0)=1,f(1)=3,f(2)=5,f(3)=114514$。

列出方程：

$\begin{cases}d=1\\a+b+c+d=3\\8a+4b+2c+d=5\\27a+9b+3c+d=114514\end{cases}$

多么简单的一个方程组啊！

$\Huge{\text{2：带导数的待定系数法}}$

$\sout{有人曾经说过：优秀的司机要控制汽车的四阶导数，跳丝滑的舞蹈要控制身体的六阶导数。}$

假设我们在上一题的基础上，还要控制导数：$f'(1)=0$，怎么办呢？

这时，我们需要一个四次函数：$f(x)=ax^4+bx^3+cx^2+dx+e$

它的导数是：$f'(x)=4ax^3+3bx^2+2cx+d$

$\begin{cases}e=1\\a+b+c+d+e=3\\16a+8b+4c+2d+e=5\\81a+27b+9c+3d+e=114514\\4a+3b+2c+d=0\end{cases}$

$\Huge{\text{3：拉格朗日插值}}$

假设我们需要让 $f(x_1)=y_1,f(x_2)=y_2,\dots,f(x_n)=y_n$。

我们可以设一些函数：$g_1(x),g_2(x),\dots,g_n(x)$

且它们满足：$g_i(i)=1$①和对于所有 $x\in\{x_j|1\le j\le n\land j\neq i\land j\in\mathbb{N}^{+}\}$，$g_i(x)=0$②。

然后显然 $f(x)=\sum_{i=1}^{n}y_ig_i(x)$。

那么 $g_i(x)$ 是什么呢？

首先设 $h_i(x)=\prod_{j=1,j\neq i}^n(x_j-x)$ 可以满足①但不满足②。

于是我们考虑设 $g_i(x)=\frac{h_i(x)}{k_i(x)}$，其中 $x\neq i$ 时 $k_i(x)=h_i(x)$，且 $k_i(x)\not\equiv0$（恒不等于）。

所以 $k_i(x)=\prod_{j=1,j\neq i}^n(x_j-x_i)$。

现在我们完成了拉格朗日插值公式的全部推导。

$f(x)=\sum_{i=1}^{n}y_i\prod_{j=1,j\neq i}^n\frac{x_j-x}{x_j-x_i}$

$\Huge{\text{4：泰勒展开}}$

注：$f^{(n)}$ 表示 $f$ 的 $n$ 阶导数。

假设有入告诉你，$f(0)=0,f'(0)=-1,f''(0)=2,f'''(0)=1$，让你求这个函数，于是我们可以使用待定系数法：

设 $f(x)=ax^3+bx^2+cx+d$。

所以 $f'(x)=3ax^2+2bx+c,f''(x)=6ax+2b,f'''(x)=6a$。

发现 $f(0)=d,f'(0)=c,f''(0)=2b,f'''(0)=6a$。

所以 $\begin{cases}a=\frac16\\b=1\\c=-1\\d=0\end{cases}$。

$f(x)=\frac16x^3+x^2-x$

那么，如果有入告诉你，$f(0),f'(0),f''(0),\dots,f^{(n)}(0)$，你又要怎么算呢？

如果设 $f(x)=a_0+a_1x+a_2x^2+\dots+a_nx^n$，显然 $f^{(i)}(0)=i!a_i$。

所以 $a_i=\frac{f^{(i)}(0)}{i!}$，然后我们能得到 $f(x)=\sum_{i=0}^n\frac{f^{(i)}(0)}{i!}x^i$。

但我们不一定总是能知道 $f(0),f'(0),f''(0),\dots,f^{(n)}(0)$，所以我们把这个函数稍微移动一下就可以了。

$f(x)=\sum_{i=0}^n\frac{f^{(i)}(x_0)}{i!}(x-x_0)^i$

如果 $f(x)$ 原来不是一个多项式函数，（大部分情况下）我们可以这样用多项式得到原函数的近似值。

如我们已知 $f(x)=\sin x$ 的以下性质：

如果 $i\equiv0(\bmod4)$（这里是同余），那么 $f^{(n)}(0)=0$；

如果 $i\equiv1(\bmod4)$，那么 $f^{(n)}(0)=1$；

如果 $i\equiv2(\bmod4)$，那么 $f^{(n)}(0)=0$；

如果 $i\equiv3(\bmod4)$，那么 $f^{(n)}(0)=-1$。

所以 $\sin x=x-\frac{1}{3!}x^3+\frac{1}{5!}x^5-\frac{1}{7!}x^7+\dots$。

$\Huge{\text{5：差分}}$

比如数列 $a=1,3,5,114514,\dots$（从 $a_0$ 开始），

我们求出差分 $\Delta a=2,2,114509,\dots$，

再求出差分的差分 $\Delta^2a=0,114507,\dots$，

最后求出差分的差分的差分 $\Delta^3a=114507,\dots$。

不管这个数列的后面是什么，我们可以用瞪眼法得到 $\Delta^3a_i=114507$，使用等幂求和公式得到 $\Delta^2a_i=114507i$，可以重复这个过程直到得到原数列的表达式。

但这样还是很慢，这个方法有什么优点呢？

假设你需要找到数列 $a=1,3,5,114514,\dots$ 的下一项，用这个方法就会快很多。

可以轻松地求得 $\Delta a=2,2,114509,\dots$，

$\Delta^2a=0,114507,\dots$，

$\Delta^3a=114507,\dots$。

我们可以相信 $\Delta^3a_1=\Delta^3a_0=114507$，

所以可以得到 $\Delta^3a=114507,114507,\dots$，

$\Delta^2a=0,114507,229014,\dots$，

$\Delta a=2,2,114509,343525,\dots$，

$a=1,3,5,114514,458039,\dots$。

（《多项式插值》完）