首页 > 技术文章 > 拉格朗日插值

tztqwq 原文

满足 (a^k eq 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(x_1) = y_1 \ f(x_1) = y_1 \ vdots \ f(x_{k+1}) = y_{k+1} ]

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

[f(x) = sum_{i=0}^{k+1} y_i I_i(x) ]

其中 Ii 满足 Ii(xi) = 1 且对于 j≠i, Ii(xj) = 0.

具体地, (I_i(x) = prod_{j eq i} frac{x-x_j}{x_i-x_j})

推荐阅读