线性代数 - 复向量与复矩阵

131

概述

本文的内容如下:

  • 复数的概念
  • 复向量与复矩阵
  • 傅里叶矩阵与快速傅里叶变换

复数

相信大家在高中时期都学过复数,这里简单复习一下。

虚数与复数

我们知道 $x^2=-1$ 在实数范围内是无解的。不过人是有创造能力的,既然实数范围内无解,那么就创造一个虚数Imaginary Number)吧!有一天,人说:要有 $i$,于是有了 $i$。人们用 $i$ 表示虚数的最小单位,并规定 $i^2=-1$。

虚数 $i$ 同实数 $1$ 一样,也可以进行加减乘除,比如 $i+i=2i$,$2i-i=i$,$2i \div i = 2$,$i \times i=-1$。

一个实数加一个虚数,就成了复数Complex Number),比如:$1+2i$,$2-3i$ 都是复数。复数的实数部分叫做实部,虚数部分叫做虚部。比如:$1+2i$ 的实部为 $1$,虚部为 $2i$。

复平面

在直角坐标系中,如果用横轴表示复数的实部,用纵轴表示复数的虚部,那么所有复数都可以用这个坐标平面上的点来表示。这个平面就叫做复平面Complex Plane),记作 $\mathbb{C}$。例如,$z= 4+3i$ 在复平面中表示为:

复平面上的点 4+3i

可以看到 $\mathbb{C}$ 中的点类似于 $\mathbb{R}^2$ 中的向量。

在复平面中,$z$ 到原点的距离叫做幅值,$z$ 与实轴正向的夹角叫做幅角

共轭复数

实部相同,虚部互为相反数的两个复数互为共轭复数Conjugate Complex Number),一个复数 $z$ 的共轭复数用 $\overline{z}$ 表示。比如 $z = 2+3i$ 的共轭复数为 $\overline{z} = 2-3i$ 。

复数的运算

两个复数可以相加减,规则为实部与实部相加减,虚部与虚部相加减,比如:$(1+2i) + (2-3i) = 3-i$,$(1+2i) - (2-3i) = -1+5i$。

