47、特征值、特征向量计算与图最短路径算法解析

特征值、特征向量计算与图最短路径算法解析

1. 特征值与特征向量计算

1.1 幂法复杂度

一般情况下，幂法的收敛条件 (n_{\epsilon}) 主要取决于矩阵 (A) 的谱性质，即 (|\lambda_2 / \lambda_1|) 的比值，而与矩阵 (A) 的阶数 (N) 无关。因此，幂法的时间复杂度与矩阵 (A) 的非零元素数量呈线性关系。

1.2 计算第二大特征值

在大多数情况下，条件 (\alpha_1 \neq 0) 是满足的，因为任意向量 (x_0) 几乎不可能不包含第一个特征向量的分量。然而，如果 (\alpha_1 = 0) 且 (|\lambda_2| > |\lambda_3|)，可以使用上述方法来计算第二大特征值及其对应的特征向量。此时，Rayleigh 商在 (n \to \infty) 时会收敛到第二特征值，即：
(\sigma_n \to \lambda_2)
(y_n \to u_2)

但直接实现此方法并不行，由于舍入误差，(x_n) 中第一个特征向量的贡献永远不会为零，最终会主导其他项。不过，可以通过定期（如每次迭代或每隔几次迭代）从 (x_n) 中减去第一个特征向量的贡献来应用该技术。对于对称矩阵 (A)，考虑以下向量序列：
(y_n = \frac{x_n}{||x_n||})
(z_n = y_n - u_1^T y_n u_1)
(x_{n + 1} = A z_n)
并像往常一样在 (x_n) 上计算 Rayleigh 系数。

另一种更稳健的选择是对矩阵 (B) 应用幂法：
(B = A - \lambda_