Wzór Shermana-Morrisona
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
Niech będzie odwracalną macierzą kwadratową i będą wektorami kolumnowymi. Ponadto niech
Zachodzi wówczas
Zastosowanie
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
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ż
- 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.).
- p
- d
- e
- Wektor
- Przestrzeń liniowa
- Macierz
Wektory i działania na nich |
|
---|---|
Układy wektorów i ich macierze | |
Wyznaczniki i miara układu wektorów | |
Przestrzenie liniowe | |
Iloczyny skalarne | |
Pojęcia zaawansowane | |
Pozostałe pojęcia |
|
Powiązane dyscypliny | |
Znani uczeni |