[行列解析0.7.4]シャーマン・モリソン・ウッドベリー(Sherman–Morrison–Woodbury)の公式

0.7.4 シャーマン・モリソン・ウッドベリー(Sherman–Morrison–Woodbury)の公式

可逆行列 \(A \in M_n(F)\) があり、その逆行列 \(A^{-1}\) が既知であるとします。ここで、

B = A + XRY

と定義し、\(X\) は \(n \times r\)、\(Y\) は \(r \times n\)、\(R\) は可逆な \(r \times r\) 行列とします。

\(B\) および \(R^{-1} + Y A^{-1} X\) が可逆であれば：

(0.7.4.1)

B^{-1} = A^{-1} - A^{-1} X (R^{-1} + Y A^{-1} X)^{-1} Y A^{-1}

実際\(BB^{-1}\)を計算すると単位行列になる。

\begin{align} BB^{-1} &= (A+XRY)(A^{-1} - A^{-1} X \{R^{-1} + Y A^{-1} X\}^{-1} Y A^{-1}) \notag \\ &=I -X\{R^{-1} + Y A^{-1} X\}^{-1} Y A^{-1} + XRYA^{-1} -XRYA^{-1} X \{R^{-1} +Y A^{-1} X\}^{-1} Y A^{-1} \notag \\ &=I + XRYA^{-1} -XRR^{-1}\{R^{-1} + Y A^{-1} X\}^{-1} Y A^{-1} -XRYA^{-1} X \{R^{-1} +Y A^{-1} X\}^{-1} Y A^{-1} \notag \\ &=I + XRYA^{-1} -XR\{R^{-1}+YA^{-1} X\} \{R^{-1} +Y A^{-1} X\}^{-1} Y A^{-1} \notag \\ &=I + XRYA^{-1} -XRY A^{-1} \notag \\ &=I \notag \end{align}

\(r \ll n\) の場合、この公式は実用的で、\(B\) を直接反転するより効率的です。

特に、\(x, y \in F^n\) が非零ベクトルで、\(X = x\)、\(Y = y^T\)、\(R = [1]\)、\(y^T A^{-1} x \neq -1\) とすると：

(0.7.4.2)

(A + x y^T)^{-1} = A^{-1} - \frac{1}{1 + y^T A^{-1} x} A^{-1} x y^T A^{-1}

特に、\(B = I + x y^T\)、\(y^T x \neq -1\) のとき：

B^{-1} = I - \frac{1}{1 + y^T x} x y^T