快速傅里叶变换(FFT)（下篇）（完结撒花）

回到方程

通过FFT，我们知道了怎么通过系数表示法转换为值表示法。

在这里插入图片描述

现在需要反过来，把值表示转换为系数表示。

我们一般称这个过程为插值。

这下要疯狂起来了。

看起来反过来插值还是比较困难的，我们再后退一步，从另一个角度审视，

实际上求值和插值是紧密联系的，

逆FFT

在这里插入图片描述

回忆我们之前可以把求值表示为矩阵-向量乘积，我们用系数向量乘以点对应的（范德蒙德）矩阵，从而得到对应点的值。

因为FFT中xk是对应的第k个n次方根，所以我们可以把这个矩阵乘法改写如下。

整个矩阵称为离散傅里叶变换（DFT）矩阵，

在这里插入图片描述

实际上大部分教科书或者算法都把FFT称为快速计算DFT和向量乘法的计算。我们刚才说在n次方处求值，实际上就是DFT矩阵和向量乘法的特例。

正因此我们可以用FFT。利用这种解释，插值也变得非常易于理解。

也不就是把这个DFT矩阵求了个逆么！

插值实际上就是给了给定位置的函数值，计算函数的系数。写作矩阵就是DFT矩阵的逆和值表示向量相乘。

我们直接看这个矩阵的逆长啥样，这里过程复杂，省略了代数过程。因为这讲起来又是另一篇文章了。

不过你瞅瞅这矩阵，有没什么想法？

事实上：这个矩阵的逆和原来的DFT矩阵看起来几乎一模一样！

实际上我们只需要把原来的w换成1/n*w^(-1)即可，

这表明我们几乎可以在插值问题上套用FFT，

我们直接对比下区别是啥，在求值过程中我们通过多项式系数系数和算法，计算n次单位根处的函数值，这实际上就是DFT矩阵和系数向量的乘法，其中w=e^(2*pi*i/n)

在这里插入图片描述

而在插值过程中，我们实际上使用逆FFT算法，逆FFT的输入是多项式在n次单位根处的函数值，输出是多项式的系数。

即反向操作FFT算法

我们前面已经看到了，我们需要做一个DFT矩阵的逆和向量的乘法，求DFT矩阵的逆，我们只需把原来矩阵中的w换成1/n*w^(-1)，

妙就妙在，这意味着逆FFT矩阵实际上和FFT的操作一模一样，只是右边的向量变臭了值表示向量，而且w换成了1/n*w^(-1)。

就这样，我们就得到了可以计算插值的逆FFT算法。

在这里插入图片描述

FFT和逆FFT

对于逆FFT，我们只需要把FFT的代码实现复制一份，把递归调用换成IFFT，然后，只需要改一行代码，一行。

然后就完事了。

总结

我们用多项式乘法问题提出了FFT算法，

第一个点子是，把多项式用对应点的值表示，

多项式的值表示我们需要选取一系列合适的点来求值， 我们首先利用的想法是利用相反数来保证点对出现，

在这里插入图片描述

不过这样递归就不好算了，除非我们用复数。

第二个点子是，我们用1的n次单位复根，这样每次平方完，他们还是正负成对出现的，这个点子利用了单位复根的特性，实际上就是FFT的核心思想，当我们反过来要做插值时，我们发现了一个惊人的事实，逆FFT实际上是一模一样的思想，只是有一行代码不同。

我们用了4个天才般的点子，才解决了这个问题。

FFT牛逼就完事了！