物理

多项式插值

（TINY NSD）

（7 月 22 日再次更新）

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

注：$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$。

（《多项式插值》没完）

$\Huge{\text{6：“分段”插值}}$

本文中第一次提到的数列是 $1,3,5,114514$，显然注意到前三项满足 $f(x)=2x+1$，而最后一项太臭了，所以不满足。

于是我们考虑 $f(x)=2x+1+g(x)$，其中 $g(x)=0$ 的根为 $x_1=0,x_2=1,x_3=2$，我们发现 $g(x)=kx(x-1)(x-2)$ 满足要求。

当 $x=3$ 时，$2\times3+1+k\times3\times(3-1)\times(3-2)=114514$，所以 $k=\frac{114507}{6}$，然后可以得到 $f(x)=2x+1+\frac{114507}{6}x(x-1)(x-2)$，我们就完成了插值。

$\Huge{\text{7：牛顿插值}}$

首先我们定义差商 $f[x_i]=y_i,f[x_i,x_{i+1},\dots,x_j]=\frac{f[x_{i+1},x_{i+2},\dots,x_j]-f[x_i,x_{i+1},\dots,x_{j-1}]}{x_j-x_i}$，计算得到：

一阶差商：$f[x_0]=1,f[x_1]=3,f[x_2]=5,f[x_3]=114514$

二阶差商：$f[x_0,x_1]=\frac{f[x_1]-f[x_0]}{x_1-x_0}=2,f[x_1,x_2]=\frac{f[x_2]-f[x_1]}{x_2-x_1}=2,f[x_2,x_3]=\frac{f[x_3]-f[x_2]}{x_3-x_2}=114509$

三阶差商：$f[x_0,x_1,x_2]=\frac{f[x_1,x_2]-f[x_0,x_1]}{x_2-x_0}=0,f[x_1,x_2,x_3]=\frac{f[x_2,x_3]-f[x_1,x_2]}{x_3-x_1}=\frac{114507}{2}$

四阶差商：$f[x_0,x_1,x_2,x_3]=\frac{f[x_1,x_2,x_3]-f[x_0,x_1,x_2]}{x_3-x_0}=\frac{114507}{6}$

然后设参数 $a_0=f[x_0],a_1=f[x_0,x_1],a_2=f[x_0,x_1,x_2],a_3=f[x_0,x_1,x_2,x_3]$

函数 $f(x)=a_0+a_1(x-x_0)+a_2(x-x_0)(x-x_1)+a_3(x-x_0)(x-x_1)(x-x_2)$

所以，函数 $f(x)=1+2x+\frac{114507}{6}x(x-1)(x-2)$ 满足要求。