Algoritmo para Resolução de Sistemas Lineares via Eliminação de Gauss

Por
| 

A eliminação de Gauss é um dos métodos mais eficientes para resolver sistemas lineares. Através desse método, podemos escrever um algoritmo que resolve sistemas lineares em tempo polinomial O(n3), que é o objetivo deste artigo.

Algoritmo para Resolução de Sistemas Lineares via Eliminação de Gauss

Inicialmente, é feita uma revisão sobre o escalonamento de sistemas lineares, com um exemplo de como resolver um sistema linear escalonado e outro exemplo de como escalonar um sistema.

Em seguida, o algoritmo da eliminação de Gauss em pseudocódigo é analisado e explicado. Por fim, disponibilizo o algoritmo codificado em Java, C e JavaScript.

Índice

Sistemas lineares escalonados

Um sistema linear está escalonado quando possui a seguinte forma [1]

a11x1+a12x2+a13x3++a1nxn=b1a22x2+a23x3++a2nxn=b2a33x3++a3nxn=b3annxn=bn

Ou seja, ...o número de coeficientes nulos, antes do primeiro coeficiente não nulo, aumenta de equação para equação. [1]

Neste artigo, vamos considerar apenas sistemas lineares nos quais o número de incógnitas é igual ao número de equações. Além disso, utilizaremos sistemas lineares na forma matricial

Ax=b

Um sistema linear escalonado na forma matricial pode ser representado da seguinte forma

[a11a12a13a1n0a22a23a2n00a33a3n000ann][x1x2x3xn]=[b1b2b3bn]

Observe que a matriz dos coeficientes é triangular.

Mas por que utilizar sistemas escalonados? Veja que a última equação pode ser resolvida de forma direta

annxn=bnxn=bnann

Se sabemos o valor de xn, podemos calcular xn1 facilmente através da penúltima equação

an1,n1xn1+an1,nxn=bn1xn1=bn1an1,nxnan1,n1

Em geral,

