Seja um sistema matricial
, onde
e
.
a) Verifique que tal sistema pode ser resolvido pela solução de
sistemas auxiliares
, onde
é a
-ésima coluna de
.
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
sistemas auxiliares.
c) Qual seria a vantagem de utilizar a fatoração
para a resolução deste sistema? Faça uma análise da complexidade computacional desta abordagem.
d) Caso
e
, quem é a matriz
? Analise a complexidade computacional de sua avaliação, utilizando a estratégia da letra a) e a da letra c).
a) Verifique que tal sistema pode ser resolvido pela solução de
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
c) Qual seria a vantagem de utilizar a fatoração
d) Caso
Passo 1
Beleza, vamos recapitular o que o enunciado pede e que matéria vamos usar.
Enunciado em miúdos: temos um sistema matricial
Enunciado em miúdos: temos um sistema matricial
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 ©.
a) Mostrar que resolver
b) Calcular a complexidade de fazer isso com eliminação gaussiana em cada sistema.
c) Ver a vantagem de usar fatoração
d) No caso especial
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
é resolver
sistemas
.
– A ideia é simples: tem colunas
, e
tem colunas
.
– Escrevendo produto de matrizes por colunas, a igualdade vira simultaneamente
– A ideia é simples:
– Escrevendo produto de matrizes por colunas, a igualdade
Cada coluna de
é independente, então basta resolver cada sistema
.
Passo 3
Parte (b): complexidade usando eliminação gaussiana em cada um dos
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 é
– Eliminação gaussiana para um sistema
– Como temos
– Logo, custo total aproximado é
Passo 4
Parte ©: e se a gente fatorar
antes de resolver tudo?
– Fatoração (elaboração da matriz
e
) custa também
operações.
– Depois, para cada coluna de
, a gente faz:
– Fatoração
– Depois, para cada coluna
- resolver
(substituição para triangular inferior) em , - 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
e
.
– Aqui (identidade), então
tem colunas que são soluções de
– Aqui
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
.
a) Método direto (eliminar
b) Com
Logo, método LU é
Resposta
a) Basta resolver
sistemas
.
b) Custo .
c) Com : custo
, muito melhor quando
é grande.
d) Se ,
, então
. Custo direto:
. Com LU:
.
b) Custo
c) Com
d) Se