Suponha que você precise resolver um sistema linear com 500 variáveis e que a matriz dos coeficientes seja esparsa. Qual método seria computacionalmente mais eficiente?
- Eliminação Gaussiana
- Gauss-Seidel
■ Decomposição LU
- Regra de Cramer
■ Decomposição LU
Passo 1
Beleza, a questão diz o seguinte: temos um sistema linear grandão, com 500 variáveis, e a matriz de coeficientes é ES-PAR-SA (ou seja, a maioria dos elementos é zero). A pergunta é: qual método entre Eliminação Gaussiana, Gauss-Seidel, Decomposição LU e Regra de Cramer é mais rápido nesse caso? O conteúdo aqui é Métodos Numéricos para resolver sistemas lineares, e vamos precisar entender o custo computacional (complexidade) de cada método e como isso muda quando a matriz é esparsa.
Passo 2
Eliminação Gaussiana (EG) e Decomposição LU são métodos diretos que exigem operações de encher a matriz de zeros com números diferentes de zero (“fill-in”). O número de operações fica da ordem de
para uma matriz densa de tamanho
. Mesmo se a matriz for esparsa, na prática o “fill-in” faz com que você perca essa vantagem e ocupe muita memória e tempo.
Passo 3
Regra de Cramer é ainda pior: envolve calcular determinantes para cada variável, e o custo é algo como
dependendo de como você calcula determinantes, mas de qualquer jeito é impraticável para
. É quase uma piada usar Cramer em mais do que 5 incógnitas.
Passo 4
Gauss-Seidel, por outro lado, é um método iterativo. A ideia básica é: você supõe um chute inicial pras variáveis, e vai melhorando esse chute linha a linha. Cada iteração só visita os coeficientes não-zero da matriz (graças à esparsidade), então o custo por iteração é da ordem de
e você só precisa de algumas dezenas ou centenas de iterações para convergir, dependendo do problema. Ou seja, em vez de
, você tem algo como
, onde
é o número de iterações e “nz” é muito menor que
.
Passo 5
Resumindo:
- Métodos diretos (Gauss, LU) são
e sofrem “fill-in”. - Cramer é proibitivo até para
bem menor que 500. - Gauss-Seidel é iterativo, explora esparsidade e fica bem mais rápido na prática.
Resposta
O método Gauss-Seidel é o mais eficiente para um sistema grande (
) com matriz esparsa.