众所周知,待定系数求解是无敌的

对于一个关于$x$的$k$次多项式,至少需要$k+1$项才能解出多项式的系数,之后才能代入求解。

但是考场上用的话,等死吧,待定系数法过于繁琐。

一般的拉格朗日插值法

拉格朗日同样想到这个问题,于是他想,能不能通过$k+1$条曲线来表示出这个多项式呢?

于是就有了拉格朗日插值法,$f(x)=\sum\limits _{i=0}^{k}y_i\prod\limits_{j\ne i} \frac{x-x_j}{x_i-x_j}$

证明

存在性

对于给定的 $k + 1$ 个点,$(x_0, y_0),\ldots,(x_k, y_k)$,拉格朗日插值法的思路是找到一个在一点$x_j$ 取值为 $1$ ,而在其他点取值都是 $0$ 的多项 $\ell_j(x)$。

这样,多项式 $y_j \ell_j(x)$ 在点 $x_j$ 取值为 $y_j$ ,而在其他点取值都是 $0$ 。

而多项式 $L(x) = \sum_{j=0}^{k} y_j \ell_j(x)$ 就可以满足

$$L(x_j) = \sum_{i=0}^{k} y_i \ell_i(x_j) = 0 + 0 + \cdots + y_j + \cdots + 0 = y_j$$

在其它点取值为 $0$ 的多项式容易找到,例如:

$$(x-x_0) \cdots (x-x_{j-1})(x-x_{j+1}) \cdots (x-x_{k})$$

它在点 $x_j$ 取值为 $(x_j-x_0) \cdots (x_j-x_{j-1})(x_j-x_{j+1}) \cdots (x_j-x_{k})$ 。由于

已经假定 $x_i$ 两两互不相同,因此上面的取值不等于 $0$ 。

于是,将多项式除以这个取值,就得到一个满足在 $x_j$ 取值为 $1$ ,而在其他点取值都是 $0$ 的多项式

$$\ell_j(x) = \prod_{i=0,\, i\neq j}^{k} \frac{x-x_i}{x_j-x_i} = \frac{(x-x_0)}{(x_j-x_0)} \cdots \frac{(x-x_{j-1})}{(x_j-x_{j-1})} \frac{(x-x_{j+1})}{(x_j-x_{j+1})} \cdots \frac{(x-x_{k})}{(x_j-x_{k})}$$

这就是拉格朗日基本多项式。

唯一性

次数不超过 $k$ 的拉格朗日多项式至多只有一个,

因为对任意两个次数不超过 $k$ 的拉格朗日多项式$P_1$ 和$P_2$,它们的差 $P_1 - P_2$ 在所有 $k+1$ 个点上取值都是 $0$ ,

因此必然是多项式 $(x-x_0)(x-x_{1}) \cdots (x-x_{k})$ 的倍数。

因此,如果这个差 $P_1 - P_2$ 不等于 $0$ ,次数就一定不小于 $k + 1$。

但是 $P_1 - P_2$ 是两个次数不超过 $k$ 的多项式之差,它的次数也不超过 $k$。

所以 $P_1 - P_2 = 0$ ,也就是说 $P_1 = P_2$。这样就证明了唯一性。

自然数幂和

$$f_k(n)=\sum\limits_{i = 1}^n i^k$$

观察第二项,为 $\tbinom{n+1}{2}= \frac{n(n+1)}{2}$ ,那不妨大胆猜测与组合数有关

那么我们需要让组合数中 $[1,n]$ 都出现,那么考虑差分 $k + 1$ 阶(这里以离散积分会比较有意思)

$$\begin{aligned}(n+1) ^{3}- n^3&=\dbinom{3}{2}n^2+\dbinom{3}{1}n+1\\n^3-(n-1)^3&=\dbinom{3}{2}(n-1)^2+\dbinom{3}{1}(n-1)+1\\2^3-1^3&=\dbinom{3}{2}1^2+\dbinom{3}{1}1+1\end{aligned}$$

两边分别求和,得:

$$(n+1)^3-1^3=\sum\limits_{i=0}^2\dbinom{3}{2}f_{2}(n)+\dbinom{3}{1}f_{1}(n)+\dbinom{3}{0}n$$

不妨令

$$f_{0}(n)= n$$

然后把 $f_2(n)$ 放到左边

$$f_{2}(n)=\frac{(n+1)^3-1^3-\sum\limits_{i=0}^1\tbinom{3}{i}f_{i}(n)}{3}$$

类似地,我们可以得到一个任意阶的递推式。

$f_{k}(n)=\frac{(n+1)^k-1-\sum\limits_{i=0}^{k-1}\tbinom{k+1}{i}f_{i}(n)}{k+1}$

很容易得到 $f_k(n)$ 是一个关于 $n$ 的 $k + 1$ 次多项式。

插值计算 $i\in[0,k + 1],f_{k}(i)$ 即可。

至此,多了一个$O(k^2)$的求解$k$次多项式方法。

在$x$取值连续的插值法

这样想,$\prod\limits_{j\ne i}\frac{x-x_j}{x_i-x_j}$,只是在一段连续的数中缺了$x_i$

那么有$P_i=\prod \limits_{j=0}^{i-1}(x-x_j),S_i=\prod\limits_{j=i+1}^k(x-x_j) $

$\prod\limits_{j\ne i}\frac{x-x_j}{x_i-x_j}=\frac{P_i*S_i}{-1^{k-i-1}*i!*(k-i-1)!}=-1^{k-i-1}*\frac{P_i*S_i}{i!(k-i-1)!}$

因此$f(x)=\sum\limits _{i=0}^k y_i*-1^{k-i-1}*\frac{P_i*S_i}{i!(k-i-1)!}$

自然数幂和

$$f_k(n)=\sum\limits_{i = 1}^n i^k$$

观察第二项,为 $\tbinom{n+1}{2}= \frac{n(n+1)}{2}$ ,那不妨大胆猜测与组合数有关

那么我们需要让组合数中 $[1,n]$ 都出现,那么考虑差分 $k + 1$ 阶(这里以离散积分会比较有意思)

$$\begin{aligned}(n+1) ^{3}- n^3&=\dbinom{3}{2}n^2+\dbinom{3}{1}n+1\\n^3-(n-1)^3&=\dbinom{3}{2}(n-1)^2+\dbinom{3}{1}(n-1)+1\\2^3-1^3&=\dbinom{3}{2}1^2+\dbinom{3}{1}1+1\end{aligned}$$

两边分别求和,得:

$$(n+1)^3-1^3=\sum\limits_{i=0}^2\dbinom{3}{2}f_{2}(n)+\dbinom{3}{1}f_{1}(n)+\dbinom{3}{0}n$$

不妨令

$$f_{0}(n)= n$$

然后把 $f_2(n)$ 放到左边

$$f_{2}(n)=\frac{(n+1)^3-1^3-\sum\limits_{i=0}^1\tbinom{3}{i}f_{i}(n)}{3}$$

类似地,我们可以得到一个任意阶的递推式。

$$f_{k}(n)=\frac{(n+1)^k-1-\sum\limits_{i=0}^{k-1}\tbinom{k+1}{i}f_{i}(n)}{k+1}$$

很容易得到 $f_k(n)$ 是一个关于 $n$ 的 $k + 1$ 次多项式。

插值计算 $i\in[0,k + 1],f_{k}(i)$ 即可。