Escalonamento ou o Método da Eliminação de Gauss

A teoria das equações lineares desempenha papel importante e motivador no campo da Álgebra Linear, onde muitos problemas são equivalentes ao estudo de um sistema de equações lineares.

Procurei neste artigo evitar todo o rigor matemático do método aplicado no Cálculo Numérico, sem abrir mão de um mínimo de formalismo necessário para o bom entendimento.

Os métodos diretos que aprendemos no ensino médio como por substituição só é prático para duas equações a duas incógnitas; para outros casos destaca-se a regra de Cramer. Esse método, se aplicado a um sistema de $n \times n$ envolve um cálculo de $n+1$ determinantes de ordem $n$. Se $n=20$, por exemplo, o total de operações efetuadas será de $21 \times 20! \times 19$ multiplicações mais um número semelhante de adições. Assim, se um computador que efetue cerca de cem milhões de multiplicações por segundo, levaria $3 \times 10^5$ anos para efetuar as operações necessárias.

Claro que na época de Gauss não existia computador. Imaginem como era para resolver sistemas com $n=4$, $n=5$, $n=10$.

O método de eliminação de Gauss consiste em transformar o sistema linear original num sistema linear equivalente com a matriz dos coeficientes triangular superior, pois estes são de resolução imediata.

Uma equação linear no campo dos números Reais pode ser representada como
\begin{equation}
a_1x_1 + a_2x_2 + a_3x_3 +\cdots + a_nx_n = b
\end{equation}
 onde $a_i, b \in \mathbb{R}$ e os $x_i$ são indeterminados, ou seja as incógnitas ou variáveis. Os escalares $a_i$ são chamados coeficientes de $x_i$ respectivamente, e $b$ é chamado de constante ou termo independente.

Um sistema de equações lineares é um conjunto de $m$ equações com $n$ incógnitas. Neste estudo, vamos nos concentrar em sistemas lineares do tipo $n \times n$, onde o número de equações é igual ao número de incógnitas.

Considere o sistema linear $Ax = b$:
\begin{equation}

