6.6 幂迭代与 PageRank

本节位置：模块 6 · 特征值 ｜ 前置：6.1 特征值与特征向量 ｜ 预计：35 分钟

一句话：反复用矩阵乘一个向量，主特征方向会自己浮现；收敛速度由 $|{\lambda }_2/{\lambda }_1|$ 决定，PageRank 就是把这个过程用在网页链接矩阵上。

0. 场景引入

一个学术论文检索站，索引了 5000 万篇论文、4 亿条引用。产品要给每篇论文打一个「影响力分」，取前 500 名做首页推荐。500 个位置里，分差很小的两篇论文谁上谁下，全靠这个分数；榜单每周更新一次，跑在周日凌晨的低峰期。直接解 5000 万阶矩阵的特征向量不现实；但矩阵是稀疏的：4 亿条边按每条 8 B 存成 CSR 约 3.2 GB，秩向量 $5\times 10^7\times 8\mathrm{B}=400$ MB，单机 64 GB 放得下。

能做的只有一件事：每轮把所有边扫一遍，做一次矩阵-向量乘。按 20 GB/s 的内存带宽，一轮读 3.2 GB 约 0.16 s。阻尼 $d=0.85$ 时最坏收敛比是 0.85，把残差压到 $10^{-6}$ 需要 $\ln (10^{-6})/\ln (0.85)\approx 85$ 轮，约 14 秒；若这张图的实际副特征值只有 0.6，则 27 轮、约 4 秒就够。

决策：迭代 30 轮就上线，还是等满 85 轮？代价：30 轮时残差最坏还有 $0.85^{30}\approx 0.8\%$，首页前 100 名的排序会抖动；而多等 55 轮只多花约 9 秒。

读完本节，你能回答的三个问题是：

1. 为什么反复乘同一个向量，方向会自己稳定下来？
2. 收敛要多少轮，由哪个比值决定？
3. 阻尼因子 $d$ 在「忠实于链接结构」和「收敛速度」之间怎么取舍？

1. 直觉

把初始向量拆成特征向量之和：${\mathbf{x}}_0={\sum }_i{c}_i{\mathbf{v}}_i$。乘一次 $A$：

乘 $k$ 次后，第 $i$ 个分量带上了因子 ${\lambda }_i^k$。若 $|{\lambda }_1|>|{\lambda }_2|\ge \cdots$，则 $|{\lambda }_1{|}^k$ 增长最快（或衰减最慢），其它分量相对它越来越小。归一化去掉长度后，方向就趋近 ${\mathbf{v}}_1$。

💡 一句话直觉：幂迭代 = 让矩阵自己「筛选」出最大的特征方向；每乘一次，主方向就比其他方向多占一点比例。

收敛速度由比值 $|{\lambda }_2/{\lambda }_1|$ 决定：比值越小，副特征方向被甩开得越快。若比值为 $0.9$，每步只缩小 10%，要很久；若为 $0.1$，几步就够。若 ${\lambda }_1<0$，方向会左右翻转；若 ${\lambda }_1$ 是复数，会旋转着逼近。

图：从 ${\mathbf{x}}_0$ 出发，每次乘 $A$ 再归一化，向量尖端沿单位圆移动并逐渐贴近主特征方向 ${\mathbf{v}}_1$。这个例子里 $|{\lambda }_2/{\lambda }_1|\approx 0.24$，所以 7 步后方向已经几乎重合。

类比边界：幂迭代只给一个特征向量（主特征向量），不给全部；若前两个特征值模相等（如 $1$ 和 $-1$），不收敛到单一方向。此时需要加位移或块方法。

1.1 它在现实世界里对应什么

对链接图，主特征向量不是抽象对象，而是**「随机冲浪者在每个页面停留的时间比例」**：

量级：4 亿条边、每轮 3.2 GB 访存，内存带宽 20 GB/s 决定单轮 0.16 s；85 轮约 14 秒。$d=0.85$ 意味着每次迭代有 15% 的概率「重置」，这个 15% 同时保证了唯一性和收敛速度——它把 $|{\lambda }_2|$ 的上界从 1 压到 $d$。

