Komputasi matriks terbalik ketika elemen berubah

18

Mengingat matriks . Biarkan matriks invers dari menjadi (yaitu, ). Asumsikan satu elemen dalam diubah (misalkan ke ). Tujuannya adalah untuk menemukan setelah perubahan ini. Apakah ada metode untuk menemukan tujuan ini yang lebih efisien daripada menghitung ulang matriks terbalik dari awal. $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 Dipotong
sumber

Jawaban bagus: Saya menemukan makalah berikut yang menangani masalah persis ini: Sankowski, Piotr. "Penutupan transitif dinamis melalui pembalikan matriks dinamis." Yayasan Ilmu Komputer, 2004. Prosiding. Simposium IEEE Tahunan ke-45 pada. IEEE, 2004.

AJed

Jika makalah ini menjawab atau mengatasi masalah Anda dengan cara tertentu, tidak apa-apa menambahkan jawaban! :) Bagaimanapun, komentar mungkin terhapus kapan saja.

Juho

12

The Sherman-Morrison rumus bisa membantu:

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

Misalkan dan , di mana adalah vektor kolom basis standar. Anda dapat memeriksa bahwa jika matriks yang diperbarui adalah maka $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
sumber

7

$A$ $A^{-1}$

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

$e_i \delta e_j^\top$ $\delta$ $ij$ $A^{-1}$ $A^{-1}$

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
sumber

Jawaban yang bagus, tetapi betapa berbedanya ini dari yang sebelumnya Yuval?

AJed

1

A^{- 1}

$A^{-1}$

Komputasi matriks terbalik ketika elemen berubah

Jawaban: