分块矩阵的Sherman-Morrison-Woodbury公式求逆算法

题目描述
Sherman-Morrison-Woodbury公式（简称SMW公式）是线性代数中一个重要的矩阵求逆引理，用于计算低秩更新后矩阵的逆。具体来说，若已知一个n×n可逆矩阵A的逆矩阵A⁻¹，现对A进行低秩修正得到新矩阵B = A + UCV，其中U是n×k矩阵，C是k×k可逆矩阵，V是k×n矩阵（通常k << n），SMW公式提供了一种高效计算B⁻¹的方法，而无需直接对B进行求逆运算。

解题过程

1. 问题分析

   • 直接对修正后的矩阵B = A + UCV进行求逆，时间复杂度为O(n³)，当n很大时计算成本高昂。
   • 由于修正项UCV的秩最多为k（通常k远小于n），SMW公式利用已知的A⁻¹，通过处理小规模的k×k矩阵来快速得到B⁻¹。
   • 核心思想是将大规模逆矩阵计算转化为小规模矩阵的求逆问题。

2. 公式推导

   • 从恒等式出发：B = A + UCV = A(I + A⁻¹UCV)
   • 若(I + A⁻¹UCV)可逆，则B⁻¹ = (I + A⁻¹UCV)⁻¹A⁻¹
   • 应用Woodbury公式（SMW的推广形式）：
     (A + UCV)⁻¹ = A⁻¹ - A⁻¹U(C⁻¹ + VA⁻¹U)⁻¹VA⁻¹
   • 验证：计算B * B⁻¹，展开后应等于单位矩阵I。

3. 计算步骤
   a. 输入：已知A⁻¹（n×n矩阵），以及修正矩阵U（n×k）、C（k×k）、V（k×n）
   b. 步骤1：计算中间矩阵W = VA⁻¹U（k×k矩阵）
   c. 步骤2：计算小矩阵M = C⁻¹ + W（k×k矩阵），并求逆M⁻¹
   d. 步骤3：计算修正项A⁻¹U M⁻¹ VA⁻¹（三个矩阵乘积，注意顺序）
   e. 步骤4：得到结果B⁻¹ = A⁻¹ - A⁻¹U M⁻¹ VA⁻¹

4. 复杂度分析

   • 直接求逆B：O(n³)
   • SMW公式：
     • 矩阵乘法VA⁻¹U：O(k²n + kn²)（利用A⁻¹的现有结构可优化）
     • k×k矩阵求逆：O(k³)
     • 矩阵加减与乘法：O(kn²)
   • 当k << n时，总复杂度近似为O(kn²)，远低于O(n³)

5. 应用示例

   • 场景：若A是单位矩阵I，修正项为秩1矩阵uvᵀ（即U=u, C=1, V=vᵀ），则SMW退化为Sherman-Morrison公式：
     (I + uvᵀ)⁻¹ = I - (uvᵀ)/(1 + vᵀu)
   • 数值稳定性：当C⁻¹ + VA⁻¹U条件数较大时，需采用数值稳定的求解方法（如SVD）。

关键点

• SMW公式的核心优势是将大规模求逆问题降维到低秩k对应的k×k矩阵求逆。
• 适用于动态更新场景（如协方差矩阵更新、机器学习中的在线学习）。