拉格朗日插值
定义
给定一个多项式函数过点 \((x_i,y_i)\)，求出这个多项式函数的在 \(x=k\) 时的取值。
公式
\[f(k)=\sum_{i=0}^ny_i\prod_{j\not=i}\dfrac{k-x_j}{x_i-x_j} \]时间复杂度 \(O(n^2)\)
横坐标连续的拉格朗日插值
在横坐标连续的情况下，可以做到 \(O(n)\) 插值。
\[\begin{aligned} f(k)&=\sum_{i=0}^ny_i\prod_{j\not=i}\dfrac{k-x_j}{x_i-x_j}\\ &=\sum_{i=0}^ny_i\prod_{j\not=i}\dfrac{k-j}{i-j} \end{aligned} \]不难得到累乘的分子为
\[\begin{aligned} \prod_{j\not=i}(k-j)&=\dfrac{\prod\limits_{j=0}^n(k-j)}{k-i} \end{aligned} \]若设 \(pre_i=\prod_{j<i}(k-j),pre_i=\prod_{j>i}(k-j)\)，那么可得
\[\begin{aligned} \prod_{j\not=i}(k-j)&=\dfrac{\prod\limits_{j=0}^n(k-j)}{k-i}\\ &=pre_i\times suf_i \end{aligned} \]分母的累乘可拆为
\[\begin{aligned} \prod_{j\not=i}(i-j)&=(-1)^{n-i}\times\prod_{j<i}(i-j)\times\prod_{j>i}(j-i)\\ &=(-1)^{n-i}\times i!\times(n-i)! \end{aligned} \]所以可得
\[\begin{aligned} f(k)&=\sum_{i=0}^ny_i\dfrac{pre_i\times suf_i}{(-1)^{n-i}\times i!\times(n-i)!} \end{aligned} \]拉格朗日插值求系数
先提出常数部分
\[a_i=\dfrac{y_i}{\prod\limits_{j\not=i}x_i-x_j} \]可以先 \(O(n^2)\) 求出每一个 \(a_i\)。
然后求一个多项式 \(g(k)=\prod_{i=0}^n(k-x_i)\)，可得递推式为
\[[k^i]g=[k^{i-1}]g-x_i[k^i]g \]注意从大到小递推。
所以可得
\[f(x)=\sum_{i=0}^na_i\times\dfrac{g(k)}{k-x_i} \]考虑快速求出 \(\dfrac{g(k)}{k-x_i}\)。设 \(h(k)=\dfrac{g(k)}{k-x_i}\)，那么有 \((k-x_i)h(k)=g(k)\)。所以有递推式
\[[k^i]g=[k^{i-1}]h-x_i[k^i]h \]移项得
\[[k^i]h=\dfrac{[k^i]g-[k^{i-1}]h}{-x_i} \]于是可以求出
\[f(k)=\sum_{i=0}^na_i\times h(k) \]时间复杂度为 \(O(n^2)\)。
标签：拉格朗,prod,插值,dfrac,sum,笔记,times,aligned From： https://www.cnblogs.com/liuir/p/18002785