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