Sherman-Morrison-Woodbury-Formel

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 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[Bearbeiten]

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
 (E-uv^T)^{-1} = E+\frac{uv^T}{1-v^Tu}.

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{A^{-1}uv^TA^{-1}}{1-v^TA^{-1}u}.

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[Bearbeiten]

Für zwei  n\times k -Matrizen  U,V \!\, verallgemeinert sich die Formel 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^TA^{-1}U)^{-1}V^T A^{-1}. \!\,

Literatur[Bearbeiten]

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

Einzelnachweise[Bearbeiten]

  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.