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 $-UV^{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 \mathbb {R} ^{n}$ ist das Produkt $uv^{T}\!\,$ eine $n\times n$-Matrix und besitzt den Rang 1.

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

$(E-uv^{T})^{-1}=E+{\frac {uv^{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\not =1$ gilt

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

Dabei ergibt sich, dass die Matrix $A-uv^{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-UV^{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.