Identité de Woodbury

En mathématiques, plus précisément en algèbre linéaire, l'identité de Woodbury – du nom du mathématicien américain Max A. Woodbury ^[1] – dit que l'inverse d'une correction de rang k d'une matrice peut être calculée en effectuant 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, la formule de Sherman-Morrison-Woodbury ou simplement la formule de Woodbury. Cependant, l'identité est apparue dans plusieurs articles avant le rapport de Woodbury^[2]^,^[3].

L'identité de Woodbury est ^[4] $\left(A+UCV\right)^{-1}=A^{-1}-A^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1},$

où A, U, C et V sont des matrices conformes : A est carrée de taille n × n, C est carrée de taille k × k, U est n × k et V est k × n. Ceci peut être obtenu en utilisant le calcul d'inversion de matrice par blocs.

Bien que l'identité soit principalement utilisée sur les matrices, elle est valable dans un anneau général ou dans une catégorie Ab .

L'identité de Woodbury permet un calcul peu coûteux des inverses et des solutions aux équations linéaires. Cependant, on sait peu de choses sur la stabilité numérique de la formule. Il n’existe aucun résultat publié concernant ses limites d’erreur. Des preuves anecdotiques ^[5] suggèrent que cette différence peut être observée même pour des exemples apparemment simples (lorsque les matrices originales et modifiées sont bien conditionnées).

Discussion

Pour prouver ce résultat, on commence par en prouver un plus simple. En remplaçant A et C par la matrice identité I, on obtient une autre identité un peu plus simple : (I + UV)^-1 = I – U(I + VU)^-1V. Pour récupérer l'équation originale à partir de cette identité réduite, il suffit de remplacer U par A^-1U et V par CV.

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é à partir de $I=(I+P)^{-1}(I+P)=(I+P)^{-1}+(I+P)^{-1}P,$ ainsi, $(I+P)^{-1}=I-(I+P)^{-1}P,$ et de même $(I+P)^{-1}=I-P(I+P)^{-1}.$ La deuxième identité est ce qu'on appelle l'identité de passage ^[6] $(I+UV)^{-1}U=U(I+VU)^{-1}$ qu'on obtient en partant de l'égalité U(I + VU) = (I + UV)U après avoir multiplié par (I + VU)^-1 à droite et par (I + UV)^-1 à gauche.

En utilisant tous les résultats, $\left(I+UV\right)^{-1}=I-UV\left(I+UV\right)^{-1}=I-U\left(I+VU\right)^{-1}V.$ où la première et la deuxième égalité proviennent respectivement de la première et de la deuxième identité.

Cas particuliers

Quand V, U sont des vecteurs (k = 1), l'identité se réduit à la formule de Sherman-Morrison.

Dans le cas scalaire, la version réduite est simplement l'égalité : ${\frac {1}{1+uv}}=1-{\frac {uv}{1+vu}}.$

Inverse d'une somme

Si n = k et U = V = I_n est la matrice identité, alors

${\begin{aligned}\left(A+B\right)^{-1}&=A^{-1}-A^{-1}\left(B^{-1}+A^{-1}\right)^{-1}A^{-1}\\[1ex]&=A^{-1}-A^{-1}\left(AB^{-1}+{I}\right)^{-1}.\end{aligned}}$

En poursuivant la fusion des termes du côté le plus à droite de l'équation ci-dessus, on obtient l'Identité de Hua $\left({A}+{B}\right)^{-1}={A}^{-1}-\left({A}+{A}{B}^{-1}{A}\right)^{-1}.$

Une autre forme utile de la même identité est $\left({A}-{B}\right)^{-1}={A}^{-1}+{A}^{-1}{B}\left({A}-{B}\right)^{-1},$

qui, contrairement à celles ci-dessus, est valable même si B est singulière. Elle possède ainsi une écriture sous forme de série $\left({A}-{B}\right)^{-1}=\sum _{k=0}^{+\infty }\left({A}^{-1}{B}\right)^{k}{A}^{-1}$ vraie si le rayon spectral de A^-1B est inférieur à 1. Autrement dit, si la somme ci-dessus converge, elle est égale à (A – B)^-1.

Cette forme peut être utilisée dans les développements perturbatifs où B est une perturbation de A.