这个对应在哪里失效：PageRank 衡量「被链接」，不衡量「可信」。新页面没有入链，分数天然接近 $0.15/n$，冷启动问题无法靠调参解决；链接农场可以人为抬高分数，阻尼只让它变贵、不能让它失效。把它当成「论文质量」或「网页权威性」的度量，是把一个图上的随机游走结果过度解释了。

2. 定义

2.1 幂迭代

给定 $A\in {\mathbb{R}}^{n\times n}$ 和非零初始向量 ${\mathbf{x}}_0$，幂迭代（power iteration） 重复：

特征值的估计用 Rayleigh 商（Rayleigh quotient）：

对对称矩阵，这个估计收敛得比向量本身快一倍（§4.3）。

2.2 收敛条件

设 $A$ 可对角化，特征值按模排序 $|{\lambda }_1|>|{\lambda }_2|\ge |{\lambda }_3|\ge \cdots \ge |{\lambda }_n|$，并设 ${\mathbf{x}}_0$ 在 ${\mathbf{v}}_1$ 方向上的分量不为零（$c_1\ne 0$）。则 ${\mathbf{x}}_k$ 的方向收敛到 $\pm {\mathbf{v}}_1$，${\lambda }^{(k)}\to {\lambda }_1$。${\lambda }_1$ 称为主特征值（dominant eigenvalue），${\mathbf{v}}_1$ 称为主特征向量（dominant eigenvector）。

2.3 收敛速度

误差按几何级数下降：$\Vert {\mathbf{x}}_k-{\mathbf{v}}_1/\Vert {\mathbf{v}}_1\Vert \Vert =O(r^k)$，其中 $r=|{\lambda }_2/{\lambda }_1|$。达到精度 $\epsilon$ 所需步数约为 $k\approx \log \epsilon /\log r$。对对称矩阵，Rayleigh 商的误差是 $O(r^{2k})$，因为它是二阶量。

2.4 马尔可夫链与平稳分布

若 $P$ 的每列非负且和为 1（列随机矩阵（column-stochastic matrix）），则 $P$ 总有特征值 1，对应特征向量 $\mathbf{\pi }$ 满足 $P\mathbf{\pi }=\mathbf{\pi }$，${\pi }_i\ge 0$、${\sum }_i{\pi }_i=1$。这个 $\mathbf{\pi }$ 称为平稳分布（stationary distribution）。若 $P$ 不可约且非周期，则幂迭代从任意概率向量出发都收敛到 $\mathbf{\pi }$，收敛比是 $|{\lambda }_2(P)|$。

2.5 PageRank

把网页链接写成列随机矩阵 $P$：$P_{ij}$ 表示从网页 $j$ 跳到 $i$ 的概率。PageRank 用阻尼（damping）修正：

其中 $d\in [0,1)$ 是阻尼因子（常用 $0.85$），$n$ 是网页数。$G$ 的每一列仍是概率分布，且所有元素为正。PageRank 向量是 $G$ 的平稳分布，即 $\mathbf{\pi }=G\mathbf{\pi }=dP\mathbf{\pi }+\frac{1-d}{n}1$。

读法：以概率 $d$ 沿链接走，以概率 $1-d$ 随机跳到任意网页。第二项保证 $G$ 是正矩阵，从而平稳分布唯一、幂迭代必收敛。

3. 为什么这样定义

如果只为求一个特征向量，直接解 $(A-\lambda I)\mathbf{v}=0$ 也可以。但那个方法需要知道 $\lambda$，还需要分解或求逆，代价是 $O(n^3)$，而且矩阵一大就存不下。

幂迭代每次只做一次矩阵-向量乘法：稀疏矩阵的代价是 $O(\text{非零元个数})$，迭代几十次也远小于 $O(n^3)$。它牺牲的是「只给主特征向量」和「收敛速度依赖谱间隙」，换来的是可扩展性。

