16/10/2012

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.

escalonamento-sistemas-lineares-metodo-de-eliminacao-de-gauss

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:


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:


COMO REFERENCIAR ESSE ARTIGO: Título: Escalonamento ou o Método da Eliminação de Gauss. Publicado por Kleber Kilhian em 16/10/2012. URL: . Leia os Termos de uso.


Siga também o blog pelo canal no Telegram.
Achou algum link quebrado? Por favor, entre em contato para reportar o erro.
Para escrever em $\LaTeX$ nos comentários, saiba mais em latex.obaricentrodamente.com.

19 comentários:

  1. Olá Kleber, sempre digo e tenho certeza que suas explicações são claras e elucidativas. Gostei muito deste post e com certeza irá contribuir para divulgar este assunto na internet. Obrigado pela divulgação da foto e do link. Abraços

    ResponderExcluir
  2. Olá Paulo,obrigado pelo comentário motivador. É uma abordagem mais simples do que encontramos em livros de cálculo numérico, o que facilita o entendimento de alunos do ensino médio.

    Obrigado e um abraço!

    ResponderExcluir
  3. O método é muito rápido computacionalmente. O tempo de cálculo é proporcional ao quadrado da ordem da matriz que será invertida. Muito mais rápido que usar a matriz de cofatores, que demanda um tempo proporcional ao fatorial da ordem da matriz.

    Fiz um algoritmo em c usando esse método (inversão por pivotamento).

    Se quiser posso enviar.

    ResponderExcluir
    Respostas
    1. Olá Rycunda,

      Gostaria sim de receber seu algoritmo. Podemos publicá-lo aqui no blog, se quiser.

      Envie no meu e-mail: kleberkilhian@gmail.com

      Grande abraço!

      Excluir
    2. Anônimo4/6/14 17:15

      Pode me manda também?

      eduardo_hmg@hotmail.com

      Excluir
    3. Olá amigo. Infelizmente formatei meu note e perdi alguns arquivos, inclusive este. Abraços.

      Excluir
  4. olá, eu também gostaria de receber o algoritmo, como faço para recebe-lo?

    ResponderExcluir
  5. Muito bom, parabéns

    ResponderExcluir
  6. Muito interessante a forma de tratar o assunto. Blogs como o seu tem facilitado muito vida academica.
    Parabéns e Obrigado

    ResponderExcluir
    Respostas
    1. Olá Vinícius, obrigado pela consideração. Durante minha graduação tive dificuldade em vários momentos por falta de material adequado. Espero continuar contribuindo.

      Um abraço.

      Excluir
  7. Muito dificil

    ResponderExcluir
  8. Otimo artipo sobre sistemas lineares.Seu blog é muito bom

    ResponderExcluir
  9. alguem tem esse algoritmo em java .... ou um pseudo codigo ?? estou em duvida de como passa pra cria

    ResponderExcluir
  10. Ola sou o Eduardo
    Gostei muito da materia,e ajudou-me bastante
    Obrgd Kleber.

    ResponderExcluir
  11. Este métodos é com pivoteamento?

    ResponderExcluir
  12. Muito obrigado, ajudou bastante em um projeto!

    ResponderExcluir
    Respostas
    1. Olá Lucas, desculpe responder somente agora, mas o blogger não me notificou de seu comentário.

      Que bom que lhe foi útil. Um forte abraço!

      Excluir

Whatsapp Button works on Mobile Device only

Pesquise no blog