共轭的两个复数相加得实数。(证明

证明
$$ (a+bi) + (a-bi) = 2a $$

共轭的两个复数相减得虚数。(证明

证明
$$ (a+bi) - (a-bi) = 2bi $$

两个复数之和的共轭与这两个复数的共轭之和相等,即 $ \overline{ z_1 + z_2 } = \overline{z_1} + \overline{z_2} $。(证明

证明 假设 $z_1 = a+bi$,$z_2 = c-di$,则:
\begin{align*} \overline{ z_1 + z_2 } &= \overline{ (a+bi) + (c+di)} = \overline{ (a+c) + (b+d)i } \\ &= (a+c) - (b+d)i = (a-bi) + (c-d)i \\&= \overline{(a+bi)} + \overline{(c+di)} = \overline{z_1} + \overline{z_2} \end{align*}

两个复数也可以相乘,规则类似多项式乘法,但要注意 $i^2=-1$,比如:$(1+2i) \times (2-3i)= 2 - 3i + 4i - 6i^2 = 8 + i$。

共轭的两个复数相乘得实数。(证明

证明
$$ (a+bi) \times (a-bi) = a^2 - abi + abi - (bi)^2 = a^2 + b^2 $$

类似于 $\mathbb{R}^2$ 中向量的模长,复数的模长为复平面中的点到原点的距离,即幅值。如下图所示:

复数的模

若 $z = a + bi$,则 $z$ 的模为:$$\left\| z \right\| = \sqrt{a^2+b^2} $$ 亦即 $$ \left\| z \right\|^2 = a^2 + b^2 $$

根据 定义 1性质 4 的证明结果。可得:

$$\left\| z \right\|^2 = z \overline{z}$$

两个复数之积的共轭与这两个复数的共轭之积相等,即:$ \overline{ z_1 \times z_2 } = \overline{z_1} \times \overline{z_2} $ (证明

证明 假设 $z_1 = a+bi$,$z_2 = c+di$,则:
\begin{align*} \overline{ z_1 \times z_2 } &= \overline{ (a+bi) \times (c+di)} = \overline{ (ac-bd) + (ad+bc)i } \\ &= (ac-bd) - (ad+bc)i = ac - adi - bci + bdi^2 \\ &= a(c-di) - bi(c-di) = (a-bi) \times (c-di) \\ &= \overline{(a+bi)} \times \overline{(c+di)} = \overline{z_1} \times \overline{z_2} \end{align*}

根据 性质 5,有:

假设 $\lambda$ 与 $\mathbf{x}$ 是实矩阵 $\mathbf{A}$ 的特征值与特征向量,那么 $\overline{\lambda}$ 与 $\overline{\mathbf{x}}$ 也是 $\mathbf{A}$ 的特征值与特征向量。(证明

证明 根据假设有:$ \mathbf{A}\mathbf{x} = \lambda \mathbf{x} $,两边取共轭,得:$ \overline{ \mathbf{A} \mathbf{x}} = \overline{\lambda \mathbf{x}} \ \Longrightarrow \ \mathbf{A} \overline{\mathbf{x}} = \overline{\lambda} \overline{\mathbf{x}} $

如何计算复数的除法?比如:$ \dfrac{1+2i}{2-i} $,在分母为复数的情况下,我们可以将分子分母分别乘以分母的共轭:

$$ \dfrac{1+2i}{2-3i} = \dfrac{1+2i}{2-i} \dfrac{2+i}{2+i} = i $$

欧拉公式

欧拉公式 巧妙地将指数函数与三角函数联系在了一起:

$$ e^{ix} = \cos x + i \sin x $$

由于 $\left\| e^{ix} \right\| = \sqrt{ \cos^2 x + \sin^2 x } = 1 $,因此在复平面内,$e^{ix}$ 是一个模长为 $1$ 的单位圆:

欧拉公式

从上图中也可以看到,当幅角 $x$ 倍增到 $2x$ 时,$e^{ix}$ 则变为 $\left( e^{ix} \right)^2 = e^{i2x}$。

复向量与复矩阵

复向量是其分量包含复数的向量。

我们已经知道如何计算一个实向量的长度:

$$ \left\| \mathbf{x} \right\|^2 = \mathbf{x}^T \mathbf{x} = \sum\limits_{i=1}^{n} x_i x_i = \sum\limits_{i=1}^{n} x_i^2 $$

上式表明实向量长度的平方等于每个分量的平方之和。而对于复向量,我们也希望它的长度能够等于其分量的模的平方之和。比如,假设有复向量 $\mathbf{z} = \begin{bmatrix} z_1 \\ z_2 \end{bmatrix} = \begin{bmatrix} 1+2i \\ 2-3i \end{bmatrix}$ ,我们希望 $\mathbf{z}$ 的长度的平方为:

$$ \left\| \mathbf{z} \right\|^2 = \left|z_1\right|^2 + \left|z_2\right|^2 = \left| 1+2i \right|^2 + \left| 2-3i \right|^2 = 1^2 + 2^2 + 2^2 + 3^2 = 18 $$

由于复数的模的平方等于它与它的共轭复数的积,结合上式,有:

$$ \left\| \mathbf{z} \right\|^2 = \left| 1+2i \right|^2 + \left| 2-3i \right|^2 = (1-2i)(1+2i) + (2+3i)(2-3i) $$

上式的结果恰好是两个向量内积的形式:

$$ (1-2i)(1+2i) + (2+3i)(2-3i) = \begin{bmatrix} 1-2i \\ 2+3i \end{bmatrix}^T \begin{bmatrix} 1+2i \\ 2-3i \end{bmatrix} $$

可以看到向量 $\begin{bmatrix} 1-2i \\ 2+3i \end{bmatrix}$ 是由 $\mathbf{z} = \begin{bmatrix} 1+2i \\ 2-3i \end{bmatrix}$ 的分量的共轭复数组成的。我们将向量 $\begin{bmatrix} 1-2i \\ 2+3i \end{bmatrix}$ 称为 $\mathbf{z} = \begin{bmatrix} 1+2i \\ 2-3i \end{bmatrix}$ 的共轭向量,记为 $\overline{\mathbf{z}}$。于是有:

$$ \left\| \mathbf{z} \right\|^2 = \overline{\mathbf{z}}^T \mathbf{z} $$

上式的 $\overline{\mathbf{z}}^T$ 称为 $\mathbf{z}$ 的共轭转置向量,也记为 $\mathbf{z}^H$,这个记号源于法国数学家埃尔米特Hermite),$H$ 是 $Hermitian$ 的首字母。即:

$$ \left\| \mathbf{z} \right\|^2 = \overline{\mathbf{z}}^T \mathbf{z} = \mathbf{z}^H \mathbf{z} $$

上式就是两个相同的复向量的内积,即 $ \mathbf{z} \cdot \mathbf{z} = \mathbf{z}^H \mathbf{z} $。我们可以通过类比,得到两个复向量 $\mathbf{u}$ 和 $\mathbf{v}$ 的内积:

$$ \mathbf{u} \cdot \mathbf{v} = \mathbf{u}^H \mathbf{v} $$

如果 $ \mathbf{u} \cdot \mathbf{v} = \mathbf{u}^H \mathbf{v} = 0 $,那么称 $\mathbf{u}$ 与 $\mathbf{v}$ 正交。

实向量标准正交的概念也同样适用于复向量:


定义 假设 $\mathbf{q}_1, \mathbf{q}_2, \cdots, \mathbf{q}_n$ 是向量空间 $\mathbb{C}^m$ 中的 $n$ 个向量,如果:

$$ \mathbf{q}_i^H \mathbf{q}_j = \left\{ \begin{array}{l} 0 \quad (i \ne j) \\ 1 \quad (i = j) \end{array} \right. \quad (i,j=1,2,\cdots,n) $$

则称 $\mathbf{q}_1, \mathbf{q}_2, \cdots, \mathbf{q}_n$ (在 $\mathbb{C}^m$ 中)标准正交。由 $\mathbf{q}_1, \mathbf{q}_2, \cdots, \mathbf{q}_n$ 组成的基为 $\mathbb{C}^m$ 下的标准正交基。

可以很容地将上述概念应用到矩阵,假设复矩阵 $\mathbf{A}$ 由复向量 $\mathbf{z}_1$, $\mathbf{z}_2$, $\cdots$, $\mathbf{z}_n$ 组成:

$$ \mathbf{A} = \begin{bmatrix} \mathbf{z}_1 & \mathbf{z}_2 & \cdots & \mathbf{z}_n \end{bmatrix} $$

那么 $\mathbf{A}$ 的共轭转置矩阵就表示为:

$$ \mathbf{A}^H = \begin{bmatrix} \mathbf{z}_1^H \\ \mathbf{z}_2^H \\ \vdots \\ \mathbf{z}_n^H \end{bmatrix} $$

在复数范围内,由标准正交基组成的方阵 $\mathbf{Q}$ 称为酉矩阵Unitary Matrix),酉矩阵满足:$ \mathbf{Q}^H \mathbf{Q} = \mathbf{I} $

如果复矩阵 $\mathbf{A}$ 的共轭转置 $\mathbf{A}^H$ 等于它本身,即如果 $\mathbf{A}^H = \mathbf{A}$,那么就称复矩阵 $\mathbf{A}$ 为埃尔米特矩阵Hermitian matrix)。比如下面的复矩阵就是埃尔米特矩阵:

$$ \begin{bmatrix} 2 & 2-i \\ 2+i & 1 \end{bmatrix} $$

傅里叶矩阵

傅里叶矩阵Fourier Matrix)如下:

$$ \mathbf{F}_n = \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & w & w^2 & \cdots & w^{n-1} \\ 1 & w^2 & w^4 & \cdots & w^{2(n-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & w^{n-1} & w^{2(n-1)} & \cdots & w^{(n-1)^2} \end{bmatrix} $$

其中 $n$ 表示矩阵的阶数,矩阵的元素为 $\left( \mathbf{F} \right)_{ij} = w^{i \times j} \ (i,j \in \{ 0, 1, 2, \cdots, n-1 \})$,其中 $w = \huge{e^{\frac{2\pi}{n}i}}$。比如 $\mathbf{F}_4$ 的第 $2$ 行第 $3$ 列的元素 $(\mathbf{F}_4)_{23} = w^{2\times 3} = w^6 = (e^{\frac{2\pi}{4}i})^6 = (\cos{\dfrac{\pi}{2}} + i \sin{\dfrac{\pi}{2}})^6 = i^6 = -1 $。

我们来分析一下傅里叶矩阵:

首先,傅里叶矩阵是一个对称矩阵,即 $\mathbf{F}^T = \mathbf{F}$。这很容易从它的定义式看出来。由于共轭不影响对称性,因此 $ \mathbf{F}^H = \overline{\mathbf{F}}^T = \overline{\mathbf{F}}$。
其次,因为傅里叶矩阵的对角线不是实数,无法满足 $\mathbf{F}^H = \mathbf{F}$,所以傅里叶矩阵不是埃尔米特矩阵。
第三,傅里叶矩阵的列向量是正交的,每一列向量的模长都是 $\sqrt{n}$,因此 $\dfrac{1}{\sqrt{n}}\mathbf{F}$ 是一个酉矩阵。于是有 $ \left(\dfrac{1}{\sqrt{n}} \mathbf{F}^H \right) \left( \dfrac{1}{\sqrt{n}} \mathbf{F} \right) = \mathbf{I} $,整理可得下面两个公式:

$$ \mathbf{F}^H \mathbf{F} = n \mathbf{I} $$

$$ \mathbf{F}^{-1} = \dfrac{1}{n} \mathbf{F}^H = \dfrac{1}{n} \overline{\mathbf{F}} $$

下面是几个例子:



$3$ 阶傅里叶矩阵为:
$$ \mathbf{F}_3 = \begin{bmatrix} w^0 & w^0 & w^0 \\ w^0 & w^1 & w^2 \\ w^0 & w^2 & w^4 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 \\ 1 & -\dfrac{1}{2} + \dfrac{\sqrt{3}}{2}i & -\dfrac{1}{2} - \dfrac{\sqrt{3}}{2}i \\ 1 & -\dfrac{1}{2} - \dfrac{\sqrt{3}}{2}i & -\dfrac{1}{2} + \dfrac{\sqrt{3}}{2}i \end{bmatrix} $$
$w^0$, $w^1$, $w^2$, $w^4$ 的计算如下图:

3阶傅里叶矩阵的计算
我们可以验证 $\mathbf{F}_3$ 的各列是正交的,比如第 $2$ 列与第 $3$ 列的内积如下:
\begin{align*} \mathbf{f}_2^H \mathbf{f}_3 &= \begin{bmatrix} 1 & -\dfrac{1}{2} - \dfrac{\sqrt{3}}{2}i & -\dfrac{1}{2} + \dfrac{\sqrt{3}}{2}i \end{bmatrix} \begin{bmatrix} 1 \\ -\dfrac{1}{2} - \dfrac{\sqrt{3}}{2}i \\ -\dfrac{1}{2} + \dfrac{\sqrt{3}}{2}i \end{bmatrix} \\ &= \left( 1 - \dfrac{1}{2} + \dfrac{\sqrt{3}}{2}i - \dfrac{1}{2} - \dfrac{\sqrt{3}}{2}i \right) \\ &= 0 \end{align*}
读者可自行验证其余各列的正交性。



$4$ 阶傅里叶矩阵为:
$$ \mathbf{F}_4 = \begin{bmatrix} w^0 & w^0 & w^0 & w^0 \\ w^0 & w^1 & w^2 & w^3 \\ w^0 & w^2 & w^4 & w^6 \\ w^0 & w^3 & w^6 & w^9 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{bmatrix} $$
其中,$w = e^{\dfrac{2\pi}{4}} = i$。$w^0$, $w^1$, $w^2$, $w^3$, $w^4$, $w^6$, $w^9$ 如下图所示:

4阶傅里叶矩阵的计算
我们可以验证 $\mathbf{F}_4$ 的各列是正交的,比如第 $2$ 列与第 $4$ 列的内积如下:
\begin{align*} \mathbf{f}_2^H \mathbf{f}_4 &= \begin{bmatrix} 1 & -i & -1 & i \end{bmatrix} \begin{bmatrix} 1 \\ -i \\ -1 \\ i \end{bmatrix} \\ &= \left( 1 - 1 + 1 - 1 \right) \\ &= 0 \end{align*}
读者可自行验证其余各列的正交性。

结合上面两个例子的图像,我们来分析 $\mathbf{F}_n$ 的元素 $w^p$ 与 $w^{kn + p}$,$(k \in \mathbb{R})$ 的关系:

\begin{align*} w^{kn+p} &= \large{e^{\frac{2\pi}{n} (kn+p) i}} \\ &= \large{e^{(2k\pi + \frac{2p\pi}{n})i}} \\ &= \cos(2k\pi + \frac{2p\pi}{n}) + i \sin(2k\pi + \frac{2p\pi}{n}) \\ &= \cos(\frac{2p\pi}{n}) + i \sin(\frac{2p\pi}{n}) \\ &= e^{\frac{2\pi}{n}pi} \\ &= w^p \end{align*}

由此可见 $n$ 阶傅里叶矩阵的元素 $w^p$ 是一个以它的 $n$ 次幂数为周期的数。比如 $4$ 阶傅里叶矩阵的元素 $w^1$ 是一个以它的 $4$ 次幂数为周期的数:$w^1 = w^5 = w^9 = w^{13} $。

$$w^p = w^{kn+p} \quad (k \in \mathbb{R}) $$

$\mathbf{F}_n$ 的元素与 $\mathbf{F}_{2n}$ 的元素也存在着对应关系,假设 $w_{2n}$ 为 $\mathbf{F}_{2n}$ 的元素,则:

\begin{align*} w_{2n}^{2p} = e^{\frac{2\pi}{2n}2pi} = e^{\frac{2\pi}{n}pi} = w_n^p \end{align*}
$$ w_{2n}^{2p} = w_n^p $$

在一些特殊的等分点,$w_n$ 还有一些特殊的值,比如 $w_n^{\frac{n}{4}} = e^{\frac{2\pi}{n}\frac{n}{4}i} = \cos \frac{\pi}{2} + i \sin \frac{\pi}{2} = i$。还有一些特殊的等分点以及对应的值:

$$ w_n^{\frac{n}{4}} = i $$

$$ w_n^{\frac{n}{2}} = -1 $$

$$ w_n^{\frac{3n}{4}} = -i $$

傅里叶变换

傅里叶变换就是用傅里叶矩阵左乘一个向量 $\mathbf{c}$,使其变换到另一个向量 $\mathbf{y}$:

变换 1
$$ \mathbf{y} = \mathbf{F} \mathbf{c} $$

也可以反过来变换,即已知 $\mathbf{y}$,求 $\mathbf{c}$:

$$ \mathbf{c} = \mathbf{F}^{-1} \mathbf{y} $$

根据 公式 4,有:

$$ \mathbf{c} = \dfrac{1}{n} \overline{\mathbf{F}} \mathbf{y} $$

在做变换时,由于 $n$ 是常数,因此通常不考虑 $n$ 的作用,直接将上式记为:

变换 2
$$ \mathbf{c} = \overline{\mathbf{F}} \mathbf{y} $$

下面是几个例子:



利用 变换 1 对 $\mathbf{c} = \begin{bmatrix} c_0 \\ c_1 \\ c_2 \\ c_3 \end{bmatrix}$ 进行傅里叶变换。
\begin{align*} \mathbf{y} &= \mathbf{F}_4 \mathbf{c} \\&= \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{bmatrix} \begin{bmatrix} c_0 \\ c_1 \\ c_2 \\ c_3 \end{bmatrix} \\ &= \begin{bmatrix} c_0 + c_1 + c_2 + c_3 \\ c_0 + c_1 i - c_2 - c_3 i \\ c_0 - c_1 + c_2 - c_3 \\ c_0 - c_1 i - c_2 + c_3 i \end{bmatrix} \end{align*}



利用 变换 2 对 $\mathbf{y} = \begin{bmatrix} y_0 \\ y_1 \\ y_2 \\ y_3 \end{bmatrix}$ 进行傅里叶变换。
\begin{align*} \mathbf{c} &= \overline{\mathbf{F}}_4 \mathbf{y} \\&= \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -i & -1 & i \\ 1 & -1 & 1 & -1 \\ 1 & i & -1 & -i \end{bmatrix} \begin{bmatrix} y_0 \\ y_1 \\ y_2 \\ y_3 \end{bmatrix} \\ &= \begin{bmatrix} y_0 + y_1 + y_2 + y_3 \\ y_0 - y_1 i - y_2 + y_3 i \\ y_0 - y_1 + y_2 - y_3 \\ y_0 + y_1 i - y_2 - y_3 i \end{bmatrix} \end{align*}

快速傅里叶变换

考虑 $n$ 傅里叶变换的效率:

\begin{align*} & \mathbf{y} = \mathbf{F}_n \mathbf{c} \\ \Longrightarrow \quad & \begin{bmatrix} y_0 \\ y_1 \\ \vdots \\ y_{n-1} \end{bmatrix} = \begin{bmatrix} w^0 & w^0 & w^0 & \cdots & w^0 \\ w^0 & w & w^2 & \cdots & w^{n-1} \\ w^0 & w^2 & w^4 & \cdots & w^{2(n-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ w^0 & w^{n-1} & w^{2(n-1)} & \cdots & w^{(n-1)^2} \end{bmatrix} \begin{bmatrix} c_0 \\ c_1 \\ \vdots \\ c_{n-1} \end{bmatrix} \end{align*}

$y_0$ 的计算需要 $n$ 次乘法,$y_1$ 的计算同样需要 $n$ 次乘法,一直到 $y_{n-1}$ 的计算还是需要 $n$ 次乘法,又因为傅里叶矩阵不存在大量的 $0$(即它不是稀疏矩阵),因此需要 $n^2$ 次乘法。用算法的语言来说,它的时间复杂度为 $\Omega (n^2)$。当 $n=1024$ 时,需要 $1024 \times 1024$ 次计算,这是非常耗时的。

那么有没有一种算法,能使这个变换效率更高呢?人们总结了很多实用的算法设计思路,分治法就是其中之一。虽然不知道分治法在这里可以起到什么作用,但是我们没有理由不尝试一下。毕竟,尝试是成功的前提(当然,尝试也是失败的前提,但我们不会因为害怕失败而停下前进的脚步,对吗?)。

下面我们用 $w_n$ 表示 $\mathbf{F}_n$ 的元素,开始尝试用分治法来化简上面的式子:

\begin{align*} & \begin{array}{lll} & \begin{bmatrix} y_0 \\ y_1 \\ \vdots \\ y_{n-1} \end{bmatrix} = \begin{bmatrix} w_n^{0 \times 0} & w_n^{0 \times 1} & w_n^{0 \times 2} & \cdots & w_n^{0 \times (n-1)} \\ w_n^{1 \times 0} & w_n^{1 \times 1} & w_n^{1 \times 2} & \cdots & w_n^{1 \times (n-1)} \\ w_n^{2 \times 0} & w_n^{2 \times 1} & w_n^{2 \times 2} & \cdots & w_n^{2 \times (n-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ w_n^{ (n-1) \times 0 } & w_n^{(n-1) \times 1} & w_n^{(n-1) \times 2} & \cdots & w_n^{(n-1) \times (n-1)} \end{bmatrix} \begin{bmatrix} c_0 \\ c_1 \\ \vdots \\ c_{n-1} \end{bmatrix} \\ &= \begin{bmatrix} \sum\limits_{k=0}^{n-1} w_n^{0k}c_k \\ \sum\limits_{k=0}^{n-1} w_n^{1k}c_k \\ \vdots \\ \sum\limits_{k=0}^{n-1} w_n^{(n-1)k}c_k \end{bmatrix} \end{array} \\ & \text{在这里使用分治法,将 $\sum$ 拆分成偶数项与奇数项。令 $m=\dfrac{1}{2}n$。继续整理:} \\ & \begin{array}{lll} & = \begin{bmatrix} \sum\limits_{k=0}^{m-1} w_n^{0 \times 2k}c_{2k} + \sum\limits_{k=0}^{m-1} w_n^{0 \times (2k+1)}c_{2k+1} \\ \sum\limits_{k=0}^{m-1} w_n^{1 \times 2k}c_{2k} + \sum\limits_{k=0}^{m-1} w_n^{1 \times (2k+1)}c_{2k+1} \\ \vdots \\ \sum\limits_{k=0}^{m-1} w_n^{(n-1) 2k}c_{2k} + \sum\limits_{k=0}^{m-1} w_n^{(n-1) (2k+1)}c_{2k+1} \end{bmatrix} \\ & = \begin{bmatrix} \sum\limits_{k=0}^{m-1} w_n^{2 (0 \times k)}c_{2k} + \sum\limits_{k=0}^{m-1} w_n^{2(0 \times k)} w_n^{0 \times 1} c_{2k+1} \\ \sum\limits_{k=0}^{m-1} w_n^{2(1 \times k)}c_{2k} + \sum\limits_{k=0}^{m-1} w_n^{2(1 \times k)} w_n^{1 \times 1} c_{2k+1} \\ \vdots \\ \sum\limits_{k=0}^{m-1} w_n^{2 (n-1) k}c_{2k} + \sum\limits_{k=0}^{m-1} w_n^{2 (n-1) k } w_n^{(n-1) \times 1} c_{2k+1} \end{bmatrix} \end{array} \\ & \text{根据 公式 6,并且注意 $m=\dfrac{1}{2}n$,有 $w_{n}^{2k} = w_m^k$。继续化简:} \\ & \begin{array}{lll} &= \begin{bmatrix} \sum\limits_{k=0}^{m-1} w_m^{0 \times k}c_{2k} + w_n^{0} \sum\limits_{k=0}^{m-1} w_m^{0 \times k} c_{2k+1} \\ \sum\limits_{k=0}^{m-1} w_m^{1 \times k}c_{2k} + w_n^{1} \sum\limits_{k=0}^{m-1} w_m^{1 \times k} c_{2k+1} \\ \vdots \\ \sum\limits_{k=0}^{m-1} w_m^{(n-1) k}c_{2k} + w_n^{n-1} \sum\limits_{k=0}^{m-1} w_m^{(n-1) k} c_{2k+1} \end{bmatrix} \end{array} \\ & \text{将前 $m$ 项看成一组,将后 $m$ 项看成一组。继续整理:} \\ & \begin{array}{lll} &= \begin{bmatrix} \sum\limits_{k=0}^{m-1} w_m^{0 \times k}c_{2k} + w_n^{0} \sum\limits_{k=0}^{m-1} w_m^{0 \times k} c_{2k+1} \\ \vdots \\ \sum\limits_{k=0}^{m-1} w_m^{(m-1) k}c_{2k} + w_n^{m-1} \sum\limits_{k=0}^{m-1} w_m^{(m-1) k} c_{2k+1} \\ \sum\limits_{k=0}^{m-1} w_m^{m k}c_{2k} + w_n^m \sum\limits_{k=0}^{m-1} w_m^{mk} c_{2k+1} \\ \vdots \\ \sum\limits_{k=0}^{m-1} w_m^{(n-1) k}c_{2k} + w_n^{n-1} \sum\limits_{k=0}^{m-1} w_m^{ (n-1)k } c_{2k+1} \end{bmatrix} \end{array} \\ & \text{从后 $m$ 项的 $w_n^j$ 中提取出 $w_n^m$,继续整理:} \\ & \begin{array}{lll} &= \begin{bmatrix} \sum\limits_{k=0}^{m-1} w_m^{0 \times k}c_{2k} + w_n^{0} \sum\limits_{k=0}^{m-1} w_m^{0 \times k} c_{2k+1} \\ \vdots \\ \sum\limits_{k=0}^{m-1} w_m^{(m-1) k}c_{2k} + w_n^{m-1} \sum\limits_{k=0}^{m-1} w_m^{(m-1) k} c_{2k+1} \\ \sum\limits_{k=0}^{m-1} w_m^{m k}c_{2k} + w_n^m w_n^0 \sum\limits_{k=0}^{m-1} w_m^{mk} c_{2k+1} \\ \vdots \\ \sum\limits_{k=0}^{m-1} w_m^{(n-1) k}c_{2k} + w_n^{m} w_n^{m -1} \sum\limits_{k=0}^{m-1} w_m^{ (n-1)k } c_{2k+1} \end{bmatrix} \end{array} \\ & \text{根据 公式 8,并注意 $m = \frac{1}{2}n$,有 $w_n^m = -1$。继续整理:} \\ & \begin{array}{lll} &= \begin{bmatrix} \sum\limits_{k=0}^{m-1} w_m^{0 \times k}c_{2k} + w_n^{0} \sum\limits_{k=0}^{m-1} w_m^{0 \times k} c_{2k+1} \\ \vdots \\ \sum\limits_{k=0}^{m-1} w_m^{(m-1) k}c_{2k} + w_n^{m-1} \sum\limits_{k=0}^{m-1} w_m^{(m-1) k} c_{2k+1} \\ \sum\limits_{k=0}^{m-1} w_m^{m k}c_{2k} - w_n^0 \sum\limits_{k=0}^{m-1} w_m^{mk} c_{2k+1} \\ \vdots \\ \sum\limits_{k=0}^{m-1} w_m^{(n-1) k}c_{2k} - w_n^{m-1} \sum\limits_{k=0}^{m-1} w_m^{ (n-1)k } c_{2k+1} \end{bmatrix} \end{array} \\ & \text{令 $\mathbf{c}_{even} = \begin{bmatrix} c_0 \\ c_2 \\ \vdots \\ c_{2(m-1)} \end{bmatrix} $,$\mathbf{c}_{odd} = \begin{bmatrix} c_1 \\ c_2 \\ \vdots \\ c_{2m-1} \end{bmatrix}$,$\mathbf{D} = \begin{bmatrix} w_n^0 & 0 & \cdots & 0 \\ 0 & w_n^1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & w_n^{m-1} \end{bmatrix}$,继续整理:} \\ & \begin{array}{lll} &= \begin{bmatrix} \mathbf{F}_m \mathbf{c}_{even} + \mathbf{D} \mathbf{F}_m \mathbf{c}_{odd} \\ \mathbf{F}_m \mathbf{c}_{even} - \mathbf{D} \mathbf{F}_m \mathbf{c}_{odd} \end{bmatrix} \\ &= \begin{bmatrix} \mathbf{F}_m & \mathbf{D} \mathbf{F}_m \\ \mathbf{F}_m & -\mathbf{D} \mathbf{F}_m \end{bmatrix} \begin{bmatrix} \mathbf{c}_{even} \\ \mathbf{c}_{odd} \end{bmatrix} \end{array} \\ & \text{令 $\mathbf{P} = \begin{bmatrix} 1&0&0&0 &\cdots&0&0 \\ 0&0&1&0&\cdots&0&0 \\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots \\ 0&0&0&0&\cdots&1&0 \\ 0&1&0&0&\cdots&0&0 \\ 0&0&0&1&\cdots&0&0 \\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots \\ 0&0&0&0&\cdots&0&1 \end{bmatrix}$,继续整理:} \\ & \begin{array}{lll} &= \begin{bmatrix} \mathbf{I} & \mathbf{D} \\ \mathbf{I} & -\mathbf{D} \end{bmatrix} \begin{bmatrix} \mathbf{F}_m & \mathbf{O} \\ \mathbf{O} & \mathbf{F}_m \end{bmatrix} \mathbf{P} \mathbf{c} \end{array} \end{align*}

于是,得到结论(注意 $m=\dfrac{1}{2}n$):

$$ \mathbf{y} = \mathbf{F}_n \mathbf{c} = \begin{bmatrix} \mathbf{I} & \mathbf{D} \\ \mathbf{I} & -\mathbf{D} \end{bmatrix} \begin{bmatrix} \mathbf{F}_{n/2} & \mathbf{O} \\ \mathbf{O} & \mathbf{F}_{n/2} \end{bmatrix} \mathbf{P} \mathbf{c} $$

$$ \mathbf{F}_n = \begin{bmatrix} \mathbf{I} & \mathbf{D} \\ \mathbf{I} & -\mathbf{D} \end{bmatrix} \begin{bmatrix} \mathbf{F}_{n/2} & \mathbf{O} \\ \mathbf{O} & \mathbf{F}_{n/2} \end{bmatrix} \mathbf{P} $$

这个算式的时间复杂度是多少呢?我们将上面推导过程中的几步提取出来:

$$ \mathbf{y} = \mathbf{F}_n \mathbf{c} = \begin{bmatrix} \mathbf{F}_{n/2} & \mathbf{D} \mathbf{F}_{n/2} \\ \mathbf{F}_{n/2} & -\mathbf{D} \mathbf{F}_{n/2} \end{bmatrix} \begin{bmatrix} \mathbf{c}_{even} \\ \mathbf{c}_{odd} \end{bmatrix} = \begin{bmatrix} \mathbf{F}_{n/2} \mathbf{c}_{even} + \mathbf{D} \mathbf{F}_{n/2} \mathbf{c}_{odd} \\ \mathbf{F}_{n/2} \mathbf{c}_{even} - \mathbf{D} \mathbf{F}_{n/2} \mathbf{c}_{odd} \end{bmatrix} $$

由于 $\mathbf{D}$ 是对角阵,因此 $\mathbf{D}\mathbf{F}_{n/2}$ 需要 $\dfrac{n}{2}$ 次乘法。$\mathbf{F}_{n/2} \mathbf{c}_{even}$ 需要 $(\dfrac{n}{2})^2$ 次乘法,而 $(\mathbf{D}\mathbf{F}_{n/2})\mathbf{c}
_{odd}$ 需要 $(\dfrac{n}{2})^2$ 次乘法,因此上式需要的乘法次数为

$$ T(n) = 2 \left(\dfrac{n}{2} \right)^2 + \dfrac{n}{2}$$

我们仍然可以使用 公式 11 求得 $\mathbf{F}_{n/2}$,再利用 公式 12 进一步减半 $T(n)$ 的二次项系数:

$$ T(n) = 2 \left( 2 \left(\dfrac{n}{4}\right)^2 + \dfrac{n}{4} \right) + \dfrac{n}{2} $$

这是一个递归的过程,经过 $\log_2{n}$ 次变换后:

$$ T(n) = n + \dfrac{1}{2} n \log_2{n} $$

因为 $n$ 是 $\dfrac{1}{2} n \log_2{n}$ 当 $n \to +\infty$ 时的无穷小。因此 公式 10 以及 公式 11 的时间复杂度为 $\Omega (n\log_2{n})$。

到此,我们成功地将傅里叶变换的时间复杂度从 $\Omega (n^2)$ 降到了 $\Omega (n\log_2{n})$。公式 10 以及 公式 11 称为快速傅里叶变换Fast Fourier Transformation),简称 $FFT$。

上述是 变换 1 的情况,当然 变换 2 也可以通过这种方式进行,只需要将 $\mathbf{F}$ 改成 $\overline{\mathbf{F}}$:

$$ \mathbf{c} = \overline{\mathbf{F}}_n \mathbf{y} = \begin{bmatrix} \mathbf{I} & \mathbf{D} \\ \mathbf{I} & -\mathbf{D} \end{bmatrix} \begin{bmatrix} \overline{\mathbf{F}}_{n/2} & \mathbf{O} \\ \mathbf{O} & \overline{\mathbf{F}}_{n/2} \end{bmatrix} \mathbf{P} \mathbf{y} $$

$$ \overline{\mathbf{F}}_n = \begin{bmatrix} \mathbf{I} & \mathbf{D} \\ \mathbf{I} & -\mathbf{D} \end{bmatrix} \begin{bmatrix} \overline{\mathbf{F}}_{n/2} & \mathbf{O} \\ \mathbf{O} & \overline{\mathbf{F}}_{n/2} \end{bmatrix} \mathbf{P} $$

复矩阵与复向量就讲到这里,感谢阅读。

版权声明:本文为原创文章,转载请注明出处。http://cynhard.com/2018/09/11/LA-Complex-Vectors-and-Matrices/

推荐文章