Berechnung der inversen Matrix, wenn sich ein Element ändert

18

Ein gegebener - Matrix A . Die inverse Matrix von A sei A - 1 (dh A A - 1 = I ). Angenommen, ein Element in A wird geändert (sagen wir a i j bis a ' i j ). Ziel ist es, nach dieser Änderung A - 1 zu finden . Gibt es eine Methode, um dieses Ziel zu finden, die effizienter ist als die Neuberechnung der inversen Matrix von Grund auf.n×nAAA1AA1=IAaijaijA1

AJed
quelle
Gute Antworten: Ich habe das folgende Papier gefunden, das genau dieses Problem angeht: Sankowski, Piotr. "Dynamisches transitives Schließen über dynamische Matrixumkehrung." Grundlagen der Informatik, 2004. Verfahren. 45. jährliches IEEE-Symposium am. IEEE, 2004.
AJed
Wenn das Papier auf irgendeine Weise auf Ihr Problem antwortet oder es anspricht, können Sie eine Antwort hinzufügen! :) Schließlich können Kommentare jederzeit gelöscht werden.
Juho

Antworten:

12

Die Sherman-Morrison-Formel könnte helfen:

(A+uvT)1=A1A1uvTA11+vTA1u.

Sei und v = e j , wobei e i der Standard-Basisspaltenvektor ist. Sie können überprüfen, ob die aktualisierte Matrix A ' ist , dann ist A ' - 1 = A - 1 - ( a ' i j - a i j ) A - 1 i A - 1u=(aijaij)eiv=ejeiA

A1=A1(aijaij)Ai1Aj1T1+(aijaij)Aij1.
Yuval Filmus
quelle
7

AA1

δ=aijaijaijeii

(A+eiδej)A1=I+eiδejA1

eiδejδijA1A1

A1(A+eiδej)=I+A1eiδej

A1

Adam W
quelle
Schöne Antwort, aber wie unterscheidet sich das von dem vorherigen von Yuval?
AJed
1
A1