Variations

Théorème binomial inverse

Si A, B, U, V sont des matrices de tailles n × n, k × k, n × k, k × n, respectivement, alors $\left(A+UBV\right)^{-1}=A^{-1}-A^{-1}UB\left(B+BVA^{-1}UB\right)^{-1}BVA^{-1}$

à condition que A et B + BVA⁻¹UB ne soient pas singulières. La non-singularité de la deuxième nécessite que B⁻¹ existe puisqu'elle est égale à B(I + VA⁻¹UB) et le rang de cette dernière ne peut excéder le rang de B^[6].

Comme B est inversible, les deux termes B encadrant la quantité inverse entre parenthèses dans le côté droit peuvent être remplacés par (B⁻¹)⁻¹, ce qui permet de retrouver l'identité de Woodbury originale.

Une variante avec B singulière et voire même non carrée^[6]: $(A+UBV)^{-1}=A^{-1}-A^{-1}U(I+BVA^{-1}U)^{-1}BVA^{-1}.$

Il existe également des formules pour certains cas où A est singulière.

Pseudo-inverse avec matrices semi-définies positives

En général, l'identité de Woodbury n'est pas valide si une ou plusieurs des matrices inverses sont remplacées par des pseudo-inverses (de Moore-Penrose). Cependant, si $A$ et $C$ sont semi-définies positives, et $V=U^{*}$ (impliquant que $A+UCV$ est elle-même semi-définie positive), alors la formule suivante fournit une généralisation^[7]^,^[8]: ${\begin{aligned}\left(XX^{*}+YY^{*}\right)^{+}&=\left(ZZ^{*}\right)^{+}+\left(I-YZ^{+}\right)^{*}X^{+*}EX^{+}\left(I-YZ^{+}\right),\\Z&=\left(I-XX^{+}\right)Y,\\E&=I-X^{+}Y\left(I-Z^{+}Z\right)F^{-1}\left(X^{+}Y\right)^{*},\\F&=I+\left(I-Z^{+}Z\right)Y^{*}\left(XX^{*}\right)^{+}Y\left(I-Z^{+}Z\right),\end{aligned}}$

où $A+UCU^{*}$ peut être écrite comme $XX^{*}+YY^{*}$ car toute matrice semi-définie positive est égale à $MM^{*}$ pour certains $M$ .

Démonstrations

Preuve directe

La formule peut être prouvée en vérifiant que $(A+UCV)$ multiplié par son inverse présumé du côté droit de l'identité de Woodbury donne la matrice d'identité : ${\begin{aligned}&\left(A+UCV\right)\left[A^{-1}-A^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\right]\\={}&\left\{I-U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\right\}+\left\{UCVA^{-1}-UCVA^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\right\}\\={}&\left\{I+UCVA^{-1}\right\}-\left\{U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}+UCVA^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\right\}\\={}&I+UCVA^{-1}-\left(U+UCVA^{-1}U\right)\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\\={}&I+UCVA^{-1}-UC\left(C^{-1}+VA^{-1}U\right)\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\\={}&I+UCVA^{-1}-UCVA^{-1}\\={}&I.\end{aligned}}$

Preuves alternatives

Preuve algébrique

On utilise les égalités suivantes : ${\begin{aligned}U+UCVA^{-1}U&=UC\left(C^{-1}+VA^{-1}U\right)=\left(A+UCV\right)A^{-1}U\\\left(A+UCV\right)^{-1}UC&=A^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}\end{aligned}}$

Ainsi ${\begin{aligned}A^{-1}&=\left(A+UCV\right)^{-1}\left(A+UCV\right)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\right)^{-1}VA^{-1}.\end{aligned}}$

Par élimination par blocs

On considère le problème d'inversion de matrice suivant : ${\begin{bmatrix}A&U\\V&-C^{-1}\end{bmatrix}}{\begin{bmatrix}X\\Y\end{bmatrix}}={\begin{bmatrix}I\\0\end{bmatrix}}.$

