Komputasi matriks terbalik ketika elemen berubah

18

Mengingat matriks A . Biarkan matriks invers dari A menjadi A - 1 (yaitu, A A - 1 = I ). Asumsikan satu elemen dalam A diubah (misalkan a i j ke a i j ). Tujuannya adalah untuk menemukan A - 1 setelah perubahan ini. Apakah ada metode untuk menemukan tujuan ini yang lebih efisien daripada menghitung ulang matriks terbalik dari awal.n×nAAA1AA1=IAaijaijA1

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

Jawaban:

12

The Sherman-Morrison rumus bisa membantu:

(A+uvT)1=A1A1uvTA11+vTA1u.

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

AA1

δ=aijaijaijeii

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

eiδejδijA1A1

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

A1

adam W
sumber
Jawaban yang bagus, tetapi betapa berbedanya ini dari yang sebelumnya Yuval?
AJed
1
A1