看zzq大佬的博客，看到了这个看似很深奥的东西，实际很简单（反正比FFT简单，我是一个要被FFT整疯了的孩子）

拉格朗日插值法

是什么

可以找到一个多项式，其恰好在各个观测点取到观测到的值。这样的多项式称为拉格朗日（插值）多项式
数学上来说，拉格朗日插值法可以给出一个恰好穿过二维平面上若干个点的多项式函数。

定义

概念

一般地，若已知y=f（x）在互不相同n+1个点x0,x1,...xn处的函数值y0,y1,...yn(即该函数（x0,y0）,(x1,y1),...(xn,yn)这n+1个点)
则可考虑构造一个过这n+1个点的、次数不超过n的多项式y=Pn(x),使其满足：
Pn（xk）=yk,k=0,1,...,n(*)
//就是说，对于很多很多个点，我们可以找到一个满足所有点的函数解析式。
要估计任一点v，v！=xi,i=0,1,...,n,则可以用Pn（v）的值作为准确值f(v)的近似值，此方法叫“插值法”。
称式（*）为插值条件（准则），含xi(i=0,1,...,n)的最小区间[a,b]，其中a=min{x0,x1,...,xn},b=max{x0,x1,...,xn}.