Lecture 24: Markov Matrices; Fourier Series

目录 · ← l22 · l24 →

Lecture 24: Markov Matrices; Fourier Series

概述

本讲把特征值理论推向两个截然不同的方向，但它们的内核其实是同一件事——用一组”好”的特征向量（正交基）把对象展开。前半讲处理马尔可夫矩阵：所有元素非负、每一列加起来等于 1 的方阵。这类矩阵必然有特征值 $\lambda = 1$，而且只要它”足够连通”，幂次 $A^k$ 就会收敛到一个稳定的概率分布——稳态向量（steady state）。后半讲把向量换成函数，把内积换成积分，于是投影公式 $P = a(a^{\mathsf T}b)/(a^{\mathsf T}a)$ 摇身一变成为傅里叶级数：$f(x) = \sum$ 投影系数 $\times$ 三角函数。整讲的主线是 Strang 反复强调的一句话：

线性代数的每一件事，在函数空间里都有一个连续版本；傅里叶级数就是把”投影到子空间”搬到无穷维。

本讲紧接讲次 22（$A^k = S\Lambda^k S^{-1}$ 与稳定性）、讲次 23（微分方程 $du/dt = Au$），并为讲次 25（对称正定矩阵）铺路。

核心概念的几何直觉

马尔可夫矩阵（Markov matrix）

• 定义与目的：方阵 $A$ 若满足 ① $a_{ij} \ge 0$（所有元素非负）； ② 对每一列 $j$：$\sum_i a_{ij} = 1$（列和为 1，称为列随机 column-stochastic）， 则称 $A$ 是马尔可夫矩阵。它的目的是描述随机过程：$A$ 把一个概率分布搬运成下一步的概率分布。
• 几何直觉（它在空间中是什么样子？）：把 $\mathbb{R}^n$ 中”所有分量非负、和为 1”的点集想象成一个单纯形（$n=2$ 是一条线段，$n=3$ 是一个三角形，$n$ 更大是更高维的”三角形”）。马尔可夫矩阵就是这个单纯形到自身的一个线性映照：单纯形里的点永远被搬回单纯形里，绝不逃出去。$A$ 的列和条件在几何上等价于说：全 1 向量 $\mathbf{1}$ 是 $A^{\mathsf T}$ 的特征向量（固有不动点方向）。为什么会收敛？因为单纯形是有界的”凸盒子”，映照反复作用只能越来越靠近它内部的那个不动点。
• 具体示例：$A = \begin{bmatrix} 0.8 & 0.3 \\ 0.2 & 0.7 \end{bmatrix}$。第一列 $0.8+0.2=1$，第二列 $0.3+0.7=1$，元素全非负 ⟹ 是马尔可夫矩阵。又例如 $S = \begin{bmatrix} 0.5 & 0.25 & 0.25 \\ 0.25 & 0.5 & 0.25 \\ 0.25 & 0.25 & 0.5 \end{bmatrix}$（三列均为 $1$）也是。

概率直觉：$a_{ij}$ 是转移概率

• 定义与目的：设系统的状态集合为 $\{1,\dots,n\}$。读法约定是 \(a_{ij} = P(\text{下一步在状态 } i \mid \text{当前在状态 } j),\) 即从列 $j$ 转移到行 $i$ 的概率。注意脚标的顺序（列是”从”，行是”到”）。设 $\mathbf{u}_k$ 是第 $k$ 步的概率分布向量，其第 $j$ 个分量 $(\mathbf{u}_k)_j = P(\text{第 } k \text{ 步在状态 } j)$，则 \(\mathbf{u}_{k+1} = A\,\mathbf{u}_k,\qquad (\mathbf{u}_{k+1})_i = \sum_j a_{ij}(\mathbf{u}_k)_j.\)
• 几何直觉：这是加权平均操作——”新的 $i$ 分量 = 所有可能来源 $j$ 的概率乘以转移概率再求和”。因为每列的和为 1，概率总量守恒：$\sum_i (\mathbf{u}{k+1})_i = \sum_i\sum_j a{ij}u_j = \sum_j u_j\big(\sum_i a_{ij}\big) = \sum_j u_j = 1$。
• 具体示例：$\mathbf{u}_0 = \begin{bmatrix}0\\1\end{bmatrix}$ 表示”初始 100% 在状态 2”。则 $\mathbf{u}_1 = \begin{bmatrix}0.8&0.3\\0.2&0.7\end{bmatrix}\begin{bmatrix}0\\1\end{bmatrix} = \begin{bmatrix}0.3\\0.7\end{bmatrix}$：从状态 2 出发，有 $0.3$ 的概率跳到状态 1，$0.7$ 的概率留在状态 2。这与”列和为 1”完全自洽。

稳态向量（steady state）

• 定义与目的：非零向量 $\mathbf{x}$ 满足 $A\mathbf{x} = \mathbf{x}$，即 $A\mathbf{x} = 1\cdot\mathbf{x}$ ——它就是 $\lambda = 1$ 的特征向量。若再把分量归一化使 $\sum_i x_i = 1$，就得到稳态概率分布。
• 几何直觉：在单纯形上，$\mathbf{x}$ 是那个”被 $A$ 搬了之后原地不动”的点。迭代 $\mathbf{u}_{k+1} = A\mathbf{u}_k$ 的任何轨迹，最终都会被吸到这个不动点上（当其余 $\vert \lambda\vert <1$ 时）。
• 具体示例：对上面的 $A$，稳态是 $\begin{bmatrix}0.6\\0.4\end{bmatrix}$（下一节逐步推导）。

为什么列和为 1 ⟹ $\lambda = 1$ 必是特征值

这是本讲最漂亮的”一句话证明”，必须逐字理解：

\(\text{每列和为 }1 \iff A^{\mathsf T}\text{ 的每行和为 }1 \iff A^{\mathsf T}\mathbf{1} = \mathbf{1} \iff \mathbf{1}\text{ 是 } A^{\mathsf T}\text{ 的特征向量（特征值 }1\text{）}\) \(\iff \det(A^{\mathsf T} - I) = 0 \iff \det(A - I) = 0 \quad(\text{因为 }\det M = \det M^{\mathsf T}) \iff 1 \text{ 是 } A \text{ 的特征值}.\)

请特别注意最后一跳：列和条件直接给出的是 $A^{\mathsf T}$ 的特征向量 $\mathbf{1}$，而 $A^{\mathsf T}$ 与 $A$ 有相同的特征值，所以 $1$ 也是 $A$ 的特征值。但 $A$ 自己的 $\lambda=1$ 特征向量不是 $\mathbf{1}$（除非 $A$ 的行和也为 1，例如 $A$ 还是对称的）。这正是学生最容易搞错的地方（见”常见误区”）。

$\vert \lambda\vert \le 1$：为什么特征值不会爆出去

• Gershgorin 圆盘定理：$A$ 的每个特征值都落在某个圆盘 \(\Big\{z : \vert z - a_{jj}\vert \le \sum_{i \ne j} \vert a_{ij}\vert \Big\}, \qquad j=1,\dots,n\) 之内（第 $j$ 个圆盘：圆心 $a_{jj}$，半径 = 第 $j$ 行其余元素绝对值之和）。关键的一步是把它用在 $A^{\mathsf T}$ 上：$A$ 与 $A^{\mathsf T}$ 有相同的特征值，而 $A^{\mathsf T}$ 的第 $j$ 行就是 $A$ 的第 $j$ 列。于是 $A^{\mathsf T}$ 的第 $j$ 个圆盘半径是 \(R_j = \sum_{i\ne j}(A^{\mathsf T})_{ji} = \sum_{i\ne j}a_{ij} = \Big(\sum_i a_{ij}\Big) - a_{jj} = 1 - a_{jj},\) 这里恰好用上了”第 $j$ 列的和为 1”。圆盘化为 $[a_{jj} - (1-a_{jj}),\ a_{jj} + (1-a_{jj})] = [2a_{jj}-1,\ 1]$，整个落在 $[-1,1]$ 内。$A^{\mathsf T}$ 的全部特征值（也就是 $A$ 的全部特征值）被这些圆盘覆盖，故 $\vert \lambda\vert \le1$。 重要提醒：直接对 $A$ 自己用行圆盘是行不通的——对演示一的 $A$，行圆盘是 $[0.8-0.3,\,0.8+0.3]=[0.5,1.1]$ 与 $[0.7-0.2,\,0.7+0.2]=[0.5,0.9]$，第一个右端 $1.1>1$，并没有给出 $\vert \lambda\vert \le1$。必须转到 $A^{\mathsf T}$（即用列圆盘）：得到 $[2(0.8)-1,\,1]=[0.6,1]$ 与 $[2(0.7)-1,\,1]=[0.4,1]$，此时特征值 $1$ 和 $0.5$ 才确实都被覆盖 ✓（脚本核对）。对演示三的 $M$：列圆盘为 $[0.8,1]$、$[0.6,1]$、$[0.6,1]$，特征值 $1,0.8,0.7$ 全部被覆盖 ✓——而 $M$ 自己的行圆盘是 $[0.7,1.1],[0.65,0.95],[0.65,0.95]$，同样会越界。
• 一个更朴素的说法：$A$ 不放大向量的 1-范数。对任意 $\mathbf{x}$，$\vert A\mathbf{x}\vert 1 = \sum_i\big\vert \sum_j a{ij}x_j\big\vert \le \sum_i\sum_j a_{ij}\vert x_j\vert = \sum_j \vert x_j\vert \sum_i a_{ij} = \sum_j\vert x_j\vert = \vert \mathbf{x}\vert _1$。任何特征向量满足 $\vert \lambda\mathbf{x}\vert _1 \le \vert \mathbf{x}\vert _1$，故 $\vert \lambda\vert \le 1$。幂次不会放大，这正是收敛的根源。

