Identità della matrice di Woodbury

Identità della matrice di Woodbury (Reindirizzato da Teorema inverso binomiale) Vai alla navigazione Vai alla ricerca In matematica (in particolare algebra lineare), l'identità della matrice di Woodbury, intitolato a Max A. Woodbury,[1][2] dice che l'inverso di una correzione di rango k di una matrice può essere calcolato eseguendo una correzione di rango k all'inverso della matrice originale. Nomi alternativi per questa formula sono il lemma di inversione di matrice, Formula Sherman–Morrison–Woodbury o semplicemente formula Woodbury. Tuttavia, l'identità è apparsa in diversi giornali prima del rapporto Woodbury.[3][4] L'identità della matrice di Woodbury è[5] {stile di visualizzazione a sinistra(A+UCVdiritto)^{-1}=A^{-1}-A^{-1}Uleft(C^{-1}+VA^{-1}Hai ragione)^{-1}VA^{-1},} dove un, u, C e V sono matrici conformabili: A è n×n, C è k × k, U è n×k, e V è k×n. Questo può essere derivato usando l'inversione di matrice a blocchi.

Mentre l'identità viene utilizzata principalmente sulle matrici, tiene in un anello generale o in una categoria Ab.

Contenuti 1 Discussione 1.1 Casi speciali 1.1.1 Inverso di una somma 1.2 Variazioni 1.2.1 Teorema inverso binomiale 2 Derivazioni 2.1 Prova diretta 2.2 Dimostrazioni alternative 3 Applicazioni 4 Guarda anche 5 Appunti 6 Collegamenti esterni Discussione Per dimostrare questo risultato, inizieremo dimostrandone uno più semplice. Sostituzione di A e C con la matrice identità I, otteniamo un'altra identità un po' più semplice: {stile di visualizzazione a sinistra(I+UVdestra)^{-1}=Io-Uleft(I+VUdestra)^{-1}V.} Per recuperare l'equazione originaria da questa identità ridotta, impostare {stile di visualizzazione U=A^{-1}X} e {stile di visualizzazione V=CY} .

Questa stessa identità può essere vista come la combinazione di due identità più semplici. Otteniamo la prima identità da {stile di visualizzazione I=(I+P)^{-1}(I+P)=(I+P)^{-1}+(I+P)^{-1}P} , così, {stile di visualizzazione (I+P)^{-1}=Io-(I+P)^{-1}P} , e similmente {stile di visualizzazione (I+P)^{-1}= I-P(I+P)^{-1}.} La seconda identità è la cosiddetta identità push-through[6] {stile di visualizzazione (I+UV)^{-1}U=U(I+VU)^{-1}} da cui otteniamo {stile di visualizzazione U(I+VU)=(I+UV)u} dopo aver moltiplicato per {stile di visualizzazione (I+VU)^{-1}} a destra e vicino {stile di visualizzazione (I+UV)^{-1}} sulla sinistra.

Casi speciali Quando {stile di visualizzazione V,u} sono vettori, l'identità si riduce alla formula Sherman-Morrison.

Nel caso scalare esso (la versione ridotta) è semplicemente {stile di visualizzazione {frac {1}{1+uv}}=1-{frac {uv}{1+uv}}.} Inversa di una somma Se n = k e U = V = In è la matrice identità, poi {stile di visualizzazione {inizio{allineato}sinistra({UN}+{B}Giusto)^{-1}&=A^{-1}-A^{-1}(B^{-1}+A^{-1})^{-1}A^{-1}\&={UN}^{-1}-{UN}^{-1}sinistra({UN}{B}^{-1}+{io}Giusto)^{-1}.fine{allineato}}} Continuando con la fusione dei termini dell'estrema destra dell'equazione sopra si ottiene l'identità di Hua {stile di visualizzazione a sinistra({UN}+{B}Giusto)^{-1}={UN}^{-1}-sinistra({UN}+{UN}{B}^{-1}{UN}Giusto)^{-1}.} Un'altra forma utile della stessa identità è {stile di visualizzazione a sinistra({UN}-{B}Giusto)^{-1}={UN}^{-1}+{UN}^{-1}{B}sinistra({UN}-{B}Giusto)^{-1},} che ha una struttura ricorsiva che cede {stile di visualizzazione a sinistra({UN}-{B}Giusto)^{-1}=somma _{k=0}^{infty }sinistra({UN}^{-1}{B}Giusto)^{K}{UN}^{-1}.} Questa forma può essere utilizzata nelle espansioni perturbative in cui B è una perturbazione di A.

Variazioni Teorema inverso binomiale Se A, B, u, V sono matrici di dimensioni n×n, k × k, n×k, k × n, rispettivamente, poi {stile di visualizzazione a sinistra(A+UBVdestra)^{-1}=A^{-1}-A^{-1}UBa sinistra(B+BVA^{-1}UBgiusto)^{-1}LONTANO^{-1}} fornito A e B + BVA−1UB non sono singolari. La non singolarità di quest'ultimo richiede che B−1 esista poiché è uguale a B(io + VA-1UB) e il grado di quest'ultimo non può eccedere il grado di B.[6] Poiché B è invertibile, i due termini B che fiancheggiano la quantità tra parentesi inversa a destra possono essere sostituiti con (B-1)-1, che si traduce nell'identità originale di Woodbury.

