1 Sistemas Lineares e Métodos Diretos
É correto afirmar 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 custo computacional ao aplicar uma substituição progressiva e regressiva na decomposição LU é o mesmo da decomposição em si?
  • Durante o processo de eliminação gaussiana sem pivotamento, foi encontrado um pivō nulo. Logo, a matriz dos coeficientes do sistema é singular.
  • O método de decomposição LU pode ser utilizado para calcular a inversa de uma matriz não singular.

Passo 1

Você me pediu para decidir se cada uma das quatro afirmações é correta ou não. As afirmações são (vou escrevê‑las exatamente para evitarmos confusão):
1. 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?
2. O custo computacional ao aplicar uma substituição progressiva e regressiva na decomposição LU é o mesmo da decomposição em si?
3. Durante o processo de eliminação gaussiana sem pivotamento, foi encontrado um pivô nulo. Logo, a matriz dos coeficientes do sistema é singular.
4. O método de decomposição LU pode ser utilizado para calcular a inversa de uma matriz não singular.
Informações que temos (implícitas no enunciado e que vamos usar): a matriz é quadrada de ordem n; quando falamos de custo usamos a medida assintótica (ordem de grandeza) em número de operações aritméticas; conhecemos os passos básicos de fatoração LU, substituição progressiva (forward) e regressiva (backward) e eliminação gaussiana.

Passo 2

Rápida revisão didática sobre LU e custos (calma, é só para firmar o raciocínio):
  • O que é LU? A fatoração LU escreve uma matriz quadrada A como produto A=LU, onde L é triangular inferior com 1’s na diagonal (ou semelhante) e U é triangular superior. Essa fatoração é, na prática, o mesmo conjunto de operações que a eliminação gaussiana organizada. A vantagem prática: depois de obter L e U você resolve Ax=b em dois passos:
    1. resolver Ly=b por substituição progressiva (forward) para obter y;
    2. resolver Ux=y por substituição regressiva (backward) para obter x.
  • Custos típicos (ordens de grandeza e números que você pode usar na prova):
    • Fazer a decomposição A=LU custa da ordem de magnitude de O(n^3) operações. Um valor frequentemente citado (para eliminação sem pivotamento) é aproximadamente \tfrac{2}{3}n^3 multiplicações/somas principais.
    • Cada substituição (progressiva ou regressiva) custa da ordem O(n^2). Mais precisamente, cada uma custa cerca de n^2/2 a n^2 operações dependendo do detalhe, mas o importante é a ordem n^2.
    • Logo, decomposição = grande custo O(n^3); forward+back = pequeno custo O(n^2).
  • Importante para raciocinar sobre vantagens: se você tem vários vetores de termo direito b (várias colunas), a decomposição LU é ótima porque você paga o custo grande O(n^3) uma vez e reaplica as substituições O(n^2) várias vezes. Se só há um b, a decomposição domina o custo.
Vou usar esses fatos nos próximos passos para analisar cada afirmação.

Passo 3

Análise da afirmação 1: “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?”
Raciocínio didático: como vimos no passo anterior, a decomposição custa O(n^3) enquanto a resolução das duas substituições custa O(n^2). Se você só precisa resolver um único sistema Ax=b, existe pouca vantagem em primeiro fazer uma decomposição separada só para isso, porque a eliminação gaussiana aplicada diretamente ao sistema (ou seja, fazer a eliminação sobre a matriz aumentada [A\mid b]) realiza essencialmente as mesmas operações de aritmética e tem custo também da ordem O(n^3). A diferença prática é que LU é extremamente vantajosa quando você tem vários b, pois então reaproveita L e U pagando só O(n^2) extra por vetor b.
Explicação com número exemplo rápido (para ficar concreto): se n=100, \tfrac{2}{3}n^3 \approx 6,66\times10^5 operações para a decomposição e algo da ordem de 2\cdot 10^4 para as duas substituições — a decomposição domina. Portanto, para um único sistema a sobrecarga da decomposição faz com que o ganho de usar LU (em vez de simplesmente eliminar sobre [A\mid b]) não seja notável. (Isso é o que a afirmação afirma.)
Nota de nuance que pode cair na prova: a eliminação direta sobre [A\mid b] é, na prática, a mesma sequência de operações aritméticas que computar L e U e em seguida fazer substituições — ou seja, não é que LU obrigatoriamente faça muitas mais operações, mas o ponto é que você paga o custo de fatoração inteira mesmo para um único RHS; a vantagem só aparece se houver múltiplos RHS.

