拉格朗日插值法入门经典

若我们有n对过某曲线的点如何构造一n-1次多项式使其通过这些点

我们使用拉格朗日插值法

1.经典法

对于每个点$k$ 我们单独构造一个多项式$f_k(x)$使得除$k$ 外所有点在该多项式中取0

易构造出
$$
f_k(x)=\prod_{i=1,i!=k}^n(x-x_i)
$$
我们希望$x_k$在此多项式$g_k(x)$中取值为$y_k$

只需使$ g_k(x)=y_k\frac{f_k(x)}{f_k(x_k)}$即可

最终答案便是所有$g_k(x)$之和

依题先将$x_i$换成$i$

然后发现新式即为
$$
f(k)=\sum_{i=1}^ny_i\prod_{i!=j}\frac{k-j}{i-j}
$$
我们对后式使用阶乘维护即可