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.
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 obliczeniowoLangville, Amy N.; and Meyer, Carl D.; „Google’s PageRank and Beyond: The Science of Search Engine Rankings”, Princeton University Press, 2006, p. 156.. W ogólnym przypadku, gdzie jest macierzą kwadratową o wymiarach x i są dowolnymi wektorami o wymiarze cała macierz jest uaktualniana i złożoność obliczeniowa wynosi Update of the inverse matrix by the Sherman-Morrison formula.. 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
Bibliografia
Kategoria:Twierdzenia o macierzach kwadratowych Kategoria:Działania na macierzach