Passo 4

Análise da afirmação 2: “O custo computacional ao aplicar uma substituição progressiva e regressiva na decomposição LU é o mesmo da decomposição em si?”
Raciocínio didático: comparemos ordens de complexidade:
  • Decomposição: O(n^3) (aprox. \tfrac{2}{3}n^3 operações).
  • Substituições (forward + backward): cada uma é O(n^2), somadas ficam O(n^2) (constante multiplicativa pequena, por exemplo cerca de n^2-ordem).
Em termos simples: O(n^3) versus O(n^2) são ordens diferentes; para grandes n o n^3 domina. Logo, os custos não são os mesmos — a decomposição é muito mais cara assintoticamente do que as substituições. Isso significa que afirmar que “o custo da substituição é o mesmo da decomposição” não bate com a análise de complexidade.

Passo 5

Análise da afirmação 3: “Durante o processo de eliminação gaussiana sem pivotamento, foi encontrado um pivô nulo. Logo, a matriz dos coeficientes do sistema é singular.”
Primeiro, conceito rápido e didático: uma matriz A é singular se não existe inversa, ou equivalentemente se \det(A)=0 ou se existe vetor não-nulo x tal que Ax=0.
Agora o ponto prático: encontrar um pivô nulo em uma etapa da eliminação sem pivotamento significa apenas que o elemento naquela posição é zero e a técnica de eliminação direta, sem permutar linhas, não consegue continuar. Mas isso não prova que a matriz é singular — muitas matrizes não-singulares têm um zero naquela posição e basta trocar linhas (pivotamento por linhas) para continuar a eliminação. Exemplo concreto e simples (pega a figura na cabeça, sem precisar de calculadora): considere
A=\begin{pmatrix}0 & 1\\[4pt] 1 & 0\end{pmatrix}.
Ao tentar eliminar na primeira etapa sem trocar linhas, o pivô a_{11}=0 e você “trava”. Entretanto essa matriz tem determinante \det(A) = -1, logo é invertível (não singular). Se você faz uma permutação de linhas (troca linha 1 com linha 2) o pivô fica 1 e a eliminação segue normalmente. Portanto achar um pivô nulo sem usar pivotamento não garante que A é singular — apenas diz que o método sem pivotamento falhou naquela forma. Assim a implicação lógica do enunciado é incorreta.]

Passo 6

Análise da afirmação 4: “O método de decomposição LU pode ser utilizado para calcular a inversa de uma matriz não singular.”
Raciocínio didático e procedimento prático: se A é invertível e você consegue fatorar A=LU, então para obter A^{-1} você resolve n sistemas Ax=e_i (onde e_i é o i-ésimo vetor canônico, isto é, a coluna i da identidade). Para cada i você faz:
  1. resolver Ly = e_i (substituição progressiva),
  2. resolver Ux = y (substituição regressiva),
    e a solução x é a coluna i de A^{-1}.
Custo: a decomposição O(n^3) mais n resoluções por substituições, cada uma O(n^2), totalizando na ordem de O(n^3) para obter a inversa — razoável e factível. Assim o método LU é um caminho padrão para calcular A^{-1} numericamente (na prática armazenamento e estabilidade podem sugerir outros cuidados, mas do ponto de vista algorítmico LU permite o cálculo da inversa).

Resposta

1. Verdadeira
2. Falsa
3. Falsa
4. Verdadeira

Exercícios relacionados