Lagrange 插值

标签：dots ell limits 插值 多项式 因式 Lagrange prod

给定 \(n\) 个横坐标不同的点，求过这 \(n\) 个点的 \(n-1\) 次多项式。

算法引入

这可以直接用高斯消元做，但是时间复杂度 \(\mathcal O(n^3)\) 不可接受，我们需要优化。
我们令 \((x_1,y_1),(x_2, y_2),\dots,(x_t, y_t)\) 为这些点。考虑构造一个函数 \(\ell_j(x)\) 满足

\[\ell_j(x)=\begin{cases} 1 &x=x_j\\ 0 &x\not=x_j \end{cases} \]

如果有这样一个函数，则该多项式可以表示为 \(F(x)=\sum\limits_{j=1}^{t}y_j\ell_j(x)\)。问题的关键变成如何构造这样一个 \(\ell _j(x)\)。
先来看看 \(\ell_j(x)\) 需要满足什么性质：

1. 是多项式函数
2. 最高次小于等于 \(n-1\)
   当 \(j\) 等于 \(1,2,\dots,j-1,j+1,j+2,\dots,t\) 时，\(\ell_j(x)=0\)。所以很显然的有 \(\ell_j(x)\) 中有 \(\prod\limits_{i\not=j}(x-x_i)\) 这个因式。又由于该因式的最高次为 \(n-1\)，则 \(\ell_j(x)\) 为该因式的倍数。

\([x_j]\prod\limits_{i\not=j}(x-x_i)=\prod\limits_{i\not=j}(x_j-x_i)\) ，\(\ell_j(x)=1\)，所以就有了如下式子

\[\ell_j(x)=\prod\limits_{i\not= j}\dfrac{x-x_i}{x_j-x_i} \]

再与前式整合，得到

\[F(x)=\sum\limits_{j=1}^ty_j\prod_{i\not=j}\dfrac{x-x_i}{x_j-x_i} \]

至此，我们就解决了如上问题。

标签：dots,ell,limits,插值,多项式,因式,Lagrange,prod
From： https://www.cnblogs.com/cqbzljh/p/18408265