Método de Eliminação de Gauss

Deixe um comentário Go to comments

Eliminação de Gauss (ou método de escalonamento) é um algoritmo para se resolver sistemas de equações lineares. Este método consiste em aplicar sucessivas operações elementares em um sistema linear, afim de transformá-lo num sistema de mais fácil resolução, tendo este as mesmas soluções que o original.

Definição de matriz escalonada

Uma matriz retangular está na sua forma escalonada quando ela satisfaz as seguintes condições:

  • Todas as linhas não-nulas estão acima de qualquer linha composta só de zeros.
  • O pivô de cada linha está numa coluna à direita do pivô da linha acima.
  • Todos os elementos de uma coluna abaixo de um pivô são zero.

Exemplo

\left[\begin{array}{rrrr}<br /><br /><br /> 2 & -3 & 2 & 1 \\<br /><br /><br /> 0 & 1 & -4 & 8 \\<br /><br /><br /> 0 & 0 & 0 & 35<br /><br /><br /> \end{array}\right]

Se uma matriz está na forma escalonada reduzida ela ainda satisfaz as seguintes características adicionais:

  • O pivô de cada linha não-nula é 1.
  • Cada pivô 1 é o único elemento não nulo de sua coluna.

Exemplo

\left[\begin{array}{rrrr}<br /><br /><br /> 1 & 0 & 0 & 12 \\<br /><br /><br /> 0 & 1 & 0 & 16 \\<br /><br /><br /> 0 & 0 & 1 & 1<br /><br /><br /> \end{array}\right]

Operações elementares de linhas

Existem três operações básicas que podem ser aplicadas a qualquer tipo de sistema linear, sem que se altere as soluções dos mesmos:

  1. Somar a uma linha um múltiplo de outra linha.
  2. Trocar duas linhas entre si.
  3. Multiplicar todos os elementos de uma linha por uma constante não-nula.

Usando essas operações, uma matriz sempre pode ser transformada em uma matriz triangular superior (forma escalonada) e, posteriormente, ser posta em sua forma escalonada reduzida. Esta forma final, por sua vez, é única e independe da sequência de operações de linha usadas, sendo mais fácil de resolver que a versão original da matriz. Também cabe ressaltar que estas operações elementares são reversíveis, sendo possível retornar ao sistema inicial aplicando a sequência de operações novamente, mas na ordem inversa.

Problema geral

Deseja-se, a partir da utilização de operações de linha, converter uma matriz a sua forma escalonada reduzida, e assim, resolver mais facilmente o sistema de equações associado àquela matriz. Para este fim, utilizamos o método de Eliminação de Gauss, sendo este composto por duas fases:

  • Fase de eliminação: cujo objetivo é empregar operações elementares na matriz aumentada, afim de obter uma correspondente a um sistema triangular superior.
  • Fase de substituição retrocedida: começa-se resolvendo a última equação, cuja solução é substituída na penúltima, a qual resolve-se na penúltima variável, e assim consecutivamente, até obter-se a solução final.

Algoritmo

Seja Ax = b um sistema linear. O Método de eliminação de Gauss para se encontrar a solução do sistema consiste nas seguintes etapas:

  • Etapa 1: Obter a matriz aumentada na forma \begin{bmatrix}A|b\end{bmatrix} que representa o sistema de equações.
  • Etapa 2:Transformar a matriz aumentada \begin{bmatrix}A|b\end{bmatrix} em uma matriz aumentada na forma \begin{bmatrix}\bar A|\bar b\end{bmatrix} onde \bar A é uma matriz triangular superior.
  • Etapa 3: Resolver o sistema linear \begin{bmatrix}\bar A|\bar b\end{bmatrix} da Etapa 2 por substituição regressiva.

Etapa 1

Considere o sistema linear de 3 equações abaixo:

\begin{alignat}{7}<br /><br /><br /> a_{11} x_1 &&\; + \;&& a_{12} x_2 &&\; + \;&& a_{13} x_3 &&\; = \;&& b_1 & \qquad (L_1) \\<br /><br /><br /> a_{21} x_1 &&\; + \;&& a_{22} x_2 &&\; + \;&& a_{23} x_3 &&\; = \;&& b_2 & \qquad (L_2) \\<br /><br /><br /> a_{31} x_1 &&\; + \;&& a_{32} x_2 &&\; +\;&& a_{33} x_3 &&\; = \;&& b_3 & \qquad (L_3)<br /><br /><br /> \end{alignat}

A matriz aumentada A do sistema é:

\begin{bmatrix}A|b\end{bmatrix}^{(0)} = \left[ \begin{array}{ccc|c}<br /><br /><br /> a_{11} & a_{12} & a_{13} & b_1 \\<br /><br /><br /> a_{21} & a_{22} & a_{23} & b_2 \\<br /><br /><br /> a_{31} & a_{32} & a_{33} & b_3<br /><br /><br /> \end{array} \right]<br /><br /><br />

 

Etapa 2

Fase 1

Deseja-se zerar todos os elementos da primeira coluna abaixo da diagonal principal. Assim, sendo a_{11} \ne 0 , defini-se as constantes k = a_{21} / a_{11} e w = a_{31} / a_{11} e faz-se as seguintes operações lineares:

L_2^{(1)} \leftarrow L_2 - k.L_1
L_3^{(1)} \leftarrow L_3 - w.L_1

Obtendo-se:

\begin{bmatrix}A|b\end{bmatrix}^{(1)} = \left[ \begin{array}{ccc|c}<br /><br /><br /> a_{11}^{(1)} & a_{12}^{(1)} & a_{13}^{(1)} & b_1^{(1)} \\<br /><br /><br /> 0 & a_{22}^{(1)} & a_{23}^{(1)} & b_2^{(1)} \\<br /><br /><br /> 0 & a_{32}^{(1)} & a_{33}^{(1)} & b_3^{(1)}<br /><br /><br /> \end{array} \right]<br /><br /><br />

Fase 2

Agora, deve-se zerar todos os elementos da segunda coluna abaixo da diagonal principal. Sendo o pivô o elemento a_{22}^{(1)} e a linha pivô a linha 2 de \begin{bmatrix}A|b\end{bmatrix}^{(1)}, supõe-se a_{22}^{(1)} \ne 0 , e define-se uma nova constante v = a_{32}^{(1)} / a_{22}^{(1)}. Realizando a operação

L_3^{(2)} \leftarrow L_3^{(1)} - v.L_2^{(1)}

obtém-se:

\begin{bmatrix}A|b\end{bmatrix}^{(2)} = \left[ \begin{array}{ccc|c}<br /><br /><br /> a_{11}^{(2)} & a_{12}^{(2)} & a_{13}^{(2)} & b_1^{(2)} \\<br /><br /><br /> 0 & a_{22}^{(2)} & a_{23}^{(2)} & b_2^{(2)} \\<br /><br /><br /> 0 & 0 & a_{33}^{(2)} & b_3^{(2)}<br /><br /><br /> \end{array} \right]<br /><br /><br />
  • Note que \begin{bmatrix}A|b\end{bmatrix}^{(2)} é uma matriz aumentada cuja matriz A é uma matriz triangular superior.

Etapa 3

Resolve-se o sistema \begin{bmatrix}A|b\end{bmatrix}^{(2)}. Assim:

x_3 = b_{3}^{(2)} / a_{33}^{(2)} \ , \ a_{33}^{(2)} \ne 0

x_2 = (b_{2}^{(2)} - (a_{23}^{(2)} x_3)) / a_{22}^{(2)}

x_1 = (b_{1}^{(2)} - (a_{12}^{(2)} x_2)) + a_{13}^{(2)} x_3)) / a_{11}^{(2)}

Assim, encontra-se a solução \begin{Bmatrix} x_1, \ x_2, \ x_3 \end{Bmatrix} do sistema \begin{bmatrix}A|b\end{bmatrix}^{(2)}, que é a mesma solução de \begin{bmatrix}A|b\end{bmatrix}.

  • Observação: o método da Eliminação de Gauss só poderá ser usado para resolver sistemas lineares associados a matrizes escalonadas reduzidas com elementos das suas diagonais principais não-nulos, ou seja, a_{11}^{(1)}, a_{22}^{(2)}, a_{33}^{(3)},...,a_{nn}^{(n)} \ne 0 .

Exemplo

Resolver o sistema de equações abaixo:

\begin{alignat}{7}<br /><br /><br /> 2x &&\; + \;&& 1y &&\; + \;&& -3z &&\; = \;&& -1 \\<br /><br /><br /> -1x &&\; + \;&& 3y &&\; + \;&& 2z &&\; = \;&& 12 \\<br /><br /><br /> 3x &&\; + \;&& 1y &&\; +\;&& -3z &&\; = \;&& 0<br /><br /><br /> \end{alignat}

Etapa 1: definir a matriz aumentada

\left[ \begin{array}{ccc|c}<br /><br /><br /> 2 & 1 & -3 & -1 \\<br /><br /><br /> -1 & 3 & 2 & 12 \\<br /><br /><br /> 3 & 1 & -3 & 0<br /><br /><br /> \end{array} \right]

 

Etapa 2:

Fase 1: zerar elementos da primeira coluna abaixo da diagonal principal