PageRank 的阻尼因子解决两个问题。其一是悬挂节点：某些网页没有出链，$P$ 的对应列为零，不满足列随机；阻尼项把概率重新分配。其二是唯一性与收敛：正矩阵由 Perron–Frobenius 定理保证有唯一正的主特征向量，且 $|{\lambda }_2(G)|\le d<1$，迭代一定收敛。$d$ 越大，越忠实于链接结构，但收敛越慢；$d$ 越小，越接近均匀分布，收敛越快。

3.1 反事实：转置一下，排序就反了

PageRank 的定义里，$P_{ij}$ 是「从 $j$ 跳到 $i$」的概率，每一列和为 1。若按直觉按行归一化（每行和为 1），你拿到的是 $P^{\top }$。取两节点图 1→2：

列随机时，平稳方程 $P\mathbf{\pi }=\mathbf{\pi }$ 给出 $\mathbf{\pi }=(0,1)$：被链接的 2 更重要，符合直觉。行随机时，右特征向量是 $(1,0)$：链接别人的 1 反而登顶，排序完全反了。同一个图，转置一下，结论就颠倒。

第二个反事实：去掉阻尼。取两页互链的 $P=\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]$，它列随机，特征值 $1$ 和 $-1$，$|{\lambda }_2|=|{\lambda }_1|$。从 $(1,0)$ 出发：$(1,0)\to (0,1)\to (1,0)\to \cdots$，永远振荡，没有极限。幂迭代不收敛不是数值没调好，是谱本身的问题；加 $d<1$ 把 $|{\lambda }_2|$ 压到 $d$ 以下，极限才存在。

4. 性质与推导

4.1 主方向为什么会出现

设 ${\mathbf{x}}_0={\sum }_i{c}_i{\mathbf{v}}_i$，则

括号里第二项随 $k$ 趋于零（因为 $|{\lambda }_i/{\lambda }_1|<1$）。除以 ${\lambda }_1^k$ 并把长度归一化，方向就趋于 ${\mathbf{v}}_1$。$c_1=0$ 时主方向没有「种子」，迭代会收敛到下一个非零分量对应的特征向量。

4.2 收敛比与迭代次数

每步副特征方向的相对权重乘 $|{\lambda }_2/{\lambda }_1|$。要把初始误差缩小到 $\epsilon$，需要 $|{\lambda }_2/{\lambda }_1{|}^k\le \epsilon$，取对数即得 §2.3 的公式。例：比值 $0.5$、$\epsilon =10^{-3}$，需 $k\approx \log (10^{-3})/\log (0.5)\approx 9.97$，约 10 步；比值 $0.99$ 时，$k\approx 687$ 步。同样的矩阵大小，收敛步数可以差两个数量级。

4.3 为什么 Rayleigh 商快一倍

对对称矩阵，设 ${\mathbf{x}}_k$ 与 ${\mathbf{v}}_1$ 的夹角误差为 ${\theta }_k=O(r^k)$，$r=|{\lambda }_2/{\lambda }_1|$。Rayleigh 商是特征值的加权平均：${\lambda }^{(k)}={\sum }_i{\lambda }_i{y}_i^2/{\sum }_i{y}_i^2={\lambda }_1-{\sum }_{i\ge 2}({\lambda }_1-{\lambda }_i)y_i^2/{\sum }_i{y}_i^2$。副方向权重 $y_i^2=O(r^{2k})$，所以 ${\lambda }^{(k)}-{\lambda }_1=O(r^{2k})$。误差平方级下降，这是对称矩阵的额外福利。

4.4 归一化的选择

用 2-范数归一化适合一般特征值问题；用 1-范数（各分量绝对值之和）适合概率向量，因为 ${\sum }_i{\pi }_i=1$ 本身就是 1-范数。归一化只改变长度，不改变方向，也不改变收敛比，但能防止上溢/下溢：若 $|{\lambda }_1|>1$，不归一化几十步就会溢出；若 $<1$，会下溢到零。

4.5 位移与其它特征值

