Ex. 108 - Suponha que seja necessário resolver os sistemas A1 x=b, A2 x=b, ldots, Ak x=b, onde as matrizes Ai 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 k sistemas
Aix = b, i=1,dots,k,
onde cada Ai difere de uma matriz base A 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 A, e usar a fórmula de Sherman–Morrison para resolver cada sistema de forma muito mais barata do que refatorar A toda vez.

Passo 2

Substituir a linha j de A pela nova linha ri^T equivale a escrever
Ai ;=; A ;+; ej,di^T,
onde
di^T ;=; ri^T - (linha j de A),
e ej é o vetor canônico com 1 na posição j. Analogamente, trocar a coluna q equivale a
Ai ;=; A ;+; ui,eq^T,
onde ui é a diferença entre a nova coluna e a coluna q de A.

Passo 3

A fórmula de Sherman–Morrison diz que, para uma matriz invertível A e um update de posto-1 U V^T, vale
(A + U V^T)^-1 = A^-1 ;-; A^-1U,(I + V^T A^-1U)^-1V^T A^-1,
No nosso caso de linha, tomo U=ej e V^T=di^T; no de coluna, U=ui e V^T=eq^T.

Passo 4

Caso “diferença numa linha j”:
  1. Fatoro A (por exemplo LU) uma única vez.
  2. Resolvo A,z = b Longrightarrow z = A^-1b
  3. Para cada i:
    a) defino di e resolvo A,yi = ej Longrightarrow yi = A^-1ej b) computo os escalares alphai = 1 + di^T yi, betai = di^T z c) aplico xi = z ;-; betaialphai,yi
Cada resolução de A,yi=ej custa O(n^2) após a fatoração, e o resto é O(n).

Passo 5

Caso “diferença numa coluna q”:
  1. Uso a mesma fatoração de A.
  2. Já tenho z = A^-1b.
  3. Para cada i:
    a) defino ui e resolvo A,yi = ui Longrightarrow yi = A^-1ui b) assino alphai = 1 + eq^T yi = 1 + yi,q, betai = eq^T z = zq c) concluo xi = z ;-; betaialphai,yi

Resposta

Use a fórmula de Sherman–Morrison para atualizar a inversa de A sob um rank-1 update.
No caso de troca de linha j:
Ai = A + ej,di^T, xi = Ai^-1b = z - di^T z1 + di^T yi,yi,
onde z=A^-1b e yi=A^-1ej são obtidos com uma única fatoração de A.
No caso de troca de coluna q:
Ai = A + ui,eq^T, xi = z - zq1 + yi,q,yi,
com z=A^-1b e yi=A^-1ui.

Exercícios de Livros Relacionados