Przejdź do zawartości

Wzór Shermana-Morrisona

Z Wikipedii, wolnej encyklopedii

Wzór Shermana-Morrisona – wzór służący do obliczenia odwrotności sumy macierzy odwracalnej i iloczynu diadycznego wektorów i 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

[edytuj | edytuj kod]

Niech będzie odwracalną macierzą kwadratową i będą wektorami kolumnowymi. Ponadto niech

Zachodzi wówczas

Zastosowanie

[edytuj | edytuj kod]

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

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

Dowód

[edytuj | edytuj kod]

Wystarczy dowieść, że

Otóż

W przedostatniej linijce wyrażenie jest skalarem, więc można było go wyłączyć przed nawias i skrócić z mianownikiem.

Stąd wynika, że macierze są wzajemnie odwrotne.

Zobacz też

[edytuj | edytuj kod]

Przypisy

[edytuj | edytuj kod]
  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.
  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.

Bibliografia

[edytuj | edytuj kod]
  • 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.).