Tożsamość macierzy Woodbury'ego

W matematyce (szczególnie w algebrze liniowej ) tożsamość macierzy Woodbury'ego , nazwana na cześć Maxa A. Woodbury'ego, mówi, że odwrotność korekty rangi k pewnej macierzy można obliczyć, wykonując poprawkę rangi k na odwrotność oryginalnej macierzy . Alternatywnymi nazwami tego wzoru są lemat o odwróceniu macierzy , wzór Shermana – Morrisona – Woodbury'ego lub po prostu wzór Woodbury'ego . Jednak tożsamość pojawiła się w kilku artykułach przed raportem Woodbury'ego.

Tożsamość macierzy Woodbury'ego to

${\ Displaystyle \ lewo (A + UCV \ prawo) ^ { -1}=A^{-1}-A^{-1}U\lewo(C^{-1}+VA^{-1}U\prawo)^{-1}VA^{-1}, }$

gdzie A , U , C i V są macierzami zgodnymi : A to n × n , C to k × k , U to n × k , a V to k × n . Można to wyprowadzić za pomocą blokowej inwersji macierzy .

Chociaż tożsamość jest używana głównie w macierzach, obowiązuje w ogólnym pierścieniu lub w kategorii Ab .

Dyskusja

Aby udowodnić ten wynik, zaczniemy od udowodnienia prostszego wyniku. Zastępując A i C macierzą tożsamościową I otrzymujemy inną tożsamość, która jest nieco prostsza:

${\ Displaystyle \ lewo (I + UV \ prawo) ^ {-1} = jm \ lewo (I + VU \ prawo) ^ {-1} V.}$

Aby odzyskać oryginalne równanie z tej zredukowanej tożsamości , ustaw ${\ Displaystyle U = A ^ {- 1} X}$ i ${\ Displaystyle V = CY}$ .

Sama tożsamość może być postrzegana jako połączenie dwóch prostszych tożsamości. Otrzymujemy pierwszą tożsamość z

${\ Displaystyle I = (I + P) ^ {- 1} (JA + P. )=(I+P)^{-1}+(I+P)^{-1}P}$ ,

zatem,

${\ Displaystyle (I + P) ^ {- 1} = I- (I + P) ^ {- 1} P}$ ,

i podobnie

${\ Displaystyle (I + P) ^ {- 1} = IP (I + P) ^ {- 1}.}$

Druga tożsamość to tak zwana tożsamość push-through

${\ Displaystyle (I + UV) ^ {- 1} U = U (I + VU) ^ {- 1}}$

z którego czerpiemy

${\ Displaystyle U (I + VU) = (I + UV) U}$

po pomnożeniu przez ${\ Displaystyle (I + VU) ^ {- 1}}$ po prawej stronie i przez ${\ Displaystyle (I + UV) ^ {- 1 }}$ po lewej stronie.

Przypadki specjalne

Kiedy są $,$ tożsamość sprowadza się do Shermana- .

W przypadku skalarnym wersja zredukowana jest po prostu

${\ Displaystyle {\ Frac {1} {1 + uv}} = 1- {\ Frac {uv} {1 + uv}}.}$

Odwrotność sumy

Jeśli n = k i U = V = I _n jest macierzą tożsamości, to

${\ Displaystyle {\ rozpocząć {wyrównane} \ lewo ({A} + {B} \ prawo) ^ {-1} i = A ^ {-1} -A ^ {-1} (B ^ {-1} + A^{-1})^{-1}A^{-1}\\&={A}^{-1}-{A}^{-1}\left({A}{B}^{ -1}+{I}\right)^{-1}.\end{wyrównane}}}$

Kontynuacja łączenia składników skrajnej prawej strony powyższego równania daje tożsamość Hua

${\ Displaystyle \ lewo ({A} + {B} \ prawo) ^ {-1} = {A} ^ {-1} - \ lewo ({A} + {A} {B} ^ {-1} A}\prawo)^{-1}.}$

Inną użyteczną formą tej samej tożsamości jest