Ce problème se réécrit sous la forme d'un système : ${\begin{cases}AX+UY=I\\VX-C^{-1}Y=0\end{cases}}$ ce qui permet d'établir $(A+UCV)X=I$ . En éliminant la première équation, on obtient $X=A^{-1}(I-UY)$ , ce qui permet de réécrire la deuxième pour avoir $VA^{-1}(I-UY)=C^{-1}Y$ . En développant et réarrangeant, on a $VA^{-1}=\left(C^{-1}+VA^{-1}U\right)Y$ , ou $\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}=Y$ . Enfin, on substitue dans la première équation d'origine $AX+UY=I$ , ce qui permet d'écrire $AX+U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}=I$ . et de conclure :

(A+UCV)^{-1}=X=A^{-1}-A^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}.

Par décomposition LDU

On considère la matrice ${\begin{bmatrix}A&U\\V&C\end{bmatrix}}$ En éliminant le bloc inférieur gauche (comme A est inversible) on a ${\begin{bmatrix}I&0\\-VA^{-1}&I\end{bmatrix}}{\begin{bmatrix}A&U\\V&C\end{bmatrix}}={\begin{bmatrix}A&U\\0&C-VA^{-1}U\end{bmatrix}}$

De même, éliminer le bloc supérieur droit donne : ${\begin{bmatrix}A&U\\V&C\end{bmatrix}}{\begin{bmatrix}I&-A^{-1}U\\0&I\end{bmatrix}}={\begin{bmatrix}A&0\\V&C-VA^{-1}U\end{bmatrix}}$

Ainsi, en combinant, on a : ${\begin{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}}$

Moving to the right side gives ${\begin{bmatrix}A&U\\V&C\end{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}}$ ce qui donne la décomposition LDU par blocs de la matrice d'origine.

Par inversion, on a : ${\begin{aligned}{\begin{bmatrix}A&U\\V&C\end{bmatrix}}^{-1}&={\begin{bmatrix}I&A^{-1}U\\0&I\end{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\right)^{-1}VA^{-1}&\left(C-VA^{-1}U\right)^{-1}\end{bmatrix}}\qquad \mathrm {(1)} \end{aligned}}$

En procédant de façon similaire mais en utilisant le fait que C est inversible, on obtient : ${\begin{bmatrix}A&U\\V&C\end{bmatrix}}={\begin{bmatrix}I&UC^{-1}\\0&I\end{bmatrix}}{\begin{bmatrix}A-UC^{-1}V&0\\0&C\end{bmatrix}}{\begin{bmatrix}I&0\\C^{-1}V&I\end{bmatrix}}$

Ce qui donne par inversion ${\begin{aligned}{\begin{bmatrix}A&U\\V&C\end{bmatrix}}^{-1}&={\begin{bmatrix}I&0\\C^{-1}V&I\end{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\right)^{-1}UC^{-1}\\-C^{-1}V\left(A-UC^{-1}V\right)^{-1}&C^{-1}+C^{-1}V\left(A-UC^{-1}V\right)^{-1}UC^{-1}\end{bmatrix}}\qquad \mathrm {(2)} \end{aligned}}$

Par identification par blocs, les deux blocs supérieurs gauches donnent l'identité de Woodbury.

Applications

Ceci est appliqué, par exemple, dans le filtre de Kalman et les méthodes des moindres carrés récursifs, pour remplacer la solution paramétrique, nécessitant l'inversion d'une matrice de taille de vecteur d'état, par 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 petite 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 $I+VA^{-1}U$ 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é^[3].

Voir aussi

Formule de Sherman-Morrison
Complément de Schur
Lemme du déterminant de la matrice, formule pour une mise à jour de rang k d'un déterminant
Matrice inversible
Pseudo-inverse de Moore-Penrose

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Woodbury matrix identity » (voir la liste des auteurs).

