Calcul d'une matrice inverse lorsqu'un élément change

18

Étant donné une matrice . Soit la matrice inverse de être (c'est-à-dire, ). Supposons qu'un élément de soit modifié (disons en ). L'objectif est de trouver après ce changement. Existe-t-il une méthode pour trouver cet objectif plus efficace que de recalculer la matrice inverse à partir de zéro.A A A - 1 A A - 1 = I A a i j a i j A - 1n×nAAA1AA1=IAaijaijA1

AJed
la source
Excellentes réponses: j'ai trouvé le document suivant qui s'attaque à ce problème exact: Sankowski, Piotr. "Fermeture transitive dynamique via matrice inverse dynamique." Foundations of Computer Science, 2004. Actes. 45e Symposium annuel de l'IEEE sur. IEEE, 2004.
AJed
Si le document répond ou résout votre problème d'une manière ou d'une autre, vous pouvez ajouter une réponse! :) Après tout, les commentaires peuvent être supprimés à tout moment.
Juho

Réponses:

12

La formule Sherman-Morrison pourrait aider:

(UNE+uvT)-1=UNE-1-UNE-1uvTUNE-11+vTUNE-1u.

Soit et v = e j , où e i est le vecteur de colonne de base standard. Vous pouvez vérifier que si la matrice mise à jour est alors u=(unejej-unejej)ejev=ejejeA - 1 = A - 1 - ( a i j - a i j ) A - 1 i A - 1 T jUNE

UNE-1=UNE-1-(unejej-unejej)UNEje-1UNEj-1T1+(unejej-unejej)UNEjej-1.
Yuval Filmus
la source
7

Un changement d'élément unique, étant donné avec A - 1 , peut être suivi avec une mise à jour de rang un. Alors oui, absolument, il y a un meilleur moyen que de recalculer l'inverse à partir de zéro.UNEUNE-1

Soit le changement de l'élément a i j . En utilisant e i comme vecteur de colonne unitaire de un dans la position i et des zéros ailleurs, nous avons ( A + e i δ e j ) A - 1 = I + e i δ e j A - 1δ=unejej-unejejunejejejeje

(UNE+ejeδej)UNE-1=je+ejeδejUNE-1

est la matrice nulle, sauf la valeur de δ enposition i j . Pouvez-vous voir ici comment une multiplication appropriée de rang 1 avec A - 1 peut donner la nouvelle inverse souhaitée? (Ou de manière équivalente, les opérations de colonne élémentaire sur A - 1. )ejeδejδjejUNE-1UNE-1

Ou si vous préférez effectuer des opérations sur les lignes, vous pouvez utiliser

UNE-1(UNE+ejeδej)=je+UNE-1ejeδej

UNE-1

adam W
la source
Belle réponse, mais en quoi est-ce différent de la précédente de Yuval?
AJed
1
UNE-1