${\ Displaystyle \ lewo ({A} - {B} \ prawej) ^ {- 1} = {A} ^ {-1}+{A}^{-1}{B}\lewo({A}-{B}\prawo)^{-1},}$

który, w przeciwieństwie do powyższych, jest ważny, nawet jeśli jest w liczbie pojedynczej i ma strukturę rekurencyjną, która daje ${\ displaystyle B}$

${\ Displaystyle \ lewo ({A} - {B} \ prawej) ^ {- 1} = \ suma _ {k = 0}^{\infty }\left({A}^{-1}{B}\right)^{k}{A}^{-1}}$

jeśli promień widmowy $jeden$ _ Oznacza to, że jeśli powyższa suma jest zbieżna, to jest równa ${\ Displaystyle (AB) ^ {- 1}}$ .

Ta forma może być używana w rozwinięciach perturbacyjnych, gdzie B jest perturbacją A .

Wariacje

Dwumianowe twierdzenie odwrotne

Jeśli A , B , U , V są macierzami odpowiednio o rozmiarach n × n , k × k , n × k , k × n , to

${\ Displaystyle \ lewo (A + UBV \ prawo) ^ {-1}=A^{-1}-A^{-1}UB\lewo(B+BVA^{-1}UB\prawo)^{-1}BVA^{-1}}$

pod warunkiem, że A i B + BVA ^-1 UB nie są liczbą pojedynczą. Nieosobliwość tego ostatniego wymaga B ⁻¹ , ponieważ jest równe B ( I + VA ⁻¹ UB ) i ranga tego ostatniego nie może przekraczać rangi B .

Ponieważ B jest odwracalne, dwa wyrazy B flankujące wielkość odwrotną w nawiasach po prawej stronie można zastąpić przez ( B ⁻¹ ) ⁻¹ , co daje pierwotną tożsamość Woodbury'ego.

Odmiana dla sytuacji, gdy B jest w liczbie pojedynczej, a być może nawet nie jest kwadratem:

${\ Displaystyle (A + UBV) ^ {-1} = A ^ {-1} -A ^ {-1} U (I + BVA ^ {-1} U) ^ {-1} BVA ^ {-1} .}$

Formuły istnieją również dla niektórych przypadków, w których A jest liczbą pojedynczą.

Pseudoodwrotność z dodatnimi półokreślonymi macierzami

Ogólnie rzecz biorąc, tożsamość Woodbury'ego nie jest ważna, jeśli jedna lub więcej odwrotności zostanie zastąpionych pseudoodwrotnościami (Moore-Penrose) . $\$ jednak i $} displaystyle A+UCV}$ dodatnie półokreślone i ( co oznacza $\$ że $displaystyle A} i$ sam jest dodatnio półokreślony), to następująca formuła zapewnia uogólnienie:

${\ Displaystyle {\ rozpocząć {wyrównane} (XX ^ {\ operatorname {H}} + YY ^ {\ operatorname {H}}) ^ {+} & = (ZZ ^ {\ operatorname {H}}) ^ {+ }+(I-YZ^{+})^{\mathrm {H} }X^{+\mathrm {H} }EX^{+}(I-YZ^{+}),\\Z&=(I -XX^{+})Y,\\E&=IX^{+}Y(IZ^{+}Z)F^{-1}(X^{+}Y)^{\mathrm {H} }, \\F&=I+(IZ^{+}Z)Y^{\mathrm {H} }(XX^{\mathrm {H} })^{+}Y(IZ^{+}Z),\end{ wyrównany}}}$

gdzie można zapisać jako ${H}} + YY$$\ Displaystyle$$operatorname$ , ponieważ każda dodatnia półokreślona macierz jest równa dla pewnego ${H}}}$ .

pochodne

Bezpośredni dowód

Formułę można udowodnić, sprawdzając, że razy jej rzekoma odwrotność po prawej stronie tożsamości Woodbury'ego daje macierz tożsamości: ${\ Displaystyle (A + UCV) }$

