Sherman-Morrison-Woodbury-Formel

Die Sherman-Morrison-Woodbury-Formel ^{[1][2][3][4][5]} gibt eine explizite Darstellung der Inversen einer regulären Matrix nach einer Änderung 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.

Rang-1-Änderung

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

Für $v^Tu\not=1$ gilt

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

Dies 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^TA^{-1}u\not=1$ gilt

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

Dabei ergibt sich, dass die Matrix (A − uv^T) ^{− 1} 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 in folgender Weise.

Es sei die $k\times k$-Matrix $I-V^T A^{-1}\!\,U$ regulär, dann gilt

$(A-UV^T)^{-1}\!\,=A^{-1}+A^{-1}U(I-V^TA^{-1}U)^{-1}V^T A^{-1}.$

Literatur

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

1. ↑ Jack Sherman: Adjustment of an Inverse Matrix Corresponding to Changes in the Elements of a Given Column or a Given Row of the Original Matrix (abstract). In: Annals of Mathematical Statistics. 20, 1949, S. 621. doi:10.1214/aoms/1177729959.
2. ↑ Jack Sherman: Adjustment of an Inverse Matrix Corresponding to a Change in One Element of a Given Matrix. In: Annals of Mathematical Statistics. 21, Nr. 1, 1950, S. 124–127. doi:10.1214/aoms/1177729893.
3. ↑ Max A. Woodbury, Inverting modified matrices, Memorandum Rept. 42, Statistical Research Group, Princeton University, Princeton, NJ, 1950, 4pp
4. ↑ Max A. Woodbury, The Stability of Out-Input Matrices. Chicago, Ill., 1949. 5 pp.
5. ↑ William W. Hager: Updating the inverse of a matrix. In: SIAM Review. 31, Nr. 2, 1989, S. 221–239. doi:10.1137/1031049.