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ée^[1],[2] C'est-à-dire, étant donné une matrice inversible ${\displaystyle A}$ et le produit tensoriel ${\displaystyle uv^{\textsf {T}}}$ des vecteurs ${\displaystyle u}$ et ${\displaystyle v,}$ la formule calcule à moindre coût une matrice inverse mise à jour ${\textstyle \left(A+uv^{\textsf {T}}\right){\vphantom {)}}^{\!-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érieures^[3],[4],[5].

On suppose ${\displaystyle A\in \mathbb {R} ^{n\times n}}$ est une matrice carrée inversible et ${\displaystyle u,v\in \mathbb {R} ^{n}}$ sont des vecteurs colonnes . Alors ${\displaystyle A+uv^{\textsf {T}}}$ est inversible si et seulement si ${\displaystyle 1+v^{\textsf {T}}A^{-1}u\neq 0}$ . Dans ce cas,

${\displaystyle \left(A+uv^{\textsf {T}}\right)^{-1}=A^{-1}-{A^{-1}uv^{\textsf {T}}A^{-1} \over 1+v^{\textsf {T}}A^{-1}u}.}$

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

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

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

${\displaystyle {\begin{aligned}XY&=\left(A+uv^{\textsf {T}}\right)\left(A^{-1}-{A^{-1}uv^{\textsf {T}}A^{-1} \over 1+v^{\textsf {T}}A^{-1}u}\right)\\[6pt]&=AA^{-1}+uv^{\textsf {T}}A^{-1}-{AA^{-1}uv^{\textsf {T}}A^{-1}+uv^{\textsf {T}}A^{-1}uv^{\textsf {T}}A^{-1} \over 1+v^{\textsf {T}}A^{-1}u}\\[6pt]&=I+uv^{\textsf {T}}A^{-1}-{uv^{\textsf {T}}A^{-1}+uv^{\textsf {T}}A^{-1}uv^{\textsf {T}}A^{-1} \over 1+v^{\textsf {T}}A^{-1}u}\\[6pt]&=I+uv^{\textsf {T}}A^{-1}-{u\left(1+v^{\textsf {T}}A^{-1}u\right)v^{\textsf {T}}A^{-1} \over 1+v^{\textsf {T}}A^{-1}u}\\[6pt]&=I+uv^{\textsf {T}}A^{-1}-uv^{\textsf {T}}A^{-1}\\[6pt]&=I\end{aligned}}}$

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

${\displaystyle YX=\left(A^{-1}-{A^{-1}uv^{\textsf {T}}A^{-1} \over 1+v^{\textsf {T}}A^{-1}u}\right)(A+uv^{\textsf {T}})=I.}$

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

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

Si l'inverse de ${\displaystyle A}$ est déjà connue, la formule fournit un moyen numériquement peu coûteux de calculer l'inverse de ${\displaystyle A}$ corrigé par la matrice ${\displaystyle uv^{\textsf {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 ${\displaystyle A^{-1}}$, la seule division étant celle d'un scalaire .

En utilisant des colonnes unitaires (colonnes de la matrice identité) pour ${\displaystyle u}$ ou ${\displaystyle v}$, les colonnes ou lignes individuelles de ${\displaystyle 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ù ${\displaystyle A^{-1}}$ est une matrice carré de taille ${\displaystyle n}$ et ${\displaystyle u}$ et ${\displaystyle v}$ sont des vecteurs arbitraires de dimension ${\displaystyle n}$, la matrice entière est mise à jour ^[6] et le calcul prend ${\displaystyle 3n^{2}}$ multiplications scalaires. Si ${\displaystyle u}$ est une colonne unitaire, le calcul ne prend que ${\displaystyle 2n^{2}}$ multiplications scalaires. Il en va de même si ${\displaystyle v}$ est une colonne unitaire. Si les deux ${\displaystyle u}$ et ${\displaystyle v}$ sont des colonnes unitaires, le calcul ne prend que ${\displaystyle 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 ${\displaystyle A+uv^{\textsf {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^[7].

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 ^[8] 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).

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

${\displaystyle \left(I+wv^{\textsf {T}}\right)^{-1}=I-{\frac {wv^{\textsf {T}}}{1+v^{\textsf {T}}w}}}$ .

Soit

${\displaystyle u=Aw,\quad {\text{et}}\quad A+uv^{\textsf {T}}=A\left(I+wv^{\textsf {T}}\right),}$

alors

${\displaystyle \left(A+uv^{\textsf {T}}\right)^{-1}=\left(I+wv^{\textsf {T}}\right)^{-1}A^{-1}=\left(I-{\frac {wv^{\textsf {T}}}{1+v^{\textsf {T}}w}}\right)A^{-1}}$ .

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

${\displaystyle \left(A+uv^{\textsf {T}}\right)^{-1}=\left(I-{\frac {A^{-1}uv^{\textsf {T}}}{1+v^{\textsf {T}}A^{-1}u}}\right)A^{-1}=A^{-1}-{\frac {A^{-1}uv^{\textsf {T}}A^{-1}}{1+v^{\textsf {T}}A^{-1}u}}}$

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

${\displaystyle B^{-1}=A^{-1}-A^{-1}U\left(I_{k}+VA^{-1}U\right)^{-1}VA^{-1}.}$

• Le lemme du déterminant matriciel (en) effectue une mise à jour de rang 1 sur un déterminant.
• Identité de Woodbury
• Méthode quasi-Newton
• Formule de Bunch-Nielsen-Sorensen (en)
• le tenseur des contraintes de Maxwell contient une application de la formule de Sherman-Morrison.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Sherman–Morrison formula » (voir la liste des auteurs).

• Portail de l’algèbre