(1.5) Quanto aos métodos diretos para sistemas lineares, é correto afirmar que:
I) O custo computacional ao aplicar uma substituiçăo progressiva e regressiva na decomposiçio LU é o mesmo da decomposição em si.
II) O custo computacional de decompor uma matriz usando a decomposição LU torna esse método năo muito vantajoso quando queremos resolver apenas um sistema linear.
III) Durante o processo de eliminaçio gaussiana sem pivotamento, foi encontrado um pivō nulo. Logo, a matriz dos coeficientes do sistema é singular.
IV) O método de decomposiçao LU pode ser utilizado para calcular a inversa de uma matriz nāo singular.
a) Todas sào falsas
b) Apenas II e III sio falsas
c) Apenas I e IV slo verdadeiras
d) Apenas IV é verdadeira
e) Apenas II e IV sảo Verdadeiras
I) O custo computacional ao aplicar uma substituiçăo progressiva e regressiva na decomposiçio LU é o mesmo da decomposição em si.
II) O custo computacional de decompor uma matriz usando a decomposição LU torna esse método năo muito vantajoso quando queremos resolver apenas um sistema linear.
III) Durante o processo de eliminaçio gaussiana sem pivotamento, foi encontrado um pivō nulo. Logo, a matriz dos coeficientes do sistema é singular.
IV) O método de decomposiçao LU pode ser utilizado para calcular a inversa de uma matriz nāo singular.
a) Todas sào falsas
b) Apenas II e III sio falsas
c) Apenas I e IV slo verdadeiras
d) Apenas IV é verdadeira
e) Apenas II e IV sảo Verdadeiras
Passo 1
O enunciado apresenta quatro afirmações sobre métodos diretos para sistemas lineares (I, II, III, IV) e pede que escolhamos qual alternativa (a–e) classifica corretamente quais são verdadeiras e falsas. As quatro afirmações são:
I) O custo computacional ao aplicar uma substituição progressiva e regressiva na decomposição LU é o mesmo da decomposição em si.
II) O custo computacional de decompor uma matriz usando a decomposição LU torna esse método não muito vantajoso quando queremos resolver apenas um sistema linear.
III) Durante o processo de eliminação gaussiana sem pivotamento, foi encontrado um pivô nulo. Logo, a matriz dos coeficientes do sistema é singular.
IV) O método de decomposição LU pode ser utilizado para calcular a inversa de uma matriz não singular.
As opções de resposta são:
a) Todas são falsas
b) Apenas II e III são falsas
c) Apenas I e IV são verdadeiras
d) Apenas IV é verdadeira
e) Apenas II e IV são Verdadeiras
a) Todas são falsas
b) Apenas II e III são falsas
c) Apenas I e IV são verdadeiras
d) Apenas IV é verdadeira
e) Apenas II e IV são Verdadeiras
Passo 2
Primeiro, explico de forma didática o que é a decomposição LU e como ela é usada para resolver
. A decomposição LU consiste em escrever uma matriz quadrada
(quando possível) como produto de uma matriz triangular inferior
e uma triangular superior
:
Se
, para resolver
fazemos primeiro a substituição progressiva (forward substitution) para
e depois a substituição regressiva (back substitution) para
. Ou seja:
Isso é útil porque resolver sistemas triangulares é muito mais barato do que eliminar diretamente toda a matriz. Mas antes de usar as substituições precisamos obter
e
— e isso é feito por um processo equivalente à eliminação de Gauss (com ou sem pivotamento).
Passo 3
Agora um pouco sobre custos computacionais (explicado de forma clara e prática). Em teoria de algoritmos numéricos costuma-se medir operações em “flops” (operações de ponto flutuante). O que importa aqui é a ordem de grandeza em termos de
(tamanho da matriz
):
- A decomposição LU (ou a eliminação de Gauss para obter
e, implicitamente, ) tem custo dominante da ordem de
Isto vem do somatório dos trabalhos de eliminação em cada etapa; não precisa decorar a derivação, só lembrar que é algo proporcional a
.
- Uma substituição progressiva (resolver
) e uma substituição regressiva (resolver ) têm custo bem menor, da ordem de
cada uma — no total as duas somam algo da ordem de
. Intuitivamente isto porque para cada uma das
linhas você faz uma soma escalar sobre no máximo
entradas restantes, então dá algo como
operações.
O ponto-chave: decomposição
, as duas substituições
. Logo a decomposição domina o custo quando
é grande.
Passo 4
Analisando a afirmação I com base no que acabamos de aprender:
I diz que “o custo computacional ao aplicar uma substituição progressiva e regressiva na decomposição LU é o mesmo da decomposição em si.”
I diz que “o custo computacional ao aplicar uma substituição progressiva e regressiva na decomposição LU é o mesmo da decomposição em si.”
- Como vimos, decomposição
enquanto substituições . Portanto os custos não são iguais: a decomposição é muito mais cara (ordem ) e as substituições são de ordem .
Conclusão: a afirmação I é falsa.
Passo 5
Interpretando a afirmação II:
II diz que “o custo computacional de decompor uma matriz usando a decomposição LU torna esse método não muito vantajoso quando queremos resolver apenas um sistema linear.”
II diz que “o custo computacional de decompor uma matriz usando a decomposição LU torna esse método não muito vantajoso quando queremos resolver apenas um sistema linear.”
- O que o enunciado quer transmitir (no contexto típico de disciplinas de métodos numéricos) é: como a decomposição LU tem custo
, há um overhead inicial grande; esse overhead só compensa se for reutilizado (por exemplo, para resolver vários vetores diferentes com a mesma ). Se você tem apenas um único , esse esforço de decompor não traz a grande vantagem de economia em múltiplas resoluções — para um único sistema o custo total (decomposição + duas substituições) é comparável ao custo de fazer eliminação de Gauss direta; em termos práticos diz-se que LU “não é muito vantajosa” para um único sistema porque não há reutilização do fator e . - Observação técnica: a eliminação de Gauss com retro-substituição tem essencialmente o mesmo custo que computar a decomposição LU e fazer as substituições; portanto não é que LU seja pior, mas também não traz vantagem quando há um só sistema — a vantagem aparece quando há muitos
.
Conclusão: no sentido pedagógico e prático usual, a afirmação II é verdadeira.
Passo 6
Analisando a afirmação III:
III diz: “Durante o processo de eliminação gaussiana sem pivotamento, foi encontrado um pivô nulo. Logo, a matriz dos coeficientes do sistema é singular.”
III diz: “Durante o processo de eliminação gaussiana sem pivotamento, foi encontrado um pivô nulo. Logo, a matriz dos coeficientes do sistema é singular.”
- Cuidado: encontrar um pivô nulo durante a eliminação sem pivotamento significa apenas que, na ordem de linhas atual, o elemento diagonal usado como pivô é zero. Isso NÃO implica automaticamente que a matriz seja singular. Muitas vezes basta fazer uma permutação de linhas (pivotamento por enumeração de linhas) para obter um pivô não nulo e continuar a eliminação; a matriz pode perfeitamente ser não singular.
- Exemplo simples e muito didático: considere
No primeiro passo, o “pivô” na posição
é
. Se você não pivotar e insistir em eliminar, fica bloqueado, mas a matriz é claramente inversível (determinante
). Com pivotamento por troca de linhas você escolhe a linha 2 como primeira e segue normalmente.
- A exceção é: se o pivô é zero e toda a coluna abaixo também é zero (ou seja, não existe nenhum elemento não nulo para trocar), então realmente não há como prosseguir e a matriz é singular. Mas o enunciado afirma a conclusão sem considerar a possibilidade de trocar linhas.
Conclusão: a afirmação III, como está formulada (sem considerar pivotamento), é falsa.]
Passo 7
Analisando a afirmação IV:
IV diz: “O método de decomposição LU pode ser utilizado para calcular a inversa de uma matriz não singular.”
IV diz: “O método de decomposição LU pode ser utilizado para calcular a inversa de uma matriz não singular.”
- Isso é verdadeiro. Procedimento prático: se
é não singular e fatorizamos , para obter resolvemos , ou seja, resolvemos sistemas para cada vetor coluna da matriz identidade. Com fazemos para cada :
e a solução
é a
-ésima coluna de
. A vantagem é que a decomposição
é feita uma única vez e depois cada coluna de
é obtida com duas substituições (cada uma
). Logo IV é verdadeira.
Passo 8
Resumindo os resultados das análises:
- I: falsa.
- II: verdadeira (no sentido prático/pedagógico: decomposição tem overhead que só compensa se houver reutilização).
- III: falsa.
- IV: verdadeira.
Portanto as afirmações verdadeiras são II e IV apenas.
Resposta
e) Apenas II e IV são Verdadeiras