§6快速傅立叶变换/ Fast Fourier Transformη 问题的背景/ background 傅立叶变换—函数展开为三角级数 设/(x)周期为,在10?m1L江为三角级数∑Ce, 其中G为复 总之要进行形型xWM笔时要取 级数的前 的计算,已e (3)重合。 即:给定[0,∠ 上的函 数值f=∫(x) m疋值条件S(x)∫。 Discrete C=∑几c (24 k=0 0“yN器器 个未知数 f=∑C,e (2 (k=0,1,…,N-1) nverse of DET j=0§6 快速傅立叶变换 /* Fast Fourier Transform */  问题的背景 /* background */ 傅立叶变换 —— 函数展开为三角级数 设 f(x) 周期为2，在 [0, 2 ] 上展开为三角级数 ， 其中Cj 为复系数， ，则实际计算时要取 级数的前 N 项，并要求在区间的N 个等分点上与f(x)重合。   0 ( ) j i jx j C e e j x i j x i jx cos sin ( )   即：给定[0, 2 ] 上N 个等分点 上的函 数值 ，令 满足插值条件 。 ( 0,1, ..., 1) 2  k k  N  N xk  ( ) k xk f  f     1 0 ( ) ( ) N j i jx j S x C e k k S( x )  f N 个未知数 N 个方程 ( 0, 1, ... , 1) 1 1 0 2              f e j N N C N k k N i j j k  Discrete Fourier Transform ( 0, 1, ... , 1) 1 0 2             f C e k N N j k N i j k j  Inverse of DFT 总之要进行形如 的计算，其中 已知，     1 0 N k k j C j xk W xk          N i W e 2