Como a_{11} = 2 \ne 0 , defini-se \ k = \frac{a_{21}}{a_{11}} = \frac{-1}{2} e \ w = \frac{a_{31}}{a_{11}} = \frac{3}{2} e calcula-se os novos elementos da segunda e da terceira linha:

a_{22}^{(1)} = a_{22} - k. a_{12} = 3 - (\frac{-1}{2}) . 1 = \frac{7}{2}
a_{23}^{(1)} = a_{23} - k. a_{13} = 2 - (\frac{-1}{2}) . (-3) = \frac{1}{2}
b_{2}^{(1)} = b_{2} - k. b_{1} = 12 - (\frac{-1}{2}) . (-1) = \frac{23}{2}
a_{32}^{(1)} = a_{32} - w. a_{12} = 1 - (\frac{3}{2}) . 1 = \frac{-1}{2}
a_{33}^{(1)} = a_{33} - w. a_{13} = -3 - (\frac{3}{2}) . (-3) = \frac{3}{2}
b_{3}^{(1)} = b_{3} - w. b_{1} = 0 - (\frac{3}{2}) . (-1) = \frac{3}{2}

Dessa forma, a matriz resultante da etapa 1 é:

\left[ \begin{array}{ccc|c}<br /><br /><br /> 2 & 1 & -3 & -1 \\<br /><br /><br /> 0 & \frac{7}{2} & \frac{1}{2} & \frac{23}{2} \\<br /><br /><br /> 0 & \frac{-1}{2} & \frac{3}{2} & \frac{3}{2}<br /><br /><br /> \end{array} \right]<br /><br /><br />

Fase 2: zerar elementos da segunda coluna abaixo da diagonal principal

Como a_{22}^{(1)} = \frac{7}{2} \ne 0 , define-se uma nova constante v = \frac{a_{32}^{(1)}}{a_{22}^{(1)}} = \frac{-1}{7} e determina-se os novos elementos da terceira linha:

a_{33}^{(2)} = a_{33}^{(1)} - v. a_{23}^{(1)} = \frac{3}{2} - (\frac{-1}{7}) . \frac{1}{2} = \frac{11}{7}
b_{3}^{(2)} = b_{3}^{(1)} - v. b_{2}^{(1)} = \frac{3}{2} - (\frac{-1}{7}) . \frac{23}{2} = \frac{22}{7}

A nova matriz aumentada após esta segunda fase é:

\left[ \begin{array}{ccc|c}<br /><br /><br /> 2 & 1 & -3 & -1 \\<br /><br /><br /> 0 & \frac{7}{2} & \frac{1}{2} & \frac{23}{2} \\<br /><br /><br /> 0 & 0 & \frac{11}{7} & \frac{22}{7}<br /><br /><br /> \end{array} \right]<br /><br /><br />

 

Etapa 3:

Tendo-se obtido o sistema:

\begin{alignat}{7}<br /><br /><br /> 2x &&\; + \;&& y &&\; - \;&& 3z &&\; = \;&& -1 \\<br /><br /><br /> &&\; \;&& \frac{7}{2}y &&\; + \;&& \frac{1}{2} z &&\; = \;&& \frac{23}{2} \\<br /><br /><br /> &&\; \;&& &&\; \;&& \frac{11}{7}z &&\; = \;&& \frac{22}{7}<br /><br /><br /> \end{alignat}

que é um sistema triangular, obtemos sua solução facilmente por substituição das variáveis.

Da última equação temos:

z = \frac{\frac{22}{7}}{\frac{11}{7}} = 2

Substituindo o valor de z na segunda equação:

\frac{7}{2}y + \frac{1}{2} . 2 = \frac{23}{2}

logo,

y = \frac{\frac{23}{2}-1}{\frac{7}{2}} = 3

Por fim, substituindo os valores z = 2 e y = 3 na primeira equação:

2x + 3 -3 . 2 = -1

resolvendo,

x = \frac{-1 -3 + 6}{2} = 1
  • Assim, a solução para o sistema linear é: \begin{Bmatrix} 1, 3, 2 \end{Bmatrix}

Referências Bibliográficas

  • Burden, Richard L. ; Faires, J. Douglas. Análise Numérica. 8ª ed. São Paulo: Cengage Learning, 2008. p. 332-338.
  • Lay, David C. Álgebra Linear e suas aplicações. 2ª ed. Rio de Janeiro: LTC, 1999. p. 6-16.
  • Pazos, Rubén Panta. Método de Eliminação de Gauss. Disponível em: http://rpanta.com/downloads/material/Gauss_01. Acesso em: 23 de mai. 2013.

–

Fonte: http://pt.wikipedia.org/wiki/Elimina%C3%A7%C3%A3o_de_Gauss

  1. Nenhum comentário ainda.
  1. No trackbacks yet.

Deixe seu comentário