快速傅里叶逆变换(Inverse FFT) 逆变换（插值） ·输入：给定xo,x1,,xm为m+1次单位根，以及p(xo),…,p(xm) 输出： 多项式的系数ao,a1,…,an 考虑n+1次单位根：0=en+i=cos 2nisin 2m n+1 n+1 DFT:p(ω)=∑=0a5w5 n FFT快速计算DFT的算法 p(x)= j=0 Inverse FFT: 也是一个DFT,唯一区别是把w→ω1，并且前面多了系数1 27 快速傅里叶逆变换 (Inverse FFT) 逆变换（插值） • 输入：给定�!, �*, … , �(为m+1次单位根，以及� �! , … , � �( • 输出： 多项式的系数�!, �*, … , �# 考虑n+1次单位根：� = � IJ KLM - = cos '. #$* + � sin '. #$* DFT: �(�+ ) = ∑%&! # �%�+% FFT:快速计算DFT的算法 Inverse FFT: �+ = * #$* ∑%&! # � �% �)+% 也是一个DFT, 唯一区别是把� → �)*，并且前面多了系数 * #$* 27 � � = - #*$ ( �#�#