Sherman-Morrison-Woodbury-Formel

Die Sherman-Morrison-Woodbury-Formel (nach Jack Sherman, Winifred J. Morrison und Max A. Woodbury) der linearen Algebra gibt eine explizite Darstellung der Inversen einer regulären Matrix $A$ nach einer Änderung $-U{V}^T$ von niederem Rang. Dies ist beispielsweise bei Quasi-Newton-Verfahren und beim Basiswechsel im Simplex-Verfahren interessant.

In numerischen Verfahren kann die Verwendung der Formel zu Stabilitätsproblemen führen, weswegen Alternativen zu bevorzugen sind.

Änderung vom Rang 1

Mit zwei Vektoren $u,v\in {ℝ}^n$ ist das Produkt $u{v}^T$ eine $n\times n$-Matrix und besitzt den Rang 1.

Für $v^{T}u=1$ gilt

$(E-u{v}^T{)}^{-1}=E+\frac{u{v}^T}{1-v^{T}u},$

wobei mit $E$ die Einheitsmatrix gemeint ist. Die Aussage prüft man elementar nach.

Die Formel überträgt sich direkt auf Rang-1-Änderungen einer beliebigen, regulären $n\times n$-Matrix $A$:

Für $v^T{A}^{-1}u=1$ gilt

$(A-u{v}^T{)}^{-1}=A^{-1}+\frac{A^{-1}u{v}^T{A}^{-1}}{1-v^T{A}^{-1}u}.$

Dabei ergibt sich, dass die Matrix $A-u{v}^T$ genau dann invertierbar ist, wenn der Nenner in obiger Formel nicht verschwindet.

Änderung vom Rang k

Für zwei $n\times k$-Matrizen $U,V$ verallgemeinert sich die Formel nach der Woodbury-Matrix-Identität in folgender Weise:

Die $k\times k$-Matrix $E-V^T{A}^{-1}U$ sei regulär, dann gilt

$(A-U{V}^T{)}^{-1}=A^{-1}+A^{-1}U(E-V^T{A}^{-1}U{)}^{-1}{V}^T{A}^{-1}.$

Literatur

• Gene H. Golub, Charles F. van Loan: Matrix Computations, Johns Hopkins Univ. Press, Baltimore, 1996.