w wyl123ly 的博客
MD

9-3-快速傅里叶变换FFT

137 KB 2026.10.11 原文件

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 需要:

  1. 做两次 点 DFT:成本 ;
  2. 做置换 (把奇偶下标分开):(只是重新排列,不需要算术运算);
  3. 算旋转因子 ( 个乘法):;
  4. 做 次加法和 次减法:。

所以

其中 是某个常数。递归的终止条件是 ( 点 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 的步骤()

  1. 给定 ,计算 。
  2. 预计算所有需要的幂次 (可以递推:,避免重复调用 exp)。
  3. 对每个 ,累加 。
  4. 输出 。

代价: 次复数乘法与 次复数加法。

4.2 FFT 的步骤(递归版,)

  1. 若 ,直接返回 (1 点 DFT 就是恒等)。
  2. 把 按下标奇偶拆成 与 (各长 )。
  3. 递归计算 与 。
  4. 计算旋转因子 ()。
  5. 对 :
  • ;
  • 。
  1. 返回 。

实用要点:

  • 尽量取 为 的幂。此时递归每一层都是奇数长度的一半,直到 ,最干净。
  • 非 的幂时,可以分解 的因子(混合基 FFT),或者把 补零到最近的 的幂(补零不会改变 DFT 的数学定义,但会改变频率采样的密度——补零相当于对频谱做插值)。
  • 迭代实现:把递归改成自底向上。此时需要先按位反转置换(bit-reversal permutation)重排输入。 时下标顺序为 。这就是 MathWorld 提到的"Cooley–Tukey 算法先按位反转重排输入"。

4.3 手工计算 的 FFT 步骤(下一节给出完整推导)

  1. 写下 与 。
  2. 写出分块分解 。
  3. 确定 (把 与 分开)。
  4. 确定 。
  5. 写出 。
  6. 逐层乘出来验证与原 一致。

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 的运算可以分成三部分:

  1. 两次 点递归调用: 次乘法、 次加减;
  2. 旋转因子乘法:,共 个(每个一次复数乘法);
  3. 蝶形加减:对 各算一次 与一次 ,共 次加减。

所以

递归终止条件: 时 点 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) @ x4numpy 用 约定,即 ;它与本篇的 互为"时间反演 + 共轭"( 与 互换)✓ 符合 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,正交频分复用)。它的做法是:

  1. 把高速数据流分成成千上万个低速子载波;
  2. 每个子载波用不同的频率 承载;
  3. 发射端用 IFFT 把这些子载波一次性合成成时域波形;
  4. 接收端用 FFT 把收到的时域信号一次性分解回各个子载波上的数据。

为什么必须用 FFT:一个 5G 载波可能有 个子载波,且要求毫米级的时间调度。 时朴素 DFT 需 次运算,FFT 只需约 次——相差 300 多倍,直接决定了能不能实时。而且"正交"这个词在这里是字面意义的:各子载波频域互不干扰,正是 列正交的物理体现。

6.4 数值求解偏微分方程

求解 (波动方程)、热传导方程等 PDE 时,谱方法(spectral method)的做法是:

  1. 把解按空间做傅里叶展开:;
  2. 代入方程后,空间导数 变成乘以 ,微分方程退化为关于 的常微分方程(每个 独立!);
  3. 解完 后用逆 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 是算法。就像"求 个数之和"是问题,"分治法求和"是算法——你不可能"只学算法不学问题",因为算法要解决的就是那个问题,不懂问题就不知道算法在算什么。

具体区别:

DFTFFT
本质一个线性变换(矩阵 )一族计算该变换的算法
复杂度定义上就是
输出与 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):

  1. 能用 rfft 就用 rfft(实输入),它直接省一半。
  2. 需要指定长度时,选"高度合数"。numpy 的 pocketfft 对 也有专门优化,不必强求 的幂。例如 比 (质数)快很多。
  3. 补零要谨慎:补零能让长度变成 的幂并加速,但会改变频率采样点(相当于做插值)。如果你需要的是"精确的 点 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 的典型场景:

  1. 频谱分析:想知道一段信号里有哪些频率成分、各自多强。这是 FFT 最经典的用途。
  2. 滤波:设计好频域响应 ,把信号变换过去、逐点相乘、再变换回来。代价 ,比时域卷积的 快得多(当滤波器很长时优势尤其明显)。
  3. 卷积 / 相关运算:两个长序列的卷积、互相关、自相关。用卷积定理(定理 7.1)。
  4. 求解 PDE 的谱方法:空间导数变成乘以 ,微分方程退化为独立的常微分方程。
  5. 频域压缩:JPEG 的 DCT、音频编码的 MDCT,都是 FFT 的实数变体。

不该用 FFT(或不合适)的场景:

  1. 数据很短( 只有几十)。此时 的常数因子更小,FFT 的递归/迭代开销反而不划算。本篇例题 1 第 7 步已经算过: 时朴素法 16 次乘法,FFT 约 10 次,几乎没优势。
  2. 信号非平稳,且你只想看"局部"的频率。FFT 给出的是整段信号的全局频谱,无法告诉你"第 3 秒到第 4 秒之间出现了什么频率"。这时要用短时傅里叶变换(STFT,即分帧做 FFT)或小波变换。
  3. 只关心少数几个频率点。如果要算的 只有几个(比如 个),而 ,直接按定义算这 个值只要 ,比做完整 FFT 的 快得多。这类需求用 Goertzel 算法 或直接按定义算。
  4. 需要极高精度(超过双精度)。FFT 会累积浮点舍入误差(虽然通常很小,约 ),在需要精确整数结果的场合(如大整数乘法、密码学)要考虑用数论变换(NTT)。
  5. 数据缺失或非均匀采样。标准 FFT 要求等间隔采样点。非均匀采样要用 NUFFT(non-uniform FFT)或 Lomb–Scargle 周期图。

一句话总结:FFT 是"把整段信号一次性分解到全部频率上"的利器。如果你的问题符合这个描述,就用它;如果你只要局部信息、少数频率点,或者数据量很小,就该考虑别的工具。


本篇小结

核心结论(八条主线)

  1. 单位根: 的 个幂 是复平面上单位圆的 等分点(正 边形顶点),构成一个循环群 。核心性质:、、、、( 偶)、 是 次本原单位根。
  2. 本原根与子群嵌套: 是本原 次单位根 (共 个);若 则 。"单位根里嵌套着更小的单位根"正是 FFT 分治的代数根源。
  3. 求和公式(正交关系的核心):。几何版本是"正多边形顶点向量之和为零"。
  4. 傅里叶矩阵:,它是对称矩阵(),满足

并且 ( 为反序置换)、、。因此 是酉矩阵, 本身是"酉矩阵的 倍"。

  1. DFT 就是换到频率基:, 是信号在频率方向上的(未归一化)投影;Parseval 恒等式 说明变换保能量。
  2. FFT 是算法不是变换:蝶形恒等式

等价于矩阵分解 。输出与 DFT 完全相同,只是快。

  1. 复杂度:递推 给出 ;精确计数是 次复数乘法、 次加减,而朴素 DFT 需要 次乘法,比值为 。加速的唯一来源是"合并矩阵稀疏"( 个非零元),而不是"分治"本身。
  2. 傅里叶矩阵的谱:由 知 的特征值 满足 ,即 ;又 是正规矩阵(),故它在复域可酉对角化(9-2-Hermitian矩阵与酉矩阵 的框架直接适用)。

易混概念对照表

容易混淆的一对关键区别判据 / 例子
DFT 与 FFTDFT 是数学变换(矩阵 ),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
  • 同济大学数学系《线性代数》第六版,高等教育出版社(本篇内容不在国内线性代数教材范围内,以授课教材为准)