想求最接近 $\sigma$ 的特征值，可以对 $(A-\sigma I{)}^{-1}$ 做幂迭代（位移反迭代（shifted inverse iteration））：$|{\lambda }_i-\sigma |$ 最小的特征值成为主特征值。想求第二个特征值，可以用收缩（deflation）：对称情形下先算出 ${\lambda }_1,{\mathbf{v}}_1$，再从 $A$ 中减去 ${\lambda }_1{\mathbf{v}}_1{\mathbf{v}}_1^{\top }$，对剩余矩阵继续幂迭代。

5. 例子

5.1 手算：$A=\left[\begin{array}{cc}2& 1\\ 1& 2\end{array}\right]$ 的幂迭代

取 ${\mathbf{x}}_0=(1,0)$。每步先乘 $A$，再除以 2-范数。Rayleigh 商用未归一化的 ${\mathbf{x}}_k^{\top }A{\mathbf{x}}_k/{\mathbf{x}}_k^{\top }{\mathbf{x}}_k$ 计算：

真实主特征值是 3、主方向 $(1,1)/\sqrt{2}$。误差 $3-{\lambda }^{(k)}$：$k=1$ 时 $0.2$，$k=2$ 时 $0.02439$，$k=3$ 时 $0.00274$，每步约缩小 9 倍——正是 $({\lambda }_2/{\lambda }_1{)}^2=(1/3{)}^2=1/9$。方向误差则每步缩小 3 倍。这与 §4.2、§4.3 的预测完全一致。

5.2 手算：三节点 PageRank

三个网页的链接：1 链到 2、3；2 链到 3；3 链到 1。按列归一化（$P_{ij}$ 为 $j\to i$ 的概率）：

取 $d=0.85$，则 $(1-d)/n=0.05$，平稳方程 $\mathbf{\pi }=0.85P\mathbf{\pi }+0.051$ 写成分量：

把 $b$ 代入 $c$：$c=0.0925+0.78625a$。再代入第一式：

解得 $a=0.128625/0.3316875\approx 0.3878$，于是 $b=0.05+0.425a\approx 0.2148$，$c=0.0925+0.78625a\approx 0.3974$。检查：和为 $1.0000$，且 $c>a>b$，网页 3 最重要——它被 1 和 2 同时链接。

从均匀分布 $(1/3,1/3,1/3)$ 开始迭代，前几步是

$P$ 的副特征值是 $-0.5\pm 0.5i$，模 $0.7071$；$G$ 的收敛比是 $d|{\lambda }_2(P)|=0.85\times 0.7071\approx 0.60$，所以大约十几步就稳定到四位小数。

5.3 场景闭环：5000 万节点、4 亿条边、14 秒

输入：$5\times 10^7$ 个节点，$4\times 10^8$ 条有向边。CSR 存邻接（每条边 4 B 列索引 + 4 B 权重 = 8 B）共 3.2 GB；秩向量 fp64 400 MB；单机 64 GB 内存。

计算：每轮做一次 $G\mathbf{x}=dP\mathbf{x}+\frac{1-d}{n}1$，即 $4\times 10^8$ 次乘加、3.2 GB 访存。20 GB/s 带宽下每轮 0.16 s；算力侧 $8\times 10^8$ FLOP 在 10 GFLOP/s 下只要 0.08 s——这是带宽瓶颈，不是算力瓶颈。

输出：收敛比的两个估计。保守上界 $r\le d=0.85$：85 轮、13.6 s；若实测 $|{\lambda }_2|\approx 0.6$：27 轮、4.3 s。同一个图、同一个算法，轮数差 3 倍——这就是 $r=|{\lambda }_2/{\lambda }_1|$ 的具体含义。

成本：全量重算一次 14 秒，按天算可以接受；改增量更新时，每次只传播受影响的分量，代价与跳数成正比而不是与边数成正比。

失败条件与兜底：