收敛定理（不可约 + 非周期 ⟹ 唯一稳态）

若马尔可夫矩阵”足够连通”（技术上：不可约 irreducible，即每个状态都能到达其他任何状态；且非周期 aperiodic），则

• $\lambda = 1$ 是单重特征值（代数重数 = 1）；
• 其余所有特征值满足 $\vert \lambda\vert < 1$；
• 于是对任意初始分布 $\mathbf{u}_0$， \(\mathbf{u}_k = A^k\mathbf{u}_0 \longrightarrow \mathbf{u}_\infty = \text{（唯一归一化的 } \lambda=1 \text{ 特征向量）}.\)

用讲次 22 的语言说：把 $\mathbf{u}_0$ 展开成 $\mathbf{u}_0 = c_1\mathbf{x}_1 + c_2\mathbf{x}_2 + c_3\mathbf{x}_3 + \cdots$，则

只有 $\lambda=1$ 的那一项存活下来，其余项因为 $\vert \lambda_j\vert ^k \to 0$ 而死亡。这就是”长期行为 = 稳态”的全部机制。

从向量到函数：函数是无穷维向量

• 定义与目的：向量 $\mathbf{v} = (v_1,\dots,v_n)$ 有 $n$ 个分量；函数 $f(x)$ 在 $[-\pi,\pi]$ 上”每个点 $x$ 有一个值”。把 $x$ 看成连续的指标，$f$ 就是一个有不可数多个分量的向量。所有”平方可积”函数构成的集合是一个无穷维向量空间。
• 几何直觉（它在空间中是什么样子？）：$n$ 维向量空间里，向量加法、数乘逐分量定义；函数空间里，$(f+g)(x) = f(x)+g(x)$，$(cf)(x) = cf(x)$，同样成立。“函数的线性组合”和”向量的线性组合”是同一种运算，只是指标集从 $\{1,\dots,n\}$ 变成了 $[-\pi,\pi]$。
• 具体示例：$f(x) = x$ 和 $g(x) = \sin x$ 的线性组合 $3f - 2g$ 就是函数 $3x - 2\sin x$ ——这跟 $\mathbb{R}^2$ 里的 $3\mathbf{u}-2\mathbf{v}$ 没有任何本质差别。

内积 = 积分（这是关键的翻译字典）

• 定义与目的：$n$ 维里 $\mathbf{v}^{\mathsf T}\mathbf{w} = \sum_{i=1}^n v_iw_i$；函数空间里把求和换成积分： \(\langle f, g\rangle = \int_{-\pi}^{\pi} f(x)g(x)\,dx.\)
• 几何直觉：内积仍然测量”一个在另一个方向上有多少分量”（投影长度）。正交仍然意味着内积为零：$\langle f,g\rangle = 0 \iff f\perp g$，”两个函数正交”就是”乘积的积分为零”——正负部分相互抵消。
• 具体示例：$\langle \sin x, \cos x\rangle = \int_{-\pi}^{\pi}\sin x\cos x\,dx = 0$（奇函数在对称区间上积分为 0），所以 $\sin x \perp \cos x$。

三角函数系是一组正交基（核心）

• 定义与目的：函数系 $\{1,\ \cos x,\ \sin x,\ \cos 2x,\ \sin 2x,\ \cos 3x,\ \sin 3x,\dots\}$ 在 $[-\pi,\pi]$ 上两两正交，并且张开整个函数空间——因此它就是一组（无穷维的）正交基。
• 正交性公式（$m, n \ge 1$）： \(\int_{-\pi}^{\pi}\sin(mx)\sin(nx)\,dx = \begin{cases}0, & m\ne n\\ \pi, & m=n\end{cases} \qquad \int_{-\pi}^{\pi}\cos(mx)\cos(nx)\,dx = \begin{cases}0, & m\ne n\\ \pi, & m=n\end{cases}\) \(\int_{-\pi}^{\pi}\sin(mx)\cos(nx)\,dx = 0 \quad(\text{对所有 } m,n),\qquad \int_{-\pi}^{\pi} 1\,dx = 2\pi.\)
• 几何直觉：这与 $\mathbb{R}^2$ 中”$\mathbf{e}_1\perp\mathbf{e}_2$、$\vert \mathbf{e}_i\vert ^2 = 1$”完全同构。区别只在于：这里的基向量长度不是 1，而是 $\sqrt{\pi}$（正弦/余弦）或 $\sqrt{2\pi}$（常数函数 1）——“未归一化的正交基”，就像讲次 14 里 $\begin{bmatrix}1\\1\end{bmatrix},\begin{bmatrix}1\\-1\end{bmatrix}$ 那样正交但长度是 $\sqrt 2$。
• 具体示例（数值验证）：$\int_{-\pi}^{\pi}\sin x\sin 2x\,dx = 0$、$\int_{-\pi}^{\pi}\cos 2x\cos 2x\,dx = \pi$、$\int_{-\pi}^{\pi}\sin x\cos x\,dx = 0$。用中点法数值积分立即得到 $0,\ 3.14159265,\ 0$ ✓。

傅里叶级数（Fourier series）

• 定义与目的：把周期为 $2\pi$ 的函数 $f$ 写成 \(f(x) = \frac{a_0}{2} + \sum_{k=1}^{\infty}\big(a_k\cos kx + b_k\sin kx\big),\) 其中系数由投影（积分）公式给出。目的是用一个”服从三角函数的简单函数”去逼近任意函数。
• 几何直觉：这就是把无穷维向量 $f$ 在正交基上展开坐标——完全等同于把 $\mathbf{b}$ 写成 $\sum \frac{\mathbf{b}^{\mathsf T}\mathbf{q}_i}{\mathbf{q}_i^{\mathsf T}\mathbf{q}_i}\mathbf{q}_i$。
• 具体示例：$f(x)=x$ 展开为 $x = 2\big[\sin x - \frac{\sin 2x}{2} + \frac{\sin 3x}{3} - \cdots\big]$。

正交性的几何图景（ASCII 示意）

   函数空间中的"正交基"  ——  把每个基函数想成一条"方向轴"

   sin x    ──────╭───────╮──────────       ∫ sin x · sin 2x dx = 0
                 ╰       ╯                  （一个周期内正负抵消，两次）
   sin 2x   ────╮───╮───╮───╮─────          ∫ sin x · sin 3x dx = 0
                ╰   ╯   ╰   ╯               
   sin 3x   ──╮─╮─╮─╮─╮─╮─╮─╮───            ∫ sin(mx)cos(nx) dx = 0
              ╰ ╯ ╰ ╯ ╰ ╯ ╰ ╯               （奇 × 偶 = 奇，恒为 0）
   cos x    ─────╮───────╮──────            
                 ╰       ╯                 ∫ sin²(nx) dx = π  ≠ 0
                                                ↑ 自己和自己不抵消，长度 √π
   投影类比：
     R^n  :   b ──投影──→ 方向 q_i ，长度 (q_i^T b)/||q_i||
     L²   :   f ──投影──→ 方向 cos kx，长度 <f,cos kx>/<cos kx,cos kx>
                          = (1/π)∫ f(x)cos(kx)dx

