Calcolare matrice inversa quando un elemento viene modificato

Question

Dato un $ n \ times n $ matrice $ \ mathbf {A} $. Lasciate che la matrice inversa di $ \ mathbf {A} $ di $ \ mathbf {A} ^ {- 1} $ (cioè, $ \ mathbf {A} \ mathbf {A} ^ {- 1} = \ mathbf {I } $). Si supponga che un elemento di $ \ mathbf {A} $ è cambiato (diciamo $ a _ {ij} $ a $ a' _ {ij} $). L'obiettivo è quello di trovare $ \ mathbf {A} ^ {- 1} $ dopo questa modifica. Esiste un metodo per trovare questo obiettivo che è più efficiente di ri-calcolare la matrice inversa da zero.

Answer 1

Il Sherman-Morrison formula potrebbe aiutare:

$$ (A + uv ^ T) ^ {- 1} = A ^ {- 1} - \ frac {A ^ {- 1} uv ^ TA ^ {- 1}} {1 + v ^ TA ^ {-1}} u. $$

Sia $ u = (a '_ {ij} -a_ {ij}) e_i $ e $ v = e_j $, dove $ e_i $ è il vettore colonna di basi standard. È possibile verificare che se la matrice è aggiornato $ A '$ allora $$ A ^ {\ prime} -1 = A ^ {- 1} - \ frac {(a '_ {ij} -a_ {ij}) A ^ {- 1} _ {i} \ rightarrow A ^ {- 1T} _ {\ downarrow j}} {1 + (un '_ {ij} -a_ {ij}) a ^ {-. 1} _ {ij}} $$

Answer 2

Una singola modifica elemento, dato $ A $ con $ A ^ {- 1} $, può essere rintracciato con un aggiornamento rango. Quindi sì, assolutamente, c'è un modo migliore di ricalcolare l'inverso da zero.

Sia $ \ delta = a_ {ij}' - a_ {ij} $ essere il cambiamento dell'elemento $ a_ {ij} $. Utilizzando $ e_i $ come colonna unità vettore di uno in $ i $ posizione e zeri altrove, abbiamo $$ (A + e_i \ delta e_j ^ \ alto) A ^ {- 1} = I + e_i \ delta e_j ^ \ cima Un ^ {- 1} $$

$ e_i \ delta e_j ^ \ superiore $ è la matrice nulla, tranne il valore di $ \ delta $ nella posizione di $ $ ij. Si può vedere qui come un adeguato grado una moltiplicazione scorretto con $ A ^ {- 1} $ può dare la nuova inversa desiderato? (O equivalentemente, le operazioni elementari di colonne su $ A ^ {- 1}. $)

O se ti piace fare operazioni di riga, invece, è possibile utilizzare $$ A ^ {- 1} (A + e_i \ delta e_j ^ \ alto) = I + A ^ {- 1} e_i \ delta e_j ^ \ top $$

Nel primo caso abbiamo l'identità con una fila aggiunto. Questo è facile da fare operazioni di colonne su di avere di nuovo l'identità. Fare queste operazioni su $ A ^ {- 1} $ e il risultato è il nuovo inversa, se lo desideri. Il secondo caso è l'identità con una colonna aggiunta. In tal caso, è possibile fare operazioni di riga, invece. Si può scegliere a seconda di quale è più conveniente.