• 悬挂节点：出链为 0，列和不为 1，概率在迭代中「蒸发」，${\sum }_i{x}_i$ 一路下降。兜底：把悬挂节点的概率按 $1/n$ 均分，并逐轮检查 ${\sum }_i{x}_i$。
• 链接农场：1000 个页面互链，能把目标顶进前 500。兜底：阻尼只让它变贵、不能让它失效；工程上还要加信任种子、人工审核与周期重算。
• 用固定轮数代替残差：85 轮是上界，不是保证。兜底：逐轮监控 $\Vert {\mathbf{x}}_{k+1}-{\mathbf{x}}_k{\Vert }_1$，低于 $10^{-6}$ 就停，不写死轮数。

6. 常见误区

1. 误区：幂迭代能求出全部特征值。纠正：它只给模最大的那一个（及其特征向量）；其它特征值要靠位移、收缩或 QR 迭代。
2. 误区：任意初始向量都能收敛到主特征向量。纠正：若 ${\mathbf{x}}_0$ 恰好与 ${\mathbf{v}}_1$ 正交（$c_1=0$），主方向没有被激发，迭代会收敛到次主方向；数值误差最终会引入一点 ${\mathbf{v}}_1$，但可能极慢。
3. 误区：收敛步数只取决于矩阵大小。纠正：取决于比值 $|{\lambda }_2/{\lambda }_1|$，与 $n$ 无直接关系；一个 $10^6$ 阶但谱间隙大的矩阵可能比 $100$ 阶但比值接近 1 的矩阵收敛得快。
4. 误区：特征值估计和特征向量同速收敛。纠正：对称矩阵的 Rayleigh 商误差是向量误差的平方，收敛快一倍；非对称矩阵没有这个保证。
5. 误区：PageRank 的阻尼因子只是为了处理没有出链的网页。纠正：阻尼还保证 $G$ 为正矩阵，从而平稳分布唯一、幂迭代收敛；悬挂节点只是它顺带解决的一个问题。

7. 概念网络

• 前置：6.1 特征值与特征向量 —— 幂迭代就是反复利用 $A\mathbf{v}=\lambda \mathbf{v}$。
• 前置：6.3 对角化 —— ${\mathbf{x}}_0$ 按特征基展开，才能看出各分量的 ${\lambda }_i^k$ 竞争。
• 关联：6.4 对称矩阵与谱定理 —— Rayleigh 商的极值性质与正交主轴，保证了对称情形的快速收敛。
• 后续：6.7 Jordan 标准形 —— 若矩阵亏损，幂迭代的收敛会出现多项式因子。
• 关联：9.5 马尔可夫链与稳态分布 —— PageRank 是马尔可夫链的一个应用。

8. 通往大模型：谱范数、检索排序与混合速度

出现位置：估计权重矩阵的谱范数时，对 $W^{\top }W$（形状 $[d,d]$，$d$ 可为 4096）做幂迭代，${\sigma }_1=\sqrt{{\lambda }_{\max }(W^{\top }W)}$ 就是谱范数；谱归一化（spectral normalization）每步用一次幂迭代把 ${\sigma }_1$ 归一化。检索系统中的文档链接图、引用图、推荐图，其稳态排序也可以用同样的迭代求。

为什么需要：谱范数是 Lipschitz 常数的上界，直接决定对抗扰动能把输出放大多少；精确 SVD 太贵，幂迭代只需几次矩阵-向量乘法就能把 ${\sigma }_1$ 估到可用精度。PageRank 类稳态则把「谁被重要节点指向」变成线性代数问题，阻尼因子控制随机跳转的比例，也控制收敛速度——$d$ 越大越忠实于图结构，但收敛越慢。

可检验结论：若 $|{\lambda }_2/{\lambda }_1|=0.9$，迭代 10 步后副方向只剩 $0.9^{10}\approx 0.349$；若比值为 $0.5$，10 步后只剩 $0.5^{10}\approx 0.001$。所以谱间隙小的矩阵（例如接近秩 1 的注意力矩阵、强社区结构的图）需要更多步或预条件。用 np.linalg.norm(W, 2) 与幂迭代结果对照，可以验证估计是否收敛。