${\ Displaystyle {\ rozpocząć {wyrównane} i \ lewo (A + UCV \ prawo) \ lewo [A ^ {-1} -A ^ {-1} U \ lewo (C ^ {-1} + VA ^ {- 1}U\right)^{-1}VA^{-1}\right]\\={}&\left\{IU\left(C^{-1}+VA^{-1}U\right )^{-1}VA^{-1}\prawo\}+\lewo\{UCVA^{-1}-UCVA^{-1}U\lewo(C^{-1}+VA^{-1 }U\right)^{-1}VA^{-1}\right\}\\={}&\left\{I+UCVA^{-1}\right\}-\left\{U\left (C^{-1}+VA^{-1}U\prawo)^{-1}VA^{-1}+UCVA^{-1}U\lewo(C^{-1}+VA^{ -1}U\prawo)^{-1}VA^{-1}\prawo\}\\={}&I+UCVA^{-1}-\lewo(U+UCVA^{-1}U\prawo )\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\\={}&I+UCVA^{-1}-UC\left( C^{-1}+VA^{-1}U\prawo)\lewo(C^{-1}+VA^{-1}U\prawo)^{-1}VA^{-1}\\ ={}&I+UCVA^{-1}-UCVA^{-1}\\={}&I.\end{wyrównane}}}$

Alternatywne dowody

Dowód algebraiczny

Najpierw rozważ te użyteczne tożsamości, ${\ Displaystyle {\ rozpocząć {wyrównane} U + UCVA ^ {-1} U & = UC \ lewo (C ^ {-1} + VA ^ {-1} U \ prawo )=\left(A+UCV\right)A^{-1}U\\\left(A+UCV\right)^{-1}UC&=A^{-1}U\left(C^{- 1}+VA^{-1}U\prawo)^{-1}\end{wyrównane}}}$ Teraz, ${\ Displaystyle {\ rozpocząć {wyrównane} A ^ {-1} & = \ lewo (A + UCV \ prawo) ^ {-1} \ lewo (A + UCV \ prawo) A ^ {-1} \\ & = \left(A+UCV\right)^{-1}\left(I+UCVA^{-1}\right)\\&=\left(A+UCV\right)^{-1}+\left( A+UCV\right)^{-1}UCVA^{-1}\\&=\left(A+UCV\right)^{-1}+A^{-1}U\left(C^{- 1}+VA^{-1}U\prawo)^{-1}VA^{-1}.\end{wyrównane}}}$

Wyprowadzenie poprzez eliminację blokową

Wyprowadzenie tożsamości macierzy Woodbury'ego można łatwo wykonać, rozwiązując następujący problem inwersji macierzy blokowej ${\ Displaystyle {\ rozpocząć {bmatrix} A&U \\ V&-C ^ {-1} \ koniec {bmatrix}} {\ rozpocząć {bmatrix} X \\ Y \ koniec {bmatrix}} = {\ rozpocząć {bmatrix} ja \\0\koniec{bmacierzy}}.}$ Rozwijając, widzimy, że powyższe sprowadza się do ${\ Displaystyle {\ rozpocząć {przypadki} AX + UY = ja \\ VX-C ^ {- 1} Y = 0 \ koniec {przypadków}}}$ co jest równoważne z ${\ Displaystyle (A + UCV) X = I}$ . $które$ stwierdzamy, że drugiego ${\ Displaystyle VA ^ {- 1} (I-UY) = C ^ {- 1} Y}$ . Rozwijając i zmieniając układ, mamy ${\ Displaystyle VA ^ {-1} = \ lewo (C ^ {-1} + VA ^ {-1} U \right)Y}$ , lub ${\ Displaystyle \ lewo (C ^ {-1} + VA ^ {-1} U \ prawo) ^ {-1} VA ^ {-1} = Y}$ . $_ \displaystyle AX+U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}=I}$ podstawiamy $do$ mamy . Zatem, ${\ Displaystyle (A + UCV) ^ {-1} = X = A ^ {-1} -A ^ {-1} U \ lewo (C ^ {-1} + VA ^ {-1} U \ prawo) ^{-1}VA^{-1}.}$ Wyprowadziliśmy tożsamość macierzy Woodbury'ego.

