Wzór Shermana-Morrisona

Wzór Shermana-Morrisona – wzór służący do obliczenia odwrotności sumy macierzy odwracalnej ${\displaystyle A}$ i iloczynu diadycznego ${\displaystyle uv^{T}}$ wektorów ${\displaystyle u}$ i ${\displaystyle 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].

Niech ${\displaystyle A}$ będzie odwracalną macierzą kwadratową i ${\displaystyle u,}$ ${\displaystyle v}$ będą wektorami kolumnowymi. Ponadto niech ${\displaystyle 1+v^{T}A^{-1}u\neq 0.}$

Zachodzi wówczas

${\displaystyle (A+uv^{T})^{-1}=A^{-1}-{\frac {A^{-1}uv^{T}A^{-1}}{1+v^{T}A^{-1}u}}.}$

Jeśli odwrotność macierzy ${\displaystyle A}$ jest nam już znana, to stosując wzór można obliczyć odwrotność tej macierzy skorygowanej przez macierz 1 rzędu ${\displaystyle uv^{T}.}$ Rachunek ten ma stosunkowo małą złożoność obliczeniową, ponieważ odwrotność ${\displaystyle 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ę) ${\displaystyle A^{-1}.}$

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

Wystarczy dowieść, że

${\displaystyle (A+uv^{T})\left(A^{-1}-{\frac {A^{-1}uv^{T}A^{-1}}{1+v^{T}A^{-1}u}}\right)\ =\ I.}$

Otóż

${\displaystyle (A+uv^{T})\left(A^{-1}-{\frac {A^{-1}uv^{T}A^{-1}}{1+v^{T}A^{-1}u}}\right)}$

${\displaystyle =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}}}$

${\displaystyle =I+uv^{T}A^{-1}-{\frac {uv^{T}A^{-1}+uv^{T}A^{-1}uv^{T}A^{-1}}{1+v^{T}A^{-1}u}}}$

${\displaystyle =I+uv^{T}A^{-1}-{\frac {u(1+v^{T}A^{-1}u)v^{T}A^{-1}}{1+v^{T}A^{-1}u}}}$

${\displaystyle =I+uv^{T}A^{-1}-uv^{T}A^{-1}=I}$

W przedostatniej linijce wyrażenie ${\displaystyle v^{T}A^{-1}u}$ jest skalarem, więc ${\displaystyle (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 ${\displaystyle A+uv^{T},\ \ A^{-1}-{\frac {A^{-1}uv^{T}A^{-1}}{1+v^{T}A^{-1}u}}}$ są wzajemnie odwrotne.

• metoda quasi-Newtona

• 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 numerów stron w książce