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

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(n³), que é o objetivo deste artigo.

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
  • Exemplo
• Escalonando um sistema linear
  • Exemplo
• Algoritmo da eliminação de Gauss
  • Explicando o algoritmo
• Complexidade assintótica
• Códigos
• Considerações finais
• Referências

Sistemas lineares escalonados

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

$$\begin{align*}a_{11}x_1+ a_{12}x_2+ a_{13}x_3+\ldots+a_{1n}x_n&=b_1\\a_{22}x_2+ a_{23}x_3+\ldots+a_{2n}x_n&=b_2\\a_{33}x_3+\ldots+a_{3n}x_n&=b_3\\\ldots \ldots \ldots \ldots &\ldots\\a_{nn}x_n&=b_n\end{align*}$$

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

$$\begin{bmatrix}a_{11}&a_{12}&a_{13}&\cdots&a_{1n}\\0&a_{22}&a_{23}&\cdots&a_{2n}\\0&0&a_{33}&\cdots&a_{3n}\\\vdots&\vdots&\vdots &\vdots &\vdots\\0 &0&0&\cdots&a_{nn}\end{bmatrix}\begin{bmatrix}x_1\\x_2\\x_3\\\vdots\\x_n\end{bmatrix}=\begin{bmatrix}b_1\\b_2\\b_3\\\vdots\\b_n\end{bmatrix}$$

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

$$\begin{align*}a_{nn}x_n=b_n\\x_n=\frac{b_n}{a_{nn}}\end{align*}$$

Se sabemos o valor de $x_n$, podemos calcular $x_{n-1}$ facilmente através da penúltima equação

$$\begin{align*}a_{n-1,n-1}x_{n-1}+a_{n-1,n}x_n=b_{n-1}\\x_{n-1}=\frac{b_{n-1}-a_{n-1,n}x_n }{a_{n-1,n-1}}\end{align*}$$

Em geral,

$$\begin{cases}x_i=\cfrac{1}{a_{ii}}\left(b_i-\sum_{j=i+1}^n x_j a_{ij}\right)\quad (1)\\x_n=\cfrac{b_n}{a_{nn}}\end{cases}$$

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(n^2)$. 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

$$\begin{bmatrix}1 & -1 & 1\\0 & 2 & 3\\0 & 0 & -4\end{bmatrix}\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}=\begin{bmatrix}2\\13\\-12\end{bmatrix}$$

Da última equação, segue que

$$\begin{align*}-4x_3&=-12\\x_3&=3\end{align*}$$

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

$$\begin{align*}2x_2+3x_3=13\\2x_2+3.3=13\\2x_2=13-9\\x_2=4/2\\x_2=2\end{align*}$$

Por último,

$$\begin{align*}x_1-x_2+x_3=2\\x_1-2+3=2\\x_1+1=2\\x_1=1\end{align*}$$

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 $K\neq 0$, 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

$$\begin{bmatrix}2 & 1 & -1\\1 & 2 & 1\\1 & 1 & 1\end{bmatrix}\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}=\begin{bmatrix}-3\\3\\2\end{bmatrix}$$

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

$$\begin{bmatrix}2 & 1 & -1\\1-1 & 2-1/2 & 1+1/2\\1 & 1 & 1\end{bmatrix}\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}=\begin{bmatrix}-3\\3+3/2\\2\end{bmatrix}$$

$$\begin{bmatrix}2 & 1 & -1\\0 & 3/2 & 3/2\\1 & 1 & 1\end{bmatrix}\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}=\begin{bmatrix}-3\\9/2\\2\end{bmatrix}$$

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

$$\begin{bmatrix}2 & 1 & -1\\0 & 3/2 & 3/2\\1-1 & 1-1/2 & 1+1/2\end{bmatrix}\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}=\begin{bmatrix}-3\\9/2\\2+3/2\end{bmatrix}$$

$$\begin{bmatrix}2 & 1 & -1\\0 & 3/2 & 3/2\\0 & 1/2 & 3/2\end{bmatrix}\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}=\begin{bmatrix}-3\\9/2\\7/2\end{bmatrix}$$

Por fim, vamos multiplicar a segunda equação por $(-1)\times \cfrac{1/2}{3/2}=-1/3$ e somar o resultado à terceira para eliminar o coeficiente da segunda incógnita.

$$\begin{bmatrix}2 & 1 & -1\\0 & 3/2 & 3/2\\0 & 1/2-1/2 & 3/2-1/2\end{bmatrix}\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}=\begin{bmatrix}-3\\9/2\\7/2-3/2\end{bmatrix}$$

$$\begin{bmatrix}2 & 1 & -1\\0 & 3/2 & 3/2\\0 & 0 & 1\end{bmatrix}\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}=\begin{bmatrix}-3\\9/2\\2\end{bmatrix}$$

Com isso, finalizamos o escalonamento. A solução do sistema é $(x_1, x_2, x_3)=(-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 ($\det A = 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

$$\begin{align*}E&=\sum_{k=1}^{n-1}\sum_{m=k+1}^n\sum_{l=k+1}^n 1\\&=\sum_{k=1}^{n-1}\sum_{m=k+1}^n (n-k)\\&=\sum_{k=1}^{n-1} (n-k)^2\\&=\frac{n^3}{3}-\frac{n^2}{2}+\frac{n}{6}\end{align*}$$

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

$$\begin{align*}R&=\sum_{i=1}^{n-1} \sum_{j=i+1}^n 1\\&=\sum_{i=1}^{n-1} (n-i)\\&=\frac{n^2}{2}-\frac{n}{2}\end{align*}$$

Somando os resultados anteriores, teremos

$$\begin{align*}T&=\frac{n^3}{3}-\frac{n^2}{2}+\frac{n}{6}+ \frac{n^2}{2}-\frac{n}{2}\\&=\frac{n^3}{3}-\frac{n}{3}\\&=O(n^3)\end{align*}$$

Portanto, a complexidade do algoritmo da eliminação de Gauss é $O(n^3)$.

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

• Eliminação de Gauss no Google Drive
• Eliminação de Gauss no GitHub

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

• [1] IEZZI, G. Fundamentos de Matemática Elementar: Sequências, Matrizes, Determinantes, Sistemas. Vol. 4. 2 ed. São Paulo: Atual, 1977.
• [2] CORMEN, T. H. et al. Algoritmos: teoria e prática. 3 ed. Rio de Janeiro: Elsevier, 2012.
• [3] FRANCO, N. B. Cálculo Numérico. 1 ed. São Paulo: Pearson, 2006.