Identität der Woodbury-Matrix

Identität der Woodbury-Matrix (Umgeleitet von binomialem Umkehrsatz) Zur Navigation springen Zur Suche springen In der Mathematik (speziell lineare Algebra), die Woodbury-Matrix-Identität, benannt nach Max A. Woodbury,[1][2] sagt, dass die Umkehrung einer Rang-k-Korrektur einer Matrix berechnet werden kann, indem eine Rang-k-Korrektur an der Umkehrung der ursprünglichen Matrix durchgeführt wird. Alternative Namen für diese Formel sind das Matrixinversionslemma, Sherman-Morrison-Woodbury-Formel oder einfach nur Woodbury-Formel. Jedoch, Die Identität erschien in mehreren Zeitungen vor dem Woodbury-Bericht.[3][4] Die Identität der Woodbury-Matrix ist[5] {Anzeigestil links(A+UCVrechts)^{-1}=A^{-1}-A^{-1}Du bist gegangen(C^{-1}+VA^{-1}Du hast Recht)^{-1}VA^{-1},} wo ein, U, C und V sind konforme Matrizen: A ist n×n, C ist k×k, U ist n×k, und V ist k×n. Dies kann durch blockweise Matrixinversion abgeleitet werden.

Während die Identität hauptsächlich auf Matrizen verwendet wird, es hält in einem allgemeinen Ring oder in einer Ab-Kategorie.

Inhalt 1 Diskussion 1.1 Spezialfälle 1.1.1 Umkehrung einer Summe 1.2 Variationen 1.2.1 Binomialer Umkehrsatz 2 Ableitungen 2.1 Direkter Beweis 2.2 Alternative Beweise 3 Anwendungen 4 Siehe auch 5 Anmerkungen 6 External links Discussion To prove this result, Wir beginnen mit dem Beweis einer einfacheren. Ersetzen von A und C durch die Identitätsmatrix I, wir erhalten eine andere Identität, die etwas einfacher ist: {Anzeigestil links(I+UVrechts)^{-1}=I-Ulinks(I+VUrichtig)^{-1}v.} Um die ursprüngliche Gleichung aus dieser reduzierten Identität wiederherzustellen, einstellen {Anzeigestil U=A^{-1}X} und {Anzeigestil V=CY} .

Diese Identität selbst kann als Kombination von zwei einfacheren Identitäten angesehen werden. Wir erhalten die erste Identität von {Anzeigestil I=(I+P)^{-1}(I+P)=(I+P)^{-1}+(I+P)^{-1}P} , daher, {Anzeigestil (I+P)^{-1}=ich-(I+P)^{-1}P} , und ähnlich {Anzeigestil (I+P)^{-1}=I-P(I+P)^{-1}.} Die zweite Identität ist die sogenannte Push-Through-Identität[6] {Anzeigestil (I+UV)^{-1}U=U(I+VU)^{-1}} von denen wir beziehen {Anzeigestil U(I+VU)=(I+UV)U} nach Multiplikation mit {Anzeigestil (I+VU)^{-1}} rechts und daneben {Anzeigestil (I+UV)^{-1}} auf der Linken.

Special cases When {Anzeigestil V,U} sind Vektoren, die Identität reduziert sich auf die Sherman-Morrison-Formel.

Im Skalarfall ist es (die reduzierte Version) ist einfach {Anzeigestil {frac {1}{1+uv}}=1-{frac {uv}{1+uv}}.} Inverse of a sum If n = k and U = V = In is the identity matrix, dann {Anzeigestil {Start{ausgerichtet}links({EIN}+{B}Rechts)^{-1}&=A^{-1}-A^{-1}(B^{-1}+A^{-1})^{-1}A^{-1}\&={EIN}^{-1}-{EIN}^{-1}links({EIN}{B}^{-1}+{ich}Rechts)^{-1}.Ende{ausgerichtet}}} Das Fortsetzen der Verschmelzung der Terme auf der ganz rechten Seite der obigen Gleichung führt zu Huas Identität {Anzeigestil links({EIN}+{B}Rechts)^{-1}={EIN}^{-1}-links({EIN}+{EIN}{B}^{-1}{EIN}Rechts)^{-1}.} Eine weitere nützliche Form derselben Identität ist {Anzeigestil links({EIN}-{B}Rechts)^{-1}={EIN}^{-1}+{EIN}^{-1}{B}links({EIN}-{B}Rechts)^{-1},} die eine rekursive Struktur hat, die nachgibt {Anzeigestil links({EIN}-{B}Rechts)^{-1}= Summe _{k=0}^{unendlich }links({EIN}^{-1}{B}Rechts)^{k}{EIN}^{-1}.} Diese Form kann in Störungsentwicklungen verwendet werden, bei denen B eine Störung von A ist.

Variations Binomial inverse theorem If A, B, U, V sind Matrizen der Größen n×n, k×k, n×k, k×n, beziehungsweise, dann {Anzeigestil links(A+UBVrichtig)^{-1}=A^{-1}-A^{-1}UBlinks(B+BVA^{-1}UBrecht)^{-1}WEG^{-1}} A und B bereitgestellt + BVA−1UB sind nichtsingulär. Die Nichtsingularität des letzteren erfordert, dass B−1 existiert, da es gleich B ist(ich + VA−1UB) und der Rang des letzteren kann den Rang von B nicht überschreiten.[6] Da B invertierbar ist, die beiden B-Terme, die den eingeklammerten Größenumkehrer auf der rechten Seite flankieren, können durch ersetzt werden (B−1)−1, was zur ursprünglichen Woodbury-Identität führt.

