O Algoritmo de Eliminação de Gauss

O Algoritmo de Eliminação de Gauss, (abrev. AEG), segue os passos que em baixo se descrevem:

Seja $A$ uma matriz $m \times n$ não nula.

1. Assuma que $(A)_{11}\ne 0$. Se tal não acontecer, então troque-se a linha 1 com uma linha $i$ para a qual $(A)_{i1}\ne 0$. Ou seja, multiplique $A$, à esquerda, por $P_{1i}$. Para simplificar a notação, $A$ denotará tanto a matriz original como a obtida por troca de duas das suas linhas. A $(A)_{11}$ chamamos pivot do algoritmo. Se todos os elementos da primeira coluna são nulos, use 2.
2. Se a estratégia indicada no passo 1 não for possível (ou seja, os elementos da primeira coluna são todos nulos), então aplique de novo o passo 1 à submatriz obtida de $A$ retirando a primeira coluna.
3. Para $i=2,\dots,m$, e em ${A}$, substitua a linha $i$ pela sua soma com um múltiplo da linha 1 por forma a que o elemento obtido na entrada $(i,1)$ seja 0. Tal corresponde a multiplicar a matriz $A$, à esquerda, por $E_{i1}\left(-\frac{(A)_{i1}}{(A)_{11}}\right)$.
4. Repita os passos anteriores à submatriz da matriz obtida pelos passos descritos, a que se retirou a primeira linha e a primeira coluna.

Após se aplicar o passo 3 em todas as linhas e na primeira coluna, e supondo que $(A)_{11}\ne 0$, a matriz que se obtem tem a forma seguinte:

$$\left[\begin{array}{cccc} (A)_{11} &(A)_{12} &(A)_{13} &(A)_{1n} ... ... & ?\\ 0 & ? & ? & ?\\ \vdots & ? & ? & ?\\ 0 & ? & ? & ?\end{array}\right].$$

Ou seja, e por operações elementares de linhas, podemos obter de $A$ uma matriz com a forma $\left[\begin{array}{c\vert c} (A)_{11}& * \hline 0 & \widetilde A\end{array}\right]$. O algoritmo continua agora aplicado à matriz $\widetilde A$ segundo os passos 1, 2 e 3. Note que as operações elementares operadas nas linhas de $\widetilde A$ são também elas operações elementares realizadas nas linhas de $\left[\begin{array}{c\vert c} (A)_{11}& * \hline 0 & \widetilde A\end{array}\right]$. As operações elementares efectuadas em $\widetilde A$ dão origem a uma matriz da forma $\left[\begin{array}{c\vert c} (\widetilde A)_{11}& * \hline 0 & \widetilde{\widetilde A}\end{array}\right]$, onde assumimos $(\widetilde A)_{11}\ne 0$. Essas operações elementares aplicadas às linhas de $\left[\begin{array}{c\vert c} (A)_{11}& * \hline 0 & \widetilde A\end{array}\right]$ dão lugar à matriz $\left[\begin{array}{cc\vert c} (A)_{11}& \dots &(A)_{1m}\\ 0 & (\widetilde A)_{11}& * \hline 0 & 0 & \widetilde{\widetilde A}\end{array}\right]$. Note que se assumiu que as entradas $(i,i)$ são não nulas, ou que existe uma troca conveniente de linhas por forma a se contornar essa questão. Como é óbvio, tal pode não ser possível. Nesse caso aplica-se o passo 2. Ou seja, e quando tal acontece, tal corresponde à não existência de pivots em colunas consecutivas. Como exemplo, considere a matriz $M=\left[\begin{array}{cccc} 2 & 2 & 2 & 2\\ 2 & 2 & 2 & 0\\ 1 & 1 & 0 & 1\end{array}\right]$. Multiplicando esta matriz, à esquerda, por $E_{31}(-\frac{1}{2})E_{21}(-1)$, ou seja, substiuindo a linha 2 pela sua soma com o simétrico da linha 1, e a linha 3 pela sua soma com metade do simétrico da linha 1, obtemos a matriz $M_2=\left[\begin{array}{c\vert ccc} 2 & 2 & 2 & 2 \hline 0 & 0 & 0 &-2\\ 0 & 0 &-1 & 0\end{array}\right]$. Aplicamos agora o algoritmo à submatriz $\widetilde M=\left[\begin{array}{ccc} 0 & 0 &-2\\ 0 &-1 & 0\end{array}\right]$. Note que a esta submatriz teremos que aplicar (2) por impossibilidade de se usar (1); de facto, não há elementos não nulos na primeira coluna de $\widetilde M$. Seja, então, $\widetilde M_2$ a matriz obtida de $\widetilde M$ a que retirou a primeira coluna; ou seja, $\widetilde M_2=\left[\begin{array}{cc} 0 &-2\\ -1 & 0\end{array}\right]$. É necessário fazer a troca das linhas por forma a obtermos um elemento não nulo que terá as funções de pivot. Essa troca de linhas é uma operação elementar também na matriz original $M_2=\left[\begin{array}{cc\vert cc} 2 & 2 & 2 & 2 \hline 0 & 0 & 0 &-2\\ 0 & 0 &-1 & 0\end{array}\right]$. Tal corresponde a multiplicá-la, à esquerda, por $P_{23}$. Repare que, sendo os elementos nas linhas 2 e 3 e nas colunas 1 e 2 nulos, a troca das linhas de facto apenas altera as entradas que estão simultaneamente nas linhas envolvidas e nas entradas à direita do novo pivot. Obtemos, assim, a matriz $\left[\begin{array}{cccc} 2 & 2 & 2 & 2\\ 0 & 0 & -1 & 0\\ 0 & 0 & 0 & 2\end{array}\right]$. A matriz obtida tem uma particularidade: debaixo de cada pivot todos os elementos são nulos.

Octave
I3 indica a matriz identidade de ordem 3.

> M=[2 2 2 2;2 2 2 0;1 1 0 1]
> P23=I3([1 3 2],:);
> E31=I3; E31(3,1)=-0.5;
> E21=I3; E21(2,1)=-1;  
> P23*E31*E21*M
U =

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

Como foi referido, a matriz obtida por aplicação dos passos descritos no Algoritmo de Eliminação de Gauss tem uma forma muito particular. De facto, debaixo de cada pivot todos os elementos são nulos. A esse tipo de matriz chamamos matriz escada (de linhas). Uma matriz $A=[a_{ij}]$ é matriz escada (de linhas) se

(i)

se $a_{ij}\ne 0$ com $a_{ik}=0$, para $k<j$, então $a_{lk}=0$ se $k\le j$ e $l>i$;

(ii)

as linhas nulas surgem depois de todas as outras.

Sempre que o contexto o permita, diremos matriz escada para significar matriz escada de linhas.

A matriz $U=\left[\begin{array}{cccc} 2 & 2 & 2 & 2\\ 0 & 0 & -1 & 0\\ 0 & 0 & 0 & 2\end{array}\right]$ é uma matriz escada (de linhas) que se obteve de $M$ por aplicação dos passos $(1)$-$(4)$. É óbvio que uma matriz escada é triangular superior, mas o recíproco não é válido em geral. Como exemplo, considere a matriz $\left[\begin{array}{cc} 0 & 1 0 &1\end{array}\right]$.

Teorema 2.3.2 (Factorização $PA=LU$)   Dada uma matriz $A$, existem matrizes $P$ permutação, $L$ triangular inferior com 1's na diagonal principal e $U$ matriz escada para as quais $PA=LU$.

Ou seja, a matriz $A$ iguala $P^{-1}LU$. Portanto, toda a matriz é equivalente por linhas a uma matriz escada de linhas.

Antes de procedermos à prova deste resultado, abrimos um parênteses para apresentarmos dois exemplos que servem de motivação ao lema que se segue.

Considere a matriz $A=\left[\begin{array}{ccc} 0 & 3 & -2\\ -1 & 3 & 0\\ 1 & 3 & -5\end{array}\right]$. A troca da primeira com a segunda linhas dá origem à matriz $\widetilde A= \left[\begin{array}{ccc} -1 & 3 & 0\\ 0 & 3 & -2\\ 1 & 3 & -5\end{array}\right]$, a qual, e usando o AEG descrito atrás, satisfaz $E_{32}(-3) E_{31}(2) \widetilde A = \left[\begin{array}{ccc} -1 & 3 & 0\\ 0 & 3 &-2\\ 0 & 0 & 1\end{array}\right]$. Ou seja, existem matrizes $P$ permutação, $L$ triangular inferior com 1's na diagonal e $U$ matriz escada para as quais $PA=LU$. Para tal, basta tomar $$P=\left[ \begin{array}{ccc} 0 & 1 & 0\\ 1 & 0 & 0\\ 0 & 0 & 1\end{array}\right]$$, $L=(E_{32}(-3) E_{31}(2))^{-1}=E_{31}(-2)E_{32}(3)$, e $U=\left[\begin{array}{ccc} -1 & 3 & 0\\ 0 & 3 &-2\\ 0 & 0 & 1\end{array}\right]$.

Considere agora a matriz $M=\left[\begin{array}{ccc} 1 & 1 & 1\\ 0 & 0 & 1\\ 1 & 0 & 1\end{array}\right]$. Ora $E_{31}(-1) M=\left[\begin{array}{ccc} 1& 1 & 1\\ 0 & 0 & 1\\ 0 & -1 & 0\end{array}\right]$, o que força a troca da segunda pela terceira linha. Obtemos, assim, $P_{23} E_{31}(-1) M=\left[\begin{array}{ccc} 1& 1 & 1\\ 0 & -1 & 0\\ 0 & 0 & 1\end{array}\right]$, que é uma matriz escada. Neste caso, como se obtêm as matrizes $P,L,U$ do teorema? Ao contrário do exemplo anterior, a realização matricial das operações elementares por linhas do AEG não nos fornece, de forma imediata, essa factorização. No entanto, poder-se-ia escrever $E_{31}(-1) M = P_{23} \left[\begin{array}{ccc} 1& 1 & 1\\ 0 & -1 & 0\\ 0 & 0 & 1 \end{array}\right]$, já que $P_{23}^{-1}=P_{23}$, e portanto $M=E_{31}(1) P_{23} \left[\begin{array}{ccc} 1& 1 & 1\\ 0 & -1 & 0\\ 0 & 0 & 1\end{array}\right]$, pois $E_{31}(-1)^{-1}=E_{31}(1)$. Note que $E_{31}(1) P_{23}\ne P_{23}E_{31}(1)$. Não obstante, repare que $E_{31}(1) P_{23}=P_{23} E_{21}(1)$, donde $M=P_{23} E_{21}(1) \left[\begin{array}{ccc} 1& 1 & 1\\ 0 & -1 & 0\\ 0 & 0 & 1\end{array}\right]$, e portanto $PA=LU$, com $P=P_{23},L=E_{21}(1)$ e $U=\left[\begin{array}{ccc} 1& 1 & 1\\ 0 & -1 & 0\\ 0 & 0 & 1\end{array}\right]$.

Lema 2.3.3   Para $i,k,l> j$, e para todo o $a \in {\mathbb{K}}$, é válida a igualdade $E_{ij}(a) P_{kl}=P_{kl}E_{lj}(a)$.

Se $k\ne i$, então a igualdade é óbvia.

Suponha que $k=i$. Pretende-se mostrar que $E_{ij}(a) P_{il}=P_{il}E_{lj}(a)$, com $i,l>j$. Sendo $P_{il}E_{lj}(a)$ a matriz obtida de $E_{lj}(A)$ trocando as linhas $i$ e $l$, e visto a linha $l$ de $E_{lj}(a)$ ser

$$\begin{array}{ccccccccccc} [ 0 & \cdots &0 & a & 0 & \cdots ... ... \uparrow& & && \uparrow &\\ & & & j & & & & l & &\end{array}$$

então a linha $i$ de $P_{il}E_{lj}(a)$ é

$$\begin{array}{ccccccccccc} [ 0 & \cdots &0 & a & 0 & \cdots ... ...\uparrow& & && \uparrow &\\ & & & j & & & & l & &\end{array}.$$

$E_{ij}(a)P_{il}$ é a matriz obtida de $P_{il}$ a que à linha $i$ se somou a linha $j$ de $P_{il}$ multiplicada por $a$. Sendo a linha $i$ de $P_{il}$

$$\begin{array}{ccccccccc} [ 0 & \cdots & 0 & \cdots &0 & 1 & ... ...ts &0 ] \\ & & & && \uparrow &\\ & & & & & l & &\end{array}$$

e a linha $j$ de $P_{il}$, e já que $j<i,l$,

$$\begin{array}{ccccccccc} [ 0 & \cdots & 0 & \cdots &0 & 1 & ... ...ts &0 ] \\ & & & && \uparrow &\\ & & & & & j & &\end{array}$$

segue que a linha $i$ de $E_{ij}(a)P_{il}$ é a soma

$$\begin{array}{ccccccccc} [ 0 & \cdots & 0 & \cdots &0 & 1 & 0... ...dots &0 ] \\ & & & && \uparrow &\\ & & & & & j & &\end{array}$$

$$\begin{array}{ccccccccccc} = [ 0 & \cdots &0 & a & 0 & \cdots... ...& \uparrow& & && \uparrow &\\ & & & j & & & & l & &\end{array}$$

Para $k\ne i$, a linha $k$ de $E_{ij}(a)P_{il}$ é a linha $k$ de $P_{il}$, sendo esta a linha $k$ da matriz identidade se $k \ne l$, ou a linha $i$ da identidade se $k=l$. Por sua vez, a linha $k$ de $P_{il}E_{lj}(a)$ é a linha $k$ da ientidade se $k \ne l$, ou é a linha $i$ de $I_n$ se $k=l$.

[Demonstração do teorema ] A prova segue da aplicação do algoritmo de eliminação de Gauss, fazendo-se uso do lema para se obter a factorização da forma $U=PLA$, onde os pivots do algoritmo são o primeiro elemento não nulo de cada linha (não nula) de $U$.

A característica de uma matriz $A$, denotada por $\mathrm{car}(A)$, por $c(A)$ ou ainda por $\mathrm{rank}(A)$, é o número de linhas não nulas na matriz escada $U$ obtida por aplicação do Algoritmo de Eliminação de Gauss. Ou seja, e sabendo que toda a linha não nula de $U$ tem exactamente 1 pivot que corresponde ao primeiro elemento não nulo da linha, a característica de $A$ é o número de pivots no algoritmo (ainda que o último possa não ser usado, por exemplo, no caso de estar na última linha). Note ainda que $\mathrm{car}(A)=\mathrm{car}(U)$. Por exemplo, $\mathrm{car}\left[\begin{array}{cccc} 2 & 2 & 2 & 2\\ 2 & 2 & 2 & 0\\ 1 & 1 & 0 & 1\end{array}\right]=3$, já que a matriz escada obtida desta tem 3 linhas não nulas.

Uma matriz quadrada $A$ de ordem $n$ diz-se não-singular se $\mathrm{car}(A)=n$. Ou seja, $A$ é não-singular se forem usados $n$ pivots no algoritmo de eliminação de Gauss. Uma matriz é singular se não for não-singular.

Teorema 2.3.4   As matrizes não-singulares são exactamente as matrizes invertíveis.

Seja $A$ uma matriz quadrada, e $U$ a matriz escada obtida de $A$ por Gauss.

Por um lado, se $A$ é invertível, e como $A\sim U$, segue que $U$ é invertível, quadrada. Como $U$ é triangular superior, não pode ter linhas nulas caso constrário teria um elemento diagonal nulo, o que contraria a invertibilidade de $U$.

Por outro lado, se $A$ é não-singular então $U$ não tem linhas nulas. Como cada coluna de $U$ tem no máximo 1 pivot, e existem $n$ linhas e $n$ pivots, então cada linha tem exactamente 1 pivot. Ou seja, os elementos diagonais de $U$ são não nulos. Como $U$ é triangular superior, segue que $U$ é invertível, e portanto $A$ é invertível visto $A\sim U$.

Teorema 2.3.5   Se $A$ é uma matriz não-singular, então existe uma matriz $P$ permutação tal que $PA$ é factorizável, de forma única, como $PA=LU$, onde $L$ é triangular inferior com 1's na diagonal e $U$ é uma matriz triangular superior com elementos diagonais não nulos.

A existência de tal factorização é consequência do teorema . Repare que, sendo a matriz não singular, tal significa que os pivots estão presentes em todas as colunas de $U$. Assim, os elementos diagonais de $U$ são os pivots, sendo estes não nulos. Resta-nos provar a unicidade. Para tal, considere as matrizes $L_1,L_2$ triangulares inferiores com 1's na diagonal, e as matrizes $U_1,U_2$ triangulares superiores com elementos diagonais diferentes de zero, matrizes essas que satisfazem $PA=L_1U_1=L_2U_2$. Portanto, $L_1U_1=L_2U_2$, o que implica, e porque $L_1,U_2$ são invertíveis (porquê?), que $U_1U_2^{-1}=L_1^{-1}L_2$. Como $L_1,U_2$ são, respectivamente, triangulares inferior e superior, então $L_1^{-1}$ e $U_2^{-1}$ são também triangulares inferior e superior, respectivamente. Recorde que sendo a diagonal de $L_1$ constituida por 1's, então a diagonal da sua inversa tem também apenas 1's. Daqui segue que $L_1^{-1}L_2$ é triangular inferior, com 1's na diagonal, e que $U_1U_2^{-1}$ é triangular superior. Sendo estes dois produtos iguais, então $L_1^{-1}L_2$ é uma matriz diagonal, com 1's na diagonal; ou seja, $L_1^{-1}L_2=I$, e portanto $L_1=L_2$. Tal leva a que $L_1U_1=L_1U_2$, o que implica, por multiplicação à esquerda por $L_1^{-1}$, que $U_1=U_2$.

Octave
Ao se usar uma ferramenta computacional numérica é necessário algum cuidado nos erros de truncatura. Como exemplo, considere a matriz A=[1E-5 1E5; 1E5 1E-5]. Esta matriz é não-singular, e a única (porquê?) matriz escada obtida, sem quaisquer trocas de linhas, é $\left[\begin{array}{cc}10^{-5}&10^5 0 & 10^{-5}-10^{15}\end{array}\right]$. Usando o Octave,

> format long
> E=eye (2); E(2,1)=-A(2,1)/A(1,1)
E =

           1           0
 -10000000000          1

> E*A
ans =

    1.00000000000000e-05    1.00000000000000e+05
   -1.45519152283669e-11   -1.00000000000000e+15

Repare que a matriz não é triangular inferior, e que o elemento $(2,2)$ dessa matriz deveria ser $10^{-5}-10^{15}$ e não $-10^{15}$ como indicado.

> (E*A)(2,2)==-1E15
ans = 1
> -1E15==-1E15+1E-5
ans = 1

Para o Octave, não existe distinção entre os dois números, por erro de arrondamento.

Embora o AEG seja pouco eficiente neste tipo de questões, existem algumas alterações que são efectuadas por forma a contornar este problema. Um exemplo é a pivotagem parcial. Este algoritmo será descrito com detalhe noutra unidade curricular de MiEB. A ideia é, quando se considera um pivot na entrada $(i,j)$, percorrer os outros elementos que estão por baixo dele e trocar a linha $i$ com a linha do elemento que seja maior, em módulo. Tal corresponde a multiplicar, à esquerda, por uma matriz da forma $P_{ij}$. Esse algorimto está implementado no Octave, sendo chamado pela instrução lu(A).

> [L,U,P]=lu (A)
L =

  1.000000000000000  0.000000000000000
  0.000000000100000  1.000000000000000

U =

   1.00000000000000e+05   1.00000000000000e-05
   0.00000000000000e+00   1.00000000000000e+05

P =

  0  1
  1  0

A matriz $L$ indica a inversa do produto das matrizes elementares, $U$ é a matriz escada, e $P$ é a matriz permutação. Obtemos, deste forma, a factorização $PA=LU$.

> all(all(P*A==L*U))
ans = 1