Computando matriz inversa quando um elemento é alterado

18

Dada uma matriz . Deixe a matriz inversa de ser (ou seja, ). Suponha que um elemento em seja alterado (digamos que para ). O objetivo é encontrar após essa alteração. Existe um método para encontrar esse objetivo mais eficiente do que recalcular a matriz inversa a partir do zero.n×nAAA1AA1=IAaijaijA1

AJed
fonte
Ótimas respostas: Encontrei o seguinte artigo que aborda exatamente esse problema: Sankowski, Piotr. "Fechamento dinâmico transitivo via matriz dinâmica inversa." Fundações de Ciência da Computação, 2004. Proceedings. 45º Simpósio Anual do IEEE em. IEEE, 2004.
Ajed
Se o documento responder ou solucionar seu problema de alguma forma, não há problema em adicionar uma resposta! :) Afinal, os comentários podem ser excluídos a qualquer momento.
Juho

Respostas:

12

A fórmula de Sherman-Morrison poderia ajudar:

(A+uvT)1=A1A1uvTA11+vTA1u.

Seja e , onde é o vetor da coluna de base padrão. Você pode verificar se, se a matriz atualizada é então v = e j e i A ' A ' - 1 = A - 1 - ( a ' i j - a i j ) A - 1 i A - 1 T ju=(aijaij)eiv=ejeiA

A1=A1(aijaij)Ai1Aj1T1+(aijaij)Aij1.
Yuval Filmus
fonte
7

Uma única alteração de elemento, dada com , pode ser rastreada com uma atualização de classificação um. Então, sim, com certeza, existe uma maneira melhor do que recalcular o inverso do zero.A - 1AA1

Seja a alteração do elemento . Usando como vetor da coluna unitária de um na posição e zera em outro lugar, temos um i j e i i ( A + e i δ e j ) Um - 1 = I + e i δ e j Um - 1δ=aijaijaijeii

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

δ i j A - 1 A - 1eiδej é a matriz zero, exceto o valor de na posição . Você pode ver aqui como uma multiplicação correta de classificação correta com pode dar o novo inverso desejado? (Ou equivalente, operações de coluna elementares em .)δijA1A1

Ou, se preferir operações de linha, você pode usar

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

No primeiro caso, temos a identidade com uma linha adicionada. É fácil executar operações de coluna para recuperar a identidade. Execute essas operações em e o resultado é o novo inverso, conforme desejado. O segundo caso é a identidade com uma coluna adicionada. Nesse caso, você pode executar operações de linha. Você pode escolher o que for mais conveniente.A1

Adam W
fonte
Boa resposta, mas quão diferente é essa da anterior de Yuval?
AJed
1
Uma perspectiva diferente é tudo: se você gosta de operações dinâmicas, este formulário mostra os valores a serem zerados e as operações de linha ou coluna podem ser feitas nesse caso. Se uma linha inteira fosse alterada, ainda funcionaria, mas as operações da coluna em seriam necessárias. A1
adam W