Sherman-Morrison-Woodbury formula

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 . ${\displaystyle A\!\,}$ ${\displaystyle -UV^{T}\!\,}$

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. ${\displaystyle u,v\in \mathbb {R} ^{n}}$ ${\displaystyle uv^{T}\!\,}$ ${\displaystyle n\times n}$

for true ${\displaystyle v^{T}u\not =1}$

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

where the identity matrix is meant. One checks the statement elementary. ${\displaystyle E}$

The formula is carried over directly to rank 1 changes of any regular matrix : ${\displaystyle n\times n}$ ${\displaystyle A\!\,}$

for true ${\displaystyle v^{T}A^{-1}u\not =1}$

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

The result is that the matrix can be inverted if and only if the denominator in the above formula does not disappear. ${\displaystyle A-uv^{T}\!\,}$

Change from rank k

For two matrices the formula generalizes in the following way: ${\displaystyle n\times k}$ ${\displaystyle U,V\!\,}$

The matrix is regular, then applies ${\displaystyle k\times k}$ ${\displaystyle E-V^{T}A^{-1}U\!\,}$

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

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 .