Mise à jour Sherman-Morrison

Il arrive que l'on doive résoudre le problème suivant : étant donné une matrice A dont on a déjà inversé l'élément (donnant A^-1), on modifie ensuite certains éléments de A et l'on souhaite inverser la matrice ainsi modifiée.

Bien sûr, ce problème peut généralement être résolu en inversant la matrice modifiée. Cependant, il existe une méthode plus efficace tenant compte du fait que l'on possède déjà A^-1 et que la matrice d'entrée a été légèrement modifiée.

Algorithme de mise à jour de la matrice inverse

La formule de Sherman-Morrison sert de base à l'algorithme suivant :

Ici, A est une matrice carrée N×N dont l'inverse est connue. u et v sont les colonnes de hauteur N définissant la modification de la matrice (u_iv_j est ajouté à a_i,_j). On constate que la mise à jour de la matrice inverse avec cette formule nécessite N² opérations sur les nombres réels, ce qui est N fois plus rapide que l'inversion par un algorithme général.

Selon les valeurs de u et v, il existe différents types de modifications de la matrice A et de mises à jour de la matrice A^-1, avec des complexités temporelles différentes. Considérons les cas principaux :

• Si seuls u_i et v_j sont non nuls, u_iv_j est ajouté à ai,j.
• Si u_i = 1 et que les autres composantes du vecteur sont nulles, le vecteur v est ajouté à la ligne i de la matrice A.
• Si v_j = 1 et que les autres composantes du vecteur sont nulles, le vecteur u est ajouté à la colonne j de la matrice A.
• Si u et v sont des vecteurs quelconques, la ligne v (colonne u) est ajoutée à différentes lignes (colonnes) avec différents multiplicateurs.

Ces cas présentent une complexité de calcul différente. La méthode la plus rapide consiste à mettre à jour la matrice inverse en modifiant un seul élément de la matrice source. Nous la considérerons comme une unité. La mise à jour de la matrice inverse par ligne ou par colonne est seulement deux fois plus lente (par conséquent, si trois éléments ou plus d'une même ligne ou colonne sont modifiés, il est préférable d'utiliser cet algorithme plutôt que le précédent). La mise à jour de la matrice inverse avec des vecteurs arbitraires u et v est trois fois plus lente que la mise à jour simple.

Remarque n° 1 : La stabilité de l'algorithme est sujette à caution. Au moins une étape est suffisamment stable si A et B sont bien conditionnées.

Description du programme

Ce module contient plusieurs sous-programmes mettant à jour A^-1, aussi bien dans le cas général que dans les cas particuliers décrits précédemment.

Le sous-programme RMatrixInvUpdateSimple met à jour A^-1 lors de l'ajout de UpdVal à l'élément de matrice situé à l'intersection de la ligne UpdRow et de la colonne UpdColumn.

Les sous-programmes RMatrixInvUpdateRow et RMatrixInvUpdateColumn mettent à jour la matrice lors de l'ajout d'un vecteur à une ligne ou une colonne de celle-ci.

Le sous-programme RMatrixInvUpdateUV met à jour la matrice inverse, définie par les vecteurs U et V, dans le cas général.