{xi=1aii(binj=i+1xjaij)(1)xn=bnann

Ou seja, o problema de resolver um sistema linear n×n se torna mais simples quando ele está escalonado, uma vez que ele pode ser resolvido utilizando a fórmula (1).

A complexidade no tempo para calcular todas as n incógnitas de um sistema linear n×n utilizando (1) é O(n2). Isso será demonstrado depois.

Essa fórmula parece complicada, entretanto ela é codificada com poucas linhas de código.

Exemplo

Como exemplo, vamos resolver o sistema escalonado a seguir

[111023004][x1x2x3]=[21312]

Da última equação, segue que

4x3=12x3=3

A próxima incógnita é calculada utilizando o resultado anterior

2x2+3x3=132x2+3.3=132x2=139x2=4/2x2=2

Por último,

x1x2+x3=2x12+3=2x1+1=2x1=1

Ir para o índice

Escalonando um sistema linear

Até agora, só vimos como resolver um sistema linear escalonado. Para escalonar um sistema qualquer, devemos utilizar dois teoremas

(T1) Multiplicando-se os membros de uma equação qualquer de um sistema linear S por um número K0, o novo sistema S' obtido será equivalente a S (IEZZI, 1977).
(T2) Se substituirmos uma equação de um sistema linear S, pela soma membro a membro dela com uma outra, o novo sistema obtido, S', será equivalente a S (IEZZI, 1977).

Se quiser a demonstração desses teoremas, consulte o livro "Fundamentos de Matemática Elementar" nas referências [1].

Além dos teoremas anteriores, também utilizaremos a propriedade dos sistemas que permite trocar as equações de posição sem que o sistema se altere.

O processo de escalonamento de um sistema é similar ao processo de triangularização de uma matriz. Utilizamos a primeira equação para zerar todos os coeficientes da primeira incógnita das equações subsequentes.

Depois, utilizamos a segunda equação para zerar os coeficientes da segunda incógnita das equações subsequentes.

Isso é feito até a penúltima equação, pois após ela o sistema estará escalonado.

O coeficiente da primeira incógnita da primeira equação não pode ser zero, portanto devemos escolher uma equação que satisfaça essa condição.

O mesmo vale para o coeficiente da segunda incógnita da segunda equação, após zerarmos os coeficientes da primeira incógnita, e assim por diante. A condição deve ser verificada a cada iteração.

Para zerar os coeficientes, utilizamos os teoremas T1 e T2.

Exemplo

Como exemplo, vamos escalonar o seguinte sistema linear

[211121111][x1x2x3]=[332]

Multiplicamos a primeira equação por (1)×1/2=1/2 e somamos o resultado à segunda equação para zerar a primeira incógnita

[2111121/21+1/2111][x1x2x3]=[33+3/22]

[21103/23/2111][x1x2x3]=[39/22]

Agora, multiplicamos a primeira equação por 1/2 e somamos à terceira

[21103/23/21111/21+1/2][x1x2x3]=[39/22+3/2]

[21103/23/201/23/2][x1x2x3]=[39/27/2]

Por fim, vamos multiplicar a segunda equação por (1)×1/23/2=1/3 e somar o resultado à terceira para eliminar o coeficiente da segunda incógnita.

[21103/23/201/21/23/21/2][x1x2x3]=[39/27/23/2]

[21103/23/2001][x1x2x3]=[39/22]

Com isso, finalizamos o escalonamento. A solução do sistema é (x1,x2,x3)=(1,1,2).

Ir para o índice

Algoritmo da eliminação de Gauss

O algoritmo da eliminação de Gauss consiste em

  1. Dado um sistema S, obtenha um sistema escalonado S' equivalente à S;
  2. Resolva S'.

O pseudocódigo do algoritmo é dado a seguir

01. //GitHub: HenriqueIni
02. //https://www.blogcyberini.com
03. gaussSolver(An×n, bn)
04. |   para k ← 1 até n - 1
05. |   |  max ← |A(k, k)|
06. |   |  maxIndex ← k
07. |   |  para i ← k + 1 até n
08. |   |   |   se(max < |A(i, k)|)
09. |   |   |   |   max ← |A(i, k)|
10. |   |   |   |   maxIndex ← i
11. |   |   |   fim_se
12. |   |   fim_para
13. |   |   se(maxIndex ≠ k)
14. |   |   |   para j ← 1 até n
15. |   |   |   |   temp ← A(k, j)
16. |   |   |   |   A(k, j) ← A(maxIndex, j)
17. |   |   |   |   A(maxIndex, j) ← temp
18. |   |   |   fim_para
19. |   |   |   temp2 ← b(k)
20. |   |   |   b(k) ← b(maxIndex)
21. |   |   |   b(maxIndex) ← temp2
22. |   |   fim_se
23. |   |   se(A(k, k) = 0)
24. |   |   |   //o sistema é impossível ou não tem solução única
25. |   |   |   //det A = 0
26. |   |   |   retorne NULL
27. |   |   senão
28. |   |   |   para m ← k + 1 até n
29. |   |   |   |   F ← (-1) * A(m, k) / A(k, k)
30. |   |   |   |   A(m, k) ← 0 //evita  uma iteração
31. |   |   |   |   b(m) ← b(m) + F * b(k)
32. |   |   |   |   para l ← k + 1 até n
33. |   |   |   |   |   A(m, l) ← A(m, l) + F * A(k, l)
34. |   |   |   |   fim_para
35. |   |   |   fim_para
36. |   |   fim_se
37. |   fim_para
38. |   inicializar vetor X[1...n]
39. |   X(n) ← b(n) / A(n, n)
40. |   para i ← n - 1 até 1 decremento de 1
41. |   |   X(i) ← b(i)
42. |   |   para j ← i + 1 até n
43. |   |   |   X(i) ← X(i) - X(j) * A(i, j)
44. |   |   fim_para
45. |   |   X(i) ← X(i) / A(i, i)
46. |   fim_para
47. |   retorne X
48. fim_gaussSolver

Explicando o algoritmo

A variável An×n é a matriz dos coeficientes do sistema. O vetor bn contém os coeficientes dos termos independentes.

O algoritmo gaussSolver irá retornar a solução do sistema num vetor. Ele é muito parecido com o algoritmo de triangularização de matrizes.

O laço da linha 4 irá iterar cada equação do sistema linear (ou linha, pois o sistema está na forma matricial), exceto a última, pois, como vimos, o sistema já estará escalonado após a penúltima equação ser iterada.

As linhas 5-22 verificam qual equação, a partir da k-ésima, possui o maior k-ésimo coeficiente em módulo e coloca-a na k-ésima posição.

Isso é importante para amenizar a propagação de erros de arredondamento (consulte o artigo sobre triangularização de matrizes para obter mais detalhes). Isso também evita que o coeficiente A(k, k) seja zero, pois ele será o divisor no cálculo do fator F na linha 29.

É claro, se a matriz dos coeficientes for singular (detA=0), então A(k, k) será nulo, em alguma iteração. Consequentemente, temos duas situações: (a) o sistema é impossível ou (b) o sistema é possível e indeterminado. Não há o que fazer na situação (a), já o caso (b) não pode ser resolvido com o algoritmo apresentado.

Em suma, o algoritmo resolve apenas sistemas possíveis e determinados.

Se A(k, k) não é zero, então, para cada equação entre k+1 e n, o laço das linhas 28-35 irá calcular o fator F de tal forma que seja possível zerar o k-ésimo coeficiente da equação iterada. Em seguida, a k-ésima equação será multiplicada por F e o resultado será somado à equação da iteração corrente.

Após tudo isso, o sistema estará escalonado. Depois da etapa de escalonamento, as linhas 38-46 utilizam a fórmula (1) para calcular o valor das incógnitas e as armazena no vetor X, retornando-o no final do algoritmo.

Ir para o índice

Complexidade assintótica

Aqui, faremos uma análise bem básica do algoritmo. Vamos contar quantas vezes os códigos dos laços mais internos são executados.

Dividiremos o cálculo em duas partes

T=E+R

T é o número total de vezes que os códigos dos laços mais internos são executados; E corresponde à etapa de escalonamento; R corresponde à etapa de resolução do sistema escalonado.

O código do laço mais interno da etapa de escalonamento é (linha 33)

A(m, l) ← A(m, l) + F * A(k, l)

Esse trecho de código está num laço triplo aninhado

E=n1k=1nm=k+1nl=k+11=n1k=1nm=k+1(nk)=n1k=1(nk)2=n33n22+n6

O código do laço mais interno da etapa de resolução é (linha 43)

X(i) ← X(i) - X(j) * A(i, j)

Esse código está num laço duplamente aninhado

R=n1i=1nj=i+11=n1i=1(ni)=n22n2

Somando os resultados anteriores, teremos

T=n33n22+n6+n22n2=n33n3=O(n3)

Portanto, a complexidade do algoritmo da eliminação de Gauss é O(n3).

A mesma complexidade será obtida se você fizer uma análise mais detalhada e considerar a porção de código que foi ignorada.

Ir para o índice

Códigos

Os códigos em Java, C e em JavaScript do algoritmo da eliminação de Gauss podem ser obtidos nos links a seguir

Ir para o índice

Considerações finais

Além de rápido, o algoritmo da eliminação de Gauss também consome pouca memória. Os coeficientes do sistema linear escalonado são armazenados na própria matriz passada nos parâmetros e no vetor dos termos independentes.

Se você precisar do sistema original, deve criar uma cópia dele antes de executar o algoritmo.

O maior problema da eliminação de Gauss ocorre quando o termo A(k, k), em alguma iteração, é muito próximo de zero. Isso pode gerar erros de arredondamento por causa da divisão A(m, k)/A(k, k). Tais erros se propagam ao longo dos cálculos e podem tornar o resultado final menos preciso.

Esse problema é amenizado quando fazemos a troca de equações nas linhas 14-21, pois o coeficiente A(k, k) será o maior possível em módulo. Contudo, se a matriz A for muito mal condicionada, então os resultados poderão ser insatisfatórios, mesmo com a troca de equações [3]. Nesse caso, outro algoritmo deve ser utilizado.

Enfatizo que o algoritmo da eliminação de Gauss é exato. Esses erros ocorrem por causa das limitações da representação de números em ponto flutuante nos computadores.

Recomendo que o leitor consulte algum livro de cálculo numérico para mais informações sobre sistemas lineares. Deixarei o livro "Cálculo Numérico" (Neide Franco) [3] como sugestão.

Além desse livro, também recomendo o livro "Algoritmos: teoria e prática" (Cormen et al) [2], onde é feita uma extensa análise sobre algoritmos para a resolução de sistemas lineares e algoritmos gerais de matrizes.

Ir para o índice

Referências

Sugestões de livros para estudantes de computação na Amazon (patrocinado): Lista de Livros

Obrigado pela leitura! Se você puder, considere apoiar financeiramente o Blog Cyberini, Chave Pix: cyberpix9@gmail.com

Doar com PayPal

Siga o blog

Redes sociais: Facebook, Twitter, YouTube, Pinterest, Instagram, Telegram

Importante: utilize o bom senso na hora de comentar. Acesse a política de privacidade para maiores informações sobre comentários.

Nenhum comentário:

Postar um comentário

Este site usa cookies para fornecer serviços, analisar o tráfego e exibir publicidade personalizada, conforme a nossa política de privacidade. Seus dados, como IP e user agent, são compartilhados com nossos parceiros (como o Google). Saiba Mais

RecusarAceitar