这里的 $\sigma$ 不是 $\lambda$：幂迭代求 ${\sigma }_1=\sqrt{{\lambda }_{\max }(W^{\top }W)}$，得到的是奇异值，不是 $W$ 的特征值。非对称时两者可以差到离谱：$W=\left[\begin{array}{cc}0& 100\\ 0& 0\end{array}\right]$ 的特征值全是 0，谱范数却是 100。用 eigvals(W) 去估 Lipschitz 常数会得到 0，把一个放大 100 倍的层当成恒等映射。

算错时下游看到什么：谱归一化里 ${\sigma }_1$ 估小，实际 Lipschitz 常数超预算，判别器训练发散、梯度爆掉；估大，每层输出被过度压缩，生成器塌缩成少数几种模式。检索侧若把行随机当列随机，排行榜整体反转——用户看到的「最权威」其实是「最爱引用别人」的页面。

9. 练习

1. 概念：为什么幂迭代每步都要归一化？如果 ${\lambda }_1<0$，归一化后的向量序列会怎样？
2. 计算：对 $A=\left[\begin{array}{cc}3& 1\\ 1& 3\end{array}\right]$，从 ${\mathbf{x}}_0=(1,0)$ 出发做两步幂迭代，计算每步的 Rayleigh 商，并与真实主特征值比较。
3. 计算：对 §5.2 的三节点图取 $d=0.5$，写出平稳方程并解出 $\mathbf{\pi }$（用分数表示）。
4. 开放：PageRank 的阻尼因子 $d$ 取 $0.85$ 而不是 $1$，对排序结果和收敛速度各有什么影响？如果图中有大量悬挂节点，会发生什么？

10. 一页速记

• 幂迭代：$\mathbf{y}=A\mathbf{x}$，再归一化；主特征方向按 $|{\lambda }_2/{\lambda }_1{|}^k$ 浮现。
• 物理意义 / 现实对应：主特征向量 = 平稳分布／长期停留比例；特征值 1 = 概率守恒；$|{\lambda }_2|$ = 混合速度；阻尼 $d$ = 用随机跳转换唯一性与收敛。
• 迭代步数 $k\approx \log \epsilon /\log (|{\lambda }_2/{\lambda }_1|)$；比值越接近 1 越慢。
• Rayleigh 商 $\lambda ={\mathbf{x}}^{\top }A\mathbf{x}/{\mathbf{x}}^{\top }\mathbf{x}$；对称矩阵误差按平方比收敛。
• 列随机矩阵有特征值 1，对应平稳分布；PageRank 的 $G=dP+(1-d)11^{\top }/n$ 保证唯一收敛。
• 阻尼 $d$ 在「忠实链接结构」与「收敛速度」之间权衡。

11. 参考文献与致谢

这一页的知识不是凭空来的。下面列出本页直接借用的原始工作与权威整理；正文中的人名、定理名已链接到对应条目。链接优先指向 DOI、arXiv 或可长期访问的原文存档。

• 冯·米泽斯（Richard von Mises, 1929）：Praktische Verfahren der Gleichungsauflösung。给出幂迭代（反复乘矩阵并归一化）求主特征值与主特征向量的实用算法，本页 §2.1 的迭代格式即源于此。ZAMM
• 佩龙（Oskar Perron, 1907）：Zur Theorie der Matrices。证明正矩阵有唯一正的主特征向量（Perron 定理），PageRank 的阻尼矩阵 $G>0$ 因此保证平稳分布唯一、幂迭代收敛。Math. Ann.
• Brin 与 Page（1998）：The anatomy of a large-scale hypertextual Web search engine。公开描述 PageRank：用链接矩阵的主特征向量给网页排序，本页 §2.5 的阻尼修正式与三节点例子都对应这套构造。Computer Networks
• Golub 与 Van Loan（2013）：Matrix Computations（4th ed.）。第 7–8 章给出幂迭代、位移反迭代与收缩的收敛分析，本页 §2.3 与 §4.5 的误差估计以它为参照。JHU Press

下一篇 → 6.7 Jordan 标准形与矩阵函数

源文件：06-特征值/06-幂迭代与PageRank.md