分块矩阵的Sherman-Morrison-Woodbury公式求逆算法
题目描述
Sherman-Morrison-Woodbury（SMW）公式用于高效计算分块矩阵的逆。设 \(A\) 为 \(n \times n\) 可逆矩阵，\(U\) 为 \(n \times k\) 矩阵，\(V\) 为 \(k \times n\) 矩阵，\(C\) 为 \(k \times k\) 可逆矩阵。SMW公式解决了如何快速计算形如 \((A + UCV)^{-1}\) 的逆矩阵，而无需直接对大规模矩阵 \(A + UCV\) 求逆。该公式在秩修正矩阵求逆、动态系统更新等场景中有重要应用。
解题过程
-
问题分析
- 直接求 \((A + UCV)^{-1}\) 的复杂度为 \(O(n^3)\)，当 \(n\) 很大时计算昂贵。
- 若 \(k \ll n\)，且已知 \(A^{-1}\)，SMW公式可将计算复杂度降至 \(O(k^2n + k^3)\)，显著提升效率。
- 核心思想是将低秩修正项 \(UCV\) 的逆通过中间的小矩阵 \(C\) 表达。
-
公式推导
- 设 \(M = A + UCV\)，目标求 \(M^{-1}\)。
- 利用恒等式：
\[ M^{-1} = A^{-1} - A^{-1}U(C^{-1} + VA^{-1}U)^{-1}VA^{-1} \]
- 推导步骤：
a. 验证 \(M \cdot M^{-1} = I\)：
\[ \begin{aligned} M \cdot M^{-1} &= (A + UCV)\left[A^{-1} - A^{-1}U(C^{-1} + VA^{-1}U)^{-1}VA^{-1}\right] \\ &= I + UCV A^{-1} - U(C^{-1} + VA^{-1}U)^{-1}VA^{-1} - UCV A^{-1}U(C^{-1} + VA^{-1}U)^{-1}VA^{-1} \end{aligned} \]
b. 合并后两项，提出公因子 $ U $：
\[ U\left[CV A^{-1} - (C^{-1} + VA^{-1}U)^{-1}VA^{-1} - CV A^{-1}U(C^{-1} + VA^{-1}U)^{-1}VA^{-1}\right] \]
c. 利用矩阵求逆引理：$ (C^{-1} + VA^{-1}U)^{-1} = C - C(VA^{-1}U + C^{-1})^{-1}VA^{-1}UC $，代入后可验证结果为 $ I $。
-
计算步骤
- 输入：\(A^{-1}\), \(U\), \(V\), \(C^{-1}\)。
- 步骤：
a. 计算 \(VA^{-1}\)（复杂度 \(O(kn^2)\)，若 \(A^{-1}\) 已知可优化为 \(O(kn)\)）。
b. 计算小矩阵 \(D = C^{-1} + VA^{-1}U\)（\(k \times k\) 矩阵，复杂度 \(O(k^2n)\)）。
c. 求 \(D^{-1}\)（复杂度 \(O(k^3)\)）。
d. 计算 \(M^{-1} = A^{-1} - (A^{-1}U) D^{-1} (VA^{-1})\)（矩阵乘法复杂度 \(O(k^2n)\)）。 - 总复杂度：\(O(k^2n + k^3)\)，远低于直接求逆的 \(O(n^3)\)。
-
应用示例
- 设 \(A = I_n\), \(U = V^T = [1, 0, ..., 0]^T\), \(C = [1]\)，则 \(M\) 为第一个对角线元素加1的单位矩阵。
- 直接计算：\(M^{-1}\) 为第一个对角线元素为 \(1/2\) 的单位矩阵。
- SMW公式：
\[ M^{-1} = I_n - \frac{[1,0,...,0]^T [1,0,...,0]}{1 + 1} = I_n - \frac{1}{2} \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix} \]
结果一致。
- 注意事项
- 需确保 \(A\) 和 \(C^{-1} + VA^{-1}U\) 可逆。
- 若 \(k\) 接近 \(n\)，SMW公式可能无优势。
- 数值稳定性问题：当 \(A\) 条件数大时，需谨慎使用。