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]

Wektory i działania na nich	zwrot wektora wektor jednostkowy mnożenie przez skalar iloczyn wektorowy reguła śruby prawoskrętnej reguła prawej dłoni symbol Leviego-Civity
Układy wektorów i ich macierze	liniowa niezależność macierz zerowa macierz jednostkowa macierz skalarna macierz diagonalna macierz trójkątna macierz schodkowa rząd macierzy operacje elementarne macierze podobne metoda eliminacji Gaussa twierdzenie Kroneckera-Capellego
Wyznaczniki i miara układu wektorów	wyznacznik permutacja minor rozwinięcie Laplace’a wzory Cramera reguła Sarrusa iloczyn mieszany
Przestrzenie liniowe	przestrzeń euklidesowa przykłady przestrzeni liniowych podprzestrzeń liniowa baza baza standardowa
Iloczyny skalarne	iloczyn skalarny symbol Kroneckera ortogonalność ortonormalność baza ortonormalna ortogonalizacja Grama-Schmidta
Pojęcia zaawansowane	tensor twierdzenie o bezwładności form kwadratowych
Pozostałe pojęcia	stożek wypukły pseudoskalar pseudowektor przestrzeń ilorazowa (algebra liniowa) przestrzeń afiniczna
Powiązane dyscypliny	algebra abstrakcyjna teoria grup analiza funkcjonalna analiza numeryczna programowanie liniowe mechanika kwantowa
Znani uczeni	Girolamo Cardano Isaac Newton Gottfried Wilhelm Leibniz Gabriel Cramer Augustin Louis Cauchy Arthur Cayley James Joseph Sylvester Hermann Grassmann Leopold Kronecker Hermann Weyl Saunders Mac Lane