09-复数与Fourier矩阵

第九部分：复数与 Fourier 矩阵

本文件对应原 PDF 第 60-66 页。

本部分内容

• 9.1 复数 与单位圆
• 9.2 复矩阵：Hermitian 矩阵与酉矩阵
• 9.3 Fourier 矩阵与离散 Fourier 变换
• 9.4 循环卷积与卷积定理
• 9.5 FFT：快速 Fourier 变换

实数线性代数与复数线性代数

实数轴

推广为复平面

两套线性代数结构的对应关系如下：

实数情形	复数情形
$	x
的根为	有 个单位根
	$|z|^2=\sum
转置	共轭转置
点积	内积
对称矩阵	Hermitian 矩阵
正交矩阵	酉矩阵

实数转置的基本伴随关系是

复数情形则是

Hermitian 矩阵具有实特征值，并可作酉对角化：

其中 为实对角矩阵。

酉矩阵保持复内积和长度：

9.1 复数与单位圆

复数写为

其中 是实部， 是虚部。

其模为

辐角 满足

但实际确定象限时应使用 。

Euler 公式给出复数的极坐标形式：

复共轭为

因此：

复数的加法按直角坐标进行：

乘法在极坐标中最简单：

也就是说，模相乘，辐角相加。

例如：

单位圆由所有满足

的复数组成，这些数都可写为 。

因为

所以

次单位根为

并满足

9.2 Hermitian 矩阵与酉矩阵

在复向量空间中，转置时必须同时取复共轭：

复内积定义为

长度平方为

若把 分为实部和虚部，则

Hermitian 矩阵

若

则称 为 Hermitian 矩阵。其对角元素必为实数，并满足

例如：

特征方程为

所以特征值为

两者均为实数。

对应特征向量可取

它们在复内积意义下相互正交：

酉矩阵

若矩阵 的列在复内积下单位正交，则

若 是方阵，则

称 为酉矩阵。

例如：

是酉矩阵。它保持长度：

酉矩阵的所有特征值都在单位圆上：

归一化 Fourier 矩阵是最重要的酉矩阵之一。

9.3 Fourier 矩阵与离散 Fourier 变换

令

正号指数约定下的 Fourier 矩阵定义为

例如 时，：

工程和软件中也经常采用负号指数的 DFT 矩阵；两种约定互为共轭，必须在正变换和逆变换中保持一致。

次单位根满足

Fourier 矩阵具有正交列，并满足

因此

是酉矩阵。

当 时，

若采用本节的正号指数矩阵作为合成矩阵，则：

是逆向的 Fourier 合成，而系数由

得到。采用负号指数作为正 DFT 时，名称会相反，但数学内容相同。

9.4 循环卷积与卷积定理

取

普通卷积等价于多项式乘法：

所以

长度为 的循环卷积把指数按 折回：

循环卷积可以写成循环矩阵乘法。由 构造：

循环矩阵彼此可交换：

所有循环矩阵都由 Fourier 矩阵的列对角化。因此：

• 与 有相同的 Fourier 特征向量；
• 它们的特征值是相应生成向量的 Fourier 变换；
• 时域中的循环卷积，变成频域中的逐分量乘法。

卷积定理为

其中

表示逐元素乘法。具体是否带比例因子 ，取决于所采用的 DFT 归一化约定。

卷积定理是数字信号处理的核心：可以先用 Fourier 变换进入频域，进行快速逐点相乘，再通过逆变换返回时域。

9.5 FFT：快速 Fourier 变换

直接用 Fourier 矩阵乘向量，需要约

次乘法。

快速 Fourier 变换（FFT）利用 Fourier 矩阵中的递归结构，把计算量降到

原讲义以

为例。直接算法约需一百万次乘法，而基二 FFT 只需约几千次核心乘法。

Cooley-Tukey 分解的第一步

置换矩阵 先把偶数编号的输入

排在前面，再放奇数编号的输入

Fourier 矩阵可分解为

其中 是由适当单位根组成的对角矩阵。

中间的两个零块意味着，原来的一个 1024 点变换被拆成两个互相独立的 512 点变换，计算量几乎减半。

下一步把每个 再分解成两个 ，如此递归：

总共有

层，每层只需 次蝶形运算，因此总复杂度为

所有层中的置换可以合并成一次整体重排。实际 FFT 软件还支持混合基数、素数长度和多维变换；FFTW 是广泛使用的高性能实现之一。