Obliczanie macierzy odwrotnej przy zmianie elementu

18

Biorąc pod uwagę macierzy . Niech macierz odwrotna do będzie (to znaczy, ). Załóżmy, że jeden element w został zmieniony (powiedzmy na ). Celem jest znalezienie po tej zmianie. Czy istnieje metoda znalezienia tego celu, który jest bardziej wydajny niż ponowne obliczenie macierzy odwrotnej od zera. $n \times n$ $\mathbf{A}$ $\mathbf{A}$ $\mathbf{A}^{-1}$ $\mathbf{A}\mathbf{A}^{-1} = \mathbf{I}$ $\mathbf{A}$ $a _{ij}$ $a' _{ij}$ $\mathbf{A}^{-1}$

algorithms numerical-analysis online-algorithms

— AJed
źródło

Świetne odpowiedzi: znalazłem następujący artykuł, który rozwiązuje ten dokładnie problem: Sankowski, Piotr. „Dynamiczne zamykanie przechodnie poprzez dynamiczną macierz odwrotną.” Podstawy informatyki, 2004. Postępowanie. 45. doroczne sympozjum IEEE w sprawie. IEEE, 2004.

— AJed

Jeśli artykuł w jakiś sposób odpowiada lub rozwiązuje Twój problem, możesz dodać odpowiedź! :) W końcu komentarze mogą zostać usunięte w dowolnym momencie.

— Juho,

12

Formuła Sherman-Morrison może pomóc:

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

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

Niech oraz , gdzie jest standardowym wektorem kolumny podstawowej. Możesz sprawdzić, czy jeśli zaktualizowana macierz to to $u = (a'_{ij}-a_{ij}) e_i$ $v = e_j$ $e_i$ $A'$

A^{' - 1} = A^{- 1} - \frac{(a_{i j}^{'} - a_{i j}) A_{i \to}^{- 1} A_{↓ j}^{- 1 T}}{1 + (a_{i j}^{'} - a_{i j}) A_{i j}^{- 1}} .

$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}}.$

— Yuval Filmus
źródło

7

Zmiana pojedynczego elementu, podana z , może być śledzona z aktualizacją rangi 1. Tak, absolutnie, istnieje lepszy sposób niż ponowne obliczenie odwrotności od zera. $A$ $A^{-1}$

Niech będzie zmianą elementu . Używanie a wektora kolumny jednostkową jeden w położenia i zerami poza nią, że ma $\delta = a_{ij}' - a_{ij}$ $a_{ij}$ $e_i$ $i$

(A + e_{i} δ e_{j}^{⊤}) A^{- 1} = I + e_{i} δ e_{j}^{⊤} A^{- 1}

$(A + e_i \delta e_j^\top )A^{-1} = I + e_i \delta e_j^\top A^{-1}$

macierz zero, z wyjątkiem wartości w pozycji. Czy widzisz tutaj, jak odpowiednie pomnożenie rangi jednej przez może dać pożądaną nową odwrotność? (Lub równoważnie, elementarne operacje na kolumnach na ). $e_i \delta e_j^\top$ $\delta$ $ij$ $A^{-1}$ $A^{-1}$

Lub jeśli zamiast tego chcesz wykonać operacje na wierszach, możesz użyć

A^{- 1} (A + e_{i} δ e_{j}^{⊤}) = I + A^{- 1} e_{i} δ e_{j}^{⊤}

$A^{-1}(A + e_i \delta e_j^\top ) = I + A^{-1}e_i \delta e_j^\top$

$A^{-1}$

— Adam W
źródło

Dobra odpowiedź, ale jak różni się to od poprzedniego Yuval?

— AJed,

1

A^{- 1}

$A^{-1}$