Sherman-Morrison-Woodbury-Formel

Die Sherman-Morrison-Woodbury-Formel (nach Jack Sherman, Winifred J. Morrison und Max A. Woodbury)<ref name = "Sherman1949"/><ref name = "Sherman1950"/><ref name = "Woodbury1950"/><ref name = "Woodbury1949"/><ref name = "Hager"/> der linearen Algebra gibt eine explizite Darstellung der Inversen einer regulären Matrix <math>A \!\,</math> nach einer Änderung <math>-UV^T \!\,</math> 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 <math> u,v \in \R^n </math> ist das Produkt <math> uv^T \!\,</math> eine <math> n\times n </math>-Matrix und besitzt den Rang 1.

Für <math> v^Tu \not= 1</math> gilt

<math> (E-uv^T)^{-1} = E+\frac{uv^T}{1-v^Tu}, </math>

wobei mit <math>E</math> 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 <math> n\times n </math>-Matrix <math>A \!\,</math>:

Für <math> v^TA^{-1}u \not= 1 </math> gilt

<math> (A-uv^T)^{-1} = A^{-1}+\frac{A^{-1}uv^TA^{-1}}{1-v^TA^{-1}u}. </math>

Dabei ergibt sich, dass die Matrix <math> A-uv^T \!\,</math> genau dann invertierbar ist, wenn der Nenner in obiger Formel nicht verschwindet.

Änderung vom Rang k

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

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

<math> (A-UV^T)^{-1} = A^{-1}+A^{-1}U(E-V^TA^{-1}U)^{-1}V^T A^{-1}. </math>

Literatur

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

Einzelnachweise

<references>

<ref name = "Hager">Vorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/Name: Updating the inverse of a matrix. In: SIAM Review. 31. Jahrgang, Nr. 2, Vorlage:Cite book/Date, S. 221–239, doi:10.1137/1031049 (Vorlage:Cite book/URL [abgerufen am -05-]). Vorlage:Cite book/URLVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/Meldung2</ref>

<ref name = "Sherman1949">Vorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/Name: 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. Jahrgang, Vorlage:Cite book/Date, S. 621, doi:10.1214/aoms/1177729959 (Vorlage:Cite book/URL [abgerufen am -05-]). Vorlage:Cite book/URLVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/Meldung2</ref>

<ref name = "Sherman1950">Vorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/NameVorlage:Cite book/Name: Adjustment of an Inverse Matrix Corresponding to a Change in One Element of a Given Matrix. In: Annals of Mathematical Statistics. 21. Jahrgang, Nr. 1, Vorlage:Cite book/Date, S. 124–127, doi:10.1214/aoms/1177729893 (Vorlage:Cite book/URL [abgerufen am -05-]). Vorlage:Cite book/URLVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/Meldung2</ref>

<ref name = "Woodbury1949">Max A. Woodbury: The Stability of Out-Input Matrices. Chicago 1949. </ref>

<ref name = "Woodbury1950">Max A. Woodbury: Inverting modified matrices. In: Statistical Research Group (Hrsg.): Memorandum Report 42. Princeton University, Princeton, NJ 1950. </ref>

</references>