Wzór Shermana-Morrisona

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

Zachodzi wówczas

$(A+u{v}^T{)}^{-1}=A^{-1}-\frac{A^{-1}u{v}^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 $u{v}^T.$ Rachunek ten ma stosunkowo małą złożoność obliczeniową, ponieważ odwrotność $A+u{v}^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+u{v}^T)(A^{-1}-\frac{A^{-1}u{v}^T{A}^{-1}}{1+v^T{A}^{-1}u})=I.$

Otóż

$(A+u{v}^T)(A^{-1}-\frac{A^{-1}u{v}^T{A}^{-1}}{1+v^T{A}^{-1}u})$

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

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

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

$=I+u{v}^T{A}^{-1}-u{v}^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+u{v}^T,A^{-1}-\frac{A^{-1}u{v}^T{A}^{-1}}{1+v^T{A}^{-1}u}$ są wzajemnie odwrotne.

Zobacz też

• metoda quasi-Newtona

Bibliografia

• Szablon:Cytuj pismo
• Szablon:Cytuj pismo
• Szablon:Cytuj książkę