拉格朗日插值法

题目描述

~~由小学知识得~~： (n + 1) 个 (x) 坐标不同的点确定唯一的最高次为 (n) 次的多项式 (y = f(n)) 。现在给出 (n + 1) 个点，求出这些点构成的多项式在某一位置的取值

拉格朗日插值法

假设给出的曲线是个二次多项式

[f(x) = ax^2 + bx + c ]

现在有三个已经确定的点 ((x_1, y_1)) ，((x_2, y_2)) , ((x_3, y_3))

代入柿子

[egin{cases} f(x_1) = ax_1^2 + bx_1 + c\ f(x_2) = ax_2^2 + bx_2 + c\ f(x_3) = ax_3^2 + bx_3 +c end{cases} ]

很显然可以用高斯消元求出 (a,b,c) , 时间复杂度 (O(n^3))

但拉格朗日插值法只需要 (n^2)

神奇的构造：

我们需要构造三条曲线 (f_1,f_2,f_3)

对于第一条曲线 (f_1(x))

令 (f_1(x_1) = 1, f_1(x_2) = f_1(x_3) = 0)

对于第二条曲线 (f_2 (x))

令 (f_2(x_2) = 1, f_2(x_1) = f_2(x_3) = 0)

对于第三条曲线 (f_3(x))

令 (f_3(x_3) = 1, f_3(x_1) = f_3(x_2) = 0)

然后

(y_1f_1(x)) 就能保证在 (x_1) 处为 (y_1) ，(x_2，x_3) 处为取值为 0
(y_2f_2(x)) 就能保证在 (x_2) 处为 (y_2) ，(x_1，x_3) 处为取值为 0
(y_3f_3(x)) 就能保证在 (x_3) 处为 (y_3) ，(x_1，x_2) 处为取值为 0

再然后

[f(x) = y_1f_1(x) + y_2f_2(x) + y_3f_3(x) ]

神奇发现这三条曲线就求出了想要的那条曲线

推导

对于上面的三条曲线显然满足性质

[f_i(x_j) = egin{cases} 1~~~(i = j)\ 0~~~(i eq j) end{cases} ]

然后构造出这么个柿子

[f_1(x) = frac{(x - x_2)(x - x_3)}{(x_1 - x_2)(x_1 - x_3)} ]

进一步推广

[f_i(x) = prod_{j eq i}^{jleq n}frac{x - x_j}{x_i - x_j} ]

然后就有了

[f(x) = sum_{i = 1}^{i = n} y_i * f_i(x) ]

P4781 【模板】拉格朗日插值

code

x 取值连续时

当题目要用到的 x 取值是连续的，上面的柿子可以优化到 (O(n))

先列出柿子

[f(k) = sum_{i = 1}^{i = n} y_i * prod_{j eq i}^{jleq n}frac{x_k - x_j}{x_i - x_j} ]

考虑 (O(1)) 求出 (prod_{j eq i}frac{x_k - x_j}{x_i - x_j})

维护 (x_k) 的前缀积和后缀积

[pre_i = prod_{j = 0}^{i} (x_k - x_j)\ suf_i = prod_{j = i}^{n} (x_k - x_j) ]

对于分母，就是个阶乘形式，柿子就成了

[f(k) = sum_{i = 0}^{n}y_ifrac{pre_{i - 1}*suf_{i + 1}}{fac_i * fac_{n - i}} ]

坑：当 (n - i) 为奇数的时候分母为负值

CF622F The Sum of the k-th Powers

code

重心拉格朗日插值法

有毒瘤题目会随时增加或者减少差值点，这个时候曲线就会改变，上面的柿子就需要重新计算了，那么上面的复杂度就会退化成 (n^3) 于是就有了重心拉格朗日插值 ~~(好像牛顿插值法也可以办到 = =)~~

还是前面的柿子

[f(x) = sum_{i = 1}^{n}y_iprod_{i eq j} frac{x - x_j}{x_i - x_j}\ ~~\ = sum_{i = 1}^{n}y_ifrac{prod_{i eq j}{x - x_j}}{prod_{i eq j}{x_i - x_j}}\ ~~\ = sum_{i = 1}^{n}y_ifrac{prod_{i = 1}^{n}(x - x_i)}{prod_{i eq j}(x_i - x_j)*(x - x_i)} ~~\ ~=prod_{i = 1}^{n}(x - x_i)sum_{i = 1}^{n}frac{y_i}{prod_{i eq j}(x_i - x_j)*(x - x_i)} ]

令 $g = prod_{i = 1}^{n}(x - x_i),t(i) = prod_{i eq j}(x_i - x_j) $

然后柿子就成了

[f(x) = gsum^n_{i = 1}frac{y_i}{(x - x_i)*t(i)} ]

对于每加入或减少一个点，可以只 (O(n)) 更新 (t(i))

对于求值，可以 (O(n)) 求出 g，然后套公式就好了

预处理出逆元

时间复杂度 (O(n))

参考资料

如何直观地理解拉格朗日插值法？

拉格朗日插值学习小结

拉格朗日插值学习总结