Wyprowadzenie z rozkładu LDU

Zaczynamy od matrixa ${\ Displaystyle {\ rozpocząć {bmatrix} A&U \\ V&C \ koniec {bmatrix}}}$ Eliminując wpis pod A (biorąc pod uwagę, że A jest odwracalny) otrzymujemy ${\ Displaystyle {\ rozpocząć {bmatrix} I & 0 \\ -VA ^ {- 1} i ja \ koniec { bmatrix}}{\begin{bmatrix}A&U\\V&C\end{bmatrix}}={\begin{bmatrix}A&U\\0&C-VA^{-1}U\end{bmatrix}}}$ Podobnie, wyeliminowanie wpisu powyżej C daje ${\ Displaystyle {\ rozpocząć {bmatrix} A & U \\ V&C \ koniec {bmatrix}} {\ rozpocząć { bmatrix}I&-A^{-1}U\\0&I\end{bmatrix}}={\begin{bmatrix}A&0\\V&C-VA^{-1}U\end{bmatrix}}}$ Teraz łącząc powyższe dwa, otrzymujemy ${\ Displaystyle {\ rozpocząć {bmatrix} I & 0 \\ -VA ^ {-1}&I\end{bmatrix}}{\begin{bmatrix}A&U\\V&C\end{bmatrix}}{\begin{bmatrix}I&-A^{-1}U\\0&I\end{bmatrix} }={\begin{bmatrix}A&0\\0&C-VA^{-1}U\end{bmatrix}}}$ Przesunięcie w prawą stronę daje $\ Displaystyle {\ rozpocząć {bmatrix} A&U \\ V&C \ koniec {bmatrix }}={\begin{bmatrix}I&0\\VA^{-1}&I\end{bmatrix}}{\begin{bmatrix}A&0\\0&C-VA^{-1}U\end{bmatrix}}{ \begin{bmatrix}I&A^{-1}U\\0&I\end{bmatrix}}}$ który jest rozkładem LDU macierzy blokowej na górną trójkątną, ukośną i dolną macierz trójkątną. Teraz odwrócenie obu stron daje ${\ Displaystyle {\ rozpocząć {wyrównane} {\ rozpocząć {bmatrix} A&U \\ V&C \ koniec {bmatrix}} ^ {-1} & = {\ rozpocząć {bmatrix} I&A ^ {-1} U \\ 0&I \ koniec {bmatrix}}^{-1}{\begin{bmatrix}A&0\\0&C-VA^{-1}U\end{bmatrix}}^{-1}{\begin{bmatrix}I&0\\VA^{ -1}&I\end{bmatrix}}^{-1}\\[8pt]&={\begin{bmatrix}I&-A^{-1}U\\0&I\end{bmatrix}}{\begin{ bmatrix}A^{-1}&0\\0&\left(C-VA^{-1}U\right)^{-1}\end{bmatrix}}{\begin{bmatrix}I&0\\-VA^ {-1}&I\end{bmatrix}}\\[8pt]&={\begin{bmatrix}A^{-1}+A^{-1}U\left(C-VA^{-1}U \right)^{-1}VA^{-1}&-A^{-1}U\left(C-VA^{-1}U\right)^{-1}\\-\left(C -VA^{-1}U\prawo)^{-1}VA^{-1}&\lewo(C-VA^{-1}U\prawo)^{-1}\end{bmacierz}}\ qquad \mathrm {(1)} \end{wyrównane}}}$ Równie dobrze moglibyśmy zrobić to w inny sposób (pod warunkiem, że C jest odwracalny), tj ${\ Displaystyle {\ rozpocząć {bmatrix} A&U \\ V&C \ koniec {bmatrix }}={\begin{bmatrix}I&UC^{-1}\\0&I\end{bmatrix}}{\begin{bmatrix}A-UC^{-1}V&0\\0&C\end{bmatrix}}{\ początek{bmacierz}I&0\\C^{-1}V&I\koniec{bmacierz}}}$ Teraz ponownie odwracając obie strony, ${\ Displaystyle {\ rozpocząć {wyrównane} {\ rozpocząć {bmatrix} A&U \\ V&C \ koniec {bmatrix}} ^ {-1} & = {\ rozpocząć {bmatrix} I & 0 \\ C ^ {-1} V & I \ koniec {bmatrix}}^{-1}{\begin{bmatrix}A-UC^{-1}V&0\\0&C\end{bmatrix}}^{-1}{\begin{bmatrix}I&UC^{-1} \\0&I\end{bmatrix}}^{-1}\\[8pt]&={\begin{bmatrix}I&0\\-C^{-1}V&I\end{bmatrix}}{\begin{bmatrix} \left(A-UC^{-1}V\right)^{-1}&0\\0&C^{-1}\end{bmatrix}}{\begin{bmatrix}I&-UC^{-1}\ \0&I\end{bmatrix}}\\[8pt]&={\begin{bmatrix}\left(A-UC^{-1}V\right)^{-1}&-\left(A-UC^ {-1}V\prawo)^{-1}UC^{-1}\\-C^{-1}V\lewo(A-UC^{-1}V\prawo)^{-1}&C ^{-1}+C^{-1}V\left(A-UC^{-1}V\right)^{-1}UC^{-1}\end{bmatrix}}\qquad \mathrm { (2)} \end{wyrównane}}}$ Teraz porównanie elementów (1, 1) RHS z (1) i (2) powyżej daje wzór Woodbury'ego ${\ Displaystyle \ lewo (A-UC ^ {-1} V \ prawo) ^ {-1} = A ^ {-1} + A ^ {-1} U \ lewo (C-VA ^ {-1} U \right)^{-1}VA^{-1}.}$

