傅立叶分析专题：傅立叶级数和傅立叶变换

参考资料：
线代启示录：傅立叶分析专题

1. 函数空间

函数空间是一个希尔伯特（Hilbert）空间，即一个保有一般几何性质的无限维实向量空间。
函数也是向量，而仅包含有限长度的函数可以形成向量空间。
以$\langle f, g\rangle$表示函数$f$和$g$的内积：

$$\langle f, g\rangle=\int_{0}^{T} f(x) g(x) d x$$

函数长度可由内积求得：$|f|^{2}=\langle f, f\rangle$

函数空间最有名的例子为傅立叶级数（Fourier series），函数$f(x)$表示为正弦函数和余弦函数的展开式：

$$f(x)=a_{0}+a_{1} \cos x+b_{1} \sin x+a_{2} \cos 2 x+b_{2} \sin 2 x+\cdots$$

傅立叶级数的基底函数包含：

$$1, \cos x, \sin x, \cos 2 x, \sin 2 x, \cdots$$

2. 傅立叶级数

考虑一有限维内积空间$\mathcal{V}$，且$\operatorname{dim} \mathcal{V}=n$。任意$\mathbf{x}, \mathbf{y} \in \mathcal{V}$的内积记为$\langle\mathbf{x}, \mathbf{y}\rangle$。令$\boldsymbol{\beta}=\left{\mathbf{v}{1}, \ldots, \mathbf{v}{n}\right}$为$\mathcal{V}$的一组单位正交基底（orthonormal basis），也就是说$\left\langle\mathbf{v}{i}, \mathbf{v}{j}\right\rangle= 1$若$i=j$，$\left\langle\mathbf{v}{i}, \mathbf{v}{j}\right\rangle= 0$若$i \neq j$，则有

$$\begin{aligned} \left\langle\mathbf{v}_{i}, \mathbf{x}\right\rangle &=\left\langle\mathbf{v}_{i}, c_{1} \mathbf{v}_{1}+\cdots+c_{n} \mathbf{v}_{n}\right\rangle \\ &= c_{1}\left\langle\mathbf{v}_{i}, \mathbf{v}_{1}\right\rangle+\cdots+ c_{n}\left\langle\mathbf{v}_{i}, \mathbf{v}_{n}\right\rangle \\ &= c_{i}\left\langle\mathbf{v}_{i}, \mathbf{v}_{i}\right\rangle= c_{i} \end{aligned}$$

故$\mathbf{x}$有下列正交分解展开式：

$$\mathbf{x}=\left\langle\mathbf{v}_{1}, \mathbf{x}\right\rangle \mathbf{v}_{1}+\cdots+\left\langle\mathbf{v}_{n}, \mathbf{x}\right\rangle \mathbf{v}_{n}$$

其中 $\left\langle\mathbf{v}_i,\mathbf{x}\right\rangle\mathbf{v}_i $即为 $\mathbf{x}$ 至“超直线” $\mathrm{span}{\mathbf{v}_i}$ 的正交投影分量。

---

周期函数$f(x)$可展开成傅立叶级数的条件：

收敛定理，狄利克雷（Dirichlet）充分条件：
（1）此函数必须是有界的（bounded），即对于任意$x$，$|f(x)|<M$，$M$是一正实数
（2）在任意区间内，除了有限个不连续点，$f(x)$必须是连续函数
（3）在任意区间内，$f(x)$必须仅包含有限个极值
（4）在一周期内，$|f(x)|$的积分必须收敛

---

三角函数系的正交性：

所谓三角函数系

$$1, \cos x, \sin x, \cos 2 x, \sin 2 x, \cdots, \cos n x, \sin n x, \cdots$$

在区间$[-\pi, \pi]$上正交，就是指在三角函数系中任何不同的两个函数的乘积$[-\pi, \pi]$上的积分等于零，即

$$\begin{aligned} &\int_{-\pi}^{\pi} \cos n x \mathrm{d} x=0 \quad(n=1,2,3, \cdots)\\ &\int_{-\pi}^{\pi} \sin n x \mathrm{d} x=0 \quad(n=1,2,3, \cdots)\\ &\int_{-\pi}^{\pi} \sin k x \cos n x \mathrm{d} x=0 \quad(k, n=1,2,3, \cdots)\\ &\int_{-\pi}^{\pi} \cos k x \cos n x \mathrm{d} x=0 \quad(k, n=1,2,3, \cdots, k \neq n)\\ &\int_{-\pi}^{\pi} \sin k x \sin n x \mathrm{d} x=0 \quad(k, n=1,2,3, \cdots, k \neq n) \end{aligned}$$

以上等式，都可以通过计算定积分来验证。
在三角函数系中，两个相同函数的乘积在区间$[-\pi, \pi]$上的积分不等于零，即

$$\int_{-\pi}^{\pi} 1^{2} \mathrm{d} x=2 \pi, \int_{-\pi}^{\pi} \sin ^{2} n x \mathrm{d} x=\pi, \int_{-\pi}^{\pi} \cos ^{2} n x \mathrm{d} x=\pi \quad(n=1,2,3, \cdots)$$

---

令$\mathcal{V}$是由定义于区间$[-\pi, \pi]$（亦可选择$[0,2 \pi]$）的实函数所成的内积空间，函数空间$\mathcal{V}$是一无限维空间。对于$\mathcal{V}$中两实函数$f(x)$和$g(x)$，其内积定义如下（有些学者采用不含$1 / \pi$的内积定义，如此一来，$1 / \sqrt{\pi}$则需乘入余弦和正弦函数）：

$$\langle f, g\rangle \stackrel{\text { def }}{=} \frac{1}{\pi} \int_{-\pi}^{\pi} f(x) g(x) d x$$

则$f(x)$的长度或范数（norm） 为

$$\|f\|=\langle f, f\rangle^{1 / 2}=\left(\frac{1}{\pi} \int_{-\pi}^{\pi}(f(x))^{2} d x\right)^{1 / 2}$$

考虑无穷函数集合

$$\boldsymbol{\beta}=\left\{\frac{1}{\sqrt{2}}, \cos x, \sin x, \cos (2 x), \sin (2 x), \ldots\right\}$$

有

$$\begin{array}{l} {\frac{1}{\pi} \int_{-\pi}^{\pi}\left(\frac{1}{\sqrt{2}}\right)^{2} d x=1} \\ {\frac{1}{\pi} \int_{-\pi}^{\pi} \cos ^{2}(m x) d x=1, m=1,2, \ldots} \\ {\frac{1}{\pi} \int_{-\pi}^{\pi} \sin ^{2}(m x) d x=1, m=1,2, \ldots} \end{array}$$

故$\boldsymbol{\beta}$是一个单位正交集。

---

周期为$2 \pi$实函数$f(x)$的傅立叶级数

周期为$2 \pi$实函数$f(x)$的傅立叶级数$F(x)$为余弦和正弦函数组成的无穷级数：

$$F(x)=\frac{a_{0}}{2}+\sum_{k=1}^{\infty} a_{k} \cos (k x)+\sum_{k=1}^{\infty} b_{k} \sin (k x)$$

其中傅立叶系数$a{k}$和$b{k}$的计算公式如下：

$$\begin{aligned} &a_{k}=\frac{1}{\pi} \int_{-\pi}^{\pi} f(x) \cos (k x) d x, \quad k=0,1,2, \ldots\\ &b_{k}=\frac{1}{\pi} \int_{-\pi}^{\pi} f(x) \sin (k x) d x, \quad k=1,2, \ldots \end{aligned}$$

若$f(x)$为奇函数，则$f(x) \cos (k x)$为奇函数，奇函数在关于原点对称区间上的积分为零，故$a{k}=0, \quad k=0,1, 2\dots$。另一方面若$f(x)$为偶函数，则$f(x) \sin (k x)$为奇函数，有$b{k}=0, \quad k=1,2, \dots$。

周期为$T$实函数$f(x)$的傅立叶级数

周期为$T$，定义于区间$[-T / 2, T / 2]$的周期函数$f(t)$。利用变数变换$t / T=x /(2 \pi)$，可使区间$[-\pi, \pi]$变换至$[-T / 2, T / 2]$，将$x=2 \pi t / T$代入$F(x)$，即得到$f(t)$的傅立叶级数：

$$F(t)=\frac{a_{0}}{2}+\sum_{k=1}^{\infty} a_{k} \cos \left(\frac{2 \pi k t}{T}\right)+\sum_{k=1}^{\infty} b_{k} \sin \left(\frac{2 \pi k t}{T}\right)$$

将$d x=2 \pi d t / T$代入$f(x)$的傅立叶系数的积分公式，可得

$$\begin{aligned} &a_{k}=\frac{2}{T} \int_{-T / 2}^{T / 2} f(t) \cos \left(\frac{2 \pi k t}{T}\right) d t, k=0,1,2, \ldots\\ &b_{k}=\frac{2}{T} \int_{-T / 2}^{T / 2} f(t) \sin \left(\frac{2 \pi k t}{T}\right) d t, k=1,2, \ldots \end{aligned}$$

对于周期为$T$的函数$f(t)$，任何区间$\left[t{0}, t{0}+T\right]$皆可使用，如何选择$t{0}$值取决于便利性和个人偏好，常见的设定有$t{0}=0$或$t_{0}=-T / 2$

指数傅立叶级数

利用欧拉公式$e^{i x}=\cos x+i \sin x$，我们可以写出更为精简的傅立叶级数表达式。

$$\cos x=\frac{e^{i x}+e^{-i x}}{2}, \sin x=\frac{e^{i x}-e^{-i x}}{2 i}$$

再将傅立叶级数$F(x)$中$\cos (k x)$和$\sin (k x)$的线形组合式改写如下：

$$\begin{aligned} a_{k} \cos (k x)+b_{k} \sin (k x) &=a_{k}\left(\frac{e^{i k x}+e^{-i k x}}{2}\right)+b_{k}\left(\frac{e^{i k x}-e^{-i k x}}{2 i}\right) \\ &=\left(\frac{a_{k}-i b_{k}}{2}\right) e^{i k x}+\left(\frac{a_{k}+i b_{k}}{2}\right) e^{-i k x} \\ &=c_{k} e^{i k x}+c_{-k} e^{-i k x}, \quad k=1,2, \ldots \end{aligned}$$

其中$e^{i k x}$和$e^{-i k x}$的系数分别为

$$c_{k}=\frac{a_{k}-i b_{k}}{2}, \quad c_{-k}=\frac{a_{k}+i b_{k}}{2}$$

若$k=0$，就有$c{0}=a{0} / 2$。将以上结果代回$2 \pi$周期函数$f(x)$的傅立叶级数即得指数傅立叶级数：

$$F(x)=\sum_{k=-\infty}^{\infty} c_{k} e^{i k x}$$

复傅立叶系数$c_{k}$有计算公式：

$$c_{k}=\frac{1}{2 \pi} \int_{-\pi}^{\pi} f(x)(\cos (k x)-i \sin (k x)) d x=\frac{1}{2 \pi} \int_{-\pi}^{\pi} f(x) e^{-i k x} d x$$

类似地，$T$周期函数$f(t)$的指数傅立叶级数如下：

$$F(t)=\sum_{k=-\infty}^{\infty} c_{k} e^{2 \pi i k t / T}$$

复傅立叶系数则为

$$c_{k}=\frac{1}{T} \int_{-T / 2}^{T / 2} f(t) e^{-2 \pi i k t / T} d t$$

如果从一开始考虑指数函数集$\boldsymbol{\beta}^{\prime}=\left{e^{i k x}, k \in \mathbb{Z}\right}$，把$f(x)$正交投影至集合$\beta^{\prime}$扩张出的子空间上，可以导出$2 \pi$周期实函数的指数傅立叶级数，但$e^{i k x}$是复指数，因此实函数的内积定义必须修改为复函数内积。对于区间$[-\pi, \pi]$的两个复函数$f(x)$和$g(x)$，我们定义内积如下：

