浅谈拉格朗⽇插值
在数值分析中，拉格朗⽇插值法是以法国⼗⼋世纪数学家约瑟夫·拉格朗⽇命名的⼀种多项式插值⽅法。许多实际问题中都⽤函数来表⽰某种内在联系或规律，⽽不少函数都只能通过实验和观测来了解。拉格朗⽇插值法可以到⼀个多项式，其恰好在各个观测的点取到观测到的值。这样的多项式称为拉格朗⽇(插值)多项式。 ——百度百科
通俗地说，拉格朗⽇插值法可以出⼀个恰好经过直⾓坐标系内\(n\)个给定点的函数
众所周知，\(n\)个点能唯⼀确定的多项式最⾼次数是\(n-1\)次
这个可以两点确定⼀次函数，三点确定⼆次函数来推出，或者我们由⽅程组有唯⼀解的充要条件也能得出
知道了这个之后我们就容易想到直接⽤⾼斯消元来搞出多项式的系数，但是复杂度消耗太⼤，是\(O(n^3)\)
长翅膀的绵羊
⽽拉格朗⽇插值法就是⼀种⼀般可以在\(O(n^2)\)的复杂度下求出多项式的⽅法(不过通常⽤来求⼀个点值，以下的讲述⼀般以此为参考)
⼀般的拉格朗⽇插值法常州技术师范学院
我们设要求的多项式为\(f(x)\)，点的坐标为\((x_i,y_i)\)，我们要多项式在\(x_0\)处的取值 先上公式，由拉格朗⽇插值法：
\[f(x_0)=\sum_{i=1}^n y_i\prod_{i\not= j} \frac{x_0-x_j}{x_i-x_j}
\]核酸杂交
看起来不是很好理解，其实很简单，我们把原来的某个给定点\(x_k\)代⼊以下有：
\[f(x_k)=\sum_{i=1}^n y_i\prod_{i\not= j} \frac{x_k-x_j}{x_i-x_j}
\]
容易发现，当\(k\not=i\)时，后⾯的\(\frac{x_k-x_j}{x_i-x_j}\)的分⼦总有⼀项是\(0\)，此时\(\prod_{i\not= j} \frac{x_k-x_j}{x_i-
x_j}=0\)
当\(k=i\)时，后⾯的\(\frac{x_k-x_j}{x_i-x_j}\)上下完全相同，此时\(\prod_{i\not= j} \frac{x_k-x_j}{x_i-x_j}=1\)
即对于\(f(x_k)\)来说，这个多项式的确给出了对应的\(y_k\)的值
不难发现这个⽅法对所有点都适⽤，因此它是正确的
从上⾯的式⼦可以看出每次计算要枚举两次，因此复杂度很简单，就是\(O(n^2)\)
在\(x\)取值连续时的插值法
因为很多时候我们做题都是先发现某个函数是多少次的多项式，然后⾃⼰随意取⼀些值代⼊插值
这样的话为了省事横坐标的取值完全可以从\(1\)开始连续取，那么我们把上⾯的式⼦中的\(x_i\)换成\(i\)就有：
\[f(x_0)=\sum_{i=1}^n y_i\prod_{i\not= j} \frac{x_0-j}{i-j}
\]
清华同方中国知网
考虑怎么快速求\(\prod_{i\not= j} \frac{k-j}{i-j}\)，我们分别考虑：
分⼦的话容易发现就是\(\frac{\prod_{t=1}^n x_0-t}{x_0-i}\)
分母⽐较复杂，\(i-j\)的累乘可以分成两个阶乘部分，因此推导⼀下就是\((-1)^{n-i}\cdot i!\cdot(n-i)!\)
这样我们⼀般就可以\(O(n\log n)\)来算了(\(\log\)主要是有求逆元的过程，当然你预处理\(O(n)\)求也没有问题)
重⼼拉格朗⽇插值法
2011四川高考数学
我们考虑到朴素的拉格朗⽇插值每次多加⼊⼀个点时就要整个重新算过，很浪费时间
那么能不能把重复算的⼀些东西利⽤起来？
我们对于
\[f(x_0)=\sum_{i=1}^n y_i\prod_{i\not= j} \frac{x_0-x_j}{x_i-x_j}
\]
把分⼦提取出来，设为\(g=\prod_{i=1}^n x_0-x_i\)，则此时：
\[f(x_0)=g\cdot\sum_{i=1}^n \prod_{i\not= j} \frac{y_i}{(x_0-x_i)(x_i-x_j)}
\]
设⼀个\(t_i=\frac{y_i}{\prod_{i\not= j} x_i-x_j}\)，则：
\[f(x_0)=g\cdot\sum_{i=1}^n \frac{t_i}{x_0-x_i}
\]
因此每次多加⼊⼀个点只需要重新\(O(n)\)算它的\(t_i\)就好了
拉格朗⽇插值的应⽤以及常⽤解题思路
⼀个经典例⼦：⾃然数幂和，即求\(\sum_{i=1}^n i^k\)
之前也提到过⽤第⼆类斯特林数做的⽅法，但那种⽅法是\(O(k^2)\)的，不够优秀
但是现在我们观察这个式⼦，如果不看求和的话\(i^k\)就是⼀个\(k\)次多项式
那么前缀和(其实就是差分)之后，次数要\(+1\)，即此时答案为⼀个关于\(n\)的\(k+1\)多项式
那我们直接代⼊\(k\)个值(取值连续，反正⾃⼰定)之后插值算即可，复杂度\(O(k\log k)\)
那么很多具体题⽬怎么办呢，⼀般就是先推出某个式⼦，然后证明它是关于某个⾃变量的多少次函数(⼀定要判断出次数！)，然后⾃⼰选⼀些点(⼀般是连续的)代⼊插值即可
其实做了⼀些题⽬之后就很套路了
拉格朗⽇插值的模板
模板看Luogu P4781 【模板】拉格朗⽇插值 ，就是⽤⼀般的\(O(n^2)\)来做就好了
CODE
#include
#define RI register int
#define CI const int&
using namespace std;
const int N=2005,mod=998244353;
int n,x[N],y[N],k;
inline int sub(CI x,CI y)
{
int t=x-y; return t<0?t+mod:t;
}
成温立交桥
inline int inv(int x,int p=mod-2,int mul=1)
{
for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul; }
inline int Lagrange(CI n,int *x,int *y,CI k)
{
int ret=0; for (RI i=1;i<=n;++i)
{
int s1=1,s2=1; for (RI j=1;j<=n;++j) if (i!=j)
s1=1LL*s1*sub(k,x[j])%mod,s2=1LL*s2*sub(x[i],x[j])%mod;
(ret+=1LL*y[i]*s1%mod*inv(s2)%mod)%=mod;
}
return ret;
}
int main()
{
scanf("%d%d",&n,&k); for (RI i=1;i<=n;++i) scanf("%d%d",&x[i],&y[i]); return printf("%d",Lagrange(n,x,y,k)),0;
}
⼀些⼊门例题
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议