Seja uma matriz invertível de ordem 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:
Fazemos , onde é permutação, triangular inferior (1’s na diagonal) e triangular superior.
Dado , calculamos resolvendo (substituição para frente).
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: