拉格朗日插值

拉插的用法是,给定好多个点,让你拟合一条多项式的曲线经过这些点,求出这个函数在x=k的时候的值.

拉插公式

$$f(x)=\sum_{i=0}^ny_i\prod_{i\neq j}\frac{k-x_j}{x_i-x_j}$$

理解一下:假如给的点是 $(1,3),(2,7),(3,13)$ ,拉插就是:

$$f(k)=3\frac{(k-2)(k-3)}{(1-2)(1-3)}+7\frac{(k-1)(k-2)}{(2-1)(2-3)}+13\frac{(k-1)(k-2)}{(3-1)(3-2)}$$

x取值连续的优化

由于x取值连续,可以快速计算前缀积和后缀积(上面)以及阶乘(下面)然后实现 $O(n)$ 的计算拉插.(N表示有几项)

$$pre_i=\prod_{j=1}^ik-j$$ $$suf_i=\prod_{j=i}^Nk-j$$ $$f(k)=\sum_{i=1}^Ny_i\frac{pre_{i-1}\cdot suf_{i+1}}{(i-1)!(N-i)!}$$

重心拉插

可以实现动态加点的计算方式:

$$f(x)=\sum_{i=0}^ny_i\prod_{i\neq j}\frac{k-x_j}{x_i-x_j}$$

令 $g=\prod^n_{i=0}k-x_i$ ,则有

$$f(k)=g\sum_{i=0}^n\prod_{i\neq j}\frac{y_i}{(k-x_i)(x_i-x_j)}$$

设 $t_i=\frac{y_i}{\prod_{i\neq j}x_i-x_j}$ ,则有

$$f(k)=g\sum_{i=0}^n\frac{t_i}{(k-x_i)}$$

这样加点的时候只需要计算他的 $t_i$ 即可.

应用

1. $$\sum_{i=1}^ni^k$$ 这是一个 $(k+1)$ 项的多项式(归纳出来的),然后”直接插值”(按n为变元,暴力算每个数,然后按点插值,因为取值连续所以可以 $O(n)$ 插值)