Identité de la matrice de Woodbury

Identité de la matrice de Woodbury (Redirigé à partir du théorème inverse binomial) Aller à la navigation Aller à la recherche En mathématiques (algèbre spécifiquement linéaire), l'identité de la matrice de Woodbury, nommé d'après Max A. Woodbury,[1][2] dit que l'inverse d'une correction de rang-k d'une certaine matrice peut être calculé en faisant une correction de rang-k à l'inverse de la matrice d'origine. Les noms alternatifs pour cette formule sont le lemme d'inversion de matrice, Formule Sherman – Morrison – Woodbury ou simplement formule de Woodbury. Cependant, l'identité est apparue dans plusieurs journaux avant le rapport Woodbury.[3][4] L'identité de la matrice de Woodbury est[5] {style d'affichage à gauche(A+UCVdroit)^{-1}=A^{-1}-Un ^{-1}Ugauche(C^{-1}+VA^{-1}Tu as raison)^{-1}VA^{-1},} où un, tu, C et V sont des matrices conformes: A est n×n, C est k×k, U est n×k, et V est k×n. Cela peut être dérivé en utilisant l'inversion de matrice par blocs.

Alors que l'identité est principalement utilisée sur les matrices, il tient dans un anneau général ou dans une catégorie Ab.

Contenu 1 Discussion 1.1 Cas spéciaux 1.1.1 Inverse d'une somme 1.2 Variantes 1.2.1 Théorème inverse binomial 2 Dérivations 2.1 Preuve directe 2.2 Preuves alternatives 3 Applications 4 Voir également 5 Remarques 6 External links Discussion To prove this result, nous allons commencer par en prouver une plus simple. Remplacer A et C par la matrice identité I, on obtient une autre identité un peu plus simple: {style d'affichage à gauche(I+UVright)^{-1}=I-Ugauche(I+VUdroit)^{-1}V} Pour retrouver l'équation originale à partir de cette identité réduite, Positionner {style d'affichage U=A^{-1}X} et {style d'affichage V=CY} .

Cette identité elle-même peut être considérée comme la combinaison de deux identités plus simples. On obtient la première identité de {style d'affichage I=(Je+P)^{-1}(Je+P)=(Je+P)^{-1}+(Je+P)^{-1}P} , Donc, {style d'affichage (Je+P)^{-1}=je-(Je+P)^{-1}P} , et de même {style d'affichage (Je+P)^{-1}=I-P(Je+P)^{-1}.} La deuxième identité est l'identité dite push-through[6] {style d'affichage (I+UV)^{-1}U=U(I+VU)^{-1}} que nous obtenons de {style d'affichage U(I+VU)=(I+UV)tu} après avoir multiplié par {style d'affichage (I+VU)^{-1}} à droite et par {style d'affichage (I+UV)^{-1}} à gauche.

Special cases When {style d'affichage V,tu} sont des vecteurs, l'identité se réduit à la formule Sherman-Morrison.

Dans le cas scalaire, il (la version réduite) est simplement {style d'affichage {frac {1}{1+UV}}=1-{frac {UV}{1+UV}}.} Inverse of a sum If n = k and U = V = In is the identity matrix, alors {style d'affichage {commencer{aligné}la gauche({UN}+{B}droit)^{-1}&=A^{-1}-Un ^{-1}(B^{-1}+Un ^{-1})^{-1}Un ^{-1}\&={UN}^{-1}-{UN}^{-1}la gauche({UN}{B}^{-1}+{je}droit)^{-1}.fin{aligné}}} En continuant avec la fusion des termes de l'extrême droite de l'équation ci-dessus, on obtient l'identité de Hua {style d'affichage à gauche({UN}+{B}droit)^{-1}={UN}^{-1}-la gauche({UN}+{UN}{B}^{-1}{UN}droit)^{-1}.} Une autre forme utile de la même identité est {style d'affichage à gauche({UN}-{B}droit)^{-1}={UN}^{-1}+{UN}^{-1}{B}la gauche({UN}-{B}droit)^{-1},} qui a une structure récursive qui donne {style d'affichage à gauche({UN}-{B}droit)^{-1}=somme _{k=0}^{infime }la gauche({UN}^{-1}{B}droit)^{k}{UN}^{-1}.} Cette forme peut être utilisée dans les développements perturbatifs où B est une perturbation de A.

Variations Binomial inverse theorem If A, B, tu, V sont des matrices de tailles n×n, k×k, n×k, k×n, respectivement, alors {style d'affichage à gauche(A+UBVdroit)^{-1}=A^{-1}-Un ^{-1}UBgauche(B+BVA^{-1}UBright)^{-1}LOIN ^{-1}} fourni A et B + BVA−1UB ne sont pas singuliers. La non-singularité de ce dernier nécessite que B−1 existe puisqu'il est égal à B(je + VA−1UB) et le rang de ce dernier ne peut excéder le rang de B.[6] Puisque B est inversible, les deux termes B encadrant la quantité entre parenthèses inverse dans le membre de droite peuvent être remplacés par (B−1)−1, ce qui donne l'identité originale de Woodbury.

Une variation pour quand B est singulier et peut-être même non carré:[6] {style d'affichage (A+UBV)^{-1}=A^{-1}-Un ^{-1}tu(I+BVA^{-1}tu)^{-1}LOIN ^{-1}.} Des formules existent aussi pour certains cas où A est singulier.[7] Derivations Direct proof The formula can be proven by checking that {style d'affichage (A+UCV)} fois son prétendu inverse sur le côté droit de l'identité de Woodbury donne la matrice d'identité: {style d'affichage {commencer{aligné}&left(A+UCVdroit)la gauche[Un ^{-1}-Un ^{-1}Ugauche(C^{-1}+VA^{-1}Tu as raison)^{-1}VA^{-1}droit]\={}&left{I-Uleft(C^{-1}+VA^{-1}Tu as raison)^{-1}VA^{-1}droit}+la gauche{UVC^{-1}-UVC^{-1}Ugauche(C^{-1}+VA^{-1}Tu as raison)^{-1}VA^{-1}droit}\={}&left{I+UCVA^{-1}droit}-la gauche{Ugauche(C^{-1}+VA^{-1}Tu as raison)^{-1}VA^{-1}+UVC^{-1}Ugauche(C^{-1}+VA^{-1}Tu as raison)^{-1}VA^{-1}droit}\={}&I+UCVA^{-1}-la gauche(U+UCVA^{-1}Tu as raison)la gauche(C^{-1}+VA^{-1}Tu as raison)^{-1}VA^{-1}\={}&I+UCVA^{-1}-UCgauche(C^{-1}+VA^{-1}Tu as raison)la gauche(C^{-1}+VA^{-1}Tu as raison)^{-1}VA^{-1}\={}&I+UCVA^{-1}-UVC^{-1}\={}&I.end{aligné}}} 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 (UN + UCV)−1. Avec l'inverse de A disponible, 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. Si C a une dimension beaucoup plus petite que A, 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 (où U n'a que quelques colonnes et V seulement quelques lignes), 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, par exemple en utilisant la décomposition en valeurs singulières.

Ceci est appliqué, par exemple., dans le filtre de Kalman et les méthodes récursives des moindres carrés, pour remplacer la solution paramétrique, nécessitant l'inversion d'une matrice de la taille d'un vecteur d'état, avec une solution basée sur des équations de condition. Dans le cas du filtre de Kalman cette matrice a les dimensions du vecteur d'observations, c'est à dire., aussi petit que 1 dans le cas où une seule nouvelle observation est traitée à la fois. Cela accélère considérablement les calculs souvent en temps réel du filtre.

Dans le cas où C est la matrice identité I, la matrice {style d'affichage I+VA^{-1}tu} est connue dans l'algèbre linéaire numérique et les équations aux dérivées partielles numériques sous le nom de matrice de capacité.[4] Voir aussi Formule de Sherman-Morrison Complément de Schur Lemme déterminant de la matrice, formule pour une mise à jour de rang k d'un déterminant Matrice inversible Moore – Penrose pseudoinverse # Mise à jour de la pseudoinverse Notes ^ Max A. Woodbury, Inversion de matrices modifiées, Rapport de mémorandum. 42, Groupe de recherche statistique, université de Princeton, Princeton, New Jersey, 1950, 4pp MR38136 ^ Max A. Woodbury, La stabilité des matrices de sortie-entrée. Chicago, Malade., 1949. 5 pp. MR32564 ^ Guttman, Louis (1946). "Méthodes d'agrandissement pour le calcul de la matrice inverse". Anne. Math. Statiste. 17 (3): 336–343. est ce que je:10.1214/aoms/1177730946. ^ Sauter à: a b Hager, Guillaume W. (1989). "Mise à jour de l'inverse d'une matrice". Examen SIAM. 31 (2): 221–239. est ce que je:10.1137/1031049. JSTOR 2030425. M 0997457. ^ Higham, Nicolas (2002). Précision et stabilité des algorithmes numériques (2sd éd.). SIAM. p. 258. ISBN 978-0-89871-521-7. M 1927606. ^ Sauter à: a b c Henderson, H. V; Searle, S. R. (1981). "Sur la dérivation de l'inverse d'une somme de matrices" (PDF). Examen SIAM. 23 (1): 53–60. est ce que je:10.1137/1023004. hdl:1813/32749. JSTOR 2029838. ^ Kurt S. Riedel, "Une identité Sherman – Morrison – Woodbury pour les matrices d'augmentation de rang avec application au centrage", SIAM Journal sur l'analyse matricielle et les applications, 13 (1992)659-662, est ce que je:10.1137/0613040 preprint MR1152773 Presse, WH; Teukolski, sur; Vetterling, WT; Flannerie, BP (2007), "Section 2.7.3. Formule de Woodbury", Recettes numériques: L'art du calcul scientifique (3e éd.), New York: la presse de l'Universite de Cambridge, ISBN 978-0-521-88068-8 External links Some matrix identities Weisstein, Eric W. "Formule de Woodbury". MathWorld. Catégories: Lemmes en algèbre linéaireMatricesThéorie des matrices