Sherman – Morrisonův vzorec - Sherman–Morrison formula - Wikipedia

v matematika, zejména lineární algebra, Sherman – Morrisonův vzorec,^[1]^[2]^[3] pojmenovaný po Jacku Shermanovi a Winifredovi J. Morrisonovi, vypočítá inverzní hodnotu součtu an invertibilní matice ${ displaystyle A}$ a vnější produkt, ${ displaystyle uv ^ { textyf {T}}}$ , z vektory ${ displaystyle u}$ a ${ displaystyle v}$ . Vzorec Sherman-Morrison je zvláštním případem Woodburyův vzorec. Ačkoli byl pojmenován po Shermanovi a Morrisonovi, objevil se již v dřívějších publikacích.^[4]

Tvrzení

Předpokládat ${ displaystyle A in mathbb {R} ^ {n krát n}}$ je invertibilní čtvercová matice a ${ displaystyle u, v in mathbb {R} ^ {n}}$ jsou vektory sloupců. Pak ${ displaystyle A + uv ^ { textyf {T}}}$ je invertibilní iff ${ displaystyle 1 + v ^ { textyf {T}} A ^ {- 1} u neq 0}$ . V tomto případě,

{ displaystyle left (A + uv ^ { textyf {T}} vpravo) ^ {- 1} = A ^ {- 1} - {A ^ {- 1} uv ^ { textyf {T}} A ^ {- 1} přes 1 + v ^ { textyf {T}} A ^ {- 1} u}.}

Tady, ${ displaystyle uv ^ { textyf {T}}}$ je vnější produkt dvou vektorů ${ displaystyle u}$ a ${ displaystyle v}$ . Zde uvedená obecná forma je forma, kterou zveřejnil Bartlett.^[5]

Důkaz

( ${ displaystyle Leftarrow}$ ) Dokázat, že zpětný směr ( ${ displaystyle 1 + v ^ { textyf {T}} A ^ {- 1} u neq 0 Rightarrow A + uv ^ { textyf {T}}}$ je invertibilní s inverzí uvedenou výše) je pravda, ověříme vlastnosti inverze. Matice ${ displaystyle Y}$ (v tomto případě pravá strana vzorce Sherman-Morrison) je inverzní k matici ${ displaystyle X}$ (v tomto případě ${ displaystyle A + uv ^ { textyf {T}}}$ ) právě tehdy ${ displaystyle XY = YX = I}$ .

Nejprve ověříme, že pravá strana ( ${ displaystyle Y}$ ) splňuje ${ displaystyle XY = I}$ .

{ displaystyle { begin {zarovnáno} XY & = left (A + uv ^ { textyf {T}} vpravo) doleva (A ^ {- 1} - {A ^ {- 1} uv ^ { textyf {T}} A ^ {- 1} nad 1 + v ^ { textyf {T}} A ^ {- 1} u} vpravo) [6pt] & = AA ^ {- 1} + uv ^ { textyf {T}} A ^ {- 1} - {AA ^ {- 1} uv ^ { textyf {T}} A ^ {- 1} + uv ^ { textyf {T}} A ^ {- 1} uv ^ { textyf {T}} A ^ {- 1} nad 1 + v ^ { textyf {T}} A ^ {- 1} u} [6pt] & = I + uv ^ { textyf {T}} A ^ {- 1} - {uv ^ { textyf {T}} A ^ {- 1} + uv ^ { textyf {T}} A ^ {- 1} uv ^ { textyf {T}} A ^ {- 1} přes 1 + v ^ { textyf {T}} A ^ {- 1} u} [6pt] & = I + uv ^ { textyf {T}} A ^ {- 1} - {u left (1 + v ^ { textyf {T}} A ^ {- 1} u vpravo) v ^ { textyf {T}} A ^ {- 1} nad 1 + v ^ { textyf {T}} A ^ {- 1} u} [6pt] & = I + uv ^ { textyf {T}} A ^ {- 1} -uv ^ { textyf {T }} A ^ {- 1} [6pt] end {zarovnáno}}}

Abychom ukončili důkaz tohoto směru, musíme to ukázat ${ displaystyle YX = I}$ podobným způsobem jako výše:

{ displaystyle YX = left (A ^ {- 1} - {A ^ {- 1} uv ^ {T} A ^ {- 1} nad 1 + v ^ {T} A ^ {- 1} u} right) (A + uv ^ {T}) = I.}

( ${ displaystyle Rightarrow}$ ) Recipročně, pokud ${ displaystyle 1 + v ^ { textyf {T}} A ^ {- 1} u = 0}$ , pak nechal ${ displaystyle x = A ^ {- 1} u}$ , ${ displaystyle left (A + uv ^ { textyf {T}} vpravo)}$ má nepravidelné jádro, a proto není invertibilní.

