拉格朗日插值求系数

· · 算法·理论

拉格朗日插值的式子为

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

拉格朗日插值求系数：

考虑每一个点值对系数的贡献。

y_i,\prod{x_i-x_j}$ 都为常数，可以在 $O(n^2)$ 的时间内求出每一项 $a_i=\frac{y_i}{\prod_{i\neq j}(x_i-x_j)} $$ f(x)=\sum_{i=1}^na_i\frac{g(x)}{x-x_i} $$ 给多项式乘 $x-a$ 相当于把原多项式向右平移一位，然后每一位减去 $a$ 乘原来这一项的系数。 给多项式除以 $x-a$：设 $h(x)=\frac{g(x)}{x-a}$，则 $$ h(x)(x-a)=g(x)\\ h[x^{i-1}]-ah[x^i]=g[x^i]\\ h[x^i]=\frac{g[x^i]-h[x^{i-1}]}{-a} $$