Seja um sistema matricial A X=B, onde A in R^n times n, X in R^n times p e B in R^n times p.
a) Verifique que tal sistema pode ser resolvido pela solução de p sistemas auxiliares A xk=bk, onde bk in R^n é a k-ésima coluna de B.
b) Analise a complexidade computacional na resolução do sistema, através da estratégia da letra a), utilizando eliminação gaussiana em cada um dos p sistemas auxiliares.
c) Qual seria a vantagem de utilizar a fatoração A=L U para a resolução deste sistema? Faça uma análise da complexidade computacional desta abordagem.
d) Caso p=n e B=I, quem é a matriz X ? Analise a complexidade computacional de sua avaliação, utilizando a estratégia da letra a) e a da letra c).

Passo 1

Beleza, vamos recapitular o que o enunciado pede e que matéria vamos usar.
Enunciado em miúdos: temos um sistema matricial
A,X = B,
em que é uma matriz quadrada , e são matrizes . A gente quer:
a) Mostrar que resolver dá no mesmo que resolver sistemas lineares separados , onde é a -ésima coluna de .
b) Calcular a complexidade de fazer isso com eliminação gaussiana em cada sistema.
c) Ver a vantagem de usar fatoração , e analisar a complexidade.
d) No caso especial e , descobrir que matriz é e comparar complexidades de (b) e ©.
Matéria e ferramentas: sistemas lineares, eliminação gaussiana, fatoração LU, análise de complexidade (ordem de grandeza em e ).

Passo 2

Parte (a): mostrar que resolver A,x1 = b1, A,x2 = b2, dots, A,xp = bp é resolver sistemas .
– A ideia é simples: tem colunas , e tem colunas .
– Escrevendo produto de matrizes por colunas, a igualdade vira simultaneamente
Cada coluna de é independente, então basta resolver cada sistema .

Passo 3

Parte (b): complexidade usando eliminação gaussiana em cada um dos p;times;23,n^3 ;=; 23,p,n^3 (mais termos (O(p,n^2))) sistemas.
– Eliminação gaussiana para um sistema custa, em ordem de grandeza, operações (mais termos menores em ).
– Como temos sistemas independentes, multiplicamos por .
– Logo, custo total aproximado é

Passo 4

Parte ©: e se a gente fatorar 23n^3 ;+; 2,p,n^2 (dominante quando (p) é menor que (n) ou mesmo assim é bem melhor que (p,n^3)) antes de resolver tudo?
– Fatoração (elaboração da matriz e ) custa também operações.
– Depois, para cada coluna de , a gente faz:
  1. resolver (substituição para triangular inferior) em ,
  2. resolver (substituição para triangular superior) em .
    – Cada coluna custa , e como são colunas, dá .
    – Somando tudo, o custo é
éé
Vantagem: você só faz a parte cara ( ) uma vez, em vez de repetir vezes.

Passo 5

Parte (d): caso A,xk = ek e X = A^-1 .
– Aqui (identidade), então tem colunas que são soluções de
onde é o -ésimo vetor canônico. Mas isso é precisamente a definição de : cada é a -ésima coluna de . Então
Complexidades:
a) Método direto (eliminar vezes):

b) Com :

Logo, método LU é em vez de .

Resposta

a) Basta resolver sistemas .
b) Custo .
c) Com : custo , muito melhor quando é grande.
d) Se , , então . Custo direto: . Com LU: .

Exercícios relacionados