↑ (en) Max A. Woodbury, Inverting modified matrices, Memorandum Rept. 42, Statistical Research Group, Princeton University, Princeton, NJ, 1950, 4pp lien Math Reviews
↑ (en) Louis Guttmann, « Enlargement methods for computing the inverse matrix », Ann. Math. Statist., vol. 17, n^o 3,‎ 1946, p. 336–343 (DOI 10.1214/aoms/1177730946)
↑ ^{a et b} (en) William W. Hager, « Updating the inverse of a matrix », SIAM Review, vol. 31, n^o 2,‎ 1989, p. 221–239 (DOI 10.1137/1031049, JSTOR 2030425, MR 997457)
↑ (en) Nicholas Higham, Accuracy and Stability of Numerical Algorithms, 2nd, 2002 (ISBN 978-0-89871-521-7, MR 1927606, lire en ligne ), 258
↑ (en) « Special considerations when using the Woodbury matrix identity numerically », MathOverflow
↑ ^{a b et c} (en) H. V. Henderson et S. R. Searle, « On deriving the inverse of a sum of matrices », SIAM Review, vol. 23, n^o 1,‎ 1981, p. 53–60 (DOI 10.1137/1023004, JSTOR 2029838, hdl 1813/32749, lire en ligne)
↑ (en) Dennis S. Bernstein, Scalar, Vector, and Matrix Mathematics: Theory, Facts, and Formulas, Princeton, Revised and expanded, 2018 (ISBN 9780691151205), p. 638
↑ (en) James R. Schott, Matrix analysis for statistics, Hoboken, New Jersey, Third, 2017 (ISBN 9781119092483), p. 219

(en) WH Press, SA Teukolsky, WT Vetterling et BP Flannery, Numerical Recipes: The Art of Scientific Computing, New York, Cambridge University Press, 2007 (ISBN 978-0-521-88068-8), « Section 2.7.3. Woodbury Formula »

Liens externes

(en) Matrix Identities
(en) Eric W. Weisstein, « Woodbury Formula », sur MathWorld

Portail de l’algèbre

Dernière mise à jour du contenu le 06/12/2024.

Droit d'auteur : le texte de l'article est disponible sous la licence CC BY-SA 3.0.
Les détails concernant les licences et crédits des images sont disponibles en cliquant sur l'image.

Le site Wikimonde est un agrégateur d'articles encyclopédiques, il n'est pas à l'origine du contenu des articles, ni des images.

Le contenu de cet article est une copie de l'article d'origine (//fr.wikipedia.org/wiki/Identit%C3%A9_de_Woodbury) publié sur Wikipédia (wiki collaboratif publié sous licence libre).
Le contenu des articles n'est pas garanti.
Le texte des articles n'est pas modifié par Wikimonde. Des modifications mineures de mise en page et des liens internes (pour faciliter la navigation) peuvent être effectués automatiquement.

Des crédits concernant les images peuvent être ajoutés automatiquement selon les informations fournis par le site d'origine.
Les images sont chargées depuis des sites externes, certaines peuvent ne pas s'afficher.

Auteurs de cet article « Identité de Woodbury » :

WikiCleanerBot, Kelam, RobokoBot.

[1] (en) Max A. Woodbury, Inverting modified matrices, Memorandum Rept. 42, Statistical Research Group, Princeton University, Princeton, NJ, 1950, 4pp lien Math Reviews

[guttman-2] (en) Louis Guttmann, « Enlargement methods for computing the inverse matrix », Ann. Math. Statist., vol. 17, n^o 3,‎ 1946, p. 336–343 (DOI 10.1214/aoms/1177730946)

[hager-3] {a et b} (en) William W. Hager, « Updating the inverse of a matrix », SIAM Review, vol. 31, n^o 2,‎ 1989, p. 221–239 (DOI 10.1137/1031049, JSTOR 2030425, MR 997457)

[higham-4] (en) Nicholas Higham, Accuracy and Stability of Numerical Algorithms, 2nd, 2002 (ISBN 978-0-89871-521-7, MR 1927606, lire en ligne ), 258

[5] (en) « Special considerations when using the Woodbury matrix identity numerically », MathOverflow

[HS-6] {a b et c} (en) H. V. Henderson et S. R. Searle, « On deriving the inverse of a sum of matrices », SIAM Review, vol. 23, n^o 1,‎ 1981, p. 53–60 (DOI 10.1137/1023004, JSTOR 2029838, hdl 1813/32749, lire en ligne)

[7] (en) Dennis S. Bernstein, Scalar, Vector, and Matrix Mathematics: Theory, Facts, and Formulas, Princeton, Revised and expanded, 2018 (ISBN 9780691151205), p. 638

[8] (en) James R. Schott, Matrix analysis for statistics, Hoboken, New Jersey, Third, 2017 (ISBN 9781119092483), p. 219

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]