正交 = 内积为零 ⟺ 乘积的积分为零 ⟺ 正负部分互相抵消。 上面每一条曲线与别的曲线相乘后，在 $[-\pi,\pi]$ 上的”正面积”与”负面积”恰好相等，所以积分为零——这就是”垂直”在函数空间里的具体样子。

计算步骤与手算演示

演示一（手算）：$2\times 2$ 马尔可夫矩阵的完整对角化 + 收敛曲线

步骤 1：验证马尔可夫条件。 \(a_{11},a_{12},a_{21},a_{22} = 0.8,\ 0.3,\ 0.2,\ 0.7 \ \ge 0\ \checkmark\) \(\text{第 1 列：} 0.8 + 0.2 = 1\ \checkmark,\qquad \text{第 2 列：} 0.3 + 0.7 = 1\ \checkmark\) 所以 $A$ 是马尔可夫矩阵。由上面的”一句话证明”，$\lambda = 1$ 必是特征值。

步骤 2：特征多项式。 \(\det(A - \lambda I) = (0.8-\lambda)(0.7-\lambda) - (0.3)(0.2) = (0.8-\lambda)(0.7-\lambda) - 0.06.\) 展开：$(0.8-\lambda)(0.7-\lambda) = 0.56 - 1.5\lambda + \lambda^2$，故 \(\det(A-\lambda I) = \lambda^2 - 1.5\lambda + 0.56 - 0.06 = \lambda^2 - 1.5\lambda + 0.5 = (\lambda - 1)(\lambda - 0.5).\) （分解验证：$(\lambda-1)(\lambda-0.5) = \lambda^2 - 1.5\lambda + 0.5$ ✓）

步骤 3：双重自检。 \(\operatorname{tr}(A) = 0.8 + 0.7 = 1.5 = \lambda_1 + \lambda_2 = 1 + 0.5\ \checkmark\) \(\det(A) = 0.8\times 0.7 - 0.3\times 0.2 = 0.56 - 0.06 = 0.5 = \lambda_1\lambda_2 = 1\times 0.5\ \checkmark\) （用脚本核对：trace $=1.5$，det $=0.49999999999999994$——浮点误差，真值 $0.5$。）

【计算机制解说】 为什么必然有一个特征值是 $1$？观察 $\det(A-I) = (\lambda-1)(\lambda-0.5)\big\vert _{\lambda=1} = 0$。更直接地：$A - I = \begin{bmatrix}-0.2 & 0.3\\ 0.2 & -0.3\end{bmatrix}$，第二行恰好是第一行的负倍，所以 $A-I$ 奇异。这不是巧合——每一列和为 1 $\iff$ $A-I$ 的每一列和为 0 $\iff$ $A-I$ 的各行之和为 0 $\iff$ 行向量线性相关（所有行加起来得到零行），所以 $A-I$ 必奇异，$1$ 必是特征值。这就是讲次 21”行列式为 0 $\iff$ 奇异 $\iff$ 有非零零空间”的直接应用。

步骤 4：求稳态向量（$\lambda = 1$ 的特征向量）。 解 $(A-I)\mathbf{x} = \mathbf{0}$： \(\begin{bmatrix} -0.2 & 0.3 \\ 0.2 & -0.3 \end{bmatrix}\begin{bmatrix} x_1 \\ x_2\end{bmatrix} = \begin{bmatrix}0\\0\end{bmatrix} \ \Longrightarrow\ -0.2x_1 + 0.3x_2 = 0 \ \Longrightarrow\ 0.2x_1 = 0.3x_2 \ \Longrightarrow\ x_1 = 1.5\,x_2.\) 取 $x_2 = 2$，得 $\mathbf{x}_1 = \begin{bmatrix}3\\2\end{bmatrix}$（也可取 $\begin{bmatrix}0.3\\0.2\end{bmatrix}$，同方向）。

验证（脚本核对 $A[3,2]^{\mathsf T}$）： \(A\begin{bmatrix}3\\2\end{bmatrix} = \begin{bmatrix}0.8\cdot 3 + 0.3\cdot 2\\ 0.2\cdot 3 + 0.7\cdot 2\end{bmatrix} = \begin{bmatrix}2.4+0.6\\ 0.6+1.4\end{bmatrix} = \begin{bmatrix}3\\2\end{bmatrix}\ \checkmark\)

归一化（让分量和为 1，成为真正的概率分布）： \(\mathbf{u}_\infty = \frac{1}{3+2}\begin{bmatrix}3\\2\end{bmatrix} = \begin{bmatrix}0.6\\0.4\end{bmatrix}\ \checkmark\)

步骤 5：求 $\lambda_2 = 0.5$ 的特征向量。 解 $(A - 0.5I)\mathbf{x} = \mathbf{0}$： \(A - 0.5I = \begin{bmatrix} 0.8-0.5 & 0.3 \\ 0.2 & 0.7-0.5\end{bmatrix} = \begin{bmatrix} 0.3 & 0.3 \\ 0.2 & 0.2\end{bmatrix}.\) \(\begin{bmatrix}0.3 & 0.3\\ 0.2 & 0.2\end{bmatrix}\begin{bmatrix}x_1\\x_2\end{bmatrix} = \mathbf{0} \ \Longrightarrow\ 0.3x_1 + 0.3x_2 = 0 \ \Longrightarrow\ x_1 = -x_2.\) 取 $\mathbf{x}_2 = \begin{bmatrix}1\\-1\end{bmatrix}$。验证： \(A\begin{bmatrix}1\\-1\end{bmatrix} = \begin{bmatrix}0.8\cdot 1 + 0.3\cdot(-1)\\ 0.2\cdot 1 + 0.7\cdot(-1)\end{bmatrix} = \begin{bmatrix}0.5\\ -0.5\end{bmatrix} = 0.5\begin{bmatrix}1\\-1\end{bmatrix}\ \checkmark\)

步骤 6：初始条件分解 $\mathbf{u}_0 = \begin{bmatrix}0\\1\end{bmatrix}$。 设 $\mathbf{u}_0 = c_1\mathbf{x}_1 + c_2\mathbf{x}_2$，即 \(c_1\begin{bmatrix}0.6\\0.4\end{bmatrix} + c_2\begin{bmatrix}1\\-1\end{bmatrix} = \begin{bmatrix}0\\1\end{bmatrix}.\) （这里 $c_1$ 乘的是已归一化的稳态向量 $\begin{bmatrix}0.6\\0.4\end{bmatrix}$，便于直接读出极限。）

第一分量：$0.6c_1 + c_2 = 0 \Rightarrow c_2 = -0.6c_1$。 第二分量：$0.4c_1 - c_2 = 1 \Rightarrow 0.4c_1 + 0.6c_1 = 1 \Rightarrow c_1 = 1$。 于是 $c_2 = -0.6\cdot 1 = -0.6$。即

自检：$1\cdot\begin{bmatrix}0.6\\0.4\end{bmatrix} + (-0.6)\begin{bmatrix}1\\-1\end{bmatrix} = \begin{bmatrix}0.6-0.6\\ 0.4+0.6\end{bmatrix} = \begin{bmatrix}0\\1\end{bmatrix}$ ✓（脚本核对输出 c1,c2 -> 1 0.4，其中第二个数是第二分量的残差验证 $0.4+0.6=1$。）

⚠️ 一个高频计算陷阱：不少同学会把 $c_2$ 也写成 $-0.4$（两分量”对称地”分配）。这是错的。必须代回两个分量：第一个分量给出 $c_2=-0.6c_1$，第二个分量才定出 $c_1=1$。只有把 $\mathbf{u}_0=[0,1]^{\mathsf T}$ 完整代入方程组才能得到正确值。用 $c_2=-0.4$ 检验：$0.6(1) + (-0.4) = 0.2 \ne 0$ ✗。

步骤 7：写出通解并观察收敛。 \(\mathbf{u}_k = c_1\lambda_1^k\mathbf{x}_1 + c_2\lambda_2^k\mathbf{x}_2 = 1\cdot 1^k\begin{bmatrix}0.6\\0.4\end{bmatrix} + (-0.6)(0.5)^k\begin{bmatrix}1\\-1\end{bmatrix}\) \(\boxed{\ \mathbf{u}_k = \begin{bmatrix}0.6 - 0.6(0.5)^k\\[2pt] 0.4 + 0.6(0.5)^k\end{bmatrix}\ }\)

