这篇blog记录一下快速傅里叶变换。它非常的经典，将之前我学到的一些数学知识串在了一起。
关于介绍FFT的分享实在是太多了，我只是芸芸众生中之一，这次就按照自己喜欢的方式来整理了。事情的来源来自于大一学高等代数，其中讲授了“拉格朗日插值法”。光看教材我当时很奇怪，因为那是在讲多项式的一章，只是顺道提了一句。从当时的角度来看，这种插值方法构造的插值基函数，可以将$n+1$个点串成一个$n$次曲线。它表示为：
用插值基函数这个说法，来源于数值分析，他们看起来就像开关一样，当$x=x_i$时，$L_n(x)=y_i$。这样保证构造出的多项式通过了每个数据点。当时的我只能想到这一层，大一下，有一个程序设计基础的大作业，有一个bmp图像的放大缩小，在插值方式中我实现了一次拉格朗日插值（MD那个最后换作业题了，气死我了）。实际上，在那个实现里，我只是想关于三个点计算一个二次函数，好让放大或缩小后的坐标可以带入得到像素值。这个操作与一般的系数表达不同，它转化成了点值表示，也就是说，我并不需要写出二次函数的$ax^2+bx+c$然后带入$x$，我只需要写成$(x-x_1)(x-x_2)$然后带入，后面我们会看到这样的方便。但是在后面的内容和FFT里，带入其他的$x$不是重点。
实际上拉格朗日插值和线性方程组密切相关。之前学的时候，可以用数学归纳法推出拉格朗日插值。现在我们换一种更直接的方法：
考虑$x_0,x_1,…,x_n$个$n+1$个互不相同的数，它们与$y_0,y_1,…,y_n$组对，设存在一个多项式使得$f(x_i)=y_i$，假设它是$f(x)=a_0+a_1x+…+a_nx^n$，根据要求，可得线性方程组：
写成矩阵形式，我们发现：
左侧的系数矩阵的行列式是一个范德蒙德行列式，它的值我们直接给出：
由于$x_0,x_1,…,x_n$互不相同，所以行列式不为零，由$Cramer$法则，线性方程组有唯一解，可以解得，方程组的解恰好是前面所说的拉格朗日插值基，过程这里从略了。这个操作的意义是，把系数和求值联系在了一起。现在我们把视线放回上一篇的DFT：
我们记旋转因子$W^{k\times n}=e^{-j\frac{2\pi}{N}kn}$，这样上式的形式就变得更一目了然：
我们发现，它实际上也可以看成一个多项式，写成前面的形式即：
在这里，我们选取的$\left\{ x_i \right\} $变成了$n$次单位根
