Ex. 108 - Suponha que seja necessário resolver os sistemas
, onde as matrizes
diferem apenas em uma única linha. Dê um método eficiente para resolver o problema. E se as matrizes diferissem em uma única coluna?
Passo 1
O enunciado pede para resolver os
sistemas
onde cada
difere de uma matriz base
em apenas uma linha. Depois, faz a mesma pergunta quando a diferença ocorre em uma coluna. Vamos explorar o fato de que trocar uma única linha (ou coluna) é um update de posto-1 em
, e usar a fórmula de Sherman–Morrison para resolver cada sistema de forma muito mais barata do que refatorar
toda vez.
Passo 2
Substituir a linha
de
pela nova linha
equivale a escrever
onde
e
é o vetor canônico com 1 na posição
. Analogamente, trocar a coluna
equivale a
onde
é a diferença entre a nova coluna e a coluna
de
.
Passo 3
A fórmula de Sherman–Morrison diz que, para uma matriz invertível
e um update de posto-1
, vale
No nosso caso de linha, tomo
e
; no de coluna,
e
.
Passo 4
Caso “diferença numa linha
”:
- Fatoro
(por exemplo LU) uma única vez. - Resolvo
- Para cada
:
a) definoe resolvo b) computo os escalares c) aplico
Cada resolução de
custa
após a fatoração, e o resto é
.
Passo 5
Caso “diferença numa coluna
”:
- Uso a mesma fatoração de
. - Já tenho
. - Para cada
:
a) definoe resolvo b) assino c) concluo
Resposta
Use a fórmula de Sherman–Morrison para atualizar a inversa de
sob um rank-1 update.
No caso de troca de linha :
No caso de troca de linha
onde
e
são obtidos com uma única fatoração de
.
No caso de troca de coluna :
No caso de troca de coluna
com
e
.