L24-马尔可夫矩阵与傅立叶级数

参考

Unit II: Least Squares, Determinants and Eigenvalues - Markov Matrices; Fourier Series | pdf
课本章节：Read Section 8.3 and 8.5 in the 4^th or Sections 10.3 and 10.5 in the 5^th edition.
练习题：L24-马尔可夫矩阵与傅立叶级数-习题集

这一节课继续介绍特征值和特征向量的应用，马尔可夫矩阵是一种特殊的矩阵，它同样可用于描述随时间变化的系统，同样是通过它的特征值和特征向量来研究该系统的趋势。

另外介绍了傅立叶级数，与向量的投影（以正交向量展开）相关，类比向量的行为，可以将任意函数展开为周期性的三角函数。

马尔可夫矩阵

满足以下两条性质的矩阵称为马尔科夫矩阵 Markov Matrix

每个元素都是非负数（大于或等于 $0$ ）
每列元素之和为 $1$

提示

马尔可夫矩阵与概率相关，由于概率都是非负数，且必然事件的概率为 $1$ ，这是马尔科夫矩阵所满足的两条性质的缘由

例如以下矩阵 $A$ 为马尔可夫矩阵

\begin{bmatrix} 0.1 & 0.01 & 0.3 \\ 0.2 & 0.99 & 0.3 \\ 0.7 & 0 & 0.4 \end{bmatrix}

马尔可夫矩阵具有以下一些特性

马尔可夫矩阵 $A$ 的平方 $A^{2}$ （或更高次幂 $A^{k}$ ），其结果矩阵依然是马尔科夫矩阵
$\lambda = 1$ 是马尔科夫矩阵的其中一个特征值
证明
假设马尔可夫矩阵 $A$ 具有特征值 $\lambda = 1$ ，根据特征值的定义可知 $Ax=1 \cdot x$ 等式成立，即方程 $(A-1 \cdot I)x=0$ 必有解
只要当 $A-1 \cdot I$ 为奇异矩阵时，方程 $(A-1 \cdot I)x=0$ 必有解
所以要证明矩阵 $A$ 具有特征值 $\lambda = 1$ ，就只需要证明 $A-1 \cdot I$ 为奇异矩阵
由于马尔可夫矩阵 $A$ 每列元素之和为 $1$ ，则从行向量的角度来考虑，它们的一种线性组合满足为 $row_{1}+row_{2}+ \dots + row_{n}=\begin{bmatrix} 1 & 1 & \dots & 1 \end{bmatrix}$
那么对于矩阵 $A-I$ 各行向量的对应的线性组合为 $row_{1}+row_{2}+ \dots + row_{n}=\begin{bmatrix} 0 & 0 & \dots & 0 \end{bmatrix}$
所以矩阵 $A-I$ 的行向量是线性相关的，即该矩阵为奇异矩阵，由此可证马尔可夫矩阵 $A$ 具有特征值 $\lambda = 1$
除此之外，其他特征是都比 $1$ 小 $\left |\lambda_{i} \right | < 1$

稳态

马尔可夫矩阵的特征值满足一些特性，所以由马尔科夫链构成的等差方程 $u^{k+1}=Au_{k}$ 其稳态也有特定的规律

由前面的课程可知等差方程 $u^{k+1}=Au_{k}$ 的通解形式为

\begin{aligned} u_{k}&=A^{k}u_{0} \\ &=c_{1}\lambda_{1}^{k}x_{1}+c_{2}\lambda_{2}^{k}x_{2}+\dots+c_{n}\lambda_{n}^{k}x_{n} \end{aligned}

马尔可夫矩阵具有特征值 $\lambda=1$ 而其他特征值满足 $\left |\lambda_{i} \right | < 1$

所以当 $k \to \infty$ 时， $u^{k} \to c_{1}x_{1}$

提示

如果初始值 $u_{0}$ 是正值，那么特征值 $\lambda=1$ 所对应的特征向量 $x_{i}$ 各元素就会是非负数，所以 $u^{k}$ 的极限值/稳态也会是非负数

转置矩阵的特征值

转置矩阵 $A^{T}$ 与原矩阵 $A$ 具有相同的特征值

证明

已知矩阵 $A$ 的特征值 $\lambda$ 满足 $det(A-\lambda I)=0$ （特征方程）

而根据行列式的特性十（转置矩阵的行列式和原来矩阵的行列式一样）可知矩阵 $(A-\lambda I)$ 的行列式和矩阵 $(A-\lambda I)^{T}$ 的行列式相等

det((A-\lambda I)^{T})=det(A-\lambda I)=0

将以上等式的的左边进行简化可得

det((A-\lambda I)^{T})=det(A^{T}-\lambda I^{T})=det(A^{T}- \lambda I)

所以 $det(A^{T}- \lambda I)=0$ 该等式形式就是针对矩阵 $A^{T}$ 而言的特征方程

