Tekst źródłowy strony Wzór Shermana-Morrisona

'''Wzór Shermana-Morrisona''' – wzór służący do obliczenia odwrotności sumy [[Macierz odwrotna|macierzy odwracalnej]] <math>A</math> i [[Iloczyn diadyczny|iloczynu diadycznego]] <math>u v^T</math> wektorów <math>u</math> i <math>v.</math> 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<ref name="hager">{{Cytuj pismo |nazwisko = Hager |imię = William W. |tytuł = Updating the inverse of a matrix |czasopismo = SIAM Review |wolumin = 31 |wydanie = 2 |strony = 221–239 |rok = 1989 |doi = 10.1137/1031049 |język = en}}</ref>.

== Twierdzenie ==
Niech <math>A</math> będzie [[Macierz odwrotna|odwracalną]] [[Macierz#Wprowadzenie i oznaczenia|macierzą kwadratową]] i <math>u,</math> <math>v</math> będą [[Przestrzeń współrzędnych#Macierze|wektorami kolumnowymi]]. Ponadto niech <math>1 + v^T A^{-1}u \neq 0.</math>

Zachodzi wówczas
: <math>(A+uv^T)^{-1} = A^{-1} - \frac{A^{-1}uv^T A^{-1}}{1 + v^T A^{-1}u}.</math>

== Zastosowanie ==
Jeśli odwrotność macierzy <math>A</math> jest nam już znana, to stosując wzór można obliczyć odwrotność tej macierzy skorygowanej przez [[Rząd macierzy|macierz 1 rzędu]] <math>uv^T.</math> Rachunek ten ma stosunkowo małą [[Złożoność obliczeniowa|złożoność obliczeniową]], ponieważ odwrotność <math>A+uv^T</math> nie musi być obliczana od podstaw (co jest złożonym działaniem), ale może być obliczana przez korekcję (lub perturbację) <math>A^{-1}.</math>

Przy wykorzystaniu kolumn jednostkowych (kolumny [[Macierz jednostkowa|macierzy jednostkowej]]) jako <math>u</math> lub/oraz <math>v,</math> poszczególne kolumny lub rzędy macierzy <math>A</math> mogą być zmieniane, a odpowiednio zmieniona odwrotność macierzy może zostać obliczona w sposób nieskomplikowany obliczeniowo<ref>Langville, Amy N.; and Meyer, Carl D.; „Google’s PageRank and Beyond: The Science of Search Engine Rankings”, Princeton University Press, 2006, p. 156.</ref>. W ogólnym przypadku, gdzie <math>A^{-1}</math> jest macierzą kwadratową o wymiarach <math>n</math> x <math>n,</math> <math>u</math> i <math>v</math> są dowolnymi wektorami o wymiarze <math>n,</math> cała macierz jest uaktualniana<ref name="B1951">{{Cytuj pismo |nazwisko = Bartlett |imię = Maurice S. |tytuł = An Inverse Matrix Adjustment Arising in Discriminant Analysis |czasopismo = [[Annals of Mathematical Statistics]] |wolumin = 22 |wydanie = 1 |strony = 107–111 |rok = 1951 |doi = 10.1214/aoms/1177729698 |język = en}}</ref> i złożoność obliczeniowa wynosi <math>3n^2</math><ref>[http://www.alglib.net/matrixops/general/invupdate.php Update of the inverse matrix by the Sherman-Morrison formula].</ref>. Jeśli <math>u</math> jest kolumną jednostkową, złożoność obliczeniowa wynosi <math>2n^2.</math> Tak samo w przypadku, gdy kolumna <math>v</math> jest kolumną jednostkową. Jeśli zarówno <math>u,</math> jak i <math>v</math> są kolumnami jednostkowymi, złożoność obliczeniowa wynosi jedynie <math>n^2.</math>

== Dowód ==
Wystarczy dowieść, że
: <math>(A + uv^T)\left( A^{-1} - \frac{A^{-1} uv^T A^{-1}}{1 + v^T A^{-1}u}\right)\ =\ I.</math>
Otóż
: <math>(A + uv^T)\left( A^{-1} - \frac{A^{-1} uv^T A^{-1}}{1 + v^T A^{-1}u}\right)</math>

::: <math>= AA^{-1} + uv^T A^{-1} - \frac{AA^{-1}uv^T A^{-1} + uv^T A^{-1}uv^T A^{-1}}{1 + v^TA^{-1}u}</math>

::: <math>= I + uv^T A^{-1} - \frac{uv^T A^{-1} + uv^T A^{-1}uv^T A^{-1}}{1 + v^T A^{-1}u}</math>

::: <math>= I + uv^T A^{-1} - \frac{u(1 + v^T A^{-1}u) v^T A^{-1}}{1 + v^T A^{-1}u}</math>

::: <math>= I + uv^T A^{-1} - uv^T A^{-1} = I</math>

W przedostatniej linijce wyrażenie <math>v^T A^{-1}u</math> jest skalarem, więc <math>(1+v^T A^{-1}u)</math> można było go wyłączyć przed nawias i skrócić z mianownikiem.

Stąd wynika, że macierze <math>A + uv^T,\ \ A^{-1} - \frac{A^{-1} uv^T A^{-1}}{1 + v^T A^{-1}u}</math> są wzajemnie odwrotne.

== Zobacz też ==
* [[metoda quasi-Newtona]]

== Przypisy ==
{{Przypisy}}

== Bibliografia ==
* {{Cytuj pismo |nazwisko = Sherman |imię = Jack |nazwisko2 = Morrison |imię2 = Winifred J. |tytuł = Adjustment of an Inverse Matrix Corresponding to Changes in the Elements of a Given Column or a Given Row of the Original Matrix (abstract) |czasopismo = Annals of Mathematical Statistics |wolumin = 20 |strony = 621 |rok = 1949 |doi = 10.1214/aoms/1177729959 |język = en}}
* {{Cytuj pismo |nazwisko = Sherman |imię = Jack |nazwisko2 = Morrison |imię2 = Winifred J. |tytuł = Adjustment of an Inverse Matrix Corresponding to a Change in One Element of a Given Matrix |czasopismo = [[Annals of Mathematical Statistics]] |wolumin = 21 |wydanie = 1 |strony = 124–127 |rok = 1950 |doi = 10.1214/aoms/1177729893 |język = en}}
* {{Cytuj książkę |nazwisko = Press |imię = William H. |nazwisko2 = Teukolsky |imię2 = Saul A. |nazwisko3 = Vetterling |imię3 = William T. |nazwisko4 = Flannery |imię4 = Brian P. |tytuł = Numerical Recipes: The Art of Scientific Computing |wydanie = 3 |wydawca = Cambridge University Press |rok = 2007 |rozdział = Section 2.7.1 Sherman-Morrison Formula |isbn = 978-0-521-88068-8 |język = en |adres rozdziału=http://apps.nrbook.com/empanel/index.html?pg=76}}

{{Algebra liniowa}}

[[Kategoria:Twierdzenia o macierzach kwadratowych]]
[[Kategoria:Działania na macierzach]]