Una variazione per quando B è singolare e forse anche non quadrato:[6] {stile di visualizzazione (A+UBV)^{-1}=A^{-1}-A^{-1}u(Io+BVA^{-1}u)^{-1}LONTANO^{-1}.} Esistono anche formule per alcuni casi in cui A è singolare.[7] Derivazioni Dimostrazione diretta La formula può essere dimostrata controllando che {stile di visualizzazione (A+UCV)} volte il suo presunto inverso sul lato destro dell'identità di Woodbury fornisce la matrice dell'identità: {stile di visualizzazione {inizio{allineato}&left(A+UCVdiritto)sinistra[A^{-1}-A^{-1}Uleft(C^{-1}+VA^{-1}Hai ragione)^{-1}VA^{-1}Giusto]\={}&left{Io-Uleft(C^{-1}+VA^{-1}Hai ragione)^{-1}VA^{-1}Giusto}+sinistra{UCVA^{-1}-UCVA^{-1}Uleft(C^{-1}+VA^{-1}Hai ragione)^{-1}VA^{-1}Giusto}\={}&left{I+UCVA^{-1}Giusto}-sinistra{Uleft(C^{-1}+VA^{-1}Hai ragione)^{-1}VA^{-1}+UCVA^{-1}Uleft(C^{-1}+VA^{-1}Hai ragione)^{-1}VA^{-1}Giusto}\={}&I+UCVA^{-1}-sinistra(U+UCVA^{-1}Hai ragione)sinistra(C^{-1}+VA^{-1}Hai ragione)^{-1}VA^{-1}\={}&I+UCVA^{-1}-UCsinistra(C^{-1}+VA^{-1}Hai ragione)sinistra(C^{-1}+VA^{-1}Hai ragione)^{-1}VA^{-1}\={}&I+UCVA^{-1}-UCVA^{-1}\={}&I.end{allineato}}} Dimostrazioni alternative show Dimostrazione algebrica show Derivazione tramite eliminazione a blocchi show Derivazione dalla decomposizione LDU Applicazioni Questa identità è utile in alcuni calcoli numerici in cui A−1 è già stato calcolato e si desidera calcolare (UN + UCV)-1. Con l'inverso di A disponibile, basta trovare l'inversa di C−1 + VA−1U per ottenere il risultato utilizzando il lato destro dell'identità. Se C ha una dimensione molto più piccola di A, questo è più efficiente dell'inversione di A + UCV direttamente. Un caso comune è trovare l'inverso di un aggiornamento di basso rango A + UCV di A (dove U ha solo poche colonne e V solo poche righe), o trovare un'approssimazione dell'inverso della matrice A + B dove la matrice B può essere approssimata da una matrice di basso rango UCV, ad esempio utilizzando la scomposizione del valore singolare.

Questo è applicato, per esempio., nel filtro di Kalman e nei metodi ricorsivi dei minimi quadrati, per sostituire la soluzione parametrica, che richiede l'inversione di una matrice delle dimensioni di un vettore di stato, con una soluzione basata su equazioni di condizione. Nel caso del filtro di Kalman questa matrice ha le dimensioni del vettore delle osservazioni, cioè., piccolo quanto 1 nel caso in cui venga elaborata una sola nuova osservazione alla volta. Ciò accelera notevolmente i calcoli spesso in tempo reale del filtro.

Nel caso in cui C sia la matrice identità I, la matrice {stile di visualizzazione I+VA^{-1}u} è noto nell'algebra lineare numerica e nelle equazioni alle derivate parziali numeriche come matrice di capacità.[4] Si veda anche la formula di Sherman-Morrison complemento di Schur lemma determinante della matrice, formula per un aggiornamento di rango k a un determinante Matrice invertibile Moore–Penrose pseudoinversa#Aggiornamento della pseudoinversa Note ^ Max A. Woodbury, Inversione di matrici modificate, Memorandum Rept. 42, Gruppo di ricerca statistica, università di Princeton, Princeton, NJ, 1950, 4pp MR38136 ^ Max A. Woodbury, La stabilità delle matrici Out-Input. Chicago, Malato., 1949. 5 pp. MR32564 ^ Guttmann, Louis (1946). "Metodi di ingrandimento per il calcolo della matrice inversa". Anna. Matematica. Statista. 17 (3): 336–343. doi:10.1214/aoms/1177730946. ^ Salta su: a b Hager, William W. (1989). "Aggiornamento dell'inverso di una matrice". Recensione SIAM. 31 (2): 221–239. doi:10.1137/1031049. JSTOR 2030425. SIG 0997457. ^ Higham, Nicola (2002). Precisione e stabilità degli algoritmi numerici (2nd ed.). SIAM. p. 258. ISBN 978-0-89871-521-7. SIG 1927606. ^ Salta su: a b c Henderson, H. V.; Searle, S. R. (1981). "Sulla derivazione dell'inverso di una somma di matrici" (PDF). Recensione SIAM. 23 (1): 53–60. doi:10.1137/1023004. hdl:1813/32749. JSTOR 2029838. ^ Kurt S. Riedel, "Un'identità Sherman-Morrison-Woodbury per matrici di aumento di grado con applicazione al centraggio", Giornale SIAM sull'analisi e le applicazioni della matrice, 13 (1992)659-662, doi:10.1137/0613040 prestampa MR1152773 Stampa, WH; Teukolsky, Su; Vetterling, WT; Flannero, BP (2007), "Sezione 2.7.3. Formula di Woodbury", Ricette Numeriche: L'arte del calcolo scientifico (33a ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8 Collegamenti esterni Alcune identità di matrice Weisstein, Eric W. "Formula Woodbury". Math World. Categorie: Lemmi in algebra lineareMatriciTeoria delle matrici