# 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 – 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$^,$.
L'identité de Woodbury est $\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 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)$^{-1}$V. Pour récupérer l'équation originale à partir de cette identité réduite, il suffit de remplacer U par A$^{-1}$U 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é 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 (en) $\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$^{-1}$B 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$^{−1}$UB ne soient pas singulières. La non-singularité de la deuxième nécessite que B$^{−1}$ existe puisqu'elle est égale à B(I + VA$^{−1}$UB) 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 (B$^{−1}$)$^{−1}$, 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+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$^,$: ${\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

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}}$
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}.$
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é.