É 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?
Passo 1
Beleza, o enunciado pergunta se faz sentido dizer que “fazer a decomposição LU de uma matriz é tão caro que não vale a pena quando a gente só quer resolver UM único sistema linear”. Isso é teoria de Álgebra Linear Numérica: vamos falar de custo computacional (complexidade) de métodos para resolver Ax = b. Pra resolver, precisamos saber quanto custa em operações (multiplicações/somas) tanto a decomposição LU quanto a eliminação de Gauss “direta”.
Passo 2
Antes de tudo, lembra do que é a decomposição LU: A = L·U, onde L é triangular inferior e U é triangular superior.
• Para achar L e U (isto é, a „decomposição LU“) a gente faz basicamente a mesma coisa que a eliminação de Gauss: custo médio ≃ (2/3)n³ operações aritméticas, se A for n×n.
• Depois, para usar a LU e achar x: a) resolve Ly = b por substituição direta (forward) em ≃ n²/2 operações, b) resolve Ux = y por substituição back em ≃ n²/2 operações. No total de ≃ n².
• Para achar L e U (isto é, a „decomposição LU“) a gente faz basicamente a mesma coisa que a eliminação de Gauss: custo médio ≃ (2/3)n³ operações aritméticas, se A for n×n.
• Depois, para usar a LU e achar x: a) resolve Ly = b por substituição direta (forward) em ≃ n²/2 operações, b) resolve Ux = y por substituição back em ≃ n²/2 operações. No total de ≃ n².
Passo 3
Agora, e a eliminação de Gauss “straight” (sem falar em L e U separadamente)? Ela elimina as incógnitas também com custo ≃ (2/3)n³ para triangularizar e mais ≃ n² para voltar a solução. Ou seja, no final das contas:
– LU + forward/back ≃ (2/3)n³ + O(n²)
– Gauss direto ≃ (2/3)n³ + O(n²)
Para UM único sistema, os custos são praticamente os mesmos.
– LU + forward/back ≃ (2/3)n³ + O(n²)
– Gauss direto ≃ (2/3)n³ + O(n²)
Para UM único sistema, os custos são praticamente os mesmos.
Resposta
A afirmação é falsa: para resolver só um sistema linear, usar decomposição LU não é mais custoso do que aplicar eliminação de Gauss direta – ambos têm custo principal de ordem O(n³).