Formule de Sherman-Morrison

En algèbre linéaire, la formule de Sherman-Morrison, nommée d'après Jack Sherman et Winifred J. Morrison, calcule l'inverse d'une « mise à jour de rang -1 » d'une matrice dont l'inverse a été précédemment calculéeModèle:, C'est-à-dire, étant donné une matrice inversible $A$ et le produit tensoriel $u{v}^{\mathsf{\text{T}}}$ des vecteurs $u$ et $v,$ la formule calcule à moindre coût une matrice inverse mise à jour $(A+u{v}^{\mathsf{\text{T}}}){\phantom{)}}^{-1}.$

La formule de Sherman-Morrison est un cas particulier de l'identité de Woodbury. Bien que nommée d'après Sherman et Morrison, elle apparaissait déjà dans des publications antérieuresModèle:,Modèle:,.

Enoncé

On suppose $A\in {ℝ}^{n\times n}$ est une matrice carrée inversible et $u,v\in {ℝ}^n$ sont des vecteurs colonnes . Alors $A+u{v}^{\mathsf{\text{T}}}$ est inversible si et seulement si $1+v^{\mathsf{\text{T}}}{A}^{-1}u\ne 0$ . Dans ce cas,

${(A+u{v}^{\mathsf{\text{T}}})}^{-1}=A^{-1}-\frac{A^{-1}u{v}^{\mathsf{\text{T}}}{A}^{-1}}{1+v^{\mathsf{\text{T}}}{A}^{-1}u}.$

Ici, $u{v}^{\mathsf{\text{T}}}$ est le produit tensoriel de deux vecteurs $u$ et $v$ . La forme générale présentée ici est celle publiée par Bartlett.

Preuve

Pour prouver le sens réciproque $1+v^{\mathsf{\text{T}}}{A}^{-1}u\ne 0\Rightarrow A+u{v}^{\mathsf{\text{T}}}$ est inversible avec l'inverse donné comme ci-dessus) est vrai, on vérifie les propriétés de l'inverse. Une matrice $Y$ (dans ce cas, le côté droit de la formule de Sherman-Morrison) est l'inverse d'une matrice $X$ (dans ce cas $A+u{v}^{\mathsf{\text{T}}}$ ) si et seulement si $XY=YX=I$.

On vérifie d’abord que le côté droit ( $Y$ ) satisfait $XY=I$ .

$\begin{array}{cc}XY& =(A+u{v}^{\mathsf{\text{T}}})(A^{-1}-\frac{A^{-1}u{v}^{\mathsf{\text{T}}}{A}^{-1}}{1+v^{\mathsf{\text{T}}}{A}^{-1}u})\\ & =A{A}^{-1}+u{v}^{\mathsf{\text{T}}}{A}^{-1}-\frac{A{A}^{-1}u{v}^{\mathsf{\text{T}}}{A}^{-1}+u{v}^{\mathsf{\text{T}}}{A}^{-1}u{v}^{\mathsf{\text{T}}}{A}^{-1}}{1+v^{\mathsf{\text{T}}}{A}^{-1}u}\\ & =I+u{v}^{\mathsf{\text{T}}}{A}^{-1}-\frac{u{v}^{\mathsf{\text{T}}}{A}^{-1}+u{v}^{\mathsf{\text{T}}}{A}^{-1}u{v}^{\mathsf{\text{T}}}{A}^{-1}}{1+v^{\mathsf{\text{T}}}{A}^{-1}u}\\ & =I+u{v}^{\mathsf{\text{T}}}{A}^{-1}-\frac{u(1+v^{\mathsf{\text{T}}}{A}^{-1}u)v^{\mathsf{\text{T}}}{A}^{-1}}{1+v^{\mathsf{\text{T}}}{A}^{-1}u}\\ & =I+u{v}^{\mathsf{\text{T}}}{A}^{-1}-u{v}^{\mathsf{\text{T}}}{A}^{-1}\\ & =I\end{array}$

Pour terminer la preuve de ce sens, il faut montrer que $YX=I$ de la même manière que ci-dessus :

$YX=(A^{-1}-\frac{A^{-1}u{v}^{\mathsf{\text{T}}}{A}^{-1}}{1+v^{\mathsf{\text{T}}}{A}^{-1}u})(A+u{v}^{\mathsf{\text{T}}})=I.$

(En fait, la dernière étape peut être évitée puisque pour les matrices carrées $X$ et $Y$, $XY=I$ est équivalent à $YX=I$ .)

Réciproquement, si $1+v^{\mathsf{\text{T}}}{A}^{-1}u=0$, alors par le lemme du déterminant, $\det (A+u{v}^{\mathsf{\text{T}}})=(1+v^{\mathsf{\text{T}}}{A}^{-1}u)\det (A)=0$, alors $(A+u{v}^{\mathsf{\text{T}}})$ n'est pas inversible.

Application

Si l'inverse de $A$ est déjà connue, la formule fournit un moyen numériquement peu coûteux de calculer l'inverse de $A$ corrigé par la matrice $u{v}^{\mathsf{\text{T}}}$ (selon le point de vue, la correction peut être vue comme une perturbation ou comme une mise à jour de rang 1). En effet, le calcul n'utilise aucune que des produits par $A^{-1}$, la seule division étant celle d'un scalaire .

En utilisant des colonnes unitaires (colonnes de la matrice identité) pour $u$ ou $v$, les colonnes ou lignes individuelles de $A$ peuvent être manipulées et l'inverse peut être calculé de manière relativement peu coûteuse de cette manière. Dans le cas général, où $A^{-1}$ est une matrice carré de taille $n$ et $u$ et $v$ sont des vecteurs arbitraires de dimension $n$, la matrice entière est mise à jour et le calcul prend $3n^2$ multiplications scalaires. Si $u$ est une colonne unitaire, le calcul ne prend que $2n^2$ multiplications scalaires. Il en va de même si $v$ est une colonne unitaire. Si les deux $u$ et $v$ sont des colonnes unitaires, le calcul ne prend que $n^2$ multiplications scalaires.

Cette formule a également une application en physique théorique. En effet, dans la théorie quantique des champs, on utilise cette formule pour calculer le propagateur d'un champ de spin 1. Le propagateur inverse (tel qu'il apparaît dans le lagrangien) a la forme $A+u{v}^{\mathsf{\text{T}}}$. On utilise la formule de Sherman-Morrison pour calculer l'inverse (satisfaisant certaines conditions limites d'ordre temporel) du propagateur inverse — ou simplement du propagateur (de Feynman) — qui est nécessaire pour effectuer tout calcul perturbatif impliquant le champ de spin 1.

L’un des problèmes de cette formule est que l’on sait peu de choses sur sa stabilité numérique. Il n’existe aucun résultat publié concernant ses limites d’erreur. Des preuves anecdotiques suggèrent que l’identité matricielle de Woodbury (une généralisation de la formule de Sherman-Morrison) peut diverger même pour des exemples apparemment bénins (lorsque les matrices originales et modifiées sont bien conditionnées).

Vérification alternative

Voici une vérification alternative de la formule de Sherman-Morrison utilisant l'identité facilement vérifiable

${(I+w{v}^{\mathsf{\text{T}}})}^{-1}=I-\frac{w{v}^{\mathsf{\text{T}}}}{1+v^{\mathsf{\text{T}}}w}$ .

Soit

$u=Aw,\text{et}A+u{v}^{\mathsf{\text{T}}}=A(I+w{v}^{\mathsf{\text{T}}}),$

alors

${(A+u{v}^{\mathsf{\text{T}}})}^{-1}={(I+w{v}^{\mathsf{\text{T}}})}^{-1}{A}^{-1}=(I-\frac{w{v}^{\mathsf{\text{T}}}}{1+v^{\mathsf{\text{T}}}w})A^{-1}$ .

En substituant $w=A^{-1}u$ on a :

${(A+u{v}^{\mathsf{\text{T}}})}^{-1}=(I-\frac{A^{-1}u{v}^{\mathsf{\text{T}}}}{1+v^{\mathsf{\text{T}}}{A}^{-1}u})A^{-1}=A^{-1}-\frac{A^{-1}u{v}^{\mathsf{\text{T}}}{A}^{-1}}{1+v^{\mathsf{\text{T}}}{A}^{-1}u}$

Généralisation (identité matricielle de Woodbury)

Étant données $A$ une matrice carrée inversible $n\times n$, $U$ une matrice $n\times k$, et $V$ une matrice $k\times n$, soit $B$ une matrice $n\times n$ telle que $B=A+UV$. Alors, en supposant que $(I_k+V{A}^{-1}U)$ est inversible, on a

$B^{-1}=A^{-1}-A^{-1}U{(I_k+V{A}^{-1}U)}^{-1}V{A}^{-1}.$

Voir aussi

• Le Modèle:Lien effectue une mise à jour de rang 1 sur un déterminant.
• Identité de Woodbury
• Méthode quasi-Newton
• Modèle:Lien
• le tenseur des contraintes de Maxwell contient une application de la formule de Sherman-Morrison.