由于 $(0.5)^k \to 0$，立刻看出 $\mathbf{u}_k \to \begin{bmatrix}0.6\\0.4\end{bmatrix}$，且误差以每步减半的速度衰减。

逐步数值表（脚本核对，与公式完全一致）：

 k |  u_k(1)        u_k(2)        |u_k - u_inf|_1 (误差)
---+--------------------------------+----------------------
 0 |  0.000000     1.000000        1.20
 1 |  0.300000     0.700000        0.60
 2 |  0.450000     0.550000        0.30
 3 |  0.525000     0.475000        0.15
 4 |  0.562500     0.437500        0.075
 5 |  0.581250     0.418750        0.0375
 6 |  0.590625     0.409375        0.01875
 7 |  0.595313     0.404687        0.009375
 8 |  0.597656     0.402344        0.0046875
 9 |  0.598828     0.401172        0.00234375
10 |  0.599414     0.400586        0.001171875

（误差定义：$\vert \mathbf{u}k - \mathbf{u}\infty\vert _1 = \vert u_k(1)-0.6\vert + \vert u_k(2)-0.4\vert = 2\times0.6\times(0.5)^k = 1.2\cdot(0.5)^k$。第 7 行的脚本输出为 0.595312 0.404687，是浮点显示末位差异；精确值是 $\frac{381}{640}=0.5953125$ 与 $\frac{259}{640}=0.4046875$。）

每一行的两个分量之和恒为 1（脚本 sum check 输出全部 $\approx 1$）——概率总量守恒，这是马尔可夫性的直接后果。

收敛曲线（ASCII 图）：

  u_k(1) 从 0 爬向稳态 0.600（纵轴放大到 [0.28, 0.60]，"+---" 横轴为步数 k）

0.600 |            * * * * *  <- 稳态 0.600
      |          *
      |        *
      |
0.520 |      *
      |
      |
      |
0.440 |    *
      |
      |
      |
0.360 |
      |
      |
      |  *
0.280 |*
      +----------------------
        0 1 2 3 4 5 6 7 8 910  k

  数值表（脚本核对）：
   k :   0      1      2      3      4      5      6      7      8      9     10
  u_k(1): 0.0000 0.3000 0.4500 0.5250 0.5625 0.5813 0.5906 0.5953 0.5977 0.5988 0.5994
  u_k(2): 1.0000 0.7000 0.5500 0.4750 0.4375 0.4188 0.4094 0.4047 0.4023 0.4012 0.4006
  误差  : 1.2000 0.6000 0.3000 0.1500 0.0750 0.0375 0.0188 0.0094 0.0047 0.0023 0.0012

  柱状图（u_k(1)，每格 = 0.015）：
   k= 0 | 0.0000 |
   k= 1 | 0.3000 |####################
   k= 2 | 0.4500 |##############################
   k= 3 | 0.5250 |###################################
   k= 4 | 0.5625 |#####################################
   k= 5 | 0.5813 |#######################################
   k= 6 | 0.5906 |#######################################
   k= 7 | 0.5953 |########################################
   k= 8 | 0.5977 |########################################
   k= 9 | 0.5988 |########################################
   k=10 | 0.5994 |########################################
       （顶端那条"横杠"就是稳态 0.6000；格子几乎填满后再也不变化）

  误差 1.2 → 0.6 → 0.3 → 0.15 → 0.075 → ...   每步严格减半（因子 λ_2 = 0.5）

曲线形状是典型的指数趋近：先大幅移动，随后越来越慢，像渐近线一样贴到 $0.6$。衰减速率由 $\vert \lambda_2\vert = 0.5$ 控制——若 $\lambda_2 = 0.9$，曲线会拖得很长；若 $\lambda_2 = 0.1$，两三步就基本到位。

步骤 8：$A^k$ 本身的极限。 用 $A^k = S\Lambda^kS^{-1}$，当 $k\to\infty$ 时 $\Lambda^k \to \begin{bmatrix}1&0\\0&0\end{bmatrix}$，于是 \(A^\infty = \begin{bmatrix}3&1\\2&-1\end{bmatrix}\begin{bmatrix}1&0\\0&0\end{bmatrix}\begin{bmatrix}3&1\\2&-1\end{bmatrix}^{-1} = \mathbf{x}_1\,\mathbf{y}_1^{\mathsf T}\) 其中 $\mathbf{y}_1^{\mathsf T}$ 是使 $\mathbf{y}_1^{\mathsf T}\mathbf{x}_1 = 1$ 的左特征向量。脚本算得 \(A^{100} = \begin{bmatrix}0.6 & 0.6 \\ 0.4 & 0.4\end{bmatrix} = \begin{bmatrix}0.6\\0.4\end{bmatrix}\begin{bmatrix}1 & 1\end{bmatrix}.\) 关键在于：$A^\infty$ 的每一列都是同一个稳态向量。 无论初始分布是什么，结果都一样。

【计算机制解说】 为什么最终只剩下秩一的矩阵？因为 $A^k = \sum_j \lambda_j^k\,\mathbf{x}_j\mathbf{y}_j^{\mathsf T}$ 是秩一外积之和，$\lambda_1 = 1$ 的那一项 $\mathbf{x}_1\mathbf{y}_1^{\mathsf T}$ 系数恒为 1 永不衰减，其余项带着 $\lambda_j^k\to 0$ 一起消失。这就是”稳态 = 秩一投影“的含义：$A^\infty$ 把任何向量投影到稳态方向上。

演示二（手算）：$f(x) = x$ 在 $[-\pi,\pi]$ 上的傅里叶级数（分部积分逐步推导）

步骤 1：$a_0$（常数项 / 平均值）。 \(a_0 = \frac{1}{\pi}\int_{-\pi}^{\pi} x\,dx = \frac{1}{\pi}\left[\frac{x^2}{2}\right]_{-\pi}^{\pi} = \frac{1}{\pi}\cdot 0 = 0.\) （$x$ 是奇函数，在对称区间上积分为 0。）注意：笔记里约定常数项写作 $\frac{a_0}{2}$，所以 $f$ 的平均值恰为 $\frac{a_0}{2} = 0$；若用另一种常见约定 $a_0 = \frac{1}{2\pi}\int f\,dx$，则 $a_0=0$ 也成立。用哪种约定都必须前后一致。

步骤 2：余弦系数 $a_k = 0$（$k\ge1$）。 \(a_k = \frac{1}{\pi}\int_{-\pi}^{\pi} x\cos(kx)\,dx.\) 被积函数 $x\cos kx$ 是（奇）×（偶）$=$ 奇函数，在对称区间 $[-\pi,\pi]$ 上积分为 0。故 \(a_k = 0\quad(k = 1,2,3,\dots).\) 几何意义：$f(x)=x$ 是奇函数，而所有 $\cos kx$ 都是偶函数，在偶子空间上没有分量。这跟”$\mathbf{b}\perp$ 某方向则投影为 0”是同一件事。

步骤 3：正弦系数 $b_k$（分部积分）。 \(b_k = \frac{1}{\pi}\int_{-\pi}^{\pi} x\sin(kx)\,dx.\) 令 $u = x$，$dv = \sin(kx)\,dx$，则 $du = dx$，$v = -\frac{\cos(kx)}{k}$。分部积分： \(\int x\sin(kx)\,dx = -\frac{x\cos(kx)}{k} + \int \frac{\cos(kx)}{k}\,dx = -\frac{x\cos(kx)}{k} + \frac{\sin(kx)}{k^2}.\) 代入上下限： \(\int_{-\pi}^{\pi} x\sin(kx)\,dx = \left[-\frac{x\cos(kx)}{k} + \frac{\sin(kx)}{k^2}\right]_{-\pi}^{\pi}.\) 正弦项在 $x = \pm\pi$ 处为 $\sin(\pm k\pi) = 0$，所以只剩第一项： \(= -\frac{\pi\cos(k\pi)}{k} - \left(-\frac{(-\pi)\cos(-k\pi)}{k}\right) = -\frac{\pi\cos k\pi}{k} - \frac{\pi\cos k\pi}{k} = -\frac{2\pi\cos(k\pi)}{k}.\) 用 $\cos(k\pi) = (-1)^k$，以及 $-\frac{2\pi(-1)^k}{k} = \frac{2\pi(-1)^{k+1}}{k}$： \(\int_{-\pi}^{\pi} x\sin(kx)\,dx = \frac{2\pi\,(-1)^{k+1}}{k}.\) 除以 $\pi$：