$$\langle f, g\rangle \stackrel{\text { def }}{=} \frac{1}{2 \pi} \int_{-\pi}^{\pi} \overline{f(x)} g(x) d x$$

复函数$f(x)$的长度或范数（norm）为

$$\begin{aligned} \|f\| &=\langle f, f\rangle^{1 / 2} \\ &=\left(\frac{1}{2 \pi} \int_{-\pi}^{\pi} \overline{f(x)} f(x) d x\right)^{1 / 2} \\ &=\left(\frac{1}{2 \pi} \int_{-\pi}^{\pi}|f(x)|^{2} d x\right)^{1 / 2} \end{aligned}$$

复函数内积引入常数$1 / 2$的目的在于使$\beta^{\prime}$成为一个单位正交（orthonormal）函数集。

$$\begin{aligned} \int_{-\pi}^{\pi} e^{-i m x} e^{i n x} d x &=\int_{-\pi}^{\pi}(\cos (m x)-i \sin (m x))(\cos (n x)+i \sin (n x)) d x \\ &=\int_{-\pi}^{\pi} \cos (m x) \cos (n x) d x+\int_{-\pi}^{\pi} \sin (m x) \sin (n x) d x \\ &+i \int_{-\pi}^{\pi} \cos (m x) \sin (n x) d x-i \int_{-\pi}^{\pi} \sin (m x) \cos (n x) d x \\ &=2 \pi \delta_{m n} \end{aligned}$$

其中$\delta{m n}=1$，若$m = n$，$\delta{m n}=0$若$m \neq n$。因此证明$\boldsymbol{\beta}^{\prime}=\left{e^{i k x}, k \in \mathbb{Z}\right}$是一个单位正交集。函数$f(x)$的指数傅立叶级数即为$f(x)$至$\beta^{\prime}$扩张成的子空间的正交投影：

$$F(x)=\sum_{k=-\infty}^{\infty}\left\langle e^{i k x}, f(x)\right\rangle e^{i k x}$$

上式中，正交分解所含的系数就是傅立叶系数：

$$c_{k}=\left\langle e^{i k x}, f(x)\right\rangle=\frac{1}{2 \pi} \int_{-\pi}^{\pi} f(x) e^{-i k x} d x$$

2. 离散傅立叶变换

考虑定义于区间$[-T / 2, T / 2]$的周期为$T$的函数$f(t)$的指数傅立叶级数

$$F(t)=\sum_{k=-\infty}^{\infty} c_{k} e^{2 \pi i k t / T}$$

其中复傅立叶系数为

$$c_{k}=\frac{1}{T} \int_{-T / 2}^{T / 2} f(t) e^{-2 \pi i k t / T} d t, \quad k \in \mathbb{Z}$$

若$f(t)$满足Dirichlet条件，可以证明$|f-F|^{2}=0$，从现在开始将解除$f(t)$是周期函数的限制，假设$\int_{-\infty}^{\infty}|f(t)| d t$是有界的。当$T \rightarrow \infty$，傅立叶级数可推广为傅立叶转换（Fourier transform）。进一步地，若$f(t)$不再是连续函数而是一有限数列，傅立叶级数又可延伸为离散傅立叶转换（discrete Fourier transform，简称DFT）。

傅立叶转换是傅立叶级数于$T \rightarrow \infty$的表达形式。令$\nu{k}=k / T$，且$\Delta \nu=\nu{k+1}-\nu{k}=1 / T$，则$f{T}(t)$的傅立叶级数为

$$f_{T}(t)=\sum_{k=-\infty}^{\infty} c_{k}(T) e^{2 \pi i \nu_{k} t}$$

其中我们令

$$c_{k}(T)=\frac{1}{T} \int_{-T / 2}^{T / 2} f_{T}(t) e^{-2 \pi i \nu_{k} t} dt$$

将$c{k}(T)$代回傅立叶级数$f{T}(t)$，可得