Aplikacje

Ta tożsamość jest przydatna w niektórych obliczeniach numerycznych, w których A ^-1 zostało już obliczone i pożądane jest obliczenie ( A + UCV ) ^-1 . Przy dostępnej odwrotności A wystarczy znaleźć odwrotność C ⁻¹ + VA ⁻¹ U , aby otrzymać wynik przy użyciu prawej strony tożsamości. Jeśli C ma znacznie mniejszy wymiar niż A , jest to bardziej wydajne niż odwrócenie A + UCV bezpośrednio. Częstym przypadkiem jest znalezienie odwrotności aktualizacji niskiego rzędu A + UCV A ( gdzie U ma tylko kilka kolumn, a V tylko kilka wierszy) lub znalezienie przybliżenia odwrotności macierzy A + B , gdzie macierz B można przybliżyć za pomocą macierzy niskiego rzędu UCV , na przykład stosując rozkład na wartości osobliwe .

Stosuje się to np. w filtrze Kalmana i metodach rekurencyjnych najmniejszych kwadratów , aby zastąpić rozwiązanie parametryczne , wymagające odwrócenia macierzy wielkości wektora stanu, rozwiązaniem opartym na równaniach warunkowych. W przypadku filtru Kalmana macierz ta ma wymiary wektora obserwacji, czyli zaledwie 1 w przypadku, gdy jednocześnie przetwarzana jest tylko jedna nowa obserwacja. To znacznie przyspiesza często przeprowadzane w czasie rzeczywistym obliczenia filtra.

W przypadku, gdy $i$ jest identyczności , macierz jest w numerycznej algebrze liniowej równaniach różniczkowych cząstkowych jako .

Zobacz też

• Formuła Shermana-Morrisona
• Uzupełnienie Schura
• Lemat o wyznaczniku macierzy , wzór na aktualizację rangi k do wyznacznika
• Odwracalna macierz
• Pseudoodwrotność Moore'a – Penrose'a # Aktualizacja pseudoodwrotności

Notatki

•   Prasa, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), „Sekcja 2.7.3. Formuła Woodbury'ego” , Przepisy numeryczne: The Art of Scientific Computing (wyd. 3), Nowy Jork: Cambridge University Press, ISBN 978-0-521-88068-8

Linki zewnętrzne

• Niektóre tożsamości macierzowe
• Weisstein, Eric W. „Formuła Woodbury'ego” . MathWorld .