Sherman-Morrison-Woodbury formula

from Wikipedia, the free encyclopedia

The Sherman-Morrison formula (after Jack Sherman, Winifred J. Morrison and Max A. Woodbury) of linear algebra is an explicit representation of the inverse of a regular matrix for a change of lower rank . This is of interest , for example, with the quasi-Newton method and when changing the base in the simplex method .

In numerical methods using the formula may lead to stability problems, for which reason alternatives are preferable.

Change from rank 1

With two vectors the product is a matrix and has rank 1.

for true

where the identity matrix is meant. One checks the statement elementary.

The formula is carried over directly to rank 1 changes of any regular matrix :

for true

The result is that the matrix can be inverted if and only if the denominator in the above formula does not disappear.

Change from rank k

For two matrices the formula generalizes in the following way:

The matrix is regular, then applies

literature

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

Individual evidence

  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, p. 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, No. 1, 1950, pp. 124-127. doi : 10.1214 / aoms / 1177729893 .
  3. Max A. Woodbury: Inverting modified matrices . In: Statistical Research Group (Ed.): 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, No. 2, 1989, pp. 221-239. doi : 10.1137 / 1031049 .