$$\begin{aligned} f_{T}(t) &=\sum_{k=-\infty}^{\infty}\left[\frac{1}{T} \int_{-T / 2}^{T / 2} f_{T}(t) e^{-2 \pi i \nu_{k} t} d t\right] e^{2 \pi i \nu_{k} t} \\ &=\sum_{k=-\infty}^{\infty}\left[\int_{-T / 2}^{T / 2} f_{T}(t) e^{-2 \pi i \nu_{k} t} d t\right] e^{2 \pi i \nu_{k} t} \Delta \nu \end{aligned}$$

注意，上式中括弧内的$t$是虚拟变量（dummy variable）。当$T$逐渐增大时，$\Delta \nu=1 / T$变成一微小量$d \nu$，使得$\nu{k}$逼近连续变量$\mathcal{V}$，总和因此趋于积分。令$T \rightarrow \infty$，则$f{T}(t) \rightarrow f(t)$，可得下列等式：

$$f(t)=\int_{-\infty}^{\infty}\left[\int_{-\infty}^{\infty} f(t) e^{-2 \pi i \nu t} d t\right] e^{2 \pi i \nu t} d \nu$$

欲看清整个关系，将上式拆开为两部分。令括弧内的函数为

$$\hat{f}(\nu)=\int_{-\infty}^{\infty} f(t) e^{-2 \pi i \nu t} d t$$

称为$f(t)$的傅立叶转换，其中变量$\nu$代表频率。因此得到

$$f(t)=\int_{-\infty}^{\infty} \hat{f}(\nu) e^{2 \pi i \nu t} d \nu$$

称为$\hat{f}(\nu)$的逆傅立叶转换。

---

傅立叶矩阵

在数值计算上，因为电脑仅能处理有限维向量，连续型态的傅立叶转换必须换装成离散傅立叶转换。离散傅立叶转换的输入不再是无限维函数$f(t)$，我们仅能运用一周期$[0, T]$内$n$个等间距函数值$x{j} \equiv f\left(t{j}\right)$，其中$t{j}=j T / n, \quad j=0,1, \ldots, n-1$。其次离散傅立叶转换的输出是复傅立叶系数构成的相同长度数列$c{k}, k=0,1, \ldots, n-1$，而非无穷数列。因为傅立叶系数$c{k}$与函数$f(t)$的关系是线性的（积分是线性函数），我们也预期离散傅立叶转换是数列$\left{x{j}\right}$和$\left{c_{k}\right}$之间的一可逆线性转换，故可表示为$n \times n$阶可逆矩阵。在连续情况下，将区间正规化，令$T=1$，复傅立叶级数即为：

$$c_{k}=\int_{0}^{1} f(t) e^{-2 \pi i k t} d t$$

在离散情况下，以$t_{j}=j / n$取代$t$，将连续函数的傅立叶系数改为计算和，可得对应的离散公式：对于$k=0,1, \ldots, n-1$

$$y_{k}=\sum_{j=0}^{n-1} x_{j} e^{-2 \pi i k j / n}$$

此即离散傅立叶转换。为了与傅立叶系数$c{k}$区分，我们以$y{k}$代表离散傅立叶转换结果。使用欧拉公式$e^{i \theta}=\cos \theta+i \sin \theta$，令

$$w=e^{-2 \pi i / n}=\cos \left(\frac{2 \pi}{n}\right)-i \sin \left(\frac{2 \pi}{n}\right)$$

离散傅立叶转换可表示成矩阵形式$\mathbf{y}=F \mathbf{x}$，如下：

