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.
É correto afirmar que:
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):
Informações que temos (implícitas no enunciado e que vamos usar): a matriz é quadrada de ordem
; 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
como produto , onde é triangular inferior com 1’s na diagonal (ou semelhante) e é 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 e você resolve em dois passos: - resolver
por substituição progressiva (forward) para obter ; - resolver
por substituição regressiva (backward) para obter .
- resolver
-
Custos típicos (ordens de grandeza e números que você pode usar na prova):
- Fazer a decomposição
custa da ordem de magnitude de operações. Um valor frequentemente citado (para eliminação sem pivotamento) é aproximadamente multiplicações/somas principais. - Cada substituição (progressiva ou regressiva) custa da ordem
. Mais precisamente, cada uma custa cerca de a operações dependendo do detalhe, mas o importante é a ordem . - Logo, decomposição
grande custo ; forward+back pequeno custo .
- Fazer a decomposição
-
Importante para raciocinar sobre vantagens: se você tem vários vetores de termo direito
(várias colunas), a decomposição LU é ótima porque você paga o custo grande uma vez e reaplica as substituições várias vezes. Se só há um , 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
: “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
enquanto a resolução das duas substituições custa
. Se você só precisa resolver um único sistema
, 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
) realiza essencialmente as mesmas operações de aritmética e tem custo também da ordem
. A diferença prática é que LU é extremamente vantajosa quando você tem vários
, pois então reaproveita
e
pagando só
extra por vetor
.
Explicação com número exemplo rápido (para ficar concreto): se
,
operações para a decomposição e algo da ordem de
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
) 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
é, na prática, a mesma sequência de operações aritméticas que computar
e
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
: “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:
(aprox. operações). - Substituições (forward + backward): cada uma é
, somadas ficam (constante multiplicativa pequena, por exemplo cerca de -ordem).
Em termos simples:
versus
são ordens diferentes; para grandes
o
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
: “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
é singular se não existe inversa, ou equivalentemente se
ou se existe vetor não-nulo
tal que
.
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
Ao tentar eliminar na primeira etapa sem trocar linhas, o pivô
e você “trava”. Entretanto essa matriz tem determinante
, logo é invertível (não singular). Se você faz uma permutação de linhas (troca linha 1 com linha 2) o pivô fica
e a eliminação segue normalmente. Portanto achar um pivô nulo sem usar pivotamento não garante que
é 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
: “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
é invertível e você consegue fatorar
, então para obter
você resolve
sistemas
(onde
é o
-ésimo vetor canônico, isto é, a coluna
da identidade). Para cada
você faz:
- resolver
(substituição progressiva), - resolver
(substituição regressiva),
e a soluçãoé a coluna de .
Custo: a decomposição
mais
resoluções por substituições, cada uma
, totalizando na ordem de
para obter a inversa — razoável e factível. Assim o método LU é um caminho padrão para calcular
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).