(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

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

Passo 2

Primeiro, explico de forma didática o que é a decomposição LU e como ela é usada para resolver Ax=b. A decomposição LU consiste em escrever uma matriz quadrada A (quando possível) como produto de uma matriz triangular inferior L e uma triangular superior U:
A = LU.
Se A=LU, para resolver Ax=b fazemos primeiro a substituição progressiva (forward substitution) para Ly=b e depois a substituição regressiva (back substitution) para Ux=y. Ou seja:
Ly=b \quad\text{(resolve-se \(y\) por substituição progressiva)},\\ Ux=y \quad\text{(resolve-se \(x\) por substituição regressiva)}.çãçã
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 L e U — 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 n (tamanho da matriz n\times n):
  • A decomposição LU (ou a eliminação de Gauss para obter U e, implicitamente, L) tem custo dominante da ordem de
\frac{2}{3}n^{3}\\ \text{operações} \quad\text{(flops, termo líder)}.çõí
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 n^{3}.
  • Uma substituição progressiva (resolver Ly=b) e uma substituição regressiva (resolver Ux=y) têm custo bem menor, da ordem de
O(n^{2})\\ \text{operações}çõ
cada uma — no total as duas somam algo da ordem de 2\,O(n^{2}). Intuitivamente isto porque para cada uma das n linhas você faz uma soma escalar sobre no máximo n entradas restantes, então dá algo como n^2 operações.
O ponto-chave: decomposição \sim O(n^{3}), as duas substituições \sim O(n^{2}). Logo a decomposição domina o custo quando n é 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.”
  • Como vimos, decomposição \sim O(n^{3}) enquanto substituições \sim O(n^{2}). Portanto os custos não são iguais: a decomposição é muito mais cara (ordem n^3) e as substituições são de ordem n^2.
    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.”
  • O que o enunciado quer transmitir (no contexto típico de disciplinas de métodos numéricos) é: como a decomposição LU tem custo \sim O(n^3), há um overhead inicial grande; esse overhead só compensa se for reutilizado (por exemplo, para resolver vários vetores b diferentes com a mesma A). Se você tem apenas um único b, 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 L e U.
  • 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 b.
    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.”
  • 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
A=\begin{pmatrix}0 & 1\\[4pt] 1 & 0\end{pmatrix}.
No primeiro passo, o “pivô” na posição (1,1) é 0. Se você não pivotar e insistir em eliminar, fica bloqueado, mas a matriz é claramente inversível (determinante -1\neq 0). 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.”
  • Isso é verdadeiro. Procedimento prático: se A é não singular e fatorizamos A=LU, para obter A^{-1} resolvemos A X = I, ou seja, resolvemos n sistemas Ax=e_i para cada vetor coluna e_i da matriz identidade. Com A=LU fazemos para cada e_i:
Ly = e_i \quad\text{(forward substitution)},\\\ Ux = y \quad\text{(back substitution)},
e a solução x é a i-ésima coluna de A^{-1}. A vantagem é que a decomposição L,U é feita uma única vez e depois cada coluna de A^{-1} é obtida com duas substituições (cada uma \sim O(n^2)). 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

Exercícios relacionados