拉格朗日插值
例题 Luogu P4781【模板】拉格朗日插值
给出 n 个点 P_i(x_i,y_i),将过这 n 个点的最多 n-1 次的多项式记为 f(x),求 f(k) 的值。
方法 1:差分法¶
差分法适用于 x_i=i 的情况。
如,用差分法求某三次多项式 f(x)=\sum_{i=0}^{3} a_ix^i 的多项式形式,已知 f(1) 至 f(6) 的值分别为 1, 5, 14, 30, 55, 91。
第一行为 f(x) 的连续的前 n 项;之后的每一行为之前一行中对应的相邻两项之差。观察到,如果这样操作的次数足够多(前提是 f(x) 为多项式),最终总会返回一个定值,可以利用这个定值求出 f(x) 的每一项的系数,然后即可将 k 代入多项式中求解。上例中可求出 f(x)=\frac 1 3 x^3+\frac 1 2 x^2+\frac 1 6 x。时间复杂度为 O(n^2)。这种方法对给出的点的限制性较强。
方法 2:待定系数法¶
设 f(x)=\sum_{i=0}^{n-1} a_ix^i 将每个 x_i 代入 f(x),有 f(x_i)=y_i,这样就可以得到一个由 n 条 n 元一次方程所组成的方程组,然后使用 高斯消元 解该方程组求出每一项 a_i,即确定了 f(x) 的表达式。
如果您不知道什么是高斯消元,请看 高斯消元。
时间复杂度 O(n^3),对给出点的坐标无要求。
方法 3:拉格朗日插值法¶
在 多项式部分简介 里我们已经定义了多项式除法。
那么我们会有:
这是显然的,因为 f(x)-f(a)=(a_0-a_0)+a_1(x^1-a^1)+a_1(x^2-a^2)+\cdots +a_n(x^n-a^n),这个式子显然有 (x-a) 这个因式,所以得证。
这样我们就可以列一个关于 f(x) 的多项式线性同余方程组:
我们根据中国剩余定理,有:
则 m_i 模 (x-x_i) 意义下的逆元就是:
所以就有:
所以在模意义下 f(x) 就是唯一的,即:
这就是拉格朗日插值的表达式。
如果要将每一项的系数都算出来,时间复杂度仍为 O(n^2),但是本题中只用求出 f(k) 的值,所以在计算上式的过程中直接将 k 代入即可。
本题中,还需要求解逆元。如果先分别计算出分子和分母,再将分子乘进分母的逆元,累加进最后的答案,时间复杂度的瓶颈就不会在求逆元上,时间复杂度为 O(n^2)。
通常意义下拉格朗日插值的一种推导
由于要求构造一个函数 f(x) 过点 P_1(x_1, y_1), P_2(x_2,y_2),\cdots,P_n(x_n,y_n)。首先设第 i 个点在 x 轴上的投影为 P_i^{\prime}(x_i,0)。
考虑构造 n 个函数 f_1(x), f_2(x), \cdots, f_n(x),使得对于第 i 个函数 f_i(x),其图像过 \begin{cases}P_j^{\prime}(x_j,0),(j\neq i)\\P_i(x_i,y_i)\end{cases},则可知题目所求的函数 f(x)=\sum\limits_{i=1}^nf_i(x)。
那么可以设 f_i(x)=a\cdot\prod_{j\neq i}(x-x_j),将点 P_i(x_i,y_i) 代入可以知道 a=\dfrac{y_i}{\prod_{j\neq i} (x_i-x_j)},所以
f_i(x)=y_i\cdot\dfrac{\prod_{j\neq i} (x-x_j)}{\prod_{j\neq i} (x_i-x_j)}=y_i\cdot\prod_{j\neq i}\dfrac{x-x_j}{x_i-x_j}。
那么我们就可以从另一个角度推导出通常意义下(而非模意义下)拉格朗日插值的式子为:
f(x)=\sum_{i=1}^ny_i\cdot\prod_{j\neq i}\dfrac{x-x_j}{x_i-x_j}。
代码实现¶
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
|
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:Ir1d, Marcythm, YanWQ-monad, x4Cx58x54
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用