即矩阵 $A$ 的特征值 $\lambda$ 也可以使得针对矩阵 $A^{T}$ 而言的特征方程成立，所以 $\lambda$ 也是矩阵 $A^{T}$ 的特征值

应用

马萨诸塞州（麻省）的人口为 $u_{mass}$ ，加利福尼亚州（加州）的人口为 $u_{cal}$ ，以它们构成一个向量 $u=\begin{bmatrix} u_{cal} \\ u_{mass} \end{bmatrix}$

假设各州的原始人口为 $u_{0}=\begin{bmatrix} 0 \\ 1000 \end{bmatrix}$

每年都会有 $90%$ 的人口留在加州，则有 $10%$ 的人口迁去麻省；而每年会有 $80%$ 的人口留着麻省，则有 $20%$ 的人口迁去加州

那么到第 $100$ 年后，各州人口 $u_{100}$ 是多少？

根据各州的人口迁移概率，可以列出人口随时间变化的递推公式（差分方程）

u_{k+1}=Au_{k} \begin{bmatrix} 0.9 & 0.2 \\ 0.1 & 0.8 \end{bmatrix} u_{k}

其中系数矩阵 $A$ 为马尔科夫矩阵

所以它具有一个特征值为 $\lambda_{1}=1$

再根据特征值之和为矩阵的迹 $trace=\lambda_{1}+\lambda_{2}=0.9+0.8=1.7$ 可得 $\lambda_{2}=0.7$

将特征值分别代入到方程 $(A-\lambda I)x=0$ 求出相应的特征向量

当 $\lambda_{1}=1$ 时 $\begin{aligned} (A-\lambda I)x&= \begin{bmatrix} 0.9-1 & 0.2 \\ 0.1 & 0.8-1 \end{bmatrix}x \\ &= \begin{bmatrix} -0.1 & 0.2 \\ 0.1 & -0.2 \end{bmatrix}x \\ &=0 \end{aligned}$
可得其中一个特征向量为 $x_{1}=\begin{bmatrix} 2 \\ 1 \end{bmatrix}$
当 $\lambda_{2}=0.7$ 时 $\begin{aligned} (A-\lambda I)x&= \begin{bmatrix} 0.90.71 & 0.2 \\ 0.1 & 0.8-0.7 \end{bmatrix}x \\ &= \begin{bmatrix} 0.2 & 0.2 \\ 0.1 & 0.1 \end{bmatrix}x \\ &=0 \end{aligned}$
可得其中一个特征向量为 $x_{2}=\begin{bmatrix} -1 \\ 1 \end{bmatrix}$

根据前面的课程可知等差方程 $u^{k+1}=Au_{k}$ 的通解形式为

\begin{aligned} u_{k}&=A^{k}u_{0} \\ &=c_{1}\lambda_{1}^{k}x_{1}+c_{2}\lambda_{2}^{k}x_{2} \\ \end{aligned}

所以 $u_{0}$ 为

\begin{aligned} u_{0}&=c_{1}\lambda_{1}^{0}x_{1}+c_{2}\lambda_{2}^{0}x_{2} \\ &=c_{1}\begin{bmatrix} 2 \\ 1 \end{bmatrix}+c_{2}\begin{bmatrix} -1 \\ 1 \end{bmatrix} \\ &=\begin{bmatrix} 0 \\ 1000 \end{bmatrix} \end{aligned}

将以上矩阵形式写成方程组形式

