16 de out de 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.
image

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 \\
a_{n1}x_1+a_{n2}x_2+\cdots +a_{nn}x_n & = & n_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:

$\bullet$ trocar duas equações ou duas colunas;
$\bullet$ multiplicar uma equação por uma constante não-nula;
$\bullet$ 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.

Veja uma outra abordagem para o método no blog Fatos Matemáticos sobre O Método de Eliminação de Gauss.

Referências:

[1] Álgebra Linear – Seymour Lipschutz – Coleção Schaum – Ed. McGraw-Hill
[2] 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

Imprimir

17 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. 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. Otimo artipo sobre sistemas lineares.Seu blog é muito bom

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

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

    ResponderExcluir
  10. Este métodos é com pivoteamento?

    ResponderExcluir
    Respostas
    1. Olá Letícia. Este método apenas escalona.

      Excluir

Por favor, leiam antes de comentar:

▪ Escreva um comentário apenas referente ao tema;

▪ Para demais, utilize o formulário de contato;

▪ Comentários ofensivos ou spans não serão publicados;

▪ Desde o dia 23/07/2013, todos os comentários passaram a ser moderados. Para maiores detalhes, veja a nota de moderação aqui;

▪ É possível escrever fórmulas em $\LaTeX$ nos comentários deste blog graças a um script da Mathjax. Para fórmulas inline ou alinhadas à esquerda, escreva a fórmula entre os símbolos de $\$$; Para fórmulas centralizadas, utilize o símbolo duplo $\$\$$.

Por exemplo, a^2 + b^2 = c^2 entre os símbolos de $\$\$$, gera:
$$a^2+b^2=c^2$$
▪ Para visualizar as fórmulas em $\LaTeX$ antes de publicá-las, acessem este link.

Seu comentário é o meu Salário!

Redes Sociais

Arquivo do Blog

Related Posts Plugin for WordPress, Blogger...