Wzór Shermana-Morrisona

Wzór Shermana-Morrisona – wzór służący do obliczenia odwrotności sumy macierzy odwracalnej $A$ i iloczynu diadycznego $uv^{T}$ wektorów $u$ i $v.$ Wzór Shermana-Morrisona jest szczególnym przypadkiem wzoru Shermana-Morrisona-Woodbury’ego. Nazwany na cześć Shermana i Morrisona, pojawiał się jednak we wcześniejszych publikacjach^[1].

Twierdzenie

Niech $A$ będzie odwracalną macierzą kwadratową i $u,$ $v$ będą wektorami kolumnowymi. Ponadto niech $1+v^{T}A^{-1}u\neq 0.$

Zachodzi wówczas

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

Zastosowanie

Jeśli odwrotność macierzy $A$ jest nam już znana, to stosując wzór można obliczyć odwrotność tej macierzy skorygowanej przez macierz 1 rzędu $uv^{T}.$ Rachunek ten ma stosunkowo małą złożoność obliczeniową, ponieważ odwrotność $A+uv^{T}$ nie musi być obliczana od podstaw (co jest złożonym działaniem), ale może być obliczana przez korekcję (lub perturbację) $A^{-1}.$

Przy wykorzystaniu kolumn jednostkowych (kolumny macierzy jednostkowej) jako $u$ lub/oraz $v,$ poszczególne kolumny lub rzędy macierzy $A$ mogą być zmieniane, a odpowiednio zmieniona odwrotność macierzy może zostać obliczona w sposób nieskomplikowany obliczeniowo^[2]. W ogólnym przypadku, gdzie $A^{-1}$ jest macierzą kwadratową o wymiarach $n$ x $n,$ $u$ i $v$ są dowolnymi wektorami o wymiarze $n,$ cała macierz jest uaktualniana^[3] i złożoność obliczeniowa wynosi $3n^{2}$ ^[4]. Jeśli $u$ jest kolumną jednostkową, złożoność obliczeniowa wynosi $2n^{2}.$ Tak samo w przypadku, gdy kolumna $v$ jest kolumną jednostkową. Jeśli zarówno $u,$ jak i $v$ są kolumnami jednostkowymi, złożoność obliczeniowa wynosi jedynie $n^{2}.$

Dowód

Wystarczy dowieść, że

(A+uv^{T})\left(A^{-1}-{\frac {A^{-1}uv^{T}A^{-1}}{1+v^{T}A^{-1}u}}\right)\ =\ I.

Otóż

(A+uv^{T})\left(A^{-1}-{\frac {A^{-1}uv^{T}A^{-1}}{1+v^{T}A^{-1}u}}\right)

=AA^{-1}+uv^{T}A^{-1}-{\frac {AA^{-1}uv^{T}A^{-1}+uv^{T}A^{-1}uv^{T}A^{-1}}{1+v^{T}A^{-1}u}}

=I+uv^{T}A^{-1}-{\frac {uv^{T}A^{-1}+uv^{T}A^{-1}uv^{T}A^{-1}}{1+v^{T}A^{-1}u}}

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

=I+uv^{T}A^{-1}-uv^{T}A^{-1}=I

W przedostatniej linijce wyrażenie $v^{T}A^{-1}u$ jest skalarem, więc $(1+v^{T}A^{-1}u)$ można było go wyłączyć przed nawias i skrócić z mianownikiem.

Stąd wynika, że macierze $A+uv^{T},\ \ A^{-1}-{\frac {A^{-1}uv^{T}A^{-1}}{1+v^{T}A^{-1}u}}$ są wzajemnie odwrotne.

Zobacz też

metoda quasi-Newtona

Przypisy

↑ William W. Hager. Updating the inverse of a matrix. „SIAM Review”. 31 (2), s. 221–239, 1989. DOI: 10.1137/1031049. (ang.).
↑ Langville, Amy N.; and Meyer, Carl D.; „Google’s PageRank and Beyond: The Science of Search Engine Rankings”, Princeton University Press, 2006, p. 156.
↑ Maurice S. Bartlett. An Inverse Matrix Adjustment Arising in Discriminant Analysis. „Annals of Mathematical Statistics”. 22 (1), s. 107–111, 1951. DOI: 10.1214/aoms/1177729698. (ang.).
↑ Update of the inverse matrix by the Sherman-Morrison formula.

Bibliografia

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). „Annals of Mathematical Statistics”. 20, s. 621, 1949. DOI: 10.1214/aoms/1177729959. (ang.).
Jack Sherman, Winifred J. Morrison. Adjustment of an Inverse Matrix Corresponding to a Change in One Element of a Given Matrix. „Annals of Mathematical Statistics”. 21 (1), s. 124–127, 1950. DOI: 10.1214/aoms/1177729893. (ang.).
Section 2.7.1 Sherman-Morrison Formula. W: William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery: Numerical Recipes: The Art of Scientific Computing. Wyd. 3. Cambridge University Press, 2007. ISBN 978-0-521-88068-8. (ang.).

[hager-1] William W. Hager. Updating the inverse of a matrix. „SIAM Review”. 31 (2), s. 221–239, 1989. DOI: 10.1137/1031049. (ang.).

[2] Langville, Amy N.; and Meyer, Carl D.; „Google’s PageRank and Beyond: The Science of Search Engine Rankings”, Princeton University Press, 2006, p. 156.

[B1951-3] Maurice S. Bartlett. An Inverse Matrix Adjustment Arising in Discriminant Analysis. „Annals of Mathematical Statistics”. 22 (1), s. 107–111, 1951. DOI: 10.1214/aoms/1177729698. (ang.).

[4] Update of the inverse matrix by the Sherman-Morrison formula.

[1]

[2]

[3]

[4]