逐项列出（脚本核对）： \(b_1 = 2,\quad b_2 = -1,\quad b_3 = \frac{2}{3}\approx0.6667,\quad b_4 = -\frac{1}{2},\quad b_5 = \frac{2}{5}=0.4,\ \dots\) （脚本输出 b1 2.0000, b2 -1.0000, b3 0.6667, b4 -0.5000, b5 0.4000 ✓） 注意 $\vert b_k\vert = 2/k \to 0$：高频分量越来越小，这是傅里叶级数能收敛的原因，也解释了为什么”少数几项就能抓住主要形状”。

独立数值验证：$\int_{-\pi}^{\pi}x\sin x\,dx$ 的数值积分 = $6.283185307$，而公式给 $\frac{2\pi(-1)^{2}}{1} = 2\pi = 6.283185307$ ✓；同时 $\int_{-\pi}^{\pi}\sin^2x\,dx = 3.141592654 = \pi$ ✓。

步骤 4：写出级数。 \(\boxed{\ x = 2\left[\sin x - \frac{\sin 2x}{2} + \frac{\sin 3x}{3} - \frac{\sin 4x}{4} + \cdots\right] = \sum_{k=1}^{\infty}\frac{2(-1)^{k+1}}{k}\sin(kx)\ }\)

步骤 5：前三项近似与数值比较。 \(S_3(x) = 2\sin x - \sin 2x + \frac{2}{3}\sin 3x.\) 在 $x = 1$（弧度）处的部分和（脚本核对）： \(S_1(1) = 2\sin 1 = 1.682942,\qquad S_2(1) = 0.773645,\qquad S_3(1) = 0.867725,\qquad \text{精确值 } f(1) = 1.\) 可见收敛是震荡式的（先冲过头、再回来），不是单调逼近——这与马尔可夫那部分的单调指数收敛形成鲜明对比。

部分和逼近图（ASCII 图）：

   f(x)=x 与部分和 S_3(x) = 2sin x - sin 2x + (2/3)sin 3x     (x ∈ [-π, π])

  y
  π |                                            ,'|
    |                                        ,-'  |
    |                                     ,-'     |   ← 虚线为 f(x)=x
    |                                  ,-'        |
    |                              ,-'            |
    |                          ,-'  ····          |
    |                      ,-' ····      ····     |
  0 |---------·------------------------------------|------→ x
    |      ··/    ···                     ····     |   S_3 在 x=0,±π 处
    |    ··/           ····                    ····|   与 f 精确相交
    |  ··/                  ·····                |
 -π |··/                                        ,'|
    +-----------------------------------------'---+
      -π        -π/2        0        π/2        π

  特征：S_N 是奇函数，在 x = 0, ±π 处与 f 完全吻合（所有 sin(kx) 在这些点都是 0）；
        在区间内部 S_N 上下摆动穿越直线 f(x)=x，N 越大摆幅越小。

步骤 6：最优性（这是讲次 15-16 的连续翻版）。 设用前 $N$ 个正弦函数张成子空间 $V_N = \operatorname{span}\{\sin x, \sin 2x, \dots, \sin Nx\}$。取 $V_N$ 中任意函数 $g = \sum_{k=1}^N c_k\sin kx$，要最小化 \(\vert f - g\vert ^2 = \int_{-\pi}^{\pi}\big(f(x) - g(x)\big)^2dx.\) 结论：最小值在 $c_k = b_k$（即 $g = S_N$）处取到。 证明与离散情况逐字对应：把 $\vert f-g\vert ^2$ 展开成 $\vert f\vert ^2 - 2\sum c_k\langle f,\sin kx\rangle + \sum c_k^2\pi$，对每个 $c_k$ 求偏导置零，得 $2c_k\pi - 2\langle f,\sin kx\rangle = 0$，即 $c_k = \frac{\langle f,\sin kx\rangle}{\langle\sin kx,\sin kx\rangle} = b_k$。这正是法方程（normal equations）的连续版本。

数值证据（脚本核对，$\vert f - S_N\vert ^2$ 递减）： \(N=1:\ 8.1045,\qquad N=2:\ 4.9629,\qquad N=3:\ 3.5666,\qquad N=5:\ 2.2786.\) 随 $N$ 增大单调下降（且趋于 0），没有任何其他系数的选择能给出更小的误差。

步骤 7：Parseval 恒等式与 $x = \pi/2$ 得到的 Leibniz 级数。 连续版”勾股定理”：$\vert f\vert ^2 = \sum$（系数）$^2\times$（基长度）$^2$： \(\int_{-\pi}^{\pi}x^2dx = \frac{2\pi^3}{3}\quad\overset{?}{=}\quad \sum_{k=1}^\infty b_k^2\cdot\pi = \pi\sum_{k=1}^\infty\frac{4}{k^2} = 4\pi\cdot\frac{\pi^2}{6} = \frac{2\pi^3}{3}\ \checkmark\) （脚本核对：左边 $20.670851$，右边取 $k\le 6$ 时 $18.741346$，加上尾部正好收敛到 $20.670851$ ✓。这说明 $\sum 1/k^2 = \pi^2/6$ 与傅里叶展开是同一件事的两面。）

令 $x = \frac{\pi}{2}$：此时 $\sin(kx)$ 依次为 $\sin\frac{\pi}{2}=1$，$\sin\pi=0$，$\sin\frac{3\pi}{2}=-1$，$\sin2\pi=0$，$\sin\frac{5\pi}{2}=1,\dots$，即 $k$ 奇时等于 $(-1)^{(k-1)/2}$，$k$ 偶时为 $0$。代入 $x = 2\big[\sin x - \frac{\sin 2x}{2} + \frac{\sin 3x}{3} - \frac{\sin 4x}{4} + \frac{\sin 5x}{5}-\cdots\big]$，偶数项全部消失，奇数项留下： \(\frac{\pi}{2} = 2\left[1 - 0 + \frac{-1}{3} - 0 + \frac{1}{5} - 0 + \frac{-1}{7} + \cdots\right] = 2\left[1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \cdots\right].\) 两边除以 2： \(\boxed{\ \frac{\pi}{4} = 1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \cdots\ }\) （注意符号来源：$-1/3$ 是 $\frac{b_3}{1}\sin(3\pi/2) = \frac{2}{3}\cdot(-1)$ 除以 $2$ 的结果，$+1/5$ 是 $\frac{2}{5}\cdot(+1)$ 除以 2 的结果——符号来自各个 $\sin(k\pi/2)$ 的正负，不是来自 $b_k$ 的 $(-1)^{k+1}$，两者在奇数 $k$ 上恰好合成同一个交错模式。脚本核对：取 $2\times10^4$ 项求和得 $1.570746$，$\pi/2 = 1.570796$ ✓（误差 $5\times10^{-5}$，正是 Leibniz 级数著名的慢收敛）。）

【计算机制解说】 为什么”投影系数”能同时做到”误差最小”和”级数收敛到 $f$”？因为三角函数系是正交基（完备正交系），基向量两两垂直意味着各分量互不干扰：调整 $c_k$ 只影响 $c_k$ 那个方向上的误差，所以在每个方向上分别取最优就得到全局最优。正交性把 $n$ 维的最小二乘问题解耦成 $n$ 个独立的一元问题——这与讲次 15 里 $\hat{\mathbf{x}} = (A^{\mathsf T}A)^{-1}A^{\mathsf T}\mathbf{b}$ 在 $A$ 的列正交时退化为逐列相除 $\hat x_i = \mathbf{q}_i^{\mathsf T}\mathbf{b}/\mathbf{q}_i^{\mathsf T}\mathbf{q}_i$，是完全相同的机制。

演示三（手算）：$3\times 3$ 马尔可夫矩阵与 $f(x)=x^2$ 的傅里叶系数

（3a）$3\times3$ 人口迁移模型。

列和验证：第 1 列 $0.9+0.05+0.05 = 1$ ✓；第 2 列 $0.1+0.8+0.1=1$ ✓；第 3 列 $0.1+0.1+0.8=1$ ✓。元素非负 ✓，故是马尔可夫矩阵。