\begin{aligned} \left\{\begin{matrix} 2c_{1}-c_{2}=0 \\ c_{1}+c_{2}=1000 \end{matrix}\right. \end{aligned}

解得 $c_{1}=\cfrac{1000}{3}$ 和 $c_{2}=\cfrac{2000}{3}$

那么 $u_{100}$ 为

\begin{aligned} u_{100}&=c_{1}\lambda_{1}^{100}x_{1}+c_{2}\lambda_{2}^{100}x_{2} \\ &=\cfrac{1000}{3} \cdot 1^{100} \cdot \begin{bmatrix} 2 \\ 1 \end{bmatrix}+\cfrac{2000}{3} \cdot 0.7^{100} \cdot \begin{bmatrix} -1 \\ 1 \end{bmatrix} \end{aligned}

由于后一项趋于 $0$ ，所以 $u_{100} \approx \cfrac{1000}{3}\begin{bmatrix} 2 \\ 1 \end{bmatrix}$

傅立叶级数

在之前关于投影的的一系列章节中介绍过正交基（标准正交向量 orthonormal basis），这些向量相互垂直 $q_{i}^{T}q_{j}=0$ ，模长都是 $q_{i}^{T}q_{i}=1$

在 $n \times n$ 向量空间中，任何一个向量 $v$ 都可以展开 expansion 为一系列标准正交向量

v=x_{1}q_{1}+x_{2}q_{2}+ \dots + x_{n}q_{n}

可以借助不同标准正交向量的内积为零 $q_{i}q_{j}^{T}=0$ （以及模长为 $q_{i}^{T}q_{i}=1$ ）的特点，求出线性组合中各个系数的值

例如需要求解第一项的系数 $x_{1}$ ，则可以在以上等式的两边同时乘上向量 $q_{1}^{T}$

\begin{aligned} q_{1}^{T}v&=x_{1}q_{1}q_{1}^{T}+x_{2}q_{2}q_{1}^{T}+ \dots + x_{n}q_{n}q_{1}^{T} \\ &=x_{1} \cdot 1 + 0 + \dots + 0 \\ &=x_{1} \end{aligned}

可得 $x_{1}=q_{1}^{T}v$ 通过类似的方法，可以求出其他项的系数 $x_{i}=q_{i}^{T}v$

提示

可以写成矩阵形式

v=Qx

其中矩阵 $Q$ 是正交矩阵，它由一系列的标准正交向量 $q_{i}$ 作为列向量构成 $Q=\begin{bmatrix} q_{1}& \dots q_{n} \end{bmatrix}$ ，而列向量 $x$ 是由线性组合的系数构成 $x=\begin{bmatrix} x_{1} \\ \vdots \\ x_{n} \end{bmatrix}$

由等式 $v=Qx$ 可解得列向量 $x$ 为 $x=Q^{-1}v$

由于正交矩阵的逆矩阵就是其转置矩阵 $Q^{-1}=Q^{T}$

所以 $x=Q^{-1}v=Q^{T}v$ 这个解的形式，和前面所得的向量中各元素 $x_{i}=q_{i}^{T}v$ 是一致的

类似地，可以用一系列三角函数 trigonometric functions（正交函数，它们直接相互「垂直」，基函数的内积为零）来展开一个函数 $f(x)$ 称为傅立叶级数

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

提示

任意向量 $v$ 可以展开为一系列的标准正交向量 $q_{i}$ 的线性组合（求和）

傅立叶级数与之类似，相当于用正交函数代替了正交向量，其中各项的基依次为 $1, \cos x, \sin x, \dots$

不同的是，向量使用正交基展开得到的是有限数量的项，而傅立叶级数展开得到的是无限数量的项

向量内积与函数内积

向量的内积 inner product 的定义为（两个向量的各元素依次相乘再求和） $v^{T}w=v_{1}w_{1}+v_{2}w_{2}+ \dots + v_{n}w_{n}$

由于向量是离散型的数据（由各个元素构成），而对于连续型的函数，其内积定义需要进行调整（从求和变成积分）

函数内积 inner product 的定义

f^{T}g=\int f(x)g(x)\mathrm{d}x

例如当 $f(x)=\sin x, g(x)=\cos x$ 它们两者的内积为（由于它们是周期函数，所以积分范围从 $0$ 到 $2\pi$ ）

f(x)^{T}g(x)=\int \sin x \cos x \mathrm{d}x=\cfrac{1}{2}(\sin x)^{2}\big|_{0}^{2\pi}=0

所以 $\sin x$ 和 $\cos x$ 的内积为 $0$ ，它们是正交函数（相当于「垂直」），可以作为傅立叶级数的展开式的基

可以类比求解向量的正交基展开式各项的系数的方法，求出傅立叶级数各项的系数

说明

第一项 $a_{0}$ 是常数项，它的值是各个展开式的平均值 ❓

所以求解系数应该从第二项 $a_{1}$ 开始

例如需要求解第一个傅立叶系数 $a_{1}$ ，则可以在展开式的两边同时乘上 $\cos$ （计算一系列的函数内积）

\int_{0}^{2\pi} f(x) \cos x \mathrm{d}x=\int_{0}^{2\pi}(a_{0}+a_{1} \cos x+b_{1} \sin x+a_{2} \cos 2x + b_{2} \sin 2x + \dots) \cos x\mathrm{d}x

由于除了第一个系数项以外， $\cos x$ 与展开式其他项的各个函数之间的内积为零（它们之间互为正交函数），所以最后右侧可以化简为只有 $\int_{0}^{2\pi} (\cos x)^{2} \mathrm{d}x$ 这一项

\begin{aligned} \int_{0}^{2\pi} f(x) \cos x \mathrm{d}x&=\int_{0}^{2\pi}(a_{0}+a_{1} \cos x+b_{1} \sin x+a_{2} \cos 2x + b_{2} \sin 2x + \dots) \cos x\mathrm{d}x\\ &=0+\int_{0}^{2\pi} (\cos x)^{2} \mathrm{d}x+0 \dots \\ &=a_{1}\pi \end{aligned}

可得 $a_{1}=\cfrac{1}{\pi}\int_{0}^{2\pi} f(x) \cos x \mathrm{d}x$