aplikace

Pokud inverzní z ${ displaystyle A}$ je již známo, vzorec poskytuje a numericky levný způsob výpočtu inverzní funkce ${ displaystyle A}$ opraveno maticí ${ displaystyle uv ^ { textyf {T}}}$ (v závislosti na úhlu pohledu může být korekce považována za a rozrušení nebo jako hodnost -1 aktualizace). Výpočet je relativně levný, protože inverzní k ${ displaystyle A + uv ^ { textyf {T}}}$ nemusí být počítán od nuly (což je obecně drahé), ale lze jej vypočítat opravou (nebo rušením) ${ displaystyle A ^ {- 1}}$ .

Pomocí jednotkových sloupců (sloupců z matice identity ) pro ${ displaystyle u}$ nebo ${ displaystyle v}$ , jednotlivé sloupce nebo řádky ${ displaystyle A}$ lze takto manipulovat a odpovídajícím způsobem aktualizovat inverzní výpočet relativně levně.^[6] V obecném případě, kde ${ displaystyle A ^ {- 1}}$ je ${ displaystyle n}$ -podle- ${ displaystyle n}$ matice a ${ displaystyle u}$ a ${ displaystyle v}$ jsou libovolné vektory dimenze ${ displaystyle n}$ , je aktualizována celá matice^[5] a výpočet trvá ${ displaystyle 3n ^ {2}}$ skalární množení.^[7] Li ${ displaystyle u}$ je sloupec jednotky, výpočet trvá pouze ${ displaystyle 2n ^ {2}}$ skalární množení. Totéž platí, pokud ${ displaystyle v}$ je jednotkový sloupec. Pokud obojí ${ displaystyle u}$ a ${ displaystyle v}$ jsou jednotkové sloupce, výpočet trvá pouze ${ displaystyle n ^ {2}}$ skalární množení.

Tento vzorec má uplatnění také v teoretické fyzice. Konkrétně v teorii kvantového pole se pomocí tohoto vzorce počítá propagátor pole spin-1.^[8]^{[kruhový odkaz ]} Inverzní propagátor (jak se objevuje v Lagrangeově) má formu ${ displaystyle left (A + uv ^ { textyf {T}} vpravo)}$ . Jeden používá Sherman-Morrisonův vzorec k výpočtu inverze (splňující určité okrajové podmínky časově uspořádaného) inverzního propagátoru - nebo jednoduše (Feynmanova) propagátoru - který je potřebný k provedení jakéhokoli rušivého výpočtu^[9] zahrnující pole spin-1.

Alternativní ověření

Následuje alternativní ověření vzorce Sherman-Morrison pomocí snadno ověřitelné identity

{ displaystyle left (I + wv ^ { textyf {T}} doprava) ^ {- 1} = I - { frac {wv ^ { textyf {T}}} {1 + v ^ { textyf {T}} w}}}

.

Nechat

{ displaystyle u = Aw, quad { text {a}} quad A + uv ^ { textyf {T}} = A doleva (I + wv ^ { textyf {T}} doprava),}

pak

{ displaystyle left (A + uv ^ { textyf {T}} vpravo) ^ {- 1} = doleva (I + wv ^ { textyf {T}} vpravo) ^ {- 1} A ^ {-1} = left (I - { frac {wv ^ { textyf {T}}} {1 + v ^ { textyf {T}} w}} doprava) A ^ {- 1}}

.

Střídání ${ displaystyle w = A ^ {- 1} u}$ dává

{ displaystyle left (A + uv ^ { textyf {T}} vpravo) ^ {- 1} = vlevo (I - { frac {A ^ {- 1} uv ^ { textyf {T}} } {1 + v ^ { textyf {T}} A ^ {- 1} u}} vpravo) A ^ {- 1} = A ^ {- 1} - { frac {A ^ {- 1} uv ^ { textyf {T}} A ^ {- 1}} {1 + v ^ { textyf {T}} A ^ {- 1} u}}}

Zobecnění (Identita matice Woodburyho )

Vzhledem k tomu, že čtverec je invertibilní ${ displaystyle n krát n}$ matice ${ displaystyle A}$ , an ${ displaystyle n krát k}$ matice ${ displaystyle U}$ a ${ displaystyle k krát n}$ matice ${ displaystyle V}$ , nechť ${ displaystyle B}$ být ${ displaystyle n krát n}$ matice taková ${ displaystyle B = A + UV}$ . Pak za předpokladu ${ displaystyle left (I_ {k} + VA ^ {- 1} U right)}$ je invertibilní, máme