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.
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]
$$\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*}$$
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)$.
Algoritmo da eliminação de Gauss
O algoritmo da eliminação de Gauss consiste em
- Dado um sistema S, obtenha um sistema escalonado S' equivalente à S;
- 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.
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.
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
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.
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.
Nenhum comentário:
Postar um comentário