Identité de Woodbury

En mathématiques, plus précisément en algèbre linéaire, lModèle:'identité de Woodbury – du nom du mathématicien américain Max A. Woodbury – 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 WoodburyModèle:,.

L'identité de Woodbury est $${(A+UCV)}^{-1}=A^{-1}-A^{-1}U{(C^{-1}+V{A}^{-1}U)}^{-1}V{A}^{-1},$$

où A, U, C et V sont des matrices conformes : A est carrée de taille Modèle:Nobr, C est carrée de taille Modèle:Nobr, U est Modèle:Nobr et V est Modèle:Nobr. 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 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 : Modèle:Nobr. Pour récupérer l'équation originale à partir de cette identité réduite, il suffit de remplacer U par Modèle:Nobr 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 $$(I+UV{)}^{-1}U=U(I+VU{)}^{-1}$$ qu'on obtient en partant de l'égalité Modèle:Nobr après avoir multiplié par Modèle:Nobr à droite et par Modèle:Nobr à gauche.

En utilisant tous les résultats, $${(I+UV)}^{-1}=I-UV{(I+UV)}^{-1}=I-U{(I+VU)}^{-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 (Modèle:Nobr), 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 Modèle:Nobr et Modèle:Nobr est la matrice identité, alors

$$\begin{array}{cc}{(A+B)}^{-1}& =A^{-1}-A^{-1}{(B^{-1}+A^{-1})}^{-1}{A}^{-1}\\ & =A^{-1}-A^{-1}{(A{B}^{-1}+I)}^{-1}.\end{array}$$

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

Une autre forme utile de la même identité est $${(A-B)}^{-1}=A^{-1}+A^{-1}B{(A-B)}^{-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 $${(A-B)}^{-1}=\sum _{k=0}^{+\mathrm{\infty }}{\left(A^{-1}B\right)}^k{A}^{-1}$$vraie si le rayon spectral de AModèle:ExpB est inférieur à 1. Autrement dit, si la somme ci-dessus converge, elle est égale à (A – B)Modèle:Exp.

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 Modèle:Nobr, Modèle:Nobr, Modèle:Nobr, Modèle:Nobr, respectivement, alors $${(A+UBV)}^{-1}=A^{-1}-A^{-1}UB{(B+BV{A}^{-1}UB)}^{-1}BV{A}^{-1}$$

à condition que A et Modèle:Nobr ne soient pas singulières. La non-singularité de la deuxième nécessite que B⁻¹ existe puisqu'elle est égale à Modèle:Nobr et le rang de cette dernière ne peut excéder le rang de B.

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 Modèle:Nobr, ce qui permet de retrouver l'identité de Woodbury originale.

Une variante avec B singulière et voire même non carrée: $$(A+UBV{)}^{-1}=A^{-1}-A^{-1}U(I+BV{A}^{-1}U{)}^{-1}BV{A}^{-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éralisationModèle:,: $$\begin{array}{cc}{(X{X}^{*}+Y{Y}^{*})}^{+}& ={\left(Z{Z}^{*}\right)}^{+}+{(I-Y{Z}^{+})}^{*}{X}^{+*}E{X}^{+}(I-Y{Z}^{+}),\\ Z& =(I-X{X}^{+})Y,\\ E& =I-X^{+}Y(I-Z^{+}Z)F^{-1}{\left(X^{+}Y\right)}^{*},\\ F& =I+(I-Z^{+}Z)Y^{*}{\left(X{X}^{*}\right)}^{+}Y(I-Z^{+}Z),\end{array}$$

où $A+UC{U}^{*}$ peut être écrite comme $X{X}^{*}+Y{Y}^{*}$ car toute matrice semi-définie positive est égale à $M{M}^{*}$ 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{array}{cc}& (A+UCV)[A^{-1}-A^{-1}U{(C^{-1}+V{A}^{-1}U)}^{-1}V{A}^{-1}]\\ =& \{I-U{(C^{-1}+V{A}^{-1}U)}^{-1}V{A}^{-1}\}+\{UCV{A}^{-1}-UCV{A}^{-1}U{(C^{-1}+V{A}^{-1}U)}^{-1}V{A}^{-1}\}\\ =& \{I+UCV{A}^{-1}\}-\{U{(C^{-1}+V{A}^{-1}U)}^{-1}V{A}^{-1}+UCV{A}^{-1}U{(C^{-1}+V{A}^{-1}U)}^{-1}V{A}^{-1}\}\\ =& I+UCV{A}^{-1}-(U+UCV{A}^{-1}U){(C^{-1}+V{A}^{-1}U)}^{-1}V{A}^{-1}\\ =& I+UCV{A}^{-1}-UC(C^{-1}+V{A}^{-1}U){(C^{-1}+V{A}^{-1}U)}^{-1}V{A}^{-1}\\ =& I+UCV{A}^{-1}-UCV{A}^{-1}\\ =& I.\end{array}$$

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+V{A}^{-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é.

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

• Modèle:Ouvrage

Liens externes

• Modèle:En Matrix Identities
• Modèle:Mathworld