$$\left[\begin{array}{c} {y_{0}} \\ {y_{1}} \\ {y_{2}} \\ {\vdots} \\ {y_{n-1}} \end{array}\right]=\left[\begin{array}{ccccc} {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{array}\right]\left[\begin{array}{c} {x_{0}} \\ {x_{1}} \\ {x_{2}} \\ {\vdots} \\ {x_{n-1}} \end{array}\right]$$

上面的$n \times n$阶矩阵$F$称为傅立叶矩阵。$F$是一种特殊的Vandermonde矩阵。

复数集$\left{1, w, w^{2}, \ldots, w^{n-1}\right}$为方程式$z^{n}=1$的根，称为$n$次方单位根，这些根在复数平面上单位圆按顺时针旋转并以相同间距排列。若$k \geq n$，则$w^{k}=w^{k \bmod n}$。对于任意整数$k$，由欧拉公式可确认

$$\overline{w^{k}}=\overline{e^{-2 \pi i k / n}}=\cos \left(\frac{2 \pi k}{n}\right)+i \sin \left(\frac{2 \pi k}{n}\right)=e^{2 \pi i k / n}=w^{-k}$$

考虑下式

$$w^{k}\left(1+w^{k}+w^{2 k}+\cdots+w^{(n-2) k}+w^{(n-1) k}\right)=w^{k}+w^{2 k}+\cdots+w^{(n-1) k}+1$$ $$\left(w^{k}-1\right)\left(1+w^{k}+w^{2 k}+\cdots+w^{(n-2) k}+w^{(n-1) k}\right)=0$$

若$k \text { mod } n \neq 0$，则$w^{k} \neq 1$，可推得

$$\sum_{j=0}^{n-1} w^{j k}=1+w^{k}+w^{2 k}+\cdots+w^{(n-2) k}+w^{(n-1) k}=0$$

可以看出，傅立叶矩阵除了第一行，其余行的所有元素之和为0
下面我们运用此等式计算逆傅立叶矩阵$F^{-1}$
令$\mathbf{f}{p}$和$\mathbf{f}{q}$代表$F$的第$p$行和第$q$行，若$p \neq q$，则$(q-p) \text { mod } n \neq 0$，两向量的内积为

$$\left\langle\mathbf{f}_{p}, \mathbf{f}_{q}\right\rangle \stackrel{\text { def }}{=} \mathbf{f}_{p}^{*} \mathbf{f}_{q}=\sum_{j=0}^{n-1} \overline{w^{p j}} w^{j q}=\sum_{j=0}^{n-1} w^{j(q-p)}=0$$

并且

$$\left\|\mathbf{f}_{p}\right\|^{2}=\mathbf{f}_{p}^{*} \mathbf{f}_{p}=\sum_{j=0}^{n-1} \overline{w^{p j}} w^{j p}=\sum_{j=0}^{n-1} 1=n$$

有$\left|\mathbf{f}_{p}\right|=\sqrt{n}$。若将$F$的各行向量单位化，$\frac{1}{\sqrt{n}} F$为一酉矩阵（unitary）。因为$F^{T}=F$，就有

$$\left(\frac{1}{\sqrt{n}} F\right)^{-1}=\left(\frac{1}{\sqrt{n}} F\right)^{H}=\frac{1}{\sqrt{n}} \bar{F}$$

故$F^{-1}=\bar{F} / n$，即$\left(F^{-1}\right)_{p q}=w^{-p q} / n$，或明确写出

$$F^{-1}=\frac{1}{n}\left[\begin{array}{ccccc} {1} & {1} & {1} & {\cdots} & {1} \\ {1} & {w^{-1}} & {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{array}\right]$$

所以，逆离散傅立叶转换$\mathbf{x}=F^{-1} \mathbf{y}$：对于$j=0,1, \ldots, n-1$

$$x_{j}=\frac{1}{n} \sum_{k=0}^{n-1} y_{k} e^{2 \pi i k j / n}$$

离散傅立叶转换$F_{\mathbf{X}}$和逆转换$F^{-1} \mathbf{y}$有相同的运算方式，因为

$$F^{-1} \mathbf{y}=\frac{\bar{F} \mathbf{y}}{n}=\frac{\overline{F \overline{\mathbf{y}}}}{n}$$

假设我们设计出一个离散傅立叶转换程序DFT(·)，则逆转换$\mathbf{x}=F^{-1} \mathbf{y}$的算法如下：
（1）计算共轭向量$\overline{\mathbf{y}}$
（2）计算离散傅立叶转换$\mathbf{z}=\operatorname{DFT}(\bar{\mathbf{y}})$
（3）计算共轭向量的纯量乘法$\mathbf{x}=(1 / n) \overline{\mathbf{z}}$