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.

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. 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 i złożoność obliczeniowa wynosi $3n^{2}$. 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

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.).brak strony w książce