这里 $ I \in \mathbb{R}^{k \times k} $ 是单位矩阵。

分块矩阵的Sherman-Morrison公式在低秩更新求逆中的应用 题目描述 考虑一个已知可逆矩阵 \( A \in \mathbb{R}^{n \times n} \) 的逆矩阵 \( A^{-1} \)，现对 \( A \) 进行低秩更新，得到新矩阵 \( B = A + UV^T \)，其中 \( U, V \in \mathbb{R}^{n \times k} \)（通常 \( k \ll n \)）。Sherman-Morrison公式提供了一种高效计算 \( B^{-1} \) 的方法，避免直接对 \( B \) 求逆，而是利用 \( A^{-1} \) 和低秩矩阵 \( U, V \) 进行组合。该公式在动态系统、最小二乘更新和机器学习中广泛应用。 解题过程 问题分析 直接求 \( B^{-1} \) 的时间复杂度为 \( O(n^3) \)，而利用Sherman-Morrison公式可将计算量降至 \( O(n^2 k + k^3) \)。 核心思想：将 \( B^{-1} \) 表示为 \( A^{-1} \) 与一个低秩修正项的组合。 公式推导 从恒等式出发： \[ B = A + UV^T = A(I + A^{-1}UV^T) \] 若 \( I + A^{-1}UV^T \) 可逆，则： \[ B^{-1} = (I + A^{-1}UV^T)^{-1}A^{-1} \] 应用Woodbury矩阵恒等式（Sherman-Morrison公式的推广）： \[ B^{-1} = A^{-1} - A^{-1}U(I + V^TA^{-1}U)^{-1}V^TA^{-1} \] 这里 \( I \in \mathbb{R}^{k \times k} \) 是单位矩阵。 计算步骤 步骤1：预计算 \( A^{-1} \) 假设 \( A^{-1} \) 已知（例如通过LU分解预先计算）。 步骤2：计算中间矩阵 \( M = V^T A^{-1} U \) 先计算 \( A^{-1}U \)（复杂度 \( O(n^2 k) \)），再左乘 \( V^T \)（复杂度 \( O(n k^2) \)），得到 \( M \in \mathbb{R}^{k \times k} \)。 步骤3：求 \( (I + M)^{-1} \) 对 \( k \times k \) 矩阵 \( I + M \) 求逆（复杂度 \( O(k^3) \)）。 步骤4：组合结果 计算 \( A^{-1}U(I + M)^{-1} \)（复杂度 \( O(n k^2) \)），再右乘 \( V^T A^{-1} \)（复杂度 \( O(n^2 k) \)），最后从 \( A^{-1} \) 中减去该结果。 算法总结 输入：\( A^{-1}, U, V \) 输出：\( B^{-1} \) 过程： 计算 \( M = V^T A^{-1} U \) 求解 \( N = (I + M)^{-1} \) 计算 \( B^{-1} = A^{-1} - (A^{-1}U) N (V^T A^{-1}) \) 应用场景 动态数据拟合：当数据矩阵增加新样本时，快速更新回归系数。 网络分析：修正邻接矩阵后快速计算中心性指标。 关键点 当 \( k \ll n \) 时，该公式显著减少计算量。 若 \( I + M \) 接近奇异，需数值稳定性处理（如正则化）。