分块矩阵的Sherman-Morrison公式在低秩更新求逆中的应用 题目描述 ： 假设已有一个 \( n \times n \) 可逆矩阵 \( A \) 的逆矩阵 \( A^{-1} \)，现对 \( A \) 进行低秩更新（Low-rank Update），得到新矩阵 \( B = A + UV^T \)，其中 \( U \) 和 \( V \) 是 \( n \times k \) 矩阵（通常 \( k \ll n \)）。要求高效计算更新后矩阵的逆 \( B^{-1} \)，而无需直接对 \( B \) 重新求逆（因为直接求逆的复杂度为 \( O(n^3) \)，而低秩更新时希望复杂度降至 \( O(n^2k) \)）。 解题过程 ： 1. 问题分析 直接求 \( B^{-1} \) 的代价过高，尤其是当 \( n \) 很大时。 低秩更新 \( UV^T \) 的秩为 \( k \)，可利用 Sherman-Morrison-Woodbury公式 （本题中 \( k=1 \) 时为Sherman-Morrison公式）将求逆问题转化为求解小规模矩阵的逆。 2. Sherman-Morrison-Woodbury公式推导 公式形式为： \[ (A + UV^T)^{-1} = A^{-1} - A^{-1}U(I_ k + V^TA^{-1}U)^{-1}V^TA^{-1}. \] 推导思路： 假设 \( B^{-1} \) 可表示为 \( A^{-1} + Z \)，通过强制 \( B B^{-1} = I \) 解出 \( Z \)。 验证步骤： 令 \( M = I_ k + V^TA^{-1}U \)，计算 \[ B \cdot \left[ A^{-1} - A^{-1}U M^{-1} V^T A^{-1} \right ] = I + UV^TA^{-1} - (U + UV^TA^{-1}U) M^{-1} V^T A^{-1}. \] 注意到 \( U + UV^TA^{-1}U = U(I_ k + V^TA^{-1}U) = UM \)，代入上式得： \[ I + UV^TA^{-1} - UM M^{-1} V^T A^{-1} = I + UV^TA^{-1} - UV^TA^{-1} = I. \] 公式得证。 3. 计算步骤 已知 \( A^{-1} \)，计算 \( B^{-1} \) 的流程如下： 计算中间矩阵 \( P = A^{-1}U \) （复杂度 \( O(n^2k) \)）。 计算 \( Q = V^T P \) （复杂度 \( O(nk^2) \)），得到 \( k \times k \) 矩阵 \( Q \)。 计算 \( M = I_ k + Q \) （复杂度 \( O(k^2) \)）。 求小矩阵 \( M \) 的逆 \( M^{-1} \) （复杂度 \( O(k^3) \)）。 计算 \( R = P M^{-1} \) （复杂度 \( O(nk^2) \)）。 计算 \( S = R V^T A^{-1} \) （复杂度 \( O(n^2k) \)）。 得到 \( B^{-1} = A^{-1} - S \) （复杂度 \( O(n^2) \)）。 总复杂度以 \( O(n^2k) \) 为主，远优于 \( O(n^3) \)。 4. 关键细节 稳定性条件 ：需保证 \( M \) 可逆，即 \( I_ k + V^TA^{-1}U \) 非奇异。 特殊情形 ：当 \( k=1 \) 时，\( U, V \) 退化为向量 \( u, v \)，公式简化为： \[ (A + uv^T)^{-1} = A^{-1} - \frac{A^{-1}uv^TA^{-1}}{1 + v^TA^{-1}u}. \] 分母为标量，计算更简单。 5. 应用场景 动态更新协方差矩阵的逆（如卡尔曼滤波）。 机器学习中在线学习模型的参数更新。 网络分析中矩阵的局部修改。 通过以上步骤，可高效利用原矩阵的逆和低秩更新结构，避免直接求逆的高计算成本。