拉格朗日插值


给出 个点 ,将过这 个点的最多 次的多项式记为 ,求 的值。

方法 1:差分法

差分法适用于 的情况。

如,用差分法求某三次多项式 的多项式形式,已知 的值分别为

第一行为 的连续的前 项;之后的每一行为之前一行中对应的相邻两项之差。观察到,如果这样操作的次数足够多(前提是 为多项式),最终总会返回一个定值,可以利用这个定值求出 的每一项的系数,然后即可将 代入多项式中求解。上例中可求出 。时间复杂度为 。这种方法对给出的点的限制性较强。

方法 2:待定系数法

将每个 代入 ,有 ,这样就可以得到一个由 元一次方程所组成的方程组,然后使用 高斯消元 解该方程组求出每一项 ,即确定了 的表达式。

如果您不知道什么是高斯消元,请看

高斯消元

时间复杂度 ,对给出点的坐标无要求。

方法 3:拉格朗日插值法

多项式部分简介 里我们已经定义了多项式除法。

那么我们会有:

这是显然的,因为 ,这个式子显然有 这个因式,所以得证。

这样我们就可以列一个关于 的多项式线性同余方程组:

我们根据中国剩余定理,有:

意义下的逆元就是:

所以就有:

所以在模意义下 就是唯一的,即:

这就是拉格朗日插值的表达式。

如果要将每一项的系数都算出来,时间复杂度仍为 ,但是本题中只用求出 的值,所以在计算上式的过程中直接将 代入即可。

本题中,还需要求解逆元。如果先分别计算出分子和分母,再将分子乘进分母的逆元,累加进最后的答案,时间复杂度的瓶颈就不会在求逆元上,时间复杂度为

由于要求构造一个函数 过点 。首先设第 个点在 轴上的投影为

考虑构造 个函数 ,使得对于第 个函数 ,其图像过 ,则可知题目所求的函数

那么可以设 ,将点 代入可以知道 ,所以

那么我们就可以从另一个角度推导出通常意义下(而非模意义下)拉格朗日插值的式子为:

代码实现

横坐标是连续整数的拉格朗日插值

如果已知点的横坐标是连续整数,我们可以做到 插值。

设要求 次多项式为 ,我们已知 ),考虑代入上面的插值公式:

后面的累乘可以分子分母分别考虑,不难得到分子为:

分母的 累乘可以拆成两段阶乘来算:

于是横坐标为 的插值公式:

预处理 前后缀积、阶乘阶乘逆,然后代入这个式子,复杂度为

给出 ,求 取模的值。

本题中,答案是一个 次多项式,因此我们可以线性筛出 的值然后进行 插值。

贡献者:@Tifa@rui_er@AtomAlpaca@qwq@kenlig@Early@Peanut-Tang@Yiming@mgt@EndlessCheng@Chrogeek@Henry-ZHR@Lee@Xeonacid

本页面最近更新:2/3/2023, 12:00:00 AM更新历史

发现错误?想一起完善? 在 GitHub 上编辑此页!

本页面的全部内容在 CC BY-SA 4.0SATA 协议之条款下提供,附加条款亦可能应用

评论

0 条评论
未登录用户


Copyright © 2016 - 2023 OI Wiki Team

最近更新:fd2ec2c, 2023-02-03

联系方式:Telegram 群组 / QQ 群组