幂迭代

通过反复相乘找到主方向

对 $1000\times1000$ 的矩阵解特征多项式是不现实的，而且常常只需要最大的特征对，例如第一主成分。幂迭代只用矩阵乘向量就能找到它。从任意向量 $\mathbf x_0$ 出发，重复 $\mathbf x_{k+1}=A\mathbf x_k/\lVert A\mathbf x_k\rVert$ 。每次相乘，主特征向量方向上的分量都比其他分量被拉伸得更多，所以步数足够多之后，向量就指向该方向。

\mathbf x_{k+1}=\frac{A\mathbf x_k}{\lVert A\mathbf x_k\rVert},\qquad \lambda\approx\frac{\mathbf x_k^{T}A\mathbf x_k}{\mathbf x_k^{T}\mathbf x_k},\qquad e_k\propto\Big|\frac{\lambda_2}{\lambda_1}\Big|^{k}

(1)

把 $\mathbf x_0=c_1\mathbf v_1+c_2\mathbf v_2+\cdots$ 按特征向量展开。迭代 $k$ 步后，各系数被乘以 $\lambda_i^k$ ，所以第二项与第一项之比为 $(\lambda_2/\lambda_1)^k$ 。当 $|\lambda_1|>|\lambda_2|$ 且初始向量在 $\mathbf v_1$ 方向上有分量时方法收敛，速度由 $|\lambda_2/\lambda_1|$ 决定：特征值越接近，收敛越慢。归一化只是防止数值溢出，重要的是方向。特征值的估计用瑞利商。要求下一个特征对，就从对称矩阵 $A$ 中减去 $\lambda_1\mathbf v_1\mathbf v_1^{T}$ 再重复，这叫降阶（deflation）。

手算几步取

A=\begin{pmatrix}2&1\\1&2\end{pmatrix}

，特征值为 3 和 1，主特征向量为

(1,1)

。从

\mathbf x_0=(1,0)

出发，得

A\mathbf x_0=(2,1)

，

(2,1)

的瑞利商是

\frac{(2,1)\cdot(5,4)}{5}=\frac{14}{5}=2.8

，已经接近 3。下一次乘积

A(2,1)=(5,4)

几乎沿

(1,1)

方向。误差每步缩小为原来的

|\lambda_2/\lambda_1|=1/3

，要缩小

10^{-6}

倍，需要满足

3^k\ge10^6

的

k

，即

k=13

。

更新：乘以 $A$ 、除以范数，重复；每步成本是一次矩阵向量乘法。
速度：误差按 $|\lambda_2/\lambda_1|^k$ 下降，最大的几个特征值越接近收敛越慢。
条件：存在间隔 $|\lambda_1|>|\lambda_2|$ ，且初始向量与 $\mathbf v_1$ 不正交。

同样的想法用于网页排名幂迭代是 PageRank 背后的方法，当协方差矩阵巨大或从不显式构造（只能做乘积

A\mathbf x

）时，也用它廉价地计算成千上万个资产的第一主成分。库中完整分解的例程约需

n^3

次运算，而稠密矩阵上每一步幂迭代只需

n^2

。

实验：评分内容

收敛到什么15 分
瑞利商20 分
收敛比10 分
迭代多少次15 分
算法的顺序15 分
何时变慢或失败15 分
为什么要归一化10 分

通过反复相乘找到主方向

\mathbf x_{k+1}=\frac{A\mathbf x_k}{\lVert A\mathbf x_k\rVert},\qquad \lambda\approx\frac{\mathbf x_k^{T}A\mathbf x_k}{\mathbf x_k^{T}\mathbf x_k},\qquad e_k\propto\Big|\frac{\lambda_2}{\lambda_1}\Big|^{k}

(1)

手算几步取

A=\begin{pmatrix}2&1\\1&2\end{pmatrix}

，特征值为 3 和 1，主特征向量为

(1,1)

。从

\mathbf x_0=(1,0)

出发，得

A\mathbf x_0=(2,1)

，

(2,1)

的瑞利商是

\frac{(2,1)\cdot(5,4)}{5}=\frac{14}{5}=2.8

，已经接近 3。下一次乘积

A(2,1)=(5,4)

几乎沿

(1,1)

方向。误差每步缩小为原来的

|\lambda_2/\lambda_1|=1/3

，要缩小

10^{-6}

倍，需要满足

3^k\ge10^6

的

k

，即

k=13

。

更新：乘以 $A$ 、除以范数，重复；每步成本是一次矩阵向量乘法。
速度：误差按 $|\lambda_2/\lambda_1|^k$ 下降，最大的几个特征值越接近收敛越慢。
条件：存在间隔 $|\lambda_1|>|\lambda_2|$ ，且初始向量与 $\mathbf v_1$ 不正交。

同样的想法用于网页排名幂迭代是 PageRank 背后的方法，当协方差矩阵巨大或从不显式构造（只能做乘积

A\mathbf x

）时，也用它廉价地计算成千上万个资产的第一主成分。库中完整分解的例程约需

n^3

次运算，而稠密矩阵上每一步幂迭代只需

n^2

。

实验：评分内容

收敛到什么15 分
瑞利商20 分
收敛比10 分
迭代多少次15 分
算法的顺序15 分
何时变慢或失败15 分
为什么要归一化10 分

通过反复相乘找到主方向

实验：评分内容

登录后即可运行你的代码。

幂迭代

通过反复相乘找到主方向

实验：评分内容

登录后即可运行你的代码。