Berechnung der inversen Matrix, wenn sich ein Element ändert

Question

Angesichts eines $ n times n $ matrix $ mathbf {a} $. Lassen Sie die inverse Matrix von $ mathbf {a} $ $ mathbf {a}^{-1} $ (dh $ mathbf {a} mathbf {a}^{-1} = mathbf {i } $). Angenommen, ein Element in $ mathbf {a} $ wird geändert (sagen wir $ a _ {ij} $ bis $ a '_ {ij} $). Das Ziel ist es, $ mathbf {a}^{-1} $ nach dieser Änderung zu finden. Gibt es eine Methode, um dieses Ziel zu finden, das effizienter ist, als die inverse Matrix von Grund auf neu zu kalkulieren?

Answer 1

Das Sherman-Morrison-Formel könnte helfen:

$$ (a + uv^t)^{-1} = a^{-1}- frac {a^{-1} uv^ta^{-1} {1 + v^ta^{-1-1-1 } u}. $$

Sei $ u = (a '_ {ij} -a_ {ij}) e_i $ und $ v = e_j $, wobei $ e_i $ der Standard-Basisspaltenvektor ist. Sie können überprüfen, ob die aktualisierte Matrix $ a '$ ist, $$ a^{ prime -1} = a^{ -1} - frac {(a' _ {ij} -a_ {ij}) a^ {-1} _ {i rightarrow} a^{-1t} _ { downarrow j}} {1 + (a '_ {ij} -a_ {ij}) a^{-1} _ {ij}}} . $$

Answer 2

Eine einzelne Elementänderung, die $ a $ mit $ a^{-1} $ ist, kann mit einem Rang One-Update verfolgt werden. Also ja, absolut gibt es einen besseren Weg, als das Inverse von Grund auf neu zu berechnen.

Sei $ delta = a_ {ij} ' - a_ {ij} $ die Änderung des Elements $ a_ {ij} $. Verwenden Sie $ e_i $ als Einheitsspaltenvektor von einem in der $ i $ -Position und an anderer Stelle, wir haben $$ (a + e_i delta e_j^ top) a^{-1} = i + e_i delta e_j^ top a^{-1} $$

$ e_i delta e_j^ top $ ist die Nullmatrix, mit Ausnahme des Wertes von $ delta $ in der Position $ ij $. Können Sie hier sehen, wie eine geeignete Rang 1-Multiplikation mit $ a^{-1} $ das gewünschte neue Umkehrung geben kann? (Oder entsprechend elementare Spaltenoperationen auf $ a^{-1} $.)

Oder wenn Sie stattdessen Zeilenoperationen durchführen möchten, können Sie $$ a^{-1} (a + e_i delta e_j^ top) = i + a^{-1} e_i delta e_j^ top $$ verwenden

Im ersten Fall haben wir die Identität mit einer Reihe hinzugefügt. Dies ist leicht zu spalten, auf die Spaltenvorgänge durchführen, um die Identität wieder zurück zu haben. Machen Sie diese Operationen auf $ a^{-1} $ und das Ergebnis ist nach Wunsch das neue Inverse. Der zweite Fall ist die Identität mit einer Spalte hinzugefügt. In diesem Fall können Sie stattdessen Reihenoperationen durchführen. Sie können wählen, was auch immer bequemer ist.