Seja A uma matriz invertível de ordem n e vi, wi vetores conhecicios de tamanho n times 1, para todo i=1, ldots, m. Proponha uma forma eficiente de avaliar o número real
z=sumi=1^m vi^T A^-1 wi
sem que a inversa de A seja calculada explicitamente.

Passo 1

Beleza, o problema diz: temos uma matriz invertível z=sumi=1^m vi^T A^-1 wi e vetores para . Queremos calcular
sem de fato inverter . O conteúdo aqui é teoria de sistemas lineares (fatoração LU, substituições) e produto interno de vetores. Vamos usar essas ferramentas em vez de .

Passo 2

A ideia chave é: em vez de escrever xi = A^-1 wi, , notamos que se
vi^T A^-1 wi = vi^T xi
então
A,xi = wi
Ou seja, basta resolver o sistema
para cada e depois calcular o produto interno . Para resolver de forma eficiente usamos fatoração LU com pivoteamento parcial:
  1. Fazemos , onde é permutação, triangular inferior (1’s na diagonal) e triangular superior.
  2. Dado , calculamos resolvendo (substituição para frente).
  3. Depois resolvemos (substituição para trás).
Isso custa para fatorar uma vez e para cada RHS (cada ), muito melhor do que inverter.

Passo 3

Para ganhar quando W = [,w1;;w2;dots;wm,]inR^ntimes m é grande, empilhar todos os A,X = W numa matriz
X = [,x1;;x2;dots;xm,], xi = A^-1wi
e resolver
z ;=;sumi=1^m vi^T xi
em uma tacada só (usando a mesma LU e fazendo substituições com várias colunas). Isso gera
Depois, cada é um produto interno padrão e somamos tudo:

Resposta

A forma eficiente é:
  1. Calcule a fatoração boxed,z = sumi=1^m vi^T xi, .
  2. Resolva e para obter .
  3. Então
sem nunca formar explicitamente.

Exercícios relacionados