O Método De Gauss-Jordan: Um jogo de adivinhação
Introdução
O método de Gauss-Jordan, para a resolução de sistemas lineares, nos é apresentado, por diversas vezes, como um jogo de adivinhação para as operações elementares sobre linhas da matriz aumentada, obtida a partir de um sistema de equações lineares. Este texto tem por intuito inicial apresentar alguns conceitos referentes ao método de Gauss-Jordan. Um segundo objetivo consiste em fazer uma análise sobre o algoritmo, computacional, apresentado para a resolução de sistemas utilizando o método e, por final, fazer uma correlação entre a resolução manual e o algoritmo computacional.
Equação Linear
Uma função linear é, no estudo das funções, uma função que associa a cada valor de $x$ um valor de $y$, de forma que $y=ax$, onde $a \in \mathbb{R}$. No estudo das funções de $\mathbb{R}^2$, a função linear tem a lei de formação $z=ax+by$. Uma equação linear de $n$ incógnitas é, por analogia, uma equação da forma $a_1 x_1+a_2 x_2+\cdots +a_n x_n=b$, onde $a_1$, $a_2$, $\cdots$, $a_n \in \mathbb{R}$.
Sistema de Equações Lineares
Um sistema de equações lineares é uma lista com $m$ equações lineares, sendo que cada uma possui $n$ incógnitas, pode ser representado da seguinte forma:
Com $a_{ij}\in\mathbb{R}$, para $1\leq i\leq m$, $1 \leq j \leq n$.
Uma solução para o sistema, aqui chamado de $(*)$, é uma lista com $n$ números, isto é, uma n-upla, $(x_1,x_2,\cdots,x_n)$, que satisfaça, simultaneamente, as $m$ equações do sistema.
Este sistema pode ser representado, também, na forma matricial, isto é, na forma $AX=B$, onde a matriz $A$ é definida como a matriz dos coeficientes das equações, enquanto que a matriz $X$ é definida como a matriz coluna com as incógnitas e a matriz $B$ como a matriz coluna dos termos independentes. Observe: Veja que se fizermos $AX=B$, iremos obter, novamente, o sistema $(*)$.
Podemos definir, também, a chamada matriz aumentada do sistema, que é uma matriz que possui $n+1$ colunas onde as $n$ primeiras colunas são as colunas de $A$ e a última coluna é a matriz $B$. Denotaremos, aqui, a matriz aumentada de um sistema $AX=B$ por $[A\text{|}B]$. A matriz aumentada do sistema $(*)$ é escrita, então, da seguinte forma: Utilizaremos, aqui, traços verticais para separar a última coluna da matriz aumentada $[A\text{|}B]$.
Considere o sistema de equações lineares, de incógnitas $x_1$, $x_2$ e $x_3$, descrito por: A partir do sistema linear podemos obter o sistema em forma matricial: Também podemos obter, a partir daí, a matriz aumentada do sistema:
Observe que solucionar o sistema acima descrito é, de fato, um trabalho complexo. Observe, então, o seguinte sistema:
Note que, de fato, podemos resolver o sistema $(\Delta)$ apenas isolando e substituindo as incógnitas. O ponto interessante é que as soluções para o primeiro sistema, enunciado no Exemplo , e este sistema $(\Delta)$ são as mesmas. O ponto de interesse, agora, é desenvolver um método pelo qual podemos fazer transformações sobre a matriz aumentada $[A\text{|}B]$ de um sistema com o propósito de encontrar um segundo sistema linear cujas soluções são, exatamente, as mesmas do primeiro e que possa ser solucionado de forma mais fácil.
Dois sistemas de equações lineares são equivalentes se, e somente se, todas as soluções de um sistema também é solução do outro sistema.
Operações elementares sobre linhas
Considere uma matriz $A$ qualquer. Utilizaremos, aqui, uma matriz $A$ genérica de tamanho $m\times n$:
Chamamos de operações elementares sobre linhas, três tipos de operações, básicas, realizadas com as linhas de uma matriz.
1) Permutação de linhas
Considere dois inteiros $i$ e $j$ que representam duas linhas da matriz $A$, então a notação $L_i \leftrightarrow L_j$ indica que a segunda matriz foi obtida permutando, isto é, trocando, as duas linhas de lugar.
Veja a operação $L_i \leftrightarrow L_j$ na matriz $A$, genérica:
2) Multiplicação por constante
Considere a linha $i$ da matriz $A$. A segunda operação elementar sobre linhas que podemos realizar consiste em multiplicar todos os elementos da linha $i$ desta matriz por uma constante $c$, não nula.
Veja a operação $L_1 \to 3L_1$ aplicada a matriz $A$, genérica:
3) Soma de duas linhas
A terceira operação elementar que podemos realizar consiste em somar duas linhas da matriz $A$.
Veja a operação $L_1\to L_1+L_2$ aplicada a matriz $A$, genérica:
Note que, em alguns casos, podemos juntar mais de uma operação elementar em uma única representação, por exemplo, $L_2 \to L_2 - 4L_1$. Para justificar este uso, veja o Exemplo .
Considere a seguinte matriz $A$ e as subsequentes operações sobre linhas realizadas na mesma matriz: 1) $L_1 \to -4L_1$ 2) $L_2 \to L_2 + L_1$ 3) $L_1 \to -\frac{1}{4}L_1$
Observe que fazer operação por operação é, de certa forma, trabalhoso e, portanto, juntar as operações em uma única, neste caso $L_2 \to L_2 - 4L_1$, acaba sendo vantajoso durante o trabalho com as matrizes.
Duas matrizes são equivalentes se uma é obtida a partir da outra realizando um número finito de operações elementares.
Já definimos, até aqui, sistemas lineares equivalentes e matrizes equivalentes. O próximo enunciado traz um resultado que correlaciona, de maneira eficiente, estas duas definições.
Dois sistemas que possuem matrizes aumentadas equivalentes são equivalentes.
A demonstração deste teorema será, aqui, omitida, pois requer diversas definições e propriedades que deixariam este texto demasiado extenso. Faremos a demonstração, porém, em outro texto e assim que este for publicado, será referenciado aqui.
Escalonamento
O Teorema nos diz que se encontrarmos dois sistemas cujas matrizes aumentadas sejam equivalentes, isto é, uma matriz aumentada é obtida a partir da outra por meio de operações elementares, então estes sistemas lineares são equivalentes, ou seja, possuem as mesmas soluções.
Forma Escalonada - Diz-se que uma matriz está na forma escalonada se satisfaz as seguintes condições:
1) O número de zeros do início de cada linha aumenta de uma linha para outra, de cima para baixo, exceto de a linha é toda nula.
2) As linhas nulas, se existirem, são as últimas da matriz.
Pivô - O primeiro elemento não nulo de cada linha não nula de uma matriz escalonada é chamado de pivô.
Forma Escalonada Reduzida - Uma matriz escalonada está na forma escalonada reduzida se satisfaz as seguintes condições:
1) Se todos os seus pivôs são iguais a 1.
2) Se os pivôs são os únicos elementos não nulos de suas colunas.
A partir destas definições, comumente, apresentam-nos o método de Gauss, ou Gauss-Jordan, como um jogo de adivinhação onde devemos adivinhar as operações elementares para aplicar em uma matriz aumentada para transforma-la na forma escalonada reduzida para podermos, então, resolver um sistema simplificado que tenha as mesmas soluções.
Apresentaremos, a partir daqui, um algoritmo que é utilizado, tanto por humanos como por computadores, para a resolução de sistemas por meio do método de Gauss, ou Gauss-Jordan.
Processo de Eliminação de Gauss-Jordan
Seja $A$ uma matriz aumentada de um sistema, com termo geral $a_{ij}$, comece, então, com a linha $i=1$ e a coluna $j=1$ e então execute os seguintes passos:
1) Se o elemento $a_{ij}=0$, então troque a linha $i$ com alguma outra linha abaixo para garantir que $a_{ij}\neq 0$. Lembre-se que este elemento $a_{ij}\neq 0$ é chamado de pivô. Caso todas as entradas da coluna $j$ sejam iguais a zero, então some 1 em $j$.
2) Divida a linha $i$ por $a_{ij}$ para que o pivô assuma o valor igual a 1.
3) Elimine todas as outras entradas da coluna $j$ subtraindo a linha $i$ multiplicada pelo elemento da coluna $j$ das demais linhas.
4) Some 1 em $i$ e 1 em $j$ para prosseguir ao proximo pivô e, então, volte ao passo 1.
Este algoritmo tem fim ao ser executado com a última linha e última coluna da matriz aumentada. O resultado final é a matriz na forma escalonada reduzida.
A partir do algoritmo apresentado podemos, então, trabalhar com o Exemplo de forma a solucionar o sistema utilizando o escalonamento de matrizes. Veja:
Considere, novamente, o sistema de incógnitas $x_1$, $x_2$ e $x_3$ do Exemplo : E considere, também, sua matriz aumentada:
Lembre-se que, seguindo o algoritmo, devemos começar com a linha $i=1$ e coluna $j=1$. Veja que o elemento $a_{11}=1\neq 0$, portanto, não há a necessidade de permutarmos esta linha. No passo 2, devemos dividir toda a linha $i$ pelo valor $a_{ij}$. Neste caso, $a_{ij}=1$, portanto não há necessidade em dividir. No terceiro passo, devemos subtrair as demais linhas pela linha $i$ multiplicada pelos elementos da coluna $j$ das demais linhas.
As duas operações do terceiro passo, são: $L_2 \to L_2 - 2L_1$ e $L_3 \to L_3 - 3L_1$ e nos resultam:
Somamos 1 a $i$ e a $j$ e então voltamos ao primeiro passo. Agora temos $i=2$ e $j=2$. Veja que, novamente, não há a necessidade de trocarmos linhas da matriz, porém, devemos dividir a linha $i$ pelo termo $a_{ij}=-2$. Temos, então, que executar a operação: $L_2 \to -\frac{1}{2}L_2$, de onde obtemos:
Continuando, ao terceiro passo, vamos eliminar os demais elementos da coluna $j=2$, utilizando as operações: $L_1\to L_1 - 2L_2$ e $L_3\to L_3 + 4L_2$:
Somando 1 a $i$ e a $j$, novamente, temos $i=3$ e $j=3$. Observe que a terceira linha é, agora, nula e portanto, o noso algoritmo para aqui.
Reescrevendo a matriz aumentada em forma de sistema, temos que $x_1=1$ e que $x_2+\frac{1}{2}x_3=1$. Observe que, da última igualdade, temos que $x_2=1-\frac{1}{2}x_3$ e que, portanto, para qualquer valor de $x_3$ temos um valor de $x_2$ e $x_1=1$ que satisfaz o sistema, donde concluimos que o sistema possui infinitas soluções, sendo uma delas $S=\{(1, 1, 0)\}$.
Considerações finais
Deve-se atentar que omitimos, aqui, as análises das matrizes na forma escalonada reduzida quanto ao número de soluções, além da demonstração de um importante teorema, pois, de fato, a ideia central do texto é o algoritmo para o processo de eliminação de Gauss-Jordan.
Referências
- BOLDRINI, J. L. et al. Álgebra Linear, 3. ed. São Paulo: Harper & Row do Brasil, 1980.
- CABRAL, M. GOLDFELD, P. Curso de Álgebra Linear: Fundamentos e Aplicações, 3. ed. Rio de Janeiro: UFRJ, 2012.
- PANFEROV V. The Gauss-Jordan Elimination Algorithm <https://goo.gl/9YF4YN> Acesso em Outubro de 2017.
