Sherman-Morrison-Woodbury-Formel

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

In numerischen Verfahren k​ann die Verwendung d​er Formel z​u Stabilitätsproblemen führen, weswegen Alternativen z​u bevorzugen sind.

Änderung vom Rang 1

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

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

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

wobei mit ${\displaystyle 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 ${\displaystyle n\times n}$-Matrix ${\displaystyle A\!\,}$:

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

${\displaystyle (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 ${\displaystyle A-uv^{T}\!\,}$ genau dann invertierbar ist, wenn der Nenner in obiger Formel nicht verschwindet.

Änderung vom Rang k

Für zwei ${\displaystyle n\times k}$-Matrizen ${\displaystyle U,V\!\,}$ verallgemeinert sich die Formel in folgender Weise:

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

${\displaystyle (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.

Einzelnachweise

1. Jack Sherman, Winifred J. Morrison: 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, Winifred J. Morrison: 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. In: Statistical Research Group (Hrsg.): Memorandum Report 42. Princeton University, Princeton, NJ 1950.
4. Max A. Woodbury: The Stability of Out-Input Matrices. Chicago 1949.
5. William W. Hager: Updating the inverse of a matrix. In: SIAM Review. 31, Nr. 2, 1989, S. 221–239. doi:10.1137/1031049.