Algoritmo de Gauss-Jordan

A aplicação do Algoritmo de Eliminação de Gauss na resolução de um sistema de equações lineares reduz o problema inicial a um outro, equivalente ao dado (ou seja, com o mesmo conjunto de soluções) onde a matriz associada ao sistema é escada de linhas. Tal permite a utilização do algoritmo da susbstituição inversa por forma a se encontrar (caso existam) as soluções para o problema. Nesse método, o valor das incógnitas básicas era encontrado à custa das incógnitas livres e dos termos independentes, bem como do valor das incógnitas básicas encontrado no passo anterior, no sentido sul $\rightarrow$norte do vector das incógnitas. Recorde que no AEG a estratégia tinha como objectivo, por operações elementares de linhas, obter zeros por debaixo de cada pivot, estratégia essa implementada no sentido NW $\rightarrow$SE. Este raciocínio pode ser estendido a obterem-se zeros por cima dos pivots, no sentido SW $\rightarrow$NE, por operações elementares de linhas. De facto, neste processo estão ausentes trocas de linhas, já que os pivots usados neste novo processo são que estiveram envolvidos na fase inicial correspondente ao AEG. O resultado final será uma matriz constituída pelos pivots, tendo estes zeros por debaixo e por cima. Ou seja, se se dividir cada linha não nula pelo pivot respectivo, obtemos uma matriz da forma, a menos de trocas de colunas, uma matriz da forma $\left[\begin{array}{c\vert c} I_k & M \hline 0 & 0\end{array}\right]$, podendo os blocos nulos não existir. A este método (à excepção da possível troca de colunas) é denominado o algoritmo de Gauss-Jordan, e a matriz obtida diz-se que está na forma canónica (reduzida) de linhas, ou na forma normal (ou canónica) de Hermite. Ou seja, a matriz $H=[h_{ij}]$, $m \times n$, obtida satisfaz:

1. $H$ é triangular superior,
2. $h_{ii}$ é ou 0 ou 1,
3. se $h_{ii}=0$ então $h_{ik}=0$, para cada $k$ tal que $1\le k\le n$,
4. se $h_{ii}=1$ então $h_{ki}=0$ para cada $k\ne i$.

Repare que só são realizadas operações elementares nas linhas da matriz. A aplicação deste método na resolução de uma sistema de equações lineares permite obter, de forma imediata, o valor das incógnitas básicas. Apesar deste método parecer mais atractivo que o de Gauss (ou suas variantes), em geral é menos eficiente do ponto de vista computacional.

Octave
Considere a matriz $A=\left[\begin{array}{cccc} 1 & 2 & 3 & 3\\ 2 & 0 & 1 & -1\\ 0 & 0 &-1 & -3\end{array}\right]$. A forma normal de Hermite de $A$ é

> rref (A)
ans =

   1   0   0  -2
   0   1   0  -2
   0   0   1   3

Ora se $A$ for a matriz aumentada associada a um sistema de equações lineares, a forma canónica apresentada atrás fornece-nos uma solução para o sistema, no caso $(-2,-2,3)$.

No que se segue, mostramos como se aplica o algoritmo de Gauss-Jordan para inverter matrizes.

Seja $A$ uma matriz $n\times n$, não-singular. Ou seja, invertível. De forma equivalente, existe uma única matriz $X$ tal que $AX=I_n$. Denotemos a matriz $X$, que pretendemos obter, à custa das suas colunas: $X=\left[\begin{array}{cccc} X_1 & X_2 &\cdots &X_n \end{array}\right]$. Pela forma como está definido o produto matricial, e tomando $e_i$ como a $i$-ésima coluna da matriz $I_n$, a igualdade $AX=I_n$ pode-se escrever como $\left[\begin{array}{cccc} AX_1 & AX_2 &\cdots &AX_n \end{array}\right]=\left[\begin{array}{cccc} e_1 & e_2 & \cdots &e_n\end{array}\right]$. Surgem-nos, então, $n$ equações matriciais:

$$AX_1 = e_1, AX_2=e_2 , \dots , AX_n=e_n.$$

Como $A$ é invertível, cada uma destas equações é consistente e tem apenas uma solução. A solução de $AX_j=e_j$ é a coluna $j$ da matriz $X$ inversa de $A$ que pretendemos calcular. Poder-se-ia aplicar a estratégia de Gauss a cada uma destas equações, ou seja, à matriz aumentada $\left[\begin{array}{c\vert c}A &e_j \end{array}\right]$. Como a matriz do sistema é a mesma, as operações elementares envolvidas seriam as mesmas para as $n$ equações. Essas operações elementares podem ser efectuadas simultaneamente, considerando a matriz aumentada $n\times 2n$

$$\left[\begin{array}{c\vert c} A& \begin{array}{cccc} 1 & 0 & \cdo... ... 1 & &\vdots \\ & \cdots &&\\ 0 & \cdots & 0 &1\end{array}\end{array}\right].$$

Sendo a matriz invertível, a matriz escada de linhas $U$ obtida de $A$ por aplicação do AEG tem elementos diagonais não nulos, que são os pivots que surgem na implementação do algoritmo. Aplicando Gauss-Jordan (ou seja, no sentido SE $\rightarrow$NW, criando zeros por cima dos pivots que se vão considerando), obtemos uma matriz da forma $$\left[\begin{array}{c\vert c} \begin{array}{cccc} d_1 & 0& \d... ...ay}{cccc} Y_1 & Y_2 & \cdots & Y_n\end{array}\end{array}\right]$$. Dividindo a linha $i$ por $d_i$, para $i=1,...,n$, obtém-se a matriz

$$\left[\begin{array}{c\vert c} I_n & \begin{array}{cccc} \tilde X_1 &\tilde X_2 & \cdots & \tilde X_n\end{array}\end{array}\right].$$

Ora tal significa que $\tilde X_i$ é a solução de $AX=e_i$. Ou seja, o segundo bloco da matriz aumentada indicada atrás não é mais que a inversa da matriz $A$. Isto é, Gauss-Jordan forneceu a matriz $\left[\begin{array}{c\vert c} I_n & A^{-1}\end{array}\right]$.