Eine Variation, wenn B singulär und möglicherweise sogar nicht quadratisch ist:[6] {Anzeigestil (A+UBV)^{-1}=A^{-1}-A^{-1}U(I+BVA^{-1}U)^{-1}WEG^{-1}.} Formeln existieren auch für bestimmte Fälle, in denen A singulär ist.[7] Derivations Direct proof The formula can be proven by checking that {Anzeigestil (A+UCV)} mal seine angebliche Umkehrung auf der rechten Seite der Woodbury-Identität ergibt die Identitätsmatrix: {Anzeigestil {Start{ausgerichtet}&left(A+UCVrechts)links[A^{-1}-A^{-1}Du bist gegangen(C^{-1}+VA^{-1}Du hast Recht)^{-1}VA^{-1}Rechts]\={}&left{I-Ulinks(C^{-1}+VA^{-1}Du hast Recht)^{-1}VA^{-1}Rechts}+links{UCVA^{-1}-UCVA^{-1}Du bist gegangen(C^{-1}+VA^{-1}Du hast Recht)^{-1}VA^{-1}Rechts}\={}&left{Ich+UCVA^{-1}Rechts}-links{Du bist gegangen(C^{-1}+VA^{-1}Du hast Recht)^{-1}VA^{-1}+UCVA^{-1}Du bist gegangen(C^{-1}+VA^{-1}Du hast Recht)^{-1}VA^{-1}Rechts}\={}&I+UCVA^{-1}-links(U+UCVA^{-1}Du hast Recht)links(C^{-1}+VA^{-1}Du hast Recht)^{-1}VA^{-1}\={}&I+UCVA^{-1}-UClinks(C^{-1}+VA^{-1}Du hast Recht)links(C^{-1}+VA^{-1}Du hast Recht)^{-1}VA^{-1}\={}&I+UCVA^{-1}-UCVA^{-1}\={}&I.end{ausgerichtet}}} Alternative proofs show Algebraic proof show Derivation via blockwise elimination show Derivation from LDU decomposition Applications This identity is useful in certain numerical computations where A−1 has already been computed and it is desired to compute (EIN + UCV)−1. Mit dem Inversen von A verfügbar, it is only necessary to find the inverse of C−1 + VA−1U in order to obtain the result using the right-hand side of the identity. Wenn C eine viel kleinere Dimension als A hat, this is more efficient than inverting A + UCV directly. A common case is finding the inverse of a low-rank update A + UCV of A (wobei U nur wenige Spalten und V nur wenige Zeilen hat), or finding an approximation of the inverse of the matrix A + B where the matrix B can be approximated by a low-rank matrix UCV, zum Beispiel unter Verwendung der Singulärwertzerlegung.

Dies wird angewendet, z.B., im Kalman-Filter und rekursiven Verfahren der kleinsten Quadrate, um die parametrische Lösung zu ersetzen, erfordert eine Inversion einer Zustandsvektorgrößenmatrix, mit einer auf Bedingungsgleichungen basierenden Lösung. Im Falle des Kalman-Filters hat diese Matrix die Dimensionen des Beobachtungsvektors, d.h., so klein wie 1 falls jeweils nur eine neue Beobachtung verarbeitet wird. Dadurch werden die oft in Echtzeit durchgeführten Berechnungen des Filters erheblich beschleunigt.

Für den Fall, dass C die Identitätsmatrix I ist, die Matrix {Anzeigestil I+VA^{-1}U} ist in der numerischen linearen Algebra und den numerischen partiellen Differentialgleichungen als Kapazitätsmatrix bekannt.[4] Siehe auch Sherman-Morrison-Formel Schur-Komplement Matrixdeterminanten-Lemma, Formel für eine Rang-k-Aktualisierung einer Determinante Invertierbare Matrix Moore-Penrose-Pseudoinverse#Aktualisierung der Pseudoinversen Anmerkungen ^ Max A. Woodbury, Modifizierte Matrizen invertieren, Memorandum Rept. 42, Statistische Forschungsgruppe, Princeton Universität, Princeton, NJ, 1950, 4S. MR38136 ^ Max A. Woodbury, Die Stabilität von Ausgabe-Eingabe-Matrizen. Chicago, Krank., 1949. 5 pp. MR32564 ^ Guttmann, Ludwig (1946). "Erweiterungsmethoden zur Berechnung der inversen Matrix". Ann. Mathematik. Statist. 17 (3): 336–343. doi:10.1214/aoms/1177730946. ^ Nach oben springen: a b Hager, Wilhelm W. (1989). "Aktualisieren der Inversen einer Matrix". SIAM-Rezension. 31 (2): 221–239. doi:10.1137/1031049. JSTOR 2030425. HERR 0997457. ^ Hocham, Nikolaus (2002). Genauigkeit und Stabilität numerischer Algorithmen (2und Aufl.). SIAM. p. 258. ISBN 978-0-89871-521-7. HERR 1927606. ^ Nach oben springen: a b c Henderson, H. v.; Searle, S. R. (1981). "Über die Ableitung der Inversen einer Summe von Matrizen" (Pdf). SIAM-Rezension. 23 (1): 53–60. doi:10.1137/1023004. hdl:1813/32749. JSTOR 2029838. ^ Kurt S. Riedel, "Eine Sherman-Morrison-Woodbury-Identität für rangsteigernde Matrizen mit Anwendung auf Zentrierung", SIAM Journal über Matrixanalyse und Anwendungen, 13 (1992)659-662, doi:10.1137/0613040 Vordruck MR1152773 Press, WH; Teukolsky, an; Vetterling, WT; Flannerie, BP (2007), "Abschnitt 2.7.3. Woodbury-Formel", Numerische Rezepte: Die Kunst des wissenschaftlichen Rechnens (3Dr. Ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8 External links Some matrix identities Weisstein, Erich W. "Woodbury-Formel". MathWorld. Kategorien: Lemmata in der linearen AlgebraMatrizenMatrixtheorie