9-3-快速傅里叶变换FFT
一句话概括
离散傅里叶变换(DFT)就是乘以傅里叶矩阵 ,朴素算法要 次运算;FFT 用一个分治恒等式把 点变换拆成两个 点变换,得到递推式 ,解出 。当 时,这意味着运算量相差数万倍——这不是"优化",而是"从不可行变成可行"。
本篇覆盖:傅里叶矩阵的构造 → 次单位根的性质 → 的酉性(含 完整验证)→ DFT 作为矩阵乘法 → 朴素 DFT 的 → FFT 的分治恒等式与复杂度分析 → 的完整手工推导 → FFT 为什么改变世界 → 频率视角下的线性代数 → 可运行的 numpy 代码(含手写朴素 DFT 与计时对比)。
一、定义
1.1 次单位根
定义 1.1( 次单位根,-th root of unity) 满足 的复数 称为 次单位根。它们恰好有 个:
其中最基本的一个(称为本原 次单位根,primitive -th root of unity)记作
于是全部 个单位根可以写成 。
1.2 傅里叶矩阵
定义 1.2(傅里叶矩阵,Fourier matrix) 设 ,。定义 复矩阵 为
显式写出:
关于记号的一个提醒
不同教材对傅里叶矩阵的定义有两处常见差异:
1. 指数符号:有的写 (本篇采用),有的写 。这只是约定 取 还是 的差别,两者互为共轭。
2. 归一化因子:有的定义中带 ,有的不带。本篇不带,因此 而不是 。
引用任何教材的 FFT 公式前,务必先确认它用的是哪一种约定。这也是本篇易错点里要专门讲"忘记归一化因子"的原因。
1.3 离散傅里叶变换
定义 1.3(离散傅里叶变换,Discrete Fourier Transform,DFT) 对向量 ,定义其 DFT 为
逐项写出:
逆变换(由 ,见定理 3.2):
1.4 FFT 的定义
定义 1.4(快速傅里叶变换,Fast Fourier Transform,FFT) FFT 不是一个新的变换,而是计算 DFT 的一族快速算法。它利用 次单位根的对称性,把 点 DFT 递归地分解为两个 点 DFT,从而把计算量从 降到 。
FFT DFT
这是初学者最常混淆的一点。
- DFT 是数学对象:一个把 映到 的线性变换,矩阵是 。
- FFT 是算法:一种在 时间内算出 的方法。
二者的输出完全相同(在精确算术下),只是计算代价不同。就像"求 "是一个数学问题,"反复平方"是解决它的算法。
二、几何直观
2.1 次单位根把单位圆 等分
的模为 ,辐角为 。由 9-1 节的定理(乘法 模相乘、角相加):
的模仍为 ,辐角为 。所以 是复平面单位圆上的 个等分点,它们构成一个正 边形的顶点。这个几何图像是理解全部 FFT 内容的底座。
几个小例子:
- :,两个点是 (单位圆直径的两端)。
- :,三个点构成等边三角形。
- :,四个点是 (内接正方形)。
- :八个点构成正八边形,其中恰好包含 的四个点(因为 )——这个"嵌套"结构正是 FFT 分治的几何来源。
2.2 傅里叶矩阵的列 = "不同频率的采样"
的第 列是
把它看成"对复指数信号 在 个等距时刻 的采样"。当 从 增到 :
- :,零频率(常数信号,直流分量);
- : 绕单位圆走一圈,最低的正频率;
- :走两圈,频率翻倍;
- :走 圈,这是最高的可分辨频率(Nyquist 频率),此时采样值交替为 ;
- :走超过 圈,但从采样点上看与某个低频信号无法区分(这就是混叠,aliasing 现象的来源)。
正交性意味着这些"频率"互不干扰: 的列两两正交(定理 3.2),所以不同的频率成分可以独立提取。这就是傅里叶分析的全部基础。
2.3 DFT 在做什么:换一组基
由 9-2 节的结论, 是酉矩阵,它的列构成 的一组标准正交基——即频率基。
因此 可以这样理解:
第 个分量 就是信号 在频率方向 上的(未归一化的)投影。
用第四章的语言说:DFT 就是"把信号投影到频率基上,读出每个频率的系数"。用几何语言说:DFT 是一次基变换,从"时间基"(标准基 ,每个向量表示"某一时刻的值")换到"频率基"(每个向量表示"某个频率的成分")。 信息一点没丢,只是换了描述方式。
这就是"频率视角下的线性代数":傅里叶分析不属于"另一种数学",它就是我们一直在学的"投影到正交基上求坐标",只不过基向量是复指数而不是 。
三、性质与定理
3.1 次单位根的性质
定理 3.1(单位根的基本性质) 设 。则:
| 编号 | 性质 | 说明 |
|---|---|---|
| (R1) | 周期性 | |
| (R2) | 落在单位圆上 | |
| (R3) | 共轭即倒数(因为模为 ) | |
| (R4) | 降幂公式,把高次幂换成共轭 | |
| (R5) | 指数相加 | |
| (R6) | 关于 与 对称 | ,故 ( 是对称矩阵) |
| (R7) | 指数可按模 化简 | |
| (R8) | 是 次本原单位根( 偶数时)—— FFT 的关键 |
证明 (R3): ,故 。
证明 (R4): 由 (R1) 与 (R3):;又由 (R3) 。
证明 (R8): 这是 FFT 分治的核心。直接验算:
而 正是 次本原单位根的定义式。于是对任意整数 :
证明 (R6): ,故 。傅里叶矩阵是对称矩阵——这条性质很实用,因为 ,也就是"共轭转置 逐元素取共轭",少一步转置。
几何含义((R6) 的推广): 次单位根在复平面上构成正 边形,因此具有正 边形的全部对称性。特别地,把全部 个单位根相加:
这就是"正 边形的顶点向量之和为零向量"。更一般地,由引理 3.3 的求和公式(下面给出)可以处理任意幂次。
引理 3.2(单位根求和公式) 对任意整数 ,
证明:
情形 : 令 ,则 , 项相加得 。
情形 : 令 ,两边同乘 :
由 ,右端 。故 。而 ,故 。
这是一个等比级数求和的结论(首项 、公比 , 项和 ),写出来是为了让 的情形(分母为零)也被覆盖。
3.2 傅里叶矩阵是酉矩阵
定理 3.3 对每个 ,
因此 是酉矩阵,且
(最后一步用了 。)
适用条件: 必须取本原 次单位根 。
证明: 计算 的第 元素。 的第 行是 第 列的共轭,而 第 列的第 个元素是 ,故 第 行第 个元素为 (用 (R3))。于是
由引理 3.2 取 。因为 ,所以 ,其中只有 满足 。故
即 。两边除以 :,所以 是酉矩阵。又由 两端左乘 得 ,即 。
推论 3.4(Parseval 恒等式,离散形式) 对任意 ,令 ,则
若使用归一化的 ,则 (完全保能量)。
证明: 。
3.3 的完整列正交验证
时 ,故 、、、、,于是
四列分别为
(1) 各列长度平方。
四列长度都是 ,长度平方都是 。✓
(2) 内积(下面是 对,逐一验证)。
:
:
:
(3) 结论。 四列两两正交、长度平方均为 ,所以
与定理 3.3 完全一致。
(4) 逆矩阵。
注意 与 的差别仅仅是把 换成 ,也就是第 2 行与第 4 行互换。正向变换与逆变换的算法结构几乎完全一样——这是 FFT 实现上的一个重要事实(np.fft.ifft 与 np.fft.fft 共用同一套代码,只差一个共轭和一个 )。
3.4 FFT 的分治恒等式
这是本篇的核心定理。
定理 3.5(FFT 分治恒等式 / Danielson–Lanczos 引理) 设 为偶数,。对任意 ,记
(两个都是 中的向量),并记 、(两个 点 DFT)。则对 :
适用条件: 为偶数(这样才能分成两个等长的子问题)。对合数 还可以进一步按其他因子分解(混合基 FFT); 为 的幂时递归最干净,这是 FFT 在工程上偏爱" 的幂次长度"的原因。
完整证明:
从 DFT 的定义出发,把求和按下标的奇偶拆成两组:
第一步:把偶数项写成 ()。
由 (R8), 正是 次本原单位根。所以右边的求和恰好是"对向量 做的 点 DFT 的第 个分量":
第二步:把奇数项写成 ()。
(把公因子 提到求和号外面,剩下的部分正是对 的 点 DFT 的第 个分量。)
第三步:合并,得到前半部分。
第四步:处理后半部分 。
关键是利用单位根的周期性 (R7):
最后一步用了 。
所以
在偶数项取 、奇数项取 ,于是同样按奇偶分组:
这里还用了一个重要的事实: 中提出来的那个因子是
所以
注意 (3.5b) 中的 与 的下标仍然是 (不是 ),因为 点 DFT 的输出只有 个分量,下标按模 循环——这由 (R8) 中 的周期性保证。
这条恒等式在说什么
一个 点 DFT 的输出,可以由两个 点 DFT 的输出"拼"出来:
- 前一半 用"加法"拼;
- 后一半 用"减法"拼;
- 拼接时奇数部分要乘上旋转因子(twiddle factor)。
这个"加一次、减一次"的结构在算法图上画出来像一只蝴蝶,所以被称为蝶形运算(butterfly operation)。它是 FFT 的基本积木块。
3.5 FFT 的矩阵形式:分块分解
定理 3.5 可以写成矩阵形式。定义置换矩阵 (把偶下标和奇下标分开):
再定义对角矩阵 (旋转因子):
则由 (3.5a) 与 (3.5b):
因为我们要的是恒等式对所有 成立,所以可以去掉 ,写成矩阵分解:
验证前一半分量():
验证后一半分量:
这个分解的三大好处
1. 它证明了递归的合法性: 可以完全由 和两个简单矩阵(对角矩阵 与置换矩阵 )表示。所以"算 "可以归约到"算两次 "。
2. 它给出了复杂度: 与 都只有 个非零元素,乘以它们只要 次运算(不是 !)。
3. 它把 的分解写成了 / 那样的"因式分解"。事实上把递归展开到底, 被分解成 个稀疏矩阵的乘积——这正是 FFT 算法的全部内容。
对照 附录-矩阵分解总览 里的其他分解: 化三角、 化正交、 化对角,而 FFT 是把 化为 个稀疏矩阵的乘积。目标不同,但"分解结构 = 加速计算"这个思想完全一致。
3.6 复杂度分析
定理 3.6(FFT 的复杂度) 当 时,用 FFT 计算 点 DFT 需要
次复数运算。而朴素 DFT 需要 次。
证明(递推 + 主定理):
设 为用 FFT 计算 点 DFT 所需的运算次数。
第一步:写出递推式。 由定理 3.5,计算 点 DFT 需要:
- 做两次 点 DFT:成本 ;
- 做置换 (把奇偶下标分开):(只是重新排列,不需要算术运算);
- 算旋转因子 ( 个乘法):;
- 做 次加法和 次减法:。
所以
其中 是某个常数。递归的终止条件是 ( 点 DFT 就是恒等变换,)。
第二步:用主定理(Master Theorem)求解。 主定理针对形如
的递推式。这里 、、,因为
这属于主定理的第二种情形( 与 同阶),结论是
第三步:直接验证(不依赖主定理)。 展开递推 层:
规律明显:第 层展开后是
取 ,此时 ,:
每一层的总工作量都是 (因为子问题数量翻倍的同时规模减半),一共有 层,所以总工作量是 。
为什么"每层总工作量恒定"是关键
递推 的解是 而不是 ,全靠"子问题数量翻倍与规模减半恰好抵消":
| 层号 | 子问题个数 | 每个子问题规模 | 该层总工作量 |
|---|---|---|---|
| 0 | 1 | | |
| 1 | 2 | | |
| 2 | 4 | | |
| | | | |
| | | 1 | |
一共 层,每层 ,总计 。
对比:朴素 DFT 没有任何"抵消"——它是 个输出,每个输出要做 次乘加,一共 次。分治之所以有效,是因为它把"每个输出都要看全部输入"这个 的表格,改写成了"每层只看 个数据"的 层流水线。
3.7 复杂度差距的实际意义
| 朴素 DFT() | FFT() | 倍数 | |
|---|---|---|---|
" 时相差数万倍"是什么意思? 假设一次复数运算耗时 纳秒(这是相当乐观的估计):
- 朴素 DFT: 次运算 秒 分钟;
- FFT: 次运算 秒。
而如果 (一段约 1 秒的 CD 音质音频,44.1 kHz 采样约有 个点/秒, 点约 秒):
- 朴素 DFT: 次运算 秒 小时;
- FFT: 次运算 秒。
这不只是"快了 43 万倍",而是"从不能用到能用"的差别。 没有 FFT,实时音频处理、医学成像(CT/MRI 重建)、无线通信(OFDM)、雷达信号处理全部都是不可能的——它们的共同特点是要求"每秒处理几十万到几百万个采样点"。 在这些场景下连一个采样块都处理不完。
算法复杂度为什么是线性代数课的内容
Strang 把 FFT 放进线性代数课,是因为它完美展示了"看清矩阵的结构 找到加速算法"这条主线:
- 是一个 的稠密矩阵,直接乘它要 次运算;
- 但 有极强的递归结构 ;
- 利用这个结构, 实际上等于 个稀疏矩阵的乘积,每个只有 个非零元。
"稠密矩阵 × 向量"一般要 ,但"稀疏矩阵 × 向量"只要 ,其中 表示非零元素的个数。 把稠密问题转化成"一串稀疏问题",就是全部快速算法的套路。这与第 11 章讲的"利用 的稀疏性做迭代求解"是同一个思路。
3.8 单位根的深一层:群结构、本原根与几何分布
3.1 节列出了单位根的八条性质,这一节把它们放进"群"的语言里重新组织——因为 FFT 的每一个分治步骤,本质上都是单位根群结构的推论。
(1) 次单位根构成一个循环群。
记
则 在乘法下封闭、有单位元 、每个元素有逆元,因此构成一个群;又因为每个元素都是 的幂,它是循环群, 是它的生成元:
封闭性验证: ✓(第四个等号用了 (R7):指数可按模 化简)。
逆元: 由 (R3)(R4), ✓。特别地 。
群结构为什么对 FFT 重要
FFT 的两条核心事实都是群论事实:
- " 是 次本原单位根"(性质 (R8))说的是 是 的子群,而且恰好是"偶次幂"那一半;
- "" 说的是 中阶为 的那个唯一元素,它正是蝶形运算里那个"加一次、减一次"的符号来源。
分治之所以可行,是因为" 等分点里天然嵌套着 等分点"——这是几何上的自相似,也是代数上的子群。
(2)本原单位根与欧拉函数。
定义 3.8 若 的阶(使 的最小正整数 )恰好等于 ,则称 是本原 次单位根。
定理 3.9(本原根的判据) 是本原 次单位根,当且仅当 。因此本原 次单位根的个数为欧拉函数 。
证明: 令 。设 为正整数,则
(最后一步用了 ,所以 必须整除 。)于是 的阶是 ,它等于 当且仅当 ,即 。
这条定理的价值:它告诉你哪些 可以拿来当"生成元"去搭建傅里叶矩阵。 为素数时,除 外的 个元素全是本原根。
(3)单位根在复平面上的几何分布。
次单位根就是单位圆上辐角为 的 个点,它们构成正 边形的顶点。三条几何性质:
| 几何事实 | 代数表达 | 依据 |
|---|---|---|
| 关于实轴上下对称 | (R4) | |
| 顶点向量之和为零向量 | () | 引理 3.2 取 |
| 为偶数时,对径点成对出现 |
的完整列表():
| 辐角 | 代数式 | 是否是本原根 | 在单位圆上的位置 | |
|---|---|---|---|---|
| ✗(阶为 ) | ||||
| ✓(阶为 ) | ||||
| ✗(阶为 ) | ||||
| ✗(阶为 ) | ||||
| ✗(阶为 ) | ||||
| ✓(阶为 ) | ||||
| —— | 回到起点 |
,本原根恰好是 与 ✓ 与定理 3.9 一致。
(4)子群嵌套:FFT 分治的代数根源。
定理 3.10 设 。则 是本原 次单位根,并且
证明: 记 。则 ,所以 ;又 (因为 ),故 的阶为 ,是本原 次单位根。
取 ( 偶数): 是本原 次单位根——这正是性质 (R8),也就是蝶形分解的全部依据。"8 等分点里嵌套着 4 等分点,4 等分点里嵌套着 2 等分点",递归由此而生。
(5)正交关系(character orthogonality) 对 ,
这正是 的分量形式(把定理 3.3 的证明用指标 重写一遍即可)。用群论的话说:单位根这 个"特征标"两两正交。它同时是"傅里叶基正交"与"不同频率互不干扰"的数学表达。
如果 不是本原单位根会怎样
傅里叶矩阵的全部结论都依赖 是本原根。举个例子:取 但错误地令 (这是 次本原单位根,不是 次的),此时"矩阵" 是
第 、 行完全相同,第 、 行完全相同,故 : 不可逆,更谈不上酉性,用它做"变换"会丢失一半信息。
教训:写 FFT 代码时 必须是 (numpy 里是 ),并且变换长度 必须与 的分母一致。这是"补零 / 分帧"时最容易出错的地方。
3.9 傅里叶矩阵酉性的完整验证:行正交与一般
3.3 节验证了 的列正交。这里补上两件事:行也正交(即 ),以及 为任意值时的一般论证。
(1)一般 的行正交性。
定理 3.11 对每个 ,。
证明: 注意由性质 (R6), 是对称矩阵(),所以
即"共轭转置"退化成"逐元素取共轭"。计算 的第 个元素:
(用了 ,即 (R3)。)合并指数:
由引理 3.2 取 ,并注意 时只有 能被 整除:
即 。
因为 是方阵, 与 互为推论(左逆等于右逆)。所以列正交与行正交是同一件事,不需要分开验证。
(2)四个直接推论。
| 编号 | 结论 | 推导 |
|---|---|---|
| (D1) | 是酉矩阵 | |
| (D2) | 由 两端左乘 | |
| (D3) | ||
| (D4) | , | 由 (R6): |
(3)数值验证()。 下面这段代码同时验证 、,以及本篇例题 6 将要证明的 ( 是反序置换矩阵):
import numpy as np
def fourier_matrix(n, sign=+1):
"""按 (F_n)_{jk} = exp(sign * 2*pi*i*j*k/n) 构造傅里叶矩阵。"""
j = np.arange(n).reshape(-1, 1)
k = np.arange(n).reshape(1, -1)
return np.exp(sign * 2j * np.pi * j * k / n)
for nn in [2, 3, 4, 6, 8]:
Fn = fourier_matrix(nn)
Prev = np.zeros((nn, nn)) # 反序置换:把下标 j 映到 -j (mod n)
for jj in range(nn):
Prev[jj, (-jj) % nn] = 1.0
print(f"n={nn}: F^H F = nI ?", np.allclose(Fn.conj().T @ Fn, nn * np.eye(nn)),
" F^T = F ?", np.allclose(Fn.T, Fn),
" F^2 = n*Prev ?", np.allclose(Fn @ Fn, nn * Prev))
实测输出(numpy 2.3.5):
n=2: F^H F = nI ? True F^T = F ? True F^2 = n*Prev ? True
n=3: F^H F = nI ? True F^T = F ? True F^2 = n*Prev ? True
n=4: F^H F = nI ? True F^T = F ? True F^2 = n*Prev ? True
n=6: F^H F = nI ? True F^T = F ? True F^2 = n*Prev ? True
n=8: F^H F = nI ? True F^T = F ? True F^2 = n*Prev ? True
五个 全部通过,说明这三条性质不是 的巧合。
(4)为什么" 对称"这件事值得单独记住。
意味着求共轭转置时不需要做转置,只需把每个元素取共轭()。这在工程实现里省掉一次数据搬移,也让"正向变换与逆向变换是同一个程序"这件事变得显式:np.fft.ifft 与 np.fft.fft 的差别只有"取共轭 + 除以 "。
与一般酉矩阵的对比
一般酉矩阵 只满足 ;傅里叶矩阵额外拥有三层结构:
1. 对称:;
2. 元素全是单位根:,且只由 决定;
3. 递归可分:。
第 1、2 条让它"好写",第 3 条让它"快算"。一个矩阵同时具备正交性(保证意义)与稀疏分解(保证速度),这就是 FFT 的全部秘密。
3.10 的分块分解:蝶形图、位反转与第二个算例
例题 1 已经验证过 的分块分解。这一节换两个角度再看它一次:从分解式读出算法图,以及用分组重排(位反转)的观点理解置换矩阵 。
(1)分解式的三层含义。
从右往左读(这正是算法执行的顺序):
| 步骤 | 矩阵 | 做了什么 | 运算量 |
|---|---|---|---|
| ① | 把偶下标与奇下标分开: | 次算术(只是搬数据) | |
| ② | 对前两个数、后两个数各做一次 点 DFT | 次乘法 | |
| ③ | 旋转因子 + 蝶形加减 | 次乘法 次加减 |
蝶形图(数据流从左到右):
x0 ----*-------------------> e0 ----+--------> y0 = e0 + 1*o0
x2 ----*--> [2 点 DFT] --> e1 -------|----+---> y1 = e1 + i*o1
x1 ----*-------------------> o0 -----+ |---> y2 = e0 - 1*o0
x3 ----*--> [2 点 DFT] --> o1 -------------+---> y3 = e1 - i*o1
(偶数组) (奇数组) (蝶形合并)
图中每个""结构就是一次蝶形运算:输入两个数,输出"和"与"差(乘上旋转因子后的差)"。
(2)位反转置换。
时 把下标排成 。把下标写成 位二进制:
把每位的二进制数字左右颠倒:
得到的新顺序恰好是 —— 这就是 的效果。所以 也叫位反转置换(bit-reversal permutation)。
- 递归实现(本篇 4.2 节的写法):在递归过程中不断按奇偶拆分,等价于自动完成位反转,无需显式构造 ;
- 迭代实现(工程上常用):先按位反转把输入重排一次,然后自底向上逐层做蝶形,省掉递归开销。
时位反转顺序是 ——与 4.2 节的说明一致。
(3)第二个算例:。
用分解路径算一遍。
第 1 步:置换。
第 2 步:两次 点 DFT。
第 3 步:乘旋转因子。 ,所以
第 4 步:蝶形合并。
用直接乘法核对: :
两者一致 ✓。
(4)解读与对照。 是"四分之一个周期的正弦波"(离散正弦 的采样)。它的 DFT 只在 与 处非零:
- :频率 的成分,幅值 、相位 ;
- :这是负频率 (因为 )的成分,与 互为共轭 ✓ 符合实信号的 Hermitian 对称性。
Parseval 核对:
| 信号 | 时域形状 | 频域非零位置 | 频率含义 |
|---|---|---|---|
| (例题 1) | 每隔一个取 | 直流 + Nyquist(最高频) | |
| (本例) | 一个完整正弦周期 | 最低频 及其共轭伙伴 |
这张对照表说明了 DFT 的核心现象:时域越"平缓/低频",频域越集中在 小的地方;时域越"剧烈/交替",频域越往高频跑。
3.11 复杂度递推的精确计数与三种解法
3.6 节用主定理与展开法得到了 。这里把常数也算清楚,因为" 记号丢掉了常数",而工程上常数决定一切。
(1) 时的精确计数。
设 ,并把"一次复数乘法"和"一次复数加法"分开计数。
乘法次数 :
- 两次 点 DFT:;
- 旋转因子乘法: 共 个,即 次乘法;
- 蝶形合并只有加减,没有乘法。
加法次数 : 蝶形合并对每个 做一次""和一次"",即 次加法:
(2)展开求解。
以乘法为例,逐层展开:
规律很清楚:展开 层后每一项都贡献 ,总共 :
取 ,此时 、、:
同理对加法:
结论():
(3)与朴素 DFT 的精确对比。
朴素 DFT 要算 , 是稠密的 矩阵:乘法 次、加法 次。
| 朴素乘法 | FFT 乘法 | 倍数 | 朴素加法 | FFT 加法 | 倍数 | |
|---|---|---|---|---|---|---|
注意 那一行:FFT 在乘法上只省了 倍,加法上几乎没省( 对 )。这就是例题 1 第 7 步说的"小规模时 FFT 不划算"——递归调用、数组拼接、索引计算的开销远大于省下的几次乘法。FFT 的收益随 增长而急剧放大, 时才开始明显。
(4)三种解法对照(同一个递推,三种视角)。
| 方法 | 做法 | 适合什么时候用 |
|---|---|---|
| 主定理 | 属第二种情形(),故 | 只想快速判断阶,不关心常数 |
| 递归树 | 每层总工作量都是 (子问题数翻倍、规模减半,恰好抵消),共 层 | 需要看清为什么不是 |
| 代入展开 | 逐层写出 ,取 | 需要精确常数(上面的 ) |
(5)为什么递推是 而不是 ?
这是整个 FFT 的关键一问,答案在稀疏性:
- 朴素方法的矩阵 有 个非零元(全是 ),乘一次要 次运算;
- FFT 用到的两个矩阵 与 都很稀疏:
- 每行每列恰好一个 ,共 个非零元;
- 中 贡献 个非零元、 与 各贡献 个,共 个非零元。
- "稀疏矩阵 × 向量"的代价是 ,所以这两步各只要 。
假如 不是对角矩阵会怎样
把 换成一个一般的稠密 矩阵,那么"旋转因子"这一步就要 次运算,递推变成
这属于主定理的第一种情形( 比 高一阶),结论是
与朴素 DFT 同阶,分治完全白做。 所以 FFT 的加速不是来自"分治"本身,而是来自"分治之后每层的合并只用稀疏矩阵"——这是理解全部快速算法(快速矩阵乘法、快速小波、稀疏 FFT)的通用教训:光有分治不够,合并的代价必须足够低。
(6)"每层 "的图像化描述。
一共 层,每层 ,总计 。"翻倍"与"减半"互相抵消,是分治算法能达到 的唯一机制(详见 11-3-迭代方法与预条件 中关于"每步代价"的讨论:迭代法之所以快,也是因为每步只需一次稀疏乘法)。
四、计算方法与步骤
4.1 朴素 DFT 的步骤()
- 给定 ,计算 。
- 预计算所有需要的幂次 (可以递推:,避免重复调用
exp)。 - 对每个 ,累加 。
- 输出 。
代价: 次复数乘法与 次复数加法。
4.2 FFT 的步骤(递归版,)
- 若 ,直接返回 (1 点 DFT 就是恒等)。
- 把 按下标奇偶拆成 与 (各长 )。
- 递归计算 与 。
- 计算旋转因子 ()。
- 对 :
- ;
- 。
- 返回 。
实用要点:
- 尽量取 为 的幂。此时递归每一层都是奇数长度的一半,直到 ,最干净。
- 非 的幂时,可以分解 的因子(混合基 FFT),或者把 补零到最近的 的幂(补零不会改变 DFT 的数学定义,但会改变频率采样的密度——补零相当于对频谱做插值)。
- 迭代实现:把递归改成自底向上。此时需要先按位反转置换(bit-reversal permutation)重排输入。 时下标顺序为 。这就是 MathWorld 提到的"Cooley–Tukey 算法先按位反转重排输入"。
4.3 手工计算 的 FFT 步骤(下一节给出完整推导)
- 写下 与 。
- 写出分块分解 。
- 确定 (把 与 分开)。
- 确定 。
- 写出 。
- 逐层乘出来验证与原 一致。
4.4 用 numpy 做 DFT / FFT(含计时对比)
只用 numpy 即可,np.fft 是 numpy 自带的子模块,无需额外依赖。
import numpy as np
import time
# ============================================================
# 1. 手写朴素 DFT(O(n^2),严格按定义 y_k = sum_j w^{jk} x_j)
# ============================================================
def naive_dft(x):
"""朴素离散傅里叶变换,直接按矩阵定义计算。"""
x = np.asarray(x, dtype=complex)
n = x.shape[0]
k = np.arange(n).reshape(-1, 1) # 形状 (n, 1) 的列,代表输出下标 k
j = np.arange(n).reshape(1, -1) # 形状 (1, n) 的行,代表输入下标 j
W = np.exp(-2j * np.pi * k * j / n) # 形状 (n, n) 的 DFT 矩阵
return W @ x
# ============================================================
# 2. 手写递归 FFT(O(n log n),严格按分治恒等式)
# ============================================================
def recursive_fft(x):
"""递归 FFT,要求 len(x) 是 2 的幂。"""
x = np.asarray(x, dtype=complex)
n = x.shape[0]
if n == 1:
return x.copy()
if n % 2 != 0:
raise ValueError("本实现要求长度为 2 的幂")
# 奇偶拆分
even = recursive_fft(x[0::2])
odd = recursive_fft(x[1::2])
# 旋转因子 w^k, k = 0..n/2-1
w = np.exp(-2j * np.pi * np.arange(n // 2) / n)
t = w * odd
return np.concatenate([even + t, even - t])
# ============================================================
# 3. 三种方法结果一致性验证
# ============================================================
rng = np.random.default_rng(0)
n = 16
x = rng.standard_normal(n) + 1j * rng.standard_normal(n)
y_numpy = np.fft.fft(x)
y_naive = naive_dft(x)
y_rec = recursive_fft(x)
print("numpy vs naive :", np.allclose(y_numpy, y_naive, atol=1e-10))
print("numpy vs recur :", np.allclose(y_numpy, y_rec, atol=1e-10))
print("naive vs recur :", np.allclose(y_naive, y_rec, atol=1e-10))
# 三个都应为 True —— 说明 FFT 与朴素 DFT 在数学上完全等价
# ============================================================
# 4. 直接构造傅里叶矩阵 F_4,验证与 np.fft.fft 一致
# ============================================================
def fourier_matrix(n):
"""按 (F_n)_{jk} = w^{jk} (w = exp(2*pi*i/n)) 构造傅里叶矩阵。"""
j = np.arange(n).reshape(-1, 1)
k = np.arange(n).reshape(1, -1)
return np.exp(2j * np.pi * j * k / n)
F4 = fourier_matrix(4)
print("\nF4 =")
print(np.round(F4, 6))
# 注意:numpy 的 fft 用的是共轭约定 exp(-2*pi*i*jk/n),
# 所以 F4 @ x 等于 np.fft.fft(x) 的“时间反演”,见下方说明。
x4 = np.array([1, 2, 3, 4], dtype=complex)
print("F4 @ x4 =", np.round(F4 @ x4, 6))
print("np.fft.fft(x4) =", np.round(np.fft.fft(x4), 6))
print("conj(F4) @ x4 =", np.round(np.conj(F4) @ x4, 6))
# numpy 的约定是 exp(-2*pi*i*jk/n),即它用的是 conj(F_n),
# 所以 np.fft.fft(x4) 等于 conj(F4) @ x4,而不是 F4 @ x4。
# 验证 F4 是“酉矩阵的 4 倍”
print("\nF4^H F4 = 4I ?", np.allclose(F4.conj().T @ F4, 4 * np.eye(4)))
# ============================================================
# 5. 验证 ± 蝶形结构(分治恒等式)
# ============================================================
n = 8
x = rng.standard_normal(n) + 1j * rng.standard_normal(n)
y = recursive_fft(x)
half = n // 2
even_part = recursive_fft(x[0::2])
odd_part = recursive_fft(x[1::2])
w = np.exp(-2j * np.pi * np.arange(half) / n)
print("\n蝴蝶结构验证:")
print("前半 y[:n/2] = e + w*o ?",
np.allclose(y[:half], even_part + w * odd_part))
print("后半 y[n/2:] = e - w*o ?",
np.allclose(y[half:], even_part - w * odd_part))
# ============================================================
# 6. 计时对比:朴素 DFT vs FFT
# ============================================================
print("\n{:<10} {:>14} {:>14} {:>12}".format("n", "naive (s)", "fft (s)", "speedup"))
for n in [256, 512, 1024, 2048, 4096]:
x = rng.standard_normal(n) + 1j * rng.standard_normal(n)
t0 = time.perf_counter()
naive_dft(x)
t_naive = time.perf_counter() - t0
t0 = time.perf_counter()
np.fft.fft(x)
t_fft = time.perf_counter() - t0
print("{:<10} {:>14.6f} {:>14.6f} {:>12.1f}".format(
n, t_naive, t_fft, t_naive / max(t_fft, 1e-12)))
# 典型输出(具体数值取决于机器):
# n naive (s) fft (s) speedup
# 256 0.0009 0.0000 61.6
# 512 0.0024 0.0000 137.4
# 1024 0.0062 0.0000 278.5
# 2048 0.0231 0.0001 391.4
# 4096 0.0894 0.0001 696.0
# 可以看到:n 翻倍时 naive 耗时约变 4 倍(O(n^2)),
# 而 fft 耗时约变 2 倍多(O(n log n)),差距随 n 迅速拉大。
# ============================================================
# 7. 频率轴:np.fft.fftfreq 的排列顺序
# ============================================================
n = 8
freqs = np.fft.fftfreq(n, d=1.0 / n)
print("\nn =", n)
print("fftfreq 顺序 :", freqs)
# [ 0. 1. 2. 3. -4. -3. -2. -1.]
# 注意!不是从低到高,而是 [0, 正频率..., 负频率...]
# 若要按频率从小到大排列,需要 fftshift:
print("fftshift 之后:", np.fft.fftshift(freqs))
# [-4. -3. -2. -1. 0. 1. 2. 3.]
# ============================================================
# 8. 实信号的 Hermitian 对称性
# ============================================================
x_real = np.array([1.0, 2.0, 3.0, 4.0])
y = np.fft.fft(x_real)
print("\n实信号的 FFT:")
print("y =", np.round(y, 6))
print("y[0] 是实数? ", np.isclose(y[0].imag, 0)) # True:直流分量必为实
print("y[k] = conj(y[n-k]) ?",
np.allclose(y[1:], np.conj(y[:0:-1]))) # True
numpy 的符号约定
numpy 的
np.fft.fft使用的定义是也就是指数上带负号,对应本篇的 (因为本篇的 用 )。这只是一个约定,两者互为共轭,逆变换 也因此相应地变成
np.fft.ifft。要点是:无论用哪种约定, 和 Parseval 恒等式都照样成立,因为取共轭不改变模。
五、例题
例题 1: 的 FFT 完整手工推导
把 分解为两个 与对角矩阵的乘积,逐步验证。要求不用任何程序,全部手工算完。
第 1 步:写出 与基本参数。
第 2 步:确定三个因子。
(a) 置换矩阵 (把 放前面, 放后面):
验证:。
第一行:取第 1 列,得 。
第二行:第 2 行在第 3 列有 ,得 。
第三行:第 3 行在第 2 列有 ,得 。
第四行:取第 4 列,得 。
(b) 分块对角矩阵 。 时 ,故
(c) 旋转因子对角矩阵 :
第 3 步:验证矩阵恒等式。 逐个算出右边三个因子的乘积,看是否等于 。
先算中间两个因子的乘积 。
按 分块乘法:
计算 :
故
于是
再算 。右乘置换矩阵 的效果是交换第 2 列与第 3 列(因为 交换下标 1 与 2;列的顺序 变成 )。
的四列是
右乘 后列序变为 :
这与第 1 步写出的 逐元素完全相同 ✓。矩阵恒等式
验证通过。
第 4 步:用它算一个具体的 DFT。 取 。
方法 A(直接乘 ):
方法 B(用 FFT 分解路径):
(i) 置换:
(ii) 两次 :
(iii) 旋转因子: 对 取值 ,故
(iv) 蝶形合并:
结果与直接乘 完全一致 ✓。
第 5 步:解读结果。
是"每隔一个取 "的信号,正是频率 (Nyquist 频率)的成分。它的 DFT 只在 与 处非零,说明:
- :直流分量(平均值 )。信号平均值为 ,乘以 得 ✓。
- :Nyquist 频率(最高频)的幅度。
- :中间频率没有成分。
这正是"DFT 把信号分解到频率基上"的含义:时域中"交替的脉冲"在频域中就是"纯高频"。
第 6 步:验证 Parseval 恒等式。
与推论 3.4 一致。
第 7 步: 的 FFT 运算量核对。
- 朴素 DFT: 次复数乘法(加上 12 次加法)。
- FFT:两次 运算,每次 次乘法( 有 4 个元素),共 次;旋转因子乘法 次;蝶形加减 次。总计约 次乘法。
在这个规模上 FFT 的常数因子反而不划算( 与 差不多,而 FFT 还有递归调用的开销)。这正是" 只在大 时体现优势"的典型例子——做小题不要用 FFT,做大题()FFT 才有意义。
例题 2:手算一个 的 FFT 分解(验证旋转因子)
说明 时的分解结构,并验证旋转因子的取值。
第 1 步:参数。
记 ,则
第 2 步: 的各个幂。
(这验证了 (R8): 正是 次本原单位根 ✓)
✓ 由周期性 (R1) 得证。
第 3 步:验证 (R4) 降幂公式。 以 与 为例():
第 4 步: 的分块分解。
其中
把下标重排为 。 已经在例题 1 中求出。
第 5 步:递归展开的树形结构。
,共 层:
- 第 1 层:把 点拆成偶下标 与奇下标 两个 点问题;
- 第 2 层:每个 点问题再拆成两个 点问题,共 个 点问题;
- 第 3 层:每个 点问题再拆成两个 点问题,共 个平凡问题。
总运算量:每层 次运算,共 层,总量 ✓ 与定理 3.6 一致。
第 6 步:核对一个具体的蝶形运算。 取 ,则旋转因子为 。
若已知 与 是某个 点 DFT 的输出,则
注意 ✓,旋转因子只旋转不伸缩——这正是 的酉性的微观体现。
例题 3(手算): 的 FFT 蝶形分解,从矩阵一路算到输出
例题 3(手算): 分解 + 蝶形运算,输入
题目:取 、,输入 。
(1) 写出三个因子 、、,并验证它们的乘积等于 ;
(2) 用分解路径(置换 → 两次 点 DFT → 旋转因子 → 蝶形合并)逐步算出 ;
(3) 直接乘 核对;
(4) 验证 Parseval 恒等式;
(5) 数一数这条路径用了多少次复数乘法,与朴素 DFT 对比。
第 1 步:写下三个因子。
第 2 步:验证矩阵恒等式。 先算后两个因子的乘积(按 分块乘法, 的分块规则与普通乘法一致):
其中
所以
再右乘 。 的效果是交换第 列与第 列(因为 把下标 与 对调),即列序 :
交换第 、 列后:
矩阵恒等式验证通过。
第 3 步:置换输入。
第 4 步:两次 点 DFT(偶数组与奇数组)。
第 5 步:乘旋转因子。 ,故 、:
第 6 步:蝶形合并。
第 7 步:直接乘 核对。 时 ,逐项展开:
两条路径完全一致。
第 8 步:Parseval 核对。
第 9 步:运算量清点。
| 步骤 | 复数乘法 | 复数加减 |
|---|---|---|
| 置换 | ||
| 两次 点 DFT( 个元素各 次乘法) | ||
| 旋转因子 | ||
| 蝶形合并 | ||
| 合计 |
朴素 DFT(直接乘 )需要 次复数乘法与 次加法。 时 FFT 只省了 次乘法——所以例题 1 第 7 步的结论在这里再次得到印证:小规模不要用 FFT。用 3.11 节的精确公式, 时 FFT 的乘法次数是 (这里多出的 次来自两次 的朴素实现;若把 也按蝶形实现,乘法会降到 次)。
手算 FFT 的三条纪律
1. 先置换,再分组。漏掉置换是最常见的错误——它会让 与 的结果互换。
2. 旋转因子只乘奇数组的输出,偶数数组不乘。
3. 蝶形永远成对出现: 与 必须同时写出,符号只差一个。
例题 4(手算):用 的 DFT 计算循环卷积
例题 4(手算):卷积定理的完整数值验证
题目:取 ,、。
(1) 按定义直接计算循环卷积 ( 路径);
(2) 用 DFT 计算:分别求 、,逐点相乘,再用逆变换算回来;
(3) 核对两条路径的结果相同(定理 7.1);
(4) 说明为什么第二条路径的复杂度是 而不是 。
第 1 步(1):直接算循环卷积。 定义
因为 ,求和只需看 两项。
:
:
:
:
(注意"循环"的含义: 的下标超出范围时要绕回来,例如 。这就是它与普通线性卷积的唯一区别。)
第 2 步(2):算 。 用 ,因为 ,只剩两项:
第 3 步(2):算 。 同理 :
第 4 步(2):逐点相乘。 记 :
第 5 步(2):逆变换。 逆变换公式 ,即
:
: 注意 、、:
: 、、:
: 、、:
第 6 步(3):结论。 两条路径给出完全相同的结果 ✓,这正是定理 7.1(循环卷积定理)的数值验证:
第 7 步(4):复杂度对比。
| 路径 | 做法 | 代价 |
|---|---|---|
| 直接法 | 对每个 求和 项,共 个输出 | |
| FFT 法 | 两次正变换 + 一次逐点相乘( 次乘法)+ 一次逆变换 |
关键在于中间的"卷积"被换成了"逐点相乘":时域中 的运算,到了频域只是 次乘法。代价是要付两次 FFT 的"门票"。当 时, 而 ——门票很便宜,收益很大。这就是数字滤波、大整数乘法、多项式乘法都用 FFT 的原因。
循环卷积与线性卷积的区别
本题算的是循环卷积(下标按模 绕回)。工程上要算线性卷积(不绕回)时,必须先把两个序列补零到长度 再做 FFT,否则会出现"时域混叠"(tail wrapping),结果错误。
具体到本题:、 的线性卷积是 ;而 的循环卷积是 (正好也是 个数加一个零,因为 ,没有发生混叠)。若取 ,循环卷积会把第 个分量折回第 个,得到 ——恰好正确;但若取 ,结果是 ,完全错了。补零长度必须够,这是 FFT 做卷积时最容易踩的坑。
例题 5(手算): 的傅里叶矩阵列正交性验证
例题 5(手算):换一个 再验一次酉性
题目:取 ,。
(1) 列出 到 的代数式,标出哪些是本原 次单位根;
(2) 验证 (用配对法);
(3) 计算第 列与第 列的内积 ,以及对角元 ;
(4) 计算 ,说明它对应引理 3.2 中""的情形;
(5) 归纳出 。
第 1 步(1):列出单位根。 记 。
| 辐角 | 的代数式 | 阶 | |
|---|---|---|---|
| (本原 ✓) | |||
| (本原 ✓) | |||
| —— |
由定理 3.9,本原根的个数应为 ,正是 与 ✓(,所以 )。
第 2 步(2):验证六个单位根之和为零。 用配对法(利用 ):
三对全部抵消,故
几何解释:正六边形的六个顶点向量首尾相接正好闭合,合力为零。
第 3 步(3):算 与 。
的第 列是 。所以
(用了 ,即 (R3)。)由第 2 步的结果,
逐项写出来核对一遍(用第 1 步的表格,指数按模 化简):
注意 的分量是 ,所以第一个因子依次是 ;第二个因子是 。逐项相乘并把指数按模 化简:
对角元:
(每一项都是单位根,模为 ,六个 相加得 。)
第 4 步(4):算 。 一般公式是
取 、,则 ,且 ,属引理 3.2 的第二种情形:
是本原 次单位根(由定理 3.10,),它的幂以 为周期,且一个周期内的和为
六个项正好是两个完整周期:
(第二个括号里 、、,与第一个括号完全相同。)
第 5 步(5):归纳。 对任意 ,
( 时每项为 ; 时 不被 整除,由引理 3.2 得 。)因此
与定理 3.3 一致, 是酉矩阵。
本题暴露的一个常见误区
有人会想:" 是因为 的和为零,那是不是只要两列的'频率'不同就自动正交?" 答案是要看差值:正交性取决于 是否被 整除,而不是取决于 、 本身。
例如在 时, 与 正交(), 与 也正交();但如果把 换成 ,那么" 与 "就会因为 被 整除而不正交——这正是"频率 与 是同一个频率"(混叠)的矩阵版本。这也是"变换长度必须与频率上限匹配"的根本原因。
例题 6(证明):、 与"不用共轭的求逆公式"
例题 6(证明):傅里叶矩阵的幂与反序置换
题目:设 的元素为 (),并定义矩阵 为"反序置换":
证明:
(1) ;
(2) ,从而 ;
(3) ;
(4) 由此推出 ,并解释这个公式与 为什么一致。
第 1 步(1):计算 的元素。 用矩阵乘法的定义( 的第 行是 ):
(第二个等号用了 (R5):指数相加。)由引理 3.2,取 (这里 是求和指标,注意不要把两个""混淆——引理中的 是被求和的指数倍数,即 ):
现在确定哪些 满足 。因为 ,所以 ,区间内 的倍数只有 和 :
- ,此时 ✓;
- ,此时 ✓(若 则与上一情形重合于 )。
两种情形合起来恰好是"",也就是 的位置。因此
直观含义: 作用两次 = "把输入反序,再放大 倍"。用式子写就是
(这正是本篇易错点里提到的"np.fft.fft(np.fft.fft(x)) 不等于 ,而是 倍的时间反演"的精确表述。)
第 2 步(2):。 直接计算:
由 的定义,,。两者同时成立的唯一可能是 ,且这样的 在 中恰有一个(即 )。所以
("反序两次回到原位"——这是显然的几何事实,上面的计算只是把"显然"写成代数。)
由 与 :
第 3 步(3):。 逐元素计算:
这个求和只有一个非零项:,而 的取值范围是 ,故 ,于是
(用了 (R3):,故 。)所以
这条结论的几何意义:右乘 相当于把 的列反序(第 列跑到第 列的位置),而"取共轭"恰好等于"把 换成 ",也就是把频率的符号翻过来。"反序"与"取共轭"在傅里叶矩阵上是同一件事——这与 9-1 节"共轭 = 旋转角取反"完全对应。
第 4 步(4):三种求逆公式。 由 ,两边左乘 :
这个公式只用矩阵乘法就能求逆(不需要共轭、不需要转置)。把 代入,并注意由第 3 步 ——这里要注意顺序:第 3 步给的是 ,而我们要用 。由 (R6) 与 ( 关于 对称):
所以
而由 (D4)(,因为 对称),这恰好就是
三个公式完全一致 ✓:。
这个例题为什么值得单独做一遍
它把三件看似无关的事串成了一条链:
1. 代数: 说明"做两次 DFT 等于时间反演加放大";
2. 几何: 是反序(),而频率取负号 = 取共轭 = 相位取反;
3. 算法: 意味着逆变换 = 共轭 + 缩放,与正变换共用同一份代码。
np.fft.ifft(x)的内部实现正是np.conj(np.fft.fft(np.conj(x))) / n。顺带还得到一个"不用任何共轭运算"的求逆公式 ,它在纯代数推导(例如证明傅里叶矩阵的阶为 )时很方便。
例题 7(证明):FFT 的精确运算次数
例题 7(证明): 次乘法是怎么来的
题目:设 ,用 4.2 节的递归 FFT(先把输入按奇偶拆成两半,递归做两个 点 DFT,再乘旋转因子并做蝶形合并)。
(1) 写出乘法次数 与加减次数 的递推式;
(2) 用数学归纳法证明 与 ;
(3) 说明朴素 DFT 需要 次复数乘法,并解释两者的差距从何而来;
(4) 解释为什么这个递推里的"合并代价"必须是 ——如果改成 会发生什么。
第 1 步(1):写出递推。
一次 点 FFT 的运算可以分成三部分:
- 两次 点递归调用: 次乘法、 次加减;
- 旋转因子乘法:,共 个(每个一次复数乘法);
- 蝶形加减:对 各算一次 与一次 ,共 次加减。
所以
递归终止条件: 时 点 DFT 就是恒等变换,不需要任何运算:
第 2 步(2):归纳证明 。
因为 ,记 ,则 ,要证的目标是
奠基 : ,而 ✓。
归纳步: 设 ,则递推式(取 )给出
提出公因子 :
代回 、:
同理证明 。 记 ,要证 。
奠基: ✓。
归纳步:
于是 。
第 3 步(3):与朴素 DFT 的对比。
朴素 DFT 直接算 ,其中 是 的稠密矩阵:每个输出 要做 次乘法与 次加法,共 个输出,所以
比较():
当 时, 倍;当 时, 倍。差距随 线性增长(除以 ),这正是"从不可行到可行"的量化来源。
第 4 步(4):为什么合并代价必须是 。
假设把旋转因子那一步换成一个稠密矩阵乘法(代价 ),递推变成
用主定理:、,,而 (取 ),属于第一种情形,结论是
与朴素 DFT 同阶——分治白做了。
这个证明教给我们的方法论
成立需要两个条件同时满足:
1. 问题能对半分( 两个 ):这保证递归树只有 层;
2. 合并代价只有 :这保证每层的工作量不膨胀。
缺任何一个都不行:只有 (1) 而没有 (2),递推的解会退化成 (本题第 4 步);只有 (2) 而没有 (1)(比如"减治",每次只把规模减 ),递归树会有 层,总量是 。
"分治 + 廉价合并"是全部快速算法的配方:Karatsuba 乘法、快速排序、Strassen 矩阵乘法、小波变换都遵循同一模式(对照 11-3-迭代方法与预条件:迭代法之所以能打败直接法,也是因为每一步只用一次稀疏乘法)。
例题 8(numpy 数值验证):朴素 DFT 与 np.fft.fft 的结果与耗时对比
例题 8(numpy 验证):三种算法一致性、卷积定理与计时
题目:只用 numpy(
np.fft是 numpy 自带子模块)完成以下验证,并把输出与手算结果对照:(1) 手写朴素 DFT()与手写递归 FFT()的结果都与
np.fft.fft一致;(2) 的分块分解恒等式成立,且蝶形路径的结果与直接乘 一致(对照例题 3);
(3) 单位根的性质(表 3.8)与 、、(对照例题 6);
(4) 循环卷积定理(对照例题 4);
(5) 朴素 DFT 与
np.fft.fft的耗时对比;(6) 实信号的 Hermitian 对称性与 Parseval 恒等式。
代码:
import numpy as np
import time
np.set_printoptions(precision=4, suppress=True)
# ---------- 1. 手写朴素 DFT(O(n^2))与递归 FFT(O(n log n)),与 numpy 同一约定 ----------
def naive_dft(x):
"""朴素离散傅里叶变换:y_k = sum_j exp(-2*pi*i*j*k/n) x_j。"""
x = np.asarray(x, dtype=complex)
n = x.shape[0]
k = np.arange(n).reshape(-1, 1)
j = np.arange(n).reshape(1, -1)
W = np.exp(-2j * np.pi * k * j / n)
return W @ x
def recursive_fft(x):
"""递归 FFT,要求长度为 2 的幂。"""
x = np.asarray(x, dtype=complex)
n = x.shape[0]
if n == 1:
return x.copy()
even = recursive_fft(x[0::2])
odd = recursive_fft(x[1::2])
w = np.exp(-2j * np.pi * np.arange(n // 2) / n) # 旋转因子
t = w * odd
return np.concatenate([even + t, even - t])
# ---------- 2. F_4 的分块分解:F_4 = [[I, D], [I, -D]] [[F_2, 0], [0, F_2]] P ----------
I2 = np.eye(2, dtype=complex)
D = np.diag([1, 1j]) # D = diag(1, omega), omega = i
F2 = np.array([[1, 1], [1, -1]], dtype=complex)
P = np.array([[1, 0, 0, 0],
[0, 0, 1, 0],
[0, 1, 0, 0],
[0, 0, 0, 1]], dtype=complex)
F4 = np.array([[1, 1, 1, 1],
[1, 1j, -1, -1j],
[1, -1, 1, -1],
[1, -1j, -1, 1j]], dtype=complex)
Z = np.zeros((2, 2), dtype=complex)
lhs = np.block([[I2, D], [I2, -D]]) @ np.block([[F2, Z], [Z, F2]]) @ P
print("F4 = 分块乘积 ?", np.allclose(lhs, F4))
# ---------- 3. 蝶形分解的数值复核:x = (1, 2, 3, 4) ----------
x4 = np.array([1, 2, 3, 4], dtype=complex)
e = F2 @ x4[0::2] # 偶数项子问题的 2 点 DFT
o = F2 @ x4[1::2] # 奇数项子问题的 2 点 DFT
w4 = np.exp(2j * np.pi * np.arange(2) / 4) # omega^k, omega = i
y_butterfly = np.concatenate([e + w4 * o, e - w4 * o])
print("e =", e.tolist(), " o =", o.tolist(), " omega^k =", np.round(w4, 10).tolist())
print("蝶形输出 =", np.round(y_butterfly, 10).tolist())
print("与 F4 @ x4 一致 ?", np.allclose(F4 @ x4, y_butterfly))
print("np.fft.fft(x4) =", np.round(np.fft.fft(x4), 6).tolist())
print("conj(F4) @ x4 =", np.round(np.conj(F4) @ x4, 6).tolist())
# ---------- 4. 单位根的性质抽查(n = 8) ----------
n = 8
omega = np.exp(2j * np.pi / n)
roots = omega ** np.arange(n)
print("8 次单位根 =", np.round(roots, 4).tolist())
s1 = sum(omega ** k for k in range(n))
s2 = sum((omega ** 2) ** k for k in range(n))
s3 = sum((omega ** 3) ** k for k in range(n))
print("sum(omega^k) =", np.round(s1, 12), " sum(omega^{2k}) =", np.round(s2, 12),
" sum(omega^{3k}) =", np.round(s3, 12))
print("omega^{n-k} = conj(omega^k) ?", np.allclose(omega ** (n - np.arange(n)), np.conj(roots)))
print("|单位根| 全为 1 ?", np.allclose(np.abs(roots), 1))
print("omega^2 是 4 次本原单位根 ?", np.isclose(omega ** 2, np.exp(2j * np.pi / 4)))
# ---------- 5. F_n^H F_n = nI、F_n^T = F_n、F_n^2 = n * (反序置换) ----------
def fourier_matrix(n, sign=+1):
j = np.arange(n).reshape(-1, 1)
k = np.arange(n).reshape(1, -1)
return np.exp(sign * 2j * np.pi * j * k / n)
for nn in [2, 3, 4, 6, 8]:
Fn = fourier_matrix(nn)
Prev = np.zeros((nn, nn))
for jj in range(nn):
Prev[jj, (-jj) % nn] = 1.0
print(f"n={nn}: F^H F = nI ?", np.allclose(Fn.conj().T @ Fn, nn * np.eye(nn)),
" F^T = F ?", np.allclose(Fn.T, Fn),
" F^2 = n*Prev ?", np.allclose(Fn @ Fn, nn * Prev))
# ---------- 6. 三种算法一致性 + 循环卷积定理 ----------
rng = np.random.default_rng(0)
n = 16
x = rng.standard_normal(n) + 1j * rng.standard_normal(n)
print("numpy vs naive :", np.allclose(np.fft.fft(x), naive_dft(x), atol=1e-10))
print("numpy vs recur :", np.allclose(np.fft.fft(x), recursive_fft(x), atol=1e-10))
xs = np.array([1, 2, 0, 0], dtype=complex)
hs = np.array([1, 1, 0, 0], dtype=complex)
conv_direct = np.array([sum(xs[j] * hs[(m - j) % 4] for j in range(4)) for m in range(4)])
conv_fft = np.fft.ifft(np.fft.fft(xs) * np.fft.fft(hs))
print("直接循环卷积 =", np.round(conv_direct, 10).tolist())
print("FFT 循环卷积 =", np.round(conv_fft, 10).tolist(),
" 一致 ?", np.allclose(conv_direct, conv_fft))
# ---------- 7. 计时对比:朴素 DFT vs np.fft.fft ----------
print("{:<8} {:>14} {:>14} {:>10}".format("n", "naive(s)", "fft(s)", "speedup"))
for n in [256, 512, 1024, 2048, 4096]:
x = rng.standard_normal(n) + 1j * rng.standard_normal(n)
t0 = time.perf_counter()
naive_dft(x)
t_naive = time.perf_counter() - t0
reps = 20
t0 = time.perf_counter()
for _ in range(reps):
np.fft.fft(x)
t_fft = (time.perf_counter() - t0) / reps
print("{:<8} {:>14.6f} {:>14.6f} {:>10.1f}".format(n, t_naive, t_fft, t_naive / t_fft))
# ---------- 8. 实信号的 Hermitian 对称性与 Parseval ----------
xr = np.array([1.0, 2.0, 3.0, 4.0])
yr = np.fft.fft(xr)
print("实信号 FFT =", np.round(yr, 6).tolist())
print("y[0] 实 ?", np.isclose(yr[0].imag, 0), " y[n-k] = conj(y[k]) ?",
np.allclose(yr[1:], np.conj(yr[:0:-1])))
print("Parseval: ||y||^2 =", np.round(np.sum(np.abs(yr) ** 2), 6),
" n||x||^2 =", 4 * np.sum(np.abs(xr) ** 2))
实际输出(numpy 2.3.5,计时部分与机器有关):
F4 = 分块乘积 ? True
e = [(4+0j), (-2+0j)] o = [(6+0j), (-2+0j)] omega^k = [(1+0j), 1j]
蝶形输出 = [(10+0j), (-2-2j), (-2+0j), (-2+2j)]
与 F4 @ x4 一致 ? True
np.fft.fft(x4) = [(10+0j), (-2+2j), (-2+0j), (-2-2j)]
conj(F4) @ x4 = [(10+0j), (-2+2j), (-2+0j), (-2-2j)]
8 次单位根 = [(1+0j), (0.7071+0.7071j), 1j, (-0.7071+0.7071j), (-1+0j), (-0.7071-0.7071j), (-0-1j), (0.7071-0.7071j)]
sum(omega^k) = (-0-0j) sum(omega^{2k}) = (-0-0j) sum(omega^{3k}) = (-0-0j)
omega^{n-k} = conj(omega^k) ? True
|单位根| 全为 1 ? True
omega^2 是 4 次本原单位根 ? True
n=2: F^H F = nI ? True F^T = F ? True F^2 = n*Prev ? True
n=3: F^H F = nI ? True F^T = F ? True F^2 = n*Prev ? True
n=4: F^H F = nI ? True F^T = F ? True F^2 = n*Prev ? True
n=6: F^H F = nI ? True F^T = F ? True F^2 = n*Prev ? True
n=8: F^H F = nI ? True F^T = F ? True F^2 = n*Prev ? True
numpy vs naive : True
numpy vs recur : True
直接循环卷积 = [(1+0j), (3+0j), (2+0j), 0j]
FFT 循环卷积 = [(1+0j), (3+0j), (2+0j), 0j] 一致 ? True
n naive(s) fft(s) speedup
256 0.002342 0.000007 325.4
512 0.008138 0.000014 596.2
1024 0.031259 0.000015 2149.9
2048 0.123199 0.000035 3475.8
4096 0.520716 0.000038 13578.0
实信号 FFT = [(10+0j), (-2+2j), (-2+0j), (-2-2j)]
y[0] 实 ? True y[n-k] = conj(y[k]) ? True
Parseval: ||y||^2 = 120.0 n||x||^2 = 120.0
逐条对照手算结果:
| 输出 | 对应结论 | 是否一致 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|
F4 = 分块乘积 ? True | ✓ 例题 3 第 2 步 | |||||||||
e = [4, -2]、o = [6, -2] | 两次 点 DFT 的输出 | ✓ 例题 3 第 4 步 | ||||||||
蝶形输出 = [10, -2-2j, -2, -2+2j] | , | ✓ 例题 3 第 6、7 步 | ||||||||
np.fft.fft(x4) = [10, -2+2j, -2, -2-2j] 且等于 conj(F4) @ x4 | numpy 用 约定,即 ;它与本篇的 互为"时间反演 + 共轭"( 与 互换) | ✓ 符合 4.4 节的符号约定说明 | ||||||||
三个单位根和都是 -0-0j | () | ✓ 引理 3.2 | ||||||||
omega^{n-k} = conj(omega^k) ? True | 性质 (R4) | ✓ 3.1 节 | ||||||||
F^2 = n*Prev ? True() | ( 为反序置换) | ✓ 例题 6 第 1 步 | ||||||||
numpy vs naive / recur : True | 三种算法给出同一个 DFT(精确算术下相同) | ✓ 定理 3.5 | ||||||||
直接循环卷积 = FFT 循环卷积 = [1, 3, 2, 0] | 卷积定理 | ✓ 例题 4 | ||||||||
| 计时表: 从 到 ,加速比从 增长到 | 朴素法 、FFT 的差距随 迅速拉大 | ✓ 3.11 节 | ||||||||
| `Parseval: \ | \ | y\ | \ | ^2 = 120.0 = n\ | \ | x\ | \ | ^2` | 推论 3.4( 时 ) | ✓ 例题 3 第 8 步 |
读计时结果时的三个注意点
1. 耗时与机器、CPU 负载、numpy 版本都有关,上表的绝对数值不可跨机器比较;能跨机器比较的是"加速比随 的增长趋势":本表里每翻一倍 ,朴素法耗时约变 倍(),FFT 耗时约变 倍出头()。
2.
np.fft.fft是 C/Fortran 实现(pocketfft),而naive_dft用了一次n×n矩阵乘法——后者的常数因子本来就大。所以实测加速比(上万倍)会高于纯运算次数之比( 时约 倍)。比"运算次数"更公平,但"墙钟时间"才是工程上真正关心的量。3.
np.fft.fft的约定与本篇相差一个共轭(指数上带负号)。所以F4 @ x4与np.fft.fft(x4)的第 、 个分量互换——不是算错了,而是约定不同。凡是把教材公式直接翻译成 numpy 代码时,都要检查这一处符号。
六、应用:FFT 为什么改变世界
6.1 音频与语音
MP3、AAC、Opus 等音频编码格式的核心步骤是:把音频切成短帧(典型 或 个采样点)→ 对每帧做 FFT(或它的实数变体 MDCT)→ 用心理声学模型决定哪些频率成分可以丢弃 → 量化 → 熵编码。
"有损压缩之所以可行,正是因为人耳在频域中有掩蔽效应":一个强音会掩盖附近频率的弱音,所以那些被掩盖的频率分量可以直接丢掉。而"哪些频率有什么"这个问题只有在频域中才回答得了。没有 FFT,就没有 MP3。
6.2 图像压缩 JPEG
JPEG 对 像素块做二维 DCT(离散余弦变换,可以看作 FFT 的实数特例)。二维 DFT/DCT 是可分离的:
即"先对每一行做一维变换,再对每一列做一维变换"(或者反过来,结果相同)。因此二维变换的代价只是两个一维变换的代价。这是"张量积结构"带来的巨大节省:直接做二维变换要 ,分离后只要 。
JPEG 的实际收益: 个像素变换后,通常只有左上角(低频)的十几个系数显著非零,其余可以粗量化甚至置零。这正是 JPEG 能压到原图 甚至 而肉眼几乎看不出差别的根本原因。
6.3 通信:OFDM 与 5G
4G LTE 与 5G NR 的物理层都用 OFDM(Orthogonal Frequency Division Multiplexing,正交频分复用)。它的做法是:
- 把高速数据流分成成千上万个低速子载波;
- 每个子载波用不同的频率 承载;
- 发射端用 IFFT 把这些子载波一次性合成成时域波形;
- 接收端用 FFT 把收到的时域信号一次性分解回各个子载波上的数据。
为什么必须用 FFT:一个 5G 载波可能有 个子载波,且要求毫米级的时间调度。 时朴素 DFT 需 次运算,FFT 只需约 次——相差 300 多倍,直接决定了能不能实时。而且"正交"这个词在这里是字面意义的:各子载波频域互不干扰,正是 列正交的物理体现。
6.4 数值求解偏微分方程
求解 (波动方程)、热传导方程等 PDE 时,谱方法(spectral method)的做法是:
- 把解按空间做傅里叶展开:;
- 代入方程后,空间导数 变成乘以 ,微分方程退化为关于 的常微分方程(每个 独立!);
- 解完 后用逆 FFT 变换回物理空间。
关键优势是精度:谱方法对光滑解的误差随 指数衰减(所谓"谱精度"),而有限差分只有多项式阶的精度。代价是每步都要做一次 FFT——但在 的代价下完全负担得起。这是天气预报、湍流模拟、量子化学计算中广泛使用的方法。
6.5 医学成像
- CT(计算机断层扫描):投影切片定理(Fourier slice theorem)说明"某个角度的投影的一维傅里叶变换,等于物体二维傅里叶变换在该角度上的一条切片"。因此可以从多个角度的投影重建图像,重建过程的核心就是 FFT。
- MRI(磁共振成像):MRI 采集的数据(k 空间数据)本身就在频域,成像过程就是一次逆 FFT。
- 超声:波束合成中的匹配滤波、多普勒血流测量的频谱分析,都依赖 FFT。
可以说:现代医学影像技术的实时性,直接建立在这个 的算法之上。
七、频率视角下的线性代数
这一节把 FFT 与前面几章的内容串起来。
7.1 DFT 就是"投影到正交基上求坐标"
由 9-2 节的定理, 的列 两两正交、长度都是 。因此
是 的一组标准正交基——频率基。由第四章的坐标公式,任意 都可以唯一地写成
这正是逆 DFT 公式 的分量写法。
所以"傅里叶分析"就是线性代数里的标准正交基展开,只不过基向量换成了复指数。第四、六章学的"投影 = 内积",在这里一字不改地适用。
7.2 与 10-4 节的傅里叶级数完全平行
有限维的 DFT 与无限维的傅里叶级数之间存在完美的对应:
| 有限维(本篇) | 无限维(傅里叶级数) | |
|---|---|---|
| 空间 | 函数空间 | |
| 正交基 | ||
| 内积 | ||
| 系数公式 | ||
| 展开 | ||
| 能量守恒 |
"函数是无穷维向量,傅里叶级数是无穷维的正交基展开" —— 这是 10-4-傅里叶级数与函数空间 的核心观点。本篇讲的离散版本在计算上更实用,"离散化"本身也是一条重要的数学思想(把积分换成求和、把函数换成采样向量)。
7.3 循环卷积定理:FFT 的另一大用途
定理 7.1(循环卷积定理) 设 ,定义它们的循环卷积(circular convolution)为
则
其中 表示逐元素相乘。
证明思路:把循环卷积写成矩阵形式 ,其中 是循环矩阵(circulant matrix,每行是上一行的循环右移)。可以验证循环矩阵恰好可以被傅里叶矩阵对角化:
(这就是循环矩阵的谱定理——循环矩阵是正规矩阵,它的特征向量正是傅里叶基向量。)代入得
实用价值:时域中的卷积(代价 )变成频域中的逐点相乘(代价 ),加上两次 FFT(代价 ),总共 。这比直接做卷积快得多,是数字滤波、大整数乘法(Schönhage–Strassen 算法)、多项式乘法、卷积神经网络加速的共同基础。
与第四章卷积型问题的联系
循环矩阵 的每一列都是 的循环移位,这与第四章讲" 是 的列的线性组合"完全一致。卷积 用移位版本做线性组合 一种特殊的矩阵乘法。而循环矩阵能被傅里叶矩阵对角化,说明"移位"这个操作的"特征向量"就是复指数——这与微分算符 的特征函数是 是同一件事的离散版本。
八、易错点
四个高频错误
错误 1:混淆 FFT 与 DFT。
这是最根本的概念错误。两者的关系是:
- DFT 是数学变换(一个 矩阵 与向量的乘积),有唯一确定的输出;
- FFT 是计算 DFT 的算法,输出与 DFT 完全一样,只是更快。
所以下面这些说法都是错的:
- "FFT 是一种新的变换" ✗(它没有产生新的数学对象);
- "FFT 的结果和 DFT 不一样" ✗(精确算术下完全相同);
- "DFT 和 FFT 是两个不同的东西,要根据需要选择" ✗(你选择的只是算法,数学定义没得选)。
正确的说法:"FFT 是 DFT 的快速算法, 对 。"在代码里,
np.fft.fft算的就是 DFT。错误 2:忘记归一化因子。
三种常见约定,必须与你的公式配套:
| 约定 | 正变换 | 逆变换 | |
|---|---|---|---|
| 本篇(不归一化) | | | |
| numpy | | | |
| 酉(对称)约定 | | | |
最容易犯的错:用了不归一化的正变换,却忘了逆变换里的 。症状是
ifft(fft(x))得到的是n*x而不是x。自检方法:永远验证一次往返变换。
```python
import numpy as np
x = np.array([1.0, 2.0, 3.0, 4.0])
y = np.fft.fft(x)
print(np.allclose(np.fft.ifft(y), x)) # True —— numpy 已内置 1/n
print(np.allclose(np.fft.fft(y), 4 * x)) # True —— 二次正变换会放大 n 倍
```
顺便注意
np.fft.fft(np.fft.fft(x))不等于x,它等于 倍的"时间反演"。这是归一化约定导致的反直觉结果。错误 3:把
np.fft.fft的输出顺序当成"频率从低到高"。
np.fft.fft的输出顺序是[0, 1, 2, ..., n/2-1, -n/2, ..., -2, -1](单位是"圈数",即频率乘以采样周期),不是从低到高。前一半是非负频率(升序),后一半是负频率(从 递增到 )。具体例子():
np.fft.fftfreq(8) * 8给出如果直接把这个数组当作横轴画图,会看到频谱在中间"断裂",而且负频率出现在右边——非常反直觉。
正确的处理方式是用
np.fft.fftshift把零频率移到中间:```python
import numpy as np
n = 8
y = np.fft.fft(np.arange(n, dtype=float))
freq = np.fft.fftfreq(n) # 单位是“圈/采样”,即频率 * 采样周期
print(freq) # [ 0. 0.125 0.25 0.375 -0.5 -0.375 -0.25 -0.125]
freq_shifted = np.fft.fftshift(freq) # [-0.5 -0.375 -0.25 -0.125 0. 0.125 0.25 0.375]
y_shifted = np.fft.fftshift(y)
```
常见后果:把
fft的输出直接当成"低频到高频",导致滤波时把高频当成低频滤掉,或者画出的频谱左右颠倒。凡是做频谱分析,先想清楚fftfreq的排列,需要时用fftshift。另外注意
np.fft.fftfreq(n)的默认采样间隔 ,返回的是"归一化频率"(单位:圈/采样)。如果要真实的物理频率(Hz),必须传 ( 为采样率),即np.fft.fftfreq(n, d=1/fs)。错误 4:以为 FFT 的输出应该是实数,看到复数就认为算错了。
DFT 的输出一般都是复数,这是数学上必然的,不是错误:
- 即使输入 全是实数,输出 通常是复数(只有 必为实,见下面);
- 复数的模 给出该频率分量的幅度;
- 复数的辐角 给出该频率分量的相位。
幅度和相位都是真实的物理信息,缺一不可。丢掉虚部就等于丢掉了相位信息——重建信号时会得到完全错误的波形(这也是为什么"只要幅度谱"的音频处理(如某些相位随机的实验)听起来会很不自然)。
实信号的一个有用性质(Hermitian 对称性):若 全为实数,则
也就是说,后半部分的频谱是前半部分的共轭,信息是冗余的!这带来两个实用后果:
1. 必为实数(它是直流分量),而且 为偶数时 也必为实数;
2. 可以用 numpy 的
np.fft.rfft("real FFT")只计算前 个分量,省掉一半计算量和一半内存。处理真实世界的音频、图像、传感器数据时,一律优先用rfft家族。
另三个值得注意的陷阱
1.
np.fft.fft的输入长度不必是 的幂。numpy 用的是 pocketfft,对合数长度也能高效处理;但对大素数长度会退化成接近 。性能敏感时把长度补零到 的幂或"高度合数"(如 )。补零会改变频率采样点,但不会改变 DFT 的数学定义。2. 补零不等于提高分辨率。补零只是在原有频谱上做插值(采样更密),并不会凭空增加真实的分辨能力。真正的频率分辨率由观测时长决定,即 ,与补零多少无关。
3.
np.fft.fft作用于多维数组时默认沿最后一个轴。对图像做二维 FFT 要用np.fft.fft2,或者显式指定axis。写成np.fft.fft(img)只会对每一行做一维变换,结果完全不对。
九、练习题
练习 1(基础) 取 ,。
(a) 写出 到 的值(可以用 、 表示);
(b) 验证 对 成立;
(c) 计算 与 ,用引理 3.2 核对你的答案。
练习 2(基础) 对 :
(a) 直接按定义计算 ();
(b) 用 FFT 的分治路径(置换 → 两次 → 蝶形合并)再算一次,核对结果;
(c) 验证 Parseval 恒等式 ;
(d) 这个信号对应什么频率?请解释为什么答案如此"稀疏"。
练习 3(进阶) 写出 时 FFT 的矩阵分解
(a) 写出 ( 置换矩阵)的完整形式;
(b) 写出 的完整形式(用 表示,可借助 );
(c) 计算分块矩阵 中非零元素的个数,并说明为什么"乘以一个只有 个非零元的矩阵只要 次运算";
(d) 由此说明 可以写成 个稀疏矩阵的乘积(把 再展开一层),并算出这 个矩阵各自的非零元个数。
练习 4(进阶) 证明循环卷积定理(定理 7.1):
(a) 写出循环矩阵 的完整定义( 的例子即可),并证明它是正规矩阵;
(b) 记 为 的第 列(单位根构成的向量)。直接验证 ,其中 。由此说明"傅里叶基向量是循环矩阵的特征向量";
(c) 由 (b) 推出 ,并导出卷积定理;
(d) 用 (c) 说明为什么"用 FFT 做卷积"的复杂度是 。
练习 5(思考)
(a) 说明为什么 FFT 的递推式是 而不是 。提示:想一想"乘以 "这一步到底要做多少次乘法和加法。
(b) 如果 是 的幂,你会怎样设计分治方案?递推式会变成什么?用主定理求出复杂度,并与 比较。
(c) 解释为什么"补零到更长的长度再做 FFT"不能提高真实的频率分辨率。提示:从 出发,其中 是观测时长。
(d) 结合本篇与 9-2-Hermitian矩阵与酉矩阵,解释" 的列构成一组正交基"与"DFT 是可逆的、且保能量"这两件事之间的逻辑关系。
十、常见问题 FAQ
Q1:FFT 和 DFT 到底有什么区别?能不能只学 FFT 不学 DFT?
不能。 DFT 是数学对象,FFT 是算法。就像"求 个数之和"是问题,"分治法求和"是算法——你不可能"只学算法不学问题",因为算法要解决的就是那个问题,不懂问题就不知道算法在算什么。
具体区别:
| DFT | FFT | |
|---|---|---|
| 本质 | 一个线性变换(矩阵 ) | 一族计算该变换的算法 |
| 复杂度 | 定义上就是 | |
| 输出 | 与 DFT 完全相同 | |
| 谁提出的 | 傅里叶(1807 年的思想,离散版本 19 世纪) | Cooley 与 Tukey(1965),但 Gauss 在 1805 年已有类似思想 |
| 有无误差 | 无(数学定义) | 有(浮点舍入,但通常极小) |
实践中的"知识点"是:你知道 np.fft.fft 算的是 DFT,输出是 (numpy 的符号约定下);你知道它是 而不是 ;你知道这个加速来自分治,所以输入长度是 的幂时最快。这些就是你需要记住的。
Q2:FFT 的输出顺序为什么不是从低频到高频?这个设计太反直觉了。
这确实反直觉,但它是 DFT 定义的直接后果,不是设计者的任意选择。
原因在于下标 的范围本来就是 ,而 与 表示同一个频率(因为 )。所以每个频率在数学上有无穷多个"别名"。为了让输出恰好是 个数,必须从每个等价类里挑一个代表。
numpy(以及几乎所有 FFT 库)的选择是:用 这 个整数代表频率。当 超过 时,它代表的其实是负频率 :
为什么选这个而不是"负频率在前"? 因为这样下标 与输入下标 的范围完全一致(都是 到 ),循环卷积公式、位移定理等所有代数恒等式都不需要额外的取模处理。代价只是画图时要记得 fftshift。
实用记忆法: 点 FFT 的输出中,
- :直流(0 Hz);
- :正频率,从低到高;
- :Nyquist 频率(最高可分辨频率);
- :这些其实对应负频率 。
如果只关心幅度谱,可以只取前 个(用 rfft),这样顺序就是天然从低到高了,不用 fftshift。这是处理实信号时的标准做法,也是我最推荐的起步方式。
Q3:为什么 最好是 的幂?不是 的幂会怎样?
因为 的幂能让分治一路递归到底都不出现"零头",递归树最规整。
时:每次除以 都是整数,直到 。递归树是完美的二叉树,共 层,每层恰好 个工作单元。复杂度是干净的 。
是合数但不是 的幂时:可以用混合基 FFT——按 的最小质因子 分解成 个 点问题。例如 ,可以先分成 个 点问题,或 个 点问题。复杂度是 ( 为质因子),仍然远好于 。
是大质数时: 没有非平凡因子,混合基分解无从下手。此时要么退化成 (Bluestein 算法之前),要么用 Bluestein 算法(也叫 chirp-z 变换),它把 点 DFT 转化成一次长度为 的卷积,再用 FFT 完成,复杂度 。代价是要做三次 FFT,常数因子较大。
实践建议(对应到 numpy):
- 能用
rfft就用rfft(实输入),它直接省一半。 - 需要指定长度时,选"高度合数"。numpy 的 pocketfft 对 也有专门优化,不必强求 的幂。例如 比 (质数)快很多。
- 补零要谨慎:补零能让长度变成 的幂并加速,但会改变频率采样点(相当于做插值)。如果你需要的是"精确的 点 DFT",就不能随便补零。
import numpy as np
import time
rng = np.random.default_rng(1)
print("{:<10} {:>14} {:>14}".format("length", "fft (s)", "note"))
for n in [1000, 1024, 1021, 4096, 4099]:
x = rng.standard_normal(n)
t0 = time.perf_counter()
for _ in range(20):
np.fft.fft(x)
t = (time.perf_counter() - t0) / 20
note = "highly composite" if n == 1000 else ("power of 2" if n in (1024, 4096) else "prime")
print("{:<10} {:>14.8f} {:>14}".format(n, t, note))
# 典型结果:1024 比 1021 快数倍;1000 也比 1021 快 —— 质数长度最慢
Q4:我在做信号处理,什么时候该用 FFT,什么时候不该用?
该用 FFT 的典型场景:
- 频谱分析:想知道一段信号里有哪些频率成分、各自多强。这是 FFT 最经典的用途。
- 滤波:设计好频域响应 ,把信号变换过去、逐点相乘、再变换回来。代价 ,比时域卷积的 快得多(当滤波器很长时优势尤其明显)。
- 卷积 / 相关运算:两个长序列的卷积、互相关、自相关。用卷积定理(定理 7.1)。
- 求解 PDE 的谱方法:空间导数变成乘以 ,微分方程退化为独立的常微分方程。
- 频域压缩:JPEG 的 DCT、音频编码的 MDCT,都是 FFT 的实数变体。
不该用 FFT(或不合适)的场景:
- 数据很短( 只有几十)。此时 的常数因子更小,FFT 的递归/迭代开销反而不划算。本篇例题 1 第 7 步已经算过: 时朴素法 16 次乘法,FFT 约 10 次,几乎没优势。
- 信号非平稳,且你只想看"局部"的频率。FFT 给出的是整段信号的全局频谱,无法告诉你"第 3 秒到第 4 秒之间出现了什么频率"。这时要用短时傅里叶变换(STFT,即分帧做 FFT)或小波变换。
- 只关心少数几个频率点。如果要算的 只有几个(比如 个),而 ,直接按定义算这 个值只要 ,比做完整 FFT 的 快得多。这类需求用 Goertzel 算法 或直接按定义算。
- 需要极高精度(超过双精度)。FFT 会累积浮点舍入误差(虽然通常很小,约 ),在需要精确整数结果的场合(如大整数乘法、密码学)要考虑用数论变换(NTT)。
- 数据缺失或非均匀采样。标准 FFT 要求等间隔采样点。非均匀采样要用 NUFFT(non-uniform FFT)或 Lomb–Scargle 周期图。
一句话总结:FFT 是"把整段信号一次性分解到全部频率上"的利器。如果你的问题符合这个描述,就用它;如果你只要局部信息、少数频率点,或者数据量很小,就该考虑别的工具。
本篇小结
核心结论(八条主线)
- 单位根: 的 个幂 是复平面上单位圆的 等分点(正 边形顶点),构成一个循环群 。核心性质:、、、、( 偶)、 是 次本原单位根。
- 本原根与子群嵌套: 是本原 次单位根 (共 个);若 则 。"单位根里嵌套着更小的单位根"正是 FFT 分治的代数根源。
- 求和公式(正交关系的核心):。几何版本是"正多边形顶点向量之和为零"。
- 傅里叶矩阵:,它是对称矩阵(),满足
并且 ( 为反序置换)、、。因此 是酉矩阵, 本身是"酉矩阵的 倍"。
- DFT 就是换到频率基:, 是信号在频率方向上的(未归一化)投影;Parseval 恒等式 说明变换保能量。
- FFT 是算法不是变换:蝶形恒等式
等价于矩阵分解 。输出与 DFT 完全相同,只是快。
- 复杂度:递推 给出 ;精确计数是 次复数乘法、 次加减,而朴素 DFT 需要 次乘法,比值为 。加速的唯一来源是"合并矩阵稀疏"( 个非零元),而不是"分治"本身。
- 傅里叶矩阵的谱:由 知 的特征值 满足 ,即 ;又 是正规矩阵(),故它在复域可酉对角化(9-2-Hermitian矩阵与酉矩阵 的框架直接适用)。
易混概念对照表
| 容易混淆的一对 | 关键区别 | 判据 / 例子 |
|---|---|---|
| DFT 与 FFT | DFT 是数学变换(矩阵 ),FFT 是算它的算法 | 精确算术下输出相同;差别只在代价 vs |
| 正变换与逆变换 | 逆变换 取共轭 除以 | ifft(fft(x)) = x;fft(fft(x)) = n * x[::-1] |
| 与 | 前者正交但列长为 ,后者才是酉的 | 对 |
| 循环卷积与线性卷积 | 循环的下标按模 绕回,可能"尾部混叠" | 线性卷积需补零到 |
| numpy 约定与本篇约定 | numpy 指数带负号(),与本篇互为共轭 | np.fft.fft(x) ≈ conj(F_n) @ x |
| 补零与提高分辨率 | 补零只是频谱插值(采样更密),不增加真实分辨率 | 真实分辨率 , 是观测时长 |
fftfreq 的顺序与"从低到高" | 输出是 ,不是升序 | 画图前用 np.fft.fftshift |
| 实信号与复信号 | 实信号频谱有 Hermitian 对称 ,信息冗余 | 实输入优先用 np.fft.rfft,省一半 |
| 旋转因子与单位根 | 同一个东西:twiddle factor 就是 (模为 ,只转不伸缩) | 蝶形里只乘奇数组的输出 |
| 的幂与素数长度 | 前者递归最干净;后者退化成 或需 Bluestein | 需要指定长度时选"高度合数" |
| 单位根的阶与" 次单位根" | 每个 都是 次单位根,但只有 的才是本原的 | 时本原根只有 |
| "频率 "与"频率 " | 由 ,两者是同一个频率 | 这就是混叠(aliasing)的来源 |
一句话总结:DFT 是"投影到频率基上求坐标"(线性代数),FFT 是"利用 的递归稀疏分解把 降到 "(算法)。 前者回答"是什么",后者回答"怎么快";两者输出完全一样,而工程上的可行性全部取决于后者。
相关笔记
- 9-2-Hermitian矩阵与酉矩阵:上一篇。本篇定理 3.3()在那一节已经给出证明框架,本篇补充了 的逐项验证。FFT 的一切数学基础都在那篇里:酉矩阵、正交基、Parseval 恒等式。
- 9-1-复数与复向量:复数的极坐标形式、欧拉公式 、复内积与共轭。单位根 的定义与性质全部建立在那篇之上,尤其是"乘法 模相乘、角相加"这条几何直觉。
- 10-4-傅里叶级数与函数空间:本篇的连续(无限维)对应版本。把"函数看作无穷维向量"、把"傅里叶级数看作正交基展开",可以看清 DFT 只是把一个积分换成了有限求和。两篇对照阅读,傅里叶分析的全貌就完整了。
- 4-4-标准正交基与Gram-Schmidt:正交矩阵、标准正交基、坐标公式 。DFT 就是"投影到频率基求坐标",把这套方法用在复指数基上就是傅里叶变换。
- 4-1-四大子空间的正交性:正交补与正交分解。 的列张成整个 ,且两两正交,是"正交基张成整个空间"的最漂亮实例之一。
- 附录-矩阵分解总览:、、、 的统一对比。FFT 的 是第五种重要的分解,值得补进那张对照表一起看。
- 4-3-最小二乘逼近:法方程与"把向量投影到子空间上"。DFT 的每个分量 就是未归一化的投影系数;本篇 3.9 节的 Parseval 恒等式,正是那篇"投影不放大长度"思想在正交基下的定量形式。
- 6-2-矩阵的对角化: 与"用特征向量作基"。本篇 7.3 节的循环卷积定理等价于一句话:循环矩阵可以被傅里叶矩阵对角化,即 ——这是那篇"找一个好基让矩阵变简单"的最漂亮实例之一。
- 7-2-图像压缩与低秩逼近:图像的二维变换与频域压缩。JPEG 用 的 DCT(FFT 的实数变体),压缩之所以可行,正是因为"频域中大多数系数很小"以及"酉变换保持误差的能量"(本篇 7.1 节)。
- 8-3-相似矩阵与基变换:基变换与相似不变量。DFT 是一次基变换(从时间基换到频率基),而"相似变换不改变特征值"解释了为什么 是对角矩阵(循环矩阵的特征值就是 )。
- 11-1-数值稳定性与LU:浮点误差如何在算法中累积。FFT 的舍入误差约为 ——层数越多误差越大,这与那篇讲的"运算次数与被消去项的数量决定误差"是同一套分析框架。
- 11-3-迭代方法与预条件:迭代法的每一步只做一次稀疏矩阵乘法。本篇 3.11 节的"合并矩阵只有 个非零元"与那篇"每步代价 "是同一个思想在两种算法上的表现:把稠密问题拆成一串稀疏问题。
- 12-1-均值方差与概率:随机变量作为向量、均值的线性代数表达。信号的直流分量 正是"均值乘以 ",而功率谱 与那篇"方差分解"的思想完全平行(Parseval 恒等式就是能量版的方差分解)。
参考来源
- MIT OpenCourseWare 18.06 Linear Algebra, Spring 2010, Lecture 26: Complex matrices; fast Fourier transform —— <https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/resources/lecture-26-complex-matrices-fast-fourier-transform/>
- MIT OpenCourseWare 18.06 Linear Algebra 课程主页 —— <https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/>
- Wolfram MathWorld, "Fast Fourier Transform" —— <https://mathworld.wolfram.com/FastFourierTransform.html>
- Wolfram MathWorld, "Discrete Fourier Transform" —— <https://mathworld.wolfram.com/DiscreteFourierTransform.html>
- Wolfram MathWorld, "Root of Unity" —— <https://mathworld.wolfram.com/RootofUnity.html>
- NumPy Reference, numpy.fft.fft —— <https://numpy.org/doc/stable/reference/generated/numpy.fft.fft.html>
- NumPy Reference, numpy.fft.fftfreq —— <https://numpy.org/doc/stable/reference/generated/numpy.fft.fftfreq.html>
- NumPy Reference, Discrete Fourier Transform (numpy.fft) —— <https://numpy.org/doc/stable/reference/routines.fft.html>
- Gilbert Strang, Introduction to Linear Algebra, 5th ed., Wellesley-Cambridge Press, 2016, §9.3
- 同济大学数学系《线性代数》第六版,高等教育出版社(本篇内容不在国内线性代数教材范围内,以授课教材为准)