特征多项式（脚本用系数 $c_1 = \operatorname{tr} = 2.5$、$c_0 = \det = 0.56$ 计算）： \(-\lambda^3 + 2.5\lambda^2 - 2.06\lambda + 0.56 = -(\lambda-1)(\lambda^2 - 1.5\lambda + 0.56) = -(\lambda-1)(\lambda-0.8)(\lambda-0.7).\) \(\lambda_1 = 1,\qquad \lambda_2 = 0.8,\qquad \lambda_3 = 0.7.\) （自检：$1+0.8+0.7 = 2.5 = \operatorname{tr}$ ✓；$1\times0.8\times0.7 = 0.56 = \det$ ✓。）

稳态（幂迭代脚本结果）：$\mathbf{u}\infty = \begin{bmatrix}0.5\\0.25\\0.25\end{bmatrix}$，且 $M\mathbf{u}\infty = \mathbf{u}_\infty$ ✓（脚本核对完全一致）。收敛速度由第二大模长 $\vert \lambda_2\vert = 0.8$ 控制，误差每步乘以 $0.8$：$0.8^{10} = 0.107374$，$0.8^{20} = 0.011529$（脚本核对 ✓）。注意不是 $0.7$ 主导——虽然 $\vert \lambda_3\vert = 0.7 < 0.8$，但 $0.7$ 那一项衰减更快，长期由更慢的 $0.8$ 说了算。这也说明”收敛速度 = 第二大特征值”这条法则用的是按模长排序的第二个，而不是随便挑一个。

（3b）$f(x) = x^2$ 的傅里叶系数（偶函数，只有余弦项）。

\(a_0 = \frac{1}{\pi}\int_{-\pi}^{\pi}x^2dx = \frac{1}{\pi}\cdot\frac{2\pi^3}{3} = \frac{2\pi^2}{3}\quad\Longrightarrow\quad \frac{a_0}{2} = \frac{\pi^2}{3}\approx3.289868.\) （数值积分得到 $3.289868$，与 $\pi^2/3$ 一致 ✓。）

\(a_k = \frac{1}{\pi}\int_{-\pi}^{\pi}x^2\cos(kx)\,dx = \frac{4(-1)^k}{k^2},\qquad b_k = 0\ (x^2\sin kx \text{ 是奇函数}).\) （脚本核对：$k=1:-4.0000$、$k=2:+1.0000$、$k=3:-0.4444$、$k=4:+0.2500$，与 $4(-1)^k/k^2$ 完全一致 ✓。）

于是 \(x^2 = \frac{\pi^2}{3} + 4\sum_{k=1}^{\infty}\frac{(-1)^k}{k^2}\cos(kx) = \frac{\pi^2}{3} - 4\cos x + \cos 2x - \frac{4}{9}\cos 3x + \cdots\) 在 $x = \pi$ 处：$\pi^2 = \frac{\pi^2}{3} + 4\sum\frac{(-1)^k}{k^2}(-1)^k = \frac{\pi^2}{3} + 4\sum\frac{1}{k^2}$，得 $\sum 1/k^2 = \pi^2/6$ ✓——又是一个”用傅里叶级数证明数论恒等式”的漂亮例子。

Parseval 自检：$2\pi\left(\frac{\pi^2}{3}\right)^2 + \pi\sum\frac{16}{k^4} = \frac{2\pi^5}{9} + \frac{16\pi}{90}\pi^4 = \frac{2\pi^5}{9}+\frac{8\pi^5}{45} = \frac{2\pi^5}{5} = \int_{-\pi}^{\pi}x^4dx$ ✓（数值：$122.4079$ 对 $122.4079$）。

演示四（应用）：天气预报、Google PageRank 与”长期行为 = 稳态”

（4a）天气模型（晴 / 雨）。 设状态 1 = 晴，状态 2 = 雨，转移矩阵

\(W = \begin{bmatrix} 0.9 & 0.5 \\ 0.1 & 0.5 \end{bmatrix}\) 其中第 1 列读作”今天晴：明天晴 0.9，明天雨 0.1”，第 2 列读作”今天雨：明天晴 0.5，明天雨 0.5”。列和 $0.9+0.1=1$、$0.5+0.5=1$ ✓。特征值：$\operatorname{tr}=1.4$，$\det = 0.9\cdot0.5-0.5\cdot0.1 = 0.45-0.05=0.40$，故 $\lambda^2-1.4\lambda+0.4=(\lambda-1)(\lambda-0.4)$，即 $\lambda_1=1,\ \lambda_2=0.4$。

稳态：$W-I = \begin{bmatrix}-0.1&0.5\\0.1&-0.5\end{bmatrix}\Rightarrow 0.1x_1=0.5x_2\Rightarrow x_1 = 5x_2$，取 $\begin{bmatrix}5\\1\end{bmatrix}$，归一化得 \(\mathbf{u}_\infty = \begin{bmatrix}5/6\\1/6\end{bmatrix}\approx\begin{bmatrix}0.8333\\0.1667\end{bmatrix}.\) 验证：$W\begin{bmatrix}0.8333\\0.1667\end{bmatrix} = \begin{bmatrix}0.9(0.8333)+0.5(0.1667)\\ 0.1(0.8333)+0.5(0.1667)\end{bmatrix} = \begin{bmatrix}0.75+0.0833\\0.0833+0.0833\end{bmatrix} \approx \begin{bmatrix}0.8333\\0.1667\end{bmatrix}$ ✓

解读：长期来看约 $5/6$ 的日子是晴天、$1/6$ 是雨天——与初始天气完全无关。衰减因子 $\vert \lambda_2\vert = 0.4$ 很小，所以约 5-6 天后就基本进入这个比例。

（4b）人口迁移模型。 演示三的 $M$ 就是其抽象形式：三个城市之间每年迁移一部分人口，$M_{ij}$ = 从城市 $j$ 迁到城市 $i$ 的比例（留在本地记入对角元）。长期分布 $\begin{bmatrix}0.5\\0.25\\0.25\end{bmatrix}$ 表示无论最初人口如何分布，最终三个城市会稳定在 $2:1:1$。这与种群生态学中的 Leslie 矩阵、化学反应的平衡浓度、疾病传播的终点分布都是同一套数学。

（4c）Google PageRank：稳态向量 = 网页排名。

把互联网想成一个巨大的有向图：节点 = 网页，边 = 超链接。定义”随机冲浪者”：站在网页 $j$ 上时，以相等概率点击 $j$ 的某个出链；即 $a_{ij} = \frac{1}{(\text{网页 }j\text{ 的出链数})}$（若 $j$ 链向 $i$），否则为 0。这样按列求和恰好为 1（$j$ 的全部出链概率之和为 1，还是”列和 = 1”！），得到一个巨型马尔可夫矩阵（今天的网页数 $n$ 是千亿量级）。

PageRank 就是求这个矩阵的稳态向量 $\mathbf{x}$：$G\mathbf{x} = \mathbf{x}$，$\sum_i x_i = 1$。分量 $x_i$ 就是网页 $i$ 的”重要性”分数，Google 用它排序搜索结果。为什么这是个好定义？因为一个网页的重要性 = 指向它的那些网页的重要性，按各自出链数摊分后求和——这正是稳态方程 $x_i = \sum_j a_{ij}x_j$ 的逐字解读。这个想法跟讲次 21-22 的”特征向量是矩阵的固有方向”完全同源；只是矩阵规模让 $S\Lambda S^{-1}$ 无法使用，实际算法是幂迭代 $\mathbf{u}_{k+1} = G\mathbf{u}_k$（等价于让随机冲浪者走很多步），由 $\vert \lambda_2\vert <1$ 保证收敛。

两个必须打的补丁：

• 悬挂节点（dangling node）：若网页 $j$ 没有任何出链，则该列为全零，列和不是 1，$G$ 不是马尔可夫矩阵，随机冲浪者的概率会”漏掉”。补法是令它等概率跳到所有网页。
• 阻尼因子（damping factor）$d = 0.85$：纯链接转移矩阵可能周期或可约，不保证收敛。Brin 与 Page 的做法是混合 \(G = 0.85\,M + 0.15\,\frac{1}{n}\mathbf{1}\mathbf{1}^{\mathsf T},\) 即”以 $0.85$ 的概率沿链接走，以 $0.15$ 的概率随机跳到任意网页”。因为 $\frac1n\mathbf{1}\mathbf{1}^{\mathsf T}$ 的每一列都是 $\frac1n\mathbf{1}$，列和仍为 1，$G$ 仍是马尔可夫矩阵；而且全部元素严格为正（$G_{ij}\ge 0.15/n > 0$）。严格正的马尔可夫矩阵自动不可约且非周期，于是 $\lambda=1$ 单重、其余 $\vert \lambda_j\vert \le 0.85$，唯一稳态 + 快速收敛（误差每步至少乘 $0.85$，$0.85^{50}\approx 0.0003$）。这就是”为什么必须加阻尼因子”的完整理由。

（4d）为什么”长期行为 = 稳态”？ 一句话：$\mathbf{u}_k = \sum_j c_j\lambda_j^k\mathbf{x}_j$，只有 $\lambda = 1$ 那一项带 $1^k$ 存活，其余 $\vert \lambda_j\vert <1$ 的项被指数式抹掉。初始条件的信息只存在于 $c_j$ 里，而 $\lambda_j^k\to0$ 让这些信息消失——这既解释了收敛，也解释了”为什么稳态与初始分布无关”。用讲次 22 的话说：$A^k$ 趋于一个秩一投影。

矩阵分解的核心思想

本讲出现的是同一个思想的两种化身：

（1）$A^k = S\Lambda^kS^{-1}$ 的”特征展开”

对演示一的 $A$，取 $S = \begin{bmatrix}3&1\\2&-1\end{bmatrix}$（列是特征向量，稳态列未归一化），$\Lambda = \begin{bmatrix}1&0\\0&0.5\end{bmatrix}$，则

这是把矩阵拆成”不变模式”之和：每个模式 $\mathbf{x}_j\mathbf{y}_j^{\mathsf T}$ 是秩一的，$A$ 作用在它上面只是乘 $\lambda_j$。极限情形 $A^\infty = \mathbf{x}_1\mathbf{y}_1^{\mathsf T}$ 是一个秩一投影（$A^\infty$ 的每一列都相同 = 稳态向量），它把任何初始分布”拍”到稳态方向上。

（2）傅里叶级数 = 无穷维的 $Q\Lambda Q^{\mathsf T}$ / 正交基展开

把 $f$ 写成 \(f = \sum_k \frac{\langle f, \varphi_k\rangle}{\langle \varphi_k,\varphi_k\rangle}\,\varphi_k,\) 其中 $\{\varphi_k\}$ 是正交函数系。逐项对比：

             有限维（讲次 14-16）            无穷维 / 连续（本讲）
  ─────────────────────────────────────────────────────────────────
  基向量      q_1, ..., q_n                  1, cos x, sin x, cos 2x, ...
  内积        v^T w = Σ v_i w_i              <f,g> = ∫ f(x)g(x) dx
  正交条件    q_i^T q_j = 0 (i≠j)            ∫ φ_i φ_j = 0 (i≠j)
  基长度平方  q_i^T q_i                      ∫ φ_i^2 = π 或 2π
  投影系数    x̂_i = q_i^T b / q_i^T q_i      a_k = <f,cos kx>/<cos kx,cos kx>
  最佳逼近    投影到 C(A) 上                  投影到 span{前 N 个三角基}
  误差最小    ||b - A x̂|| 最小               ||f - S_N|| 最小
  勾股定理    ||b||^2 = Σ (q_i^T b)^2/||q_i||^2   ||f||^2 = Σ (系数)^2 ||φ_i||^2

同一个分解的两个极端：

离散化的傅里叶 = 正交矩阵。 若只在 $n$ 个等距点上采样 $f$，则积分变成求和，傅里叶系数变成矩阵乘法 $\hat{\mathbf{c}} = F\mathbf{f}$，其中 $F$ 是离散傅里叶变换矩阵（DFT matrix），它的列是采样后的三角基。$F$ 是酉/正交矩阵（差一个 $1/\sqrt n$ 归一化），$F^{-1} = F^{*}$ —— 这正是讲次 14”正交矩阵 $Q^{-1}=Q^{\mathsf T}$”的直接体现。$n$ 个点的 DFT 若直接乘矩阵要 $O(n^2)$，FFT（快速傅里叶变换）把它降到 $O(n\log n)$，这是 20 世纪最重要的算法之一。Strang 在课上用一句话概括：”整个信号处理产业都建立在’正交矩阵’这一个概念上。”

马尔可夫与傅里叶的共同点：两处都在用一组基把对象展开，然后让每个分量独立演化。马尔可夫里分量按 $\lambda_j^k$ 衰减；傅里叶里分量按频率排布。$A^k$ 收敛是因为 $\vert \lambda_j\vert <1$；傅里叶级数收敛是因为 $\vert c_k\vert $ 随 $k$ 快速衰减。“对角化 = 解耦”是这门课自始至终的主旋律。

与其他讲次的关联

• 讲次 21（特征值与特征向量）：本讲全部计算都建立在 $A\mathbf{x}=\lambda\mathbf{x}$ 与 $\det(A-\lambda I)=0$ 之上。$A - I$ 的行线性相关 $\iff$ 列和为 1，是”奇异矩阵有非零零空间”的直接应用。
• 讲次 22（对角化与 $A^k$）：$A^k = S\Lambda^kS^{-1}$ 是本讲马尔可夫收敛的唯一工具。$\mathbf{u}_k = \sum_j c_j\lambda_j^k\mathbf{x}_j$ 中只有 $\lambda=1$ 项存活，这就是”稳态”。也再次印证讲次 22 的稳定性判据：所有 $\vert \lambda_j\vert <1$ 时 $A^k\to 0$；有 $\vert \lambda_j\vert >1$ 时发散。马尔可夫矩阵恰好卡在临界情形（一个 $=1$，其余 $<1$）——所以收敛到一个非零矩阵而不是零。
• 讲次 23（微分方程 $du/dt=Au$）：连续时间的稳态是 $\lambda = 0$（即 $du/dt = 0$），因为解里 $e^{\lambda t}$ 只有 $\lambda=0$ 不衰减；离散时间的稳态是 $\lambda = 1$，因为 $\lambda^k$ 只有 $\lambda=1$ 不衰减。两个”1”与”0”的呼应：$e^{0 t}=1$ 对 $\lambda=0$，$\lambda^k = 1$ 对 $\lambda=1$ —— 这正是把 $A$ 换成 $A - I$ 的对应（$e^{(A-I)t}$ 的特征值 $e^{(\lambda-1)t}$）。
• 讲次 25（对称矩阵与正定矩阵）：对称马尔可夫矩阵（如演示三里的 $S$，三列全同）有实特征值且特征向量正交，收敛行为最干净：$\lambda_1=1$，其余 $\vert \lambda_j\vert <1$，稳态 $\mathbf{u}\infty = \mathbf{1}/n$。讲次 25 会给出”实特征值 + 正交特征向量”的完美理论。演示三的 $M$ 不是对称的（$M{12}=0.1 \ne 0.05 = M_{21}$），所以它的特征向量不正交，但收敛性依然成立。
• 讲次 14-16（正交、投影、最小二乘）：傅里叶系数就是投影系数 $\hat x = \frac{\mathbf{a}^{\mathsf T}\mathbf{b}}{\mathbf{a}^{\mathsf T}\mathbf{a}}$ 的积分版本；”截断傅里叶级数是 $L^2$ 意义下的最佳逼近”就是投影定理；法方程 $A^{\mathsf T}A\hat{\mathbf{x}} = A^{\mathsf T}\mathbf{b}$ 在基正交时解耦为逐项相除。
• 讲次 27-29（SVD）：SVD $A = U\Sigma V^{\mathsf T}$ 也是”用正交基展开”，而且是对任意矩阵都成立的展开（不要求对称、不要求可对角化）。马尔可夫的 $A^\infty = \mathbf{x}_1\mathbf{y}_1^{\mathsf T}$ 本身就是一种”秩一分解”，是 SVD 思想的雏形。
• 讲次 11-12（图与网络）：PageRank 的马尔可夫矩阵正是”网络图”的转移矩阵，把讲次 12 的关联矩阵视角接了过来。

关键要点

1. 马尔可夫矩阵 = 非负 + 每列和 1（列随机）。$a_{ij}$ 读作”从状态 $j$ 到状态 $i$”的转移概率，$\mathbf{u}_{k+1}=A\mathbf{u}_k$，且 $A$ 保持分量和与 1-范数不增。
2. $\lambda = 1$ 永远是特征值，因为列和 1 $\iff A^{\mathsf T}\mathbf{1}=\mathbf{1}$ $\iff \det(A-I)=0$。注意 $\mathbf{1}$ 是 $A^{\mathsf T}$ 的特征向量，不是（一般地）$A$ 的。
3. 全部特征值满足 $\vert \lambda\vert \le 1$：直接论证是”$A$ 不放大 1-范数”（因为列和为 1），$\vert A\mathbf{x}\vert 1\le\vert \mathbf{x}\vert _1$；Gershgorin 论证要用在 $A^{\mathsf T}$ 上（等价的”列圆盘” $[2a{jj}-1,\,1]\subseteq[-1,1]$），用在 $A$ 自己的行圆盘上会越界。若不可约且非周期，则 $\lambda=1$ 单重、其余 $\vert \lambda\vert <1$，于是 $\mathbf{u}_k = A^k\mathbf{u}_0 \to$ 稳态向量（归一化使分量和为 1 的 $\lambda=1$ 特征向量）。收敛速度由第二大模长 $\vert \lambda_2\vert $ 决定。
4. $A^\infty$ 是秩一投影：$A^\infty = \mathbf{x}_1\mathbf{y}_1^{\mathsf T}$，每一列都是同一个稳态向量，秩为 1 —— 这是 $A^k=S\Lambda^kS^{-1}$ 中只有 $\lambda_1=1$ 项存活的几何含义。
5. 傅里叶系数就是投影系数： \(a_k = \frac{\langle f,\cos kx\rangle}{\langle\cos kx,\cos kx\rangle} = \frac{1}{\pi}\int_{-\pi}^{\pi}f(x)\cos(kx)\,dx,\qquad b_k = \frac{1}{\pi}\int_{-\pi}^{\pi}f(x)\sin(kx)\,dx\) 与离散的 $\hat x_i = \frac{\mathbf{q}_i^{\mathsf T}\mathbf{b}}{\mathbf{q}_i^{\mathsf T}\mathbf{q}_i}$ 结构完全相同，只是”求和”换成了”积分”。
6. 必背范例：$x = 2\sum_{k\ge1}\frac{(-1)^{k+1}}{k}\sin kx$ 于 $[-\pi,\pi]$；取 $x=\pi/2$ 得 $\frac{\pi}{4} = 1-\frac13+\frac15-\cdots$。截断的部分和 $S_N$ 是 $L^2$ 意义下最佳逼近，且 $\vert f\vert ^2 = \sum c_k^2\vert \varphi_k\vert ^2$（Parseval）。

常见误区与注意事项

1. 把”列和为 1”记成”行和为 1”。 本课程的约定是列随机：$A^{\mathsf T}\mathbf{1} = \mathbf{1}$。若改成行和为 1（行随机），则 $\mathbf{1}$ 是 $A$（而非 $A^{\mathsf T}$）的特征向量，$\lambda=1$ 的结论仍然成立，但稳态向量 $A\mathbf{x}=\mathbf{x}$ 与 $\mathbf{1}$ 的关系、以及 $a_{ij}$ 的”从 $j$ 到 $i$”解读全会颠倒。判定题目给的是哪种约定，是第一件事。记忆口诀：列和 = 1 时，$\mathbf{u}$ 是列向量且 $A\mathbf{u}$ 保证概率守恒（$\mathbf{1}^{\mathsf T}A\mathbf{u} = \mathbf{1}^{\mathsf T}\mathbf{u}$）；这正是”列和”的用武之处。

2. 以为”所有 $\vert \lambda\vert <1$”，或者以为 $\lambda=1$ 的项也会衰减。 正确的是：$\lambda = 1$ 必然是特征值之一（所以不可能全部 $<1$），而其余才能严格 $<1$。$1^k = 1$ 永不衰减，这正是稳态非零的原因。相应地，$A^k $ 不趋于零矩阵，而趋于秩一的 $A^\infty$。若错说成”趋向零”，那是对讲次 22 中 $\vert \lambda\vert <1\Rightarrow A^k\to0$ 的判据误用——马尔可夫矩阵恰好不满足那个前提。

3. 傅里叶系数的归一化常数搞混。 必须先声明区间与公式再计算。本讲的约定是区间 $[-\pi,\pi]$、$a_k = \frac1\pi\int f\cos kx$、$b_k = \frac1\pi\int f\sin kx$、常数项写 $\frac{a_0}{2}$（用 $a_0 = \frac1\pi\int f$）。若改用区间 $[-L,L]$，则所有 $\frac{1}{\pi}$ 变成 $\frac{1}{L}$，且 $kx$ 变成 $\frac{k\pi x}{L}$；若改用复指数形式 $f = \sum c_ke^{ikx}$，则 $c_k = \frac{1}{2\pi}\int f e^{-ikx}dx$，且 $c_k$ 与 $a_k,b_k$ 的关系是 $c_k = \frac{a_k - ib_k}{2}$（$k>0$）。混用会导致结果差 2 倍或 $\pi$ 倍。

4. 以为傅里叶级数在每个点都收敛到 $f(x)$。 在跳跃间断点处，级数收敛到左右极限的平均值 $\frac{f(x^-)+f(x^+)}{2}$。典型例子：方波 $f(x) = +1\ (0<x<\pi)$、$-1\ (-\pi<x<0)$ 的展开是 $f = \frac{4}{\pi}\big(\sin x + \frac{\sin 3x}{3} + \frac{\sin 5x}{5}+\cdots\big)$（只有奇次谐波），在 $x=0$ 处级数收敛到 $0$，而 $f(0)$ 本身要么未定义要么取 $\pm1$。这也是吉布斯现象（Gibbs phenomenon）的来源：部分和在跳点附近永远有约 $9\%$ 的过冲，$N\to\infty$ 也不消失（只是被压缩到跳点附近）。此外，收敛还要求 $f$ 满足一定条件（分段光滑即可），病态函数可能不逐点收敛。

5. 以为傅里叶基是”唯一”的正交基。 三角函数系只是一组方便的正交基（对周期函数、对平移不变的算子特别自然），但绝非唯一。勒让德多项式在 $[-1,1]$ 上正交（带权 1）、切比雪夫多项式带权 $1/\sqrt{1-x^2}$ 正交、哈尔小波（Haar wavelets）也是正交基。选哪组基要看问题：解热传导方程用三角函数（它们是 $d^2/dx^2$ 的特征函数！），压缩图像用小波。这与讲次 30”选对基能让矩阵变简单”是同一思想，也是本课程最后一章”基变换”的伏笔。

思考题（带答案）

Q1.（纯计算）设马尔可夫矩阵 \(A = \begin{bmatrix} 0.7 & 0.2 \\ 0.3 & 0.8 \end{bmatrix}.\) (a) 验证它是马尔可夫矩阵；(b) 求全部特征值；(c) 求归一化的稳态向量；(d) 若 $\mathbf{u}_0 = \begin{bmatrix}1\\0\end{bmatrix}$，写出 $\mathbf{u}_k$ 的闭式表达式，并指出误差按什么比率衰减。

Q2.（判断 + 概念）判断下列矩阵哪些是马尔可夫矩阵，并说明理由： \(B = \begin{bmatrix} 0.2 & 0.3 \\ 0.9 & 0.6\end{bmatrix},\qquad C = \begin{bmatrix} 0.7 & -0.1 \\ 0.3 & 1.1\end{bmatrix},\qquad D = \begin{bmatrix} 0.5 & 0.5 \\ 0.5 & 0.5\end{bmatrix}.\) 对 $B$，$B^k\mathbf{u}_0$ 会收敛吗？

Q3.（纯计算）求 $f(x) = \begin{cases}1, & 0 < x < \pi\\ -1, & -\pi < x < 0\end{cases}$（方波）在 $[-\pi,\pi]$ 上的傅里叶级数，并求级数在 $x=0$ 处的值。

Q4.（概念）(a) 为什么”列和为 1”能保证 $A$ 必定有特征值 $1$，而 $A^{\mathsf T}$ 的特征向量 $\mathbf{1}$ 一般不是 $A$ 的特征向量？(b) 若马尔可夫矩阵 $A$ 的 $\lambda=1$ 是二重特征值，$\mathbf{u}_k = A^k\mathbf{u}_0$ 还会收敛到唯一的稳态吗？(c) 为什么傅里叶部分和 $S_N$ 是”最小二乘意义下最佳”的？