拉格朗日插值

满足 \(a^k\neq 0\) 的 多项式 \(A(x) = \sum_{i=0}^k a_ix^i\) 是 k 次多项式， 多项式的次数即其系数不为 0 的最高次幂的次数。

至少 k+1 个点可以唯一确定一个 k 次多项式

给定 k+1 个点 \((x_i,y_i)\) 和数 X， 要求求出 f(X)， f 要求满足：

这个 f 可以构造出来， 构造的方法和用于解决模数互质的同余方程的 CRT 算法很像， 即，

其中 I_i 满足 I_i(x_i) = 1 且对于 j≠i， I_i(x_j) = 0.

具体地， \(I_i(x) = \prod_{j\neq i} \frac{x-x_j}{x_i-x_j}\)

拉格朗日插值

原文：https://www.cnblogs.com/tztqwq/p/14198458.html