\left\{\begin{matrix}

a_{11}x_1+a_{12}x_2+\cdots +a_{1n}x_n & = & b_1\\
\ \\

a_{21}x_1+a_{22}x_2+\cdots +a_{2n}x_n & = & b_2\\
\ \\
\vdots & \vdots & \vdots \\

\ \\

a_{n1}x_1+a_{n2}x_2+\cdots +a_{nn}x_n & = & b_n

\end{matrix}\right.
\end{equation}
O método de eliminação de Gauss consiste em transformar convenientemente o sistema linear original para obter um sistema linear equivalente com matriz dos coeficientes triangular superior.

Para modificar convenientemente um sistema linear num equivalente, podemos fazer uso do teorema abaixo:

Teorema:

Seja $Ax = b$ um sistema linear $n \times n$. Aplicamos sobre as equações desse sistema uma sequência de operações elementares escolhidas entre:

• Trocar duas equações ou duas colunas;
• Multiplicar uma equação por uma constante não-nula;
• Adicionar um múltiplo de uma equação a outra equação.

Assim, obteremos um novo sistema $A^\prime x = b^\prime$ de modo que os sistemas $Ax = b$ e $A^\prime x = b^\prime$ são equivalentes.

Considere o sistema de equações lineares dado em $(2)$. A triangularização do sistema é dada como segue:

1. Transpomos linhas e/ou colunas de modo que o termo $a_{11}$ seja não-nulo;
2. Para cada $i > 1$, aplicamos a operação:

\begin{equation}
L_i \longrightarrow -a_{ik}L_k+a_{kk}L_i
\end{equation}

onde $k$ é cada etapa da eliminação.

Para cada etapa $k$, sendo cada etapa a eliminação de uma variável das equações, substituímos a i-ésima equação linear $L_i$ pela equação equivalente resultante da multiplicação da equação $L_k$ por $-a_{ik}$ somada ao produto da equação $L_i$ por $a_{kk}$. Com isso eliminamos o termo $a_{ik}$ da equação $L_i$:

\begin{equation}
\left\{\begin{matrix}
a_{11}x_1&+&a_{12}x_2&+&\cdots &+&a_{1n}x_n & = & b_1\\
&&a_{22}x_2&+&\cdots &+&a_{2n}x_n & = & b_2\\
&&&&\vdots \\
&&&&&&a_{nn}x_n & = & b_n
\end{matrix}\right.
\end{equation}

A cada etapa desse processo elimina uma incógnita de equações sucessivas até, por fim, encontrarmos somente:

\begin{equation}
a_{nn}x_n=b_n
\end{equation}

Que nos dá imediatamente o valor de $x_n$.

Substituindo $x_n$ na equação $L_{i-1}$, obteremos o valor de $x_{n-2}$ e assim sucessivamente.

Exemplo 1:

Considere o sistema de equações abaixo. Encontre os valores de $x$, $y$ e $z$.

\begin{equation*}
\left\{\begin{matrix}
2x & + & y & - & 2z & = & 10\\
3x & + & 2y & + & 2z & = & 1\\
5x & + & 4y & + & 3z & = & 4
\end{matrix}\right.
\end{equation*}
Primeiramente, vemos que o termo $a_{11}$ é não-nulo e igual a $2$. Vamos identificar cada equação como:

\begin{matrix}
L_1 \longrightarrow & 2x & + & y & - & 2z & = & 10\\
L_2 \longrightarrow & 3x & + & 2y & + & 2z & = & 1\\
L_3 \longrightarrow & 5x & + & 4y & + & z & = & 4
\end{matrix} 

Etapa k=1: Eliminando a incógnita $x$ da segunda e terceira equações

Primeiramente vamos eliminar a incógnita $x$ da equação $L_2$. Assim, devemos aplicar a operação:
\begin{equation*}
L_i \longrightarrow -a_{ik}L_k + a_{kk}L_i
\end{equation*}
Então, fazemos:
\begin{equation*}
L_2 \longrightarrow  -a_{21}L_1  +  a_{11}L_2=-3L_1  +  2L_2
\end{equation*}
Desse modo:
\begin{matrix}
-3L_1&=&-3(2x+y-2z)&=&-3(10)\\
&=&-6x-3y+6z&=&-30
\end{matrix}
e
\begin{matrix}
2L_2&=&2(3x+2y+2z)&=&2(1)\\
&=&6x+4y+4z&=&2
\end{matrix}
Somando termo a termo:
\begin{matrix}
-3L_1 + 2L_2&=&-6x-3y+6z+6x+4y+4z&=&-30+2\\
&=&y+10z&=&-28
\end{matrix}
Assim, a equação $L_2$ será equivalente a $L_2 \longrightarrow y+10z=-28$

Eliminemos agora a incógnita $x$ da terceira equação:

\begin{equation*}
L_3 \longrightarrow  -a_{31}L_1  +  a_{11}L_3=-5L_1  +  2L_3
\end{equation*}
Desse modo:
\begin{matrix}
-5L_1&=&-5(2x+y-2z)&=&-5(10)\\
&=&-10x-5y+10z&=&-50
\end{matrix}
e
\begin{matrix}
2L_3&=&2(5x+4y+3z)&=&2(4)\\
&=&10x+8y+6z&=&8
\end{matrix}
Somando termo a termo:
\begin{matrix}
-5L_1 + 2L_3&=&-10x-5y+10z+10x+8y+6z&=&-50+8\\
&=&3y+16z&=&-42
\end{matrix}
Assim, a equação $L_3$ será equivalente a $L_3 \longrightarrow 3y+16z=-42$


Obtemos, assim, um sistema equivalente ao original, mas com as primeiras incógnitas eliminadas:
\begin{equation*}
\left\{\begin{matrix}
2x & + & y & - & 2z & = & 10\\
 &  & y & + & 10z & = & -28\\
 &  & 3y & + & 16z & = & -42
\end{matrix}\right.
\end{equation*}

Etapa k=2: Eliminando a incógnita $y$ da terceira equação

Agora vamos eliminar a incógnita $y$ da terceira equação. Aplicamos a operação:
\begin{equation*}
L_i \longrightarrow -a_{ik}L_k + a_{kk}L_i
\end{equation*}
Então fazemos:
\begin{equation*}
L_3 \longrightarrow  -a_{32}L_2  +  a_{22}L_3=-3L_2  +  1L_3
\end{equation*}
 Desse modo:
\begin{matrix}
-3L_2&=&-3(y+10z)&=&-3(-28)\\
&=&-3y-30z&=&84
\end{matrix}
e
\begin{matrix}
L_3&=&3y+16z&=&-42\\
\end{matrix}
Somando termo a termo, obtemos:
\begin{matrix}
-3L_2 + L_3&=&-3y+30z+3y+16z&=&84-42\\
&=&-14z&=&42 
\end{matrix}
Assim, a equação $L_3$ será equivalente a $L_3\longrightarrow -14z=42$.

Obtemos agora um sistema linear triangular superior:
\begin{equation*}
\left\{\begin{matrix}
2x & + & y & - & 2z & = & 10\\ 
 &  & y & + & 10z & = & -28\\ 
 &  &  &  & -14z & = & 42
\end{matrix}\right.
\end{equation*}
Agora fica fácil a resolução. Vejam que a equação $L_3$ já nos fornece diretamente o valor da incógnita $z$:
\begin{equation*}
-14z=42 \Longrightarrow z=-3\\
\end{equation*}

Substituímos $z$ na equação $L_2$ obtendo:
\begin{equation*}
y+10(-3)=-28 \Longrightarrow y=2\\
\end{equation*}

Substituímos $z$ e $y$ na equação $L_1$, obtendo:
\begin{equation*}
2x+2-2(-3)=10 \Longrightarrow x=1\\
\end{equation*}
O sistema de equações lineares tem solução única e é dado pela 3-upla: $(1, 2, –3)$.

Para verificarmos se a solução encontrada é consistente, basta substituir os valores encontrados nas equações dadas e checar as igualdades. 

Exemplo 2:

Considere o sistema de equações abaixo. Encontre os valores de $x$, $y$ e $z$.

\begin{equation*}
\left\{\begin{matrix}
3x & + & 2y & + & 4z & = & 1\\
x & + & y & + & 2z & = & 2\\
4x & + & 3y & - & 2z & = & 3
\end{matrix}\right.
\end{equation*}
Primeiramente, vemos que o termo $a_{11}$ é não-nulo e igual a $3$. Vamos identificar cada equação como:

\begin{matrix}
L_1 \longrightarrow & 3x & + & 2y & + & 4z & = & 1\\
L_2 \longrightarrow & x & + & y & + & 2z & = & 2\\
L_3 \longrightarrow & 4x & + & 3y & - & 2z & = & 3
\end{matrix} 

Etapa k=1: Eliminando a incógnita $x$ da segunda e terceira equações

Primeiramente vamos eliminar a incógnita $x$ da equação $L_2$. Assim, devemos aplicar a operação:
\begin{equation*}
L_i \longrightarrow -a_{ik}L_k + a_{kk}L_i
\end{equation*}
Então, fazemos:
\begin{equation*}
L_2 \longrightarrow  -a_{21}L_1  +  a_{11}L_2=-1L_1  +  3L_2
\end{equation*}
Desse modo:
\begin{matrix}
-L_1&=&-3x-2y-4z&=&-1\\
\end{matrix}
e
\begin{matrix}
3L_2&=&3(x+y+2z)&=&3(2)\\
&=&3x+3y+6z&=&6
\end{matrix}
Somando termo a termo:
\begin{matrix}
-L_1 + 3L_2&=&-3x-2y-4z+3x+3y+6z&=&-1+6\\
&=&y+2z&=&5
\end{matrix}
Assim, a equação $L_2$ será equivalente a $L_2 \longrightarrow y+2z=5$

Eliminemos agora a incógnita $x$ da terceira equação:

\begin{equation*}
L_3 \longrightarrow  -a_{31}L_1  +  a_{11}L_3= -4L_1 + L_3
\end{equation*}
Desse modo:
\begin{matrix}
-4L_1&=&-4(x+y+2z)&=&-4(2)\\
&=&-4x-4y-8z&=&-8
\end{matrix}
e
\begin{matrix}
L_3&=&4x+3y-2z&=&3\\
\end{matrix}
Somando termo a termo:
\begin{matrix}
-4L_1 + L_3&=&-4x-4y-8z+4x+3y-2z&=&-8+3\\
&=&-y-10z&=&-5
\end{matrix}
Assim, a equação $L_3$ será equivalente a $L_3 \longrightarrow -y-10z=-5$

Obtemos, assim, um sistema equivalente ao original, mas com as primeiras incógnitas eliminadas:
\begin{equation*}
\left\{\begin{matrix}
3x & + & 2y & + & 4z & = & 1\\
 &  & y & + & 2z & = & 5\\
 & - &y & - & 10z & = & -5
\end{matrix}\right.
\end{equation*}

Etapa k=2: Eliminando a incógnita $y$ da terceira equação

Agora vamos eliminar a incógnita $y$ da terceira equação. Aplicamos a operação:
\begin{equation*}
L_i \longrightarrow -a_{ik}L_k + a_{kk}L_i
\end{equation*}
Então fazemos:
\begin{equation*}
L_3 \longrightarrow  -a_{32}L_2  +  a_{22}L_3=-1L_2  +  1L_3
\end{equation*}
 Desse modo:
\begin{matrix}
L_2&=&y+2z&=&5\\
\end{matrix}
e
\begin{matrix}
L_3&=&-y-10z&=&-5\\
\end{matrix}
Somando termo a termos, obtemos:
\begin{matrix}
-L_2 + L_3&=&y+2z-y-10z&=&5-5\\
&=&-8z&=&0 
\end{matrix}
Assim, a equação $L_3$ será equivalente a $L_3\longrightarrow -8z=0$.

Obtemos agora um sistema linear triangular superior:
\begin{equation*}
\left\{\begin{matrix}
3x & + & 2y & + & 4z & = & 1\\ 
 &  & y & + & 2z & = & 5\\ 
 &  &  &  & -8z & = & 0
\end{matrix}\right.
\end{equation*}
Agora fica fácil a resolução. Vejam que a equação $L_3$ já nos fornece diretamente o valor da incógnita $z$:
\begin{equation*}
-8z=0 \Longrightarrow z=0\\
\end{equation*}

Substituímos $z$ na equação $L_2$ obtendo:
\begin{equation*}
y+2(0)=5 \Longrightarrow y=5\\
\end{equation*}

Substituímos $z$ e $y$ na equação $L_1$, obtendo:
\begin{equation*}
3x+2(5)+4(0)=1 \Longrightarrow x=-3\\
\end{equation*}
O sistema de equações lineares tem solução única e é dado pela 3-upla: $(-3, 5, 0)$.

Para verificarmos se a solução encontrada é consistente, basta substituir os valores encontrados nas equações dadas e checar as igualdades.

Exemplo 3:

Considere o sistema de equações abaixo. Encontre os valores de $x$, $y$ e $z$.

\begin{equation*}
\left\{\begin{matrix}
x & + & y & + & z & = & 6\\
3x &  &  & - & 2z & = & -3\\
2x & - & 2y & + & z & = &1
\end{matrix}\right.
\end{equation*}
Neste caso, vamos trocar a segunda pela terceira linha e a segunda pela primeira coluna para facilitar os cálculos, obtendo:
\begin{equation*}
\left\{\begin{matrix}
y & + & x & + & z & = & 6\\
-2y & + & 2x & + & z & = & 1\\
 &  & 3x & - & 2z & = &-3
\end{matrix}\right.
\end{equation*}

Agora, vemos que o termo $a_{11}$ é não-nulo e igual a $1$. Vamos identificar cada equação como:

\begin{matrix}
L_1 \longrightarrow & y & + & x & + & z & = & 6\\
L_2 \longrightarrow & -2y & + & 2x & + & z & = & 1\\
L_3 \longrightarrow &  &  & 3x & - & 2z & = & -3
\end{matrix} 

Etapa k=1: Eliminando a incógnita $y$ da segunda equação

Primeiramente vamos eliminar a incógnita $y$ da equação $L_2$. Assim, devemos aplicar a operação:
\begin{equation*}
L_i \longrightarrow -a_{ik}L_k + a_{kk}L_i
\end{equation*}
Então, fazemos:
\begin{equation*}
L_2 \longrightarrow  -a_{21}L_1  +  a_{11}L_2=2L_1  + L_2
\end{equation*}
Desse modo:
\begin{matrix}
2L_1&=&2(y+x+z)&=&2(6)\\
&=&2y+2x+2z&=&12
\end{matrix}
e
\begin{matrix}
L_2&=&-2y+2x+z&=&1\\
\end{matrix}
Somando termo a termo:
\begin{matrix}
2L_1 + L_2&=&2y+2x+2z-2y+2x-2z&=&12+1\\
&=&4x+3z&=&13
\end{matrix}
Assim, a equação $L_2$ será equivalente a $L_2 \longrightarrow 4x+3z=12$

Obtemos, assim, um sistema equivalente ao original, mas com as primeiras incógnitas eliminadas:

\begin{equation*}
\left\{\begin{matrix}
y & + & x & + & z & = & 6\\
 &  & 4x & + & 3z & = & 13\\
 &  &3x & - & 2z & = & -3
\end{matrix}\right.
\end{equation*}

Etapa k=2: Eliminando a incógnita $x$ da terceira equação

Agora vamos eliminar a incógnita $x$ da terceira equação. Aplicamos a operação:
\begin{equation*}
L_i \longrightarrow -a_{ik}L_k + a_{kk}L_i
\end{equation*}
Então fazemos:
\begin{equation*}
L_3 \longrightarrow  -a_{32}L_2  +  a_{22}L_3=-3L_2  + 4L_3
\end{equation*}
 Desse modo:
\begin{matrix}
-3L_2&=&-12x-9z&=&-39\\
\end{matrix}
e
\begin{matrix}
4L_3&=&12x-8z&=&-12\\
\end{matrix}
Somando termo a termos, obtemos:
\begin{matrix}
-3L_2 + 4L_3&=&12x-9z+12x-8z&=&-39-12\\
&=&-17z&=&-51 
\end{matrix}
Assim, a equação $L_3$ será equivalente a $L_3\longrightarrow -17z=-51$.

Obtemos agora um sistema linear triangular superior:
\begin{equation*}
\left\{\begin{matrix}
y & + & x & + & z & = & 6\\ 
 &  & 4x & + & 3z & = & 13\\ 
 &  &  &  & -17z & = & -51
\end{matrix}\right.
\end{equation*}
Agora fica fácil a resolução. Vejam que a equação $L_3$ já nos fornece diretamente o valor da incógnita $z$:
\begin{equation*}
-17z=-51 \Longrightarrow z=3\\
\end{equation*}

Substituímos $z$ na equação $L_2$ obtendo:
\begin{equation*}4x+3(3)=13 \Longrightarrow x=1\\
\end{equation*}

Substituímos $z$ e $x$ na equação $L_1$, obtendo:
\begin{equation*}
y+1+3=6 \Longrightarrow y=2\\
\end{equation*}
O sistema de equações lineares tem solução única e é dado pela 3-upla: $(1,2,3)$.

Para verificarmos se a solução encontrada é consistente, basta substituir os valores encontrados nas equações dadas e checar as igualdades.

Links para este artigo:

• http://bit.ly/MetodoGauss
• https://www.obaricentrodamente.com/2012/10/escalonamento-ou-o-metodo-da-eliminacao.html

Referências:

• Álgebra Linear – Seymour Lipschutz – Coleção Schaum – Ed. McGraw-Hill
• Cálculo Numérico – Márcia A. G. Ruggiero – Ed. Makron Books

Veja mais:

• Método de Castilho para Resolução de Sistemas Lineares
• Sistemas Lineares e Determinantes: Origens e Desenvolvimento
• Classificação dos Sistemas Lineares
• Cayley e a Teoria das Matrizes