Eliminação Gaussiana

O método da Eliminação Gaussiana consiste em aplicar, convenientemente, operações elementares sobre as equações de um sistema linear para obter um sistema linear equivalente que seja triangular e mais simples de resolver.

Seja

Ax = b

um sistema linear com

n

equações e

n

incógnitas. Vamos descrever o método de eliminação proposto por Gauss, de modo a obter um sistema

A'x = b'

que seja triangular superior. A mesma ideia pode ser usada para obter um sistema que seja triangular inferior, caso necessário.

Como o nome do método já diz, precisamos eliminar algumas incógnitas das equações do sistema. Para que a matriz final seja triangular superior é preciso eliminar

x_1

das equações

2, 3, ..., n

, eliminar

x_2

das equações

3, 4, ..., n

e assim por diante, até eliminarmos

x_{n-1}

da equação

n

. Dessa forma, a eliminação é feita por colunas e chamaremos de etapa k a fase do processo em que se elimina a incógnita

x_k

das equações

k+1, k+2..., n

. Denotaremos por

a_{ij}^{(k)}

o coeficiente na linha

i

e coluna

j

no final da etapa k e

b_i^{(k)}

i

-ésimo elemento do vetor constante no final da etapa k.

Vamos supor inicialmente que

det(A) \neq 0

. Com isso, é sempre possível reescrever o sistema linear de modo que o elemento

a_{11}

seja diferente de zero, usando apenas a operação elementar (i): trocar a posição de duas linhas da matriz

A

. Portanto, na etapa 0 escrevemos a matriz ampliada do sistema da seguinte forma:

[ A^{(0)}|b^{(0)} ] = \left[ A|b \right] = \left[ \begin{array}{cccc|c} a_{11}^{(0)} & a_{12}^{(0)} & \cdots & a_{1n}^{(0)} & b_1^{(0)} \\ a_{21}^{(0)} & a_{22}^{(0)} & \cdots & a_{2n}^{(0)} & b_2^{(0)} \\ \vdots & \vdots & & \vdots & \vdots \\ a_{n1}^{(0)} & a_{n2}^{(0)} & \cdots & a_{nn}^{(0)} & b_n^{(0)} \end{array} \right]

onde

a_{11}^{(0)} \neq 0

.

Etapa 1: nessa etapa eliminamos

x_1

das equações

i = 2, 3, ..., n

utilizando a operação elementar: da linha

i

subtrair a linha 1 multiplicada por

m_{i1} = \frac{a_{i1}^{(0)}}{a_{11}^{(0)}}

para

i = 2, ..., n

. Observe que a linha 1 é a linha auxiliar na etapa 1, uma vez que o elemento

a_{11} \neq 0

. Em geral, a linha k é auxiliar na etapa k do processo de eliminação. Ao final da etapa 1, teremos:

[ A^{(1)}|b^{(1)} ] = \left[ \begin{array}{cccc|c} a_{11}^{(1)} & a_{12}^{(1)} & \cdots & a_{1n}^{(1)} & b_1^{(1)} \\ 0 & a_{22}^{(1)} & \cdots & a_{2n}^{(1)} & b_2^{(1)} \\ \vdots & \vdots & & \vdots & \vdots \\ 0 & a_{n2}^{(1)} & \cdots & a_{nn}^{(1)} & b_n^{(1)} \end{array} \right]

onde, na primeira linha:

a_{1j}^{(1)} = a_{1j}^{(0)}

para

j = 1, ..., n

b_1^{(1)} = b_1^{(0)}

. E para as demais linhas:

a_{ij}^{(1)} = a_{ij}^{(0)} - m_{i1}a_{1j}^{(0)}

b_i^{(1)} = b_i^{(0)} - m_{i1}b_1^{(0)}

, para

i = 2, ..., n, j = 1, ..., n

.

Os elementos

m_{i1} = \frac{a_{i1}^{(0)}}{a_{11}^{(0)}}

i = 2,...,n

são denominados multiplicadores e o elemento

a_{11}^{(0)}

é o pivô da primeira etapa.

Etapa 2: como

det(A) \neq 0

, então

det(A^{(1)}) \neq 0

e é sempre possível reescrever a matriz

A^{(1)}

, sem alterarmos a posição da linha 1, de modo que o elemento

a_{22}^{(1)}

seja diferente de zero, utilizando a operação elementar (i): trocar a posição de duas linhas da matriz. Feito isso, a linha 2 será auxiliar no processo de eliminação e nesta etapa eliminamos

x_2

das equações

i = 3,..., n

utilizando a operação elementar: da linha i subtrair a linha 2 multiplicada por

m_{i2} = \frac{a_{i2}^{(1)}}{a_{22}^{(1)}}

para

i = 3, ..., n

. Ao final desta etapa teremos:

[ A^{(2)}|b^{(2)} ] = \left[ \begin{array}{ccccc|c} a_{11}^{(2)} & a_{12}^{(2)} & a_{13}^{(2)} & \cdots & a_{1n}^{(2)} & b_1^{(2)} \\ 0 & a_{22}^{(2)} & a_{23}^{(2)} & \cdots & a_{2n}^{(2)} & b_2^{(2)} \\ 0 & 0 & a_{33}^{(2)} & \cdots & a_{3n}^{(2)} & b_3^{(2)} \\ \vdots & \vdots & \vdots & & \vdots & \vdots \\ 0 & 0 & a_{n3}^{(2)} & \cdots & a_{nn}^{(2)} & b_n^{(2)} \end{array} \right]

onde, na primeira e na segunda linha:

a_{ij}^{(2)} = a_{ij}^{(1)}

b_i^{(2)} = b_i^{(1)}

, para

i = 1,2

j = i, i+1, ..., n

. E nas demais linhas:

a_{ij}^{(2)} = a_{ij}^{(1)} - m_{i2}a_{2j}^{(1)}

b_i^{(2)} = b_i^{(1)} - m_{i2}b_2^{(1)}

, para

i = 3,..., n

j = 2,...,n

.

Nesse caso, os elementos

m_{i2} = \frac{a_{i2}^{(1)}}{a_{22}^{(1)}}

para

i = 3,..., n

são os multiplicadores e

a_{22}^{(1)}

é o pivô da segunda etapa.

Seguimos o mesmo raciocínio para as demais etapas, até que no final da etapa n-1 a matriz será:

[ A^{(n-1)}|b^{(n-1)} ] = \left[ \begin{array}{ccccc|c} a_{11}^{(n-1)} & a_{12}^{(n-1)} & a_{13}^{(n-1)} & \cdots & a_{1n}^{(n-1)} & b_1^{(n-1)} \\ 0 & a_{22}^{(n-1)} & a_{23}^{(n-1)} & \cdots & a_{2n}^{(n-1)} & b_2^{(n-1)} \\ 0 & 0 & a_{33}^{(n-1)} & \cdots & a_{3n}^{(n-1)} & b_3^{(n-1)} \\ \vdots & \vdots & \vdots & & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & a_{nn}^{(n-1)} & b_n^{(n-1)} \end{array} \right]

e o novo sistema

A^{(n-1)}x = b^{(n-1)}

é triangular superior e equivalente ao sistema original

Ax = b

, uma vez que só utilizamos operações elementares para obtê-lo.

Exemplo 1: Considere o seguinte sistema linear:

\left\lbrace \begin{array}{rrrrrrr} 1x_1 & - & 2x_2 & + & 1x_3 & = &-1 \\ 2x_1 & - & 3x_2 & + & 1x_3 & = & -3 \\ 1x_1 & + & 4x_2 & + & 2x_3 & = & 7 \end{array}\right.

Escrevendo a matriz ampliada do sistema, temos:

[A | b] = [A^{(0)} | b^{(0)}] = \left[ \begin{array}{rrr|r} 1 & -2 & 1 & -1 \\ 2 & -3 & 1 & -3 \\ 1 & 4 & 2 & 7 \end{array} \right]

Etapa 1: Nesse caso, o pivô da primeira etapa é 1 e os multiplicadores são

m_{21} = \frac{2}{1} = 2

m_{31} = \frac{1}{1} = 1

. Dessa forma, eliminamos a incógnita

x_1

da equação 2 aplicando a operação elementar:

l_2 \longleftarrow l_2 - m_{21}l_1

, ou seja,

l_2 \longleftarrow l_2 - 2l_1

. E, eliminamos

x_1

da equação 3 aplicando a operação elementar:

l_3 \longleftarrow l_3 - m_{31}l_1

, ou seja,

l_3 \longleftarrow l_3 - l_1

. No final desta etapa teremos:

[A^{(1)} | b^{(1)}] = \left[ \begin{array}{rrr|r} 1 & -2 & 1 & -1 \\ 0 & 1 & -1 & -1 \\ 0 & 6 & 1 & 8 \end{array} \right]

Etapa 2: O pivô da segunda etapa é 1 e o multiplicador é

m_{32} = \frac{6}{1} = 6

. Assim, eliminamos a incógnita

x_2

da equação 3 aplicando a operação elementar:

l_3 \longleftarrow l_3 - m_{32}l_2

, ou seja,

l_3 \longleftarrow l_3 - 6l_2

. No final desta etapa teremos:

[A^{(2)} | b^{(2)}] = \left[ \begin{array}{rrr|r} 1 & -2 & 1 & -1 \\ 0 & 1 & -1 & -1 \\ 0 & 0 & 7 & 14 \end{array} \right]

obtemos então um sistema linear

A^{(2)}x = b^{(2)}

, dado por:

\left\lbrace \begin{array}{rrrrrrr} 1x_1 & - & 2x_2 & + & 1x_3 & = &-1 \\ & & 1x_2 & - & 1x_3 & = & -1 \\ & & & & 7x_3 & = & 14 \end{array}\right.

que é triangular superior e equivalente ao original. Da terceira equação obtemos:

x_3 = 2

. Substituíndo na segunda equação, temos:

x_2 = -1 + 2 \Rightarrow x_2 = 1

e finalmente, substituíndo na primeira equação, temos:

x_1 = -1 + 2 - 2 \Rightarrow x_1 = -1

. Portanto, a solução do sistema é

(x_1, x_2, x_3) = (-1, 1, 2)

.

Algoritmo (Resolução de um sistema linear através da Eliminação Gaussiana): Considere o sistema linear

Ax = b

, onde

A

é uma matriz

n \ti

Suponha que o elemento que está na posição

a_{kk}

é diferente de zero no início da etapa k. A resolução desse sistema pode ser feita da seguinte forma:
Algoritmo.

Voltar ao Topo.

Pivoteamento

Durante o processo da eliminação de Gauss, precisamos efetuar o cálculo dos multiplicadores:

m_{ik} = \frac{a_{ik}^{(k-1)}}{a_{kk}^{(k-1)}}

em cada etapa k. Nesses cálculos, estamos dividindo pelos pivôs de cada etapa. Observe que se os pivôs forem nulos não podemos efetuar a divisão e, caso um pivô seja muito próximo de zero, trabalhar com esse pivô conduziria a resultados imprecisos, pois em qualquer calculadora ou computador os cálculos são efetuados com uma aritmética de precisão finita, e pivôs próximos de zero dariam origem a multiplicadores muito grandes e assim, teríamos uma ampliação dos erros de arredondamento.

Para solucionar estes problemas, vamos adotar uma estratégia de pivoteamento, ou seja, um processo de escolha do pivô em cada etapa. Uma estratégia útil é:

i) durante a etapa k do processo de eliminação, escolher para pivô o maior elemento, em módulo, entre os coeficientes

a_{ik}^{(k-1)}

i = k, k+1, ..., n

.

ii) permutar as linhas k e

i

, caso

a_{ik}^{(k-1)}

seja maior, em módulo, que

a_{kk}^{(k-1)}

.

Exemplo 2: Considere o seguinte sistema linear:

\left\lbrace \begin{array}{rrrrrrr} 0x_1 & + & 1x_2 & - & 2x_3 & = & 7 \\ 2x_1 & - & 2x_2 & + & 3x_3 & = & -10 \\ 1x_1 & + & 3x_2 & + & 1x_3 & = & 8 \end{array}\right.

Escrevendo a matriz ampliada do sistema, temos:

[A | b] = [A^{(0)} | b^{(0)}] = \left[ \begin{array}{rrr|r} 0 & 1 & -2 & 7 \\ 2 & -2 & 3 & -10 \\ 1 & 3 & 1 & 8 \end{array} \right]

Etapa 1: Observe que o elemento

a_{11}

é nulo e evidentemente não pode ser o pivô da etapa 1. Escolhendo o maior elemento em módulo entre os coeficientes

a_{i1}^{(0)}

para

i = 1,2,3

teremos

a_{21}^{(0)} = 2

. Logo, no início da etapa 1, permutamos as linhas 1 e 2:

[A^{(0)} | b^{(0)}] = \left[ \begin{array}{rrr|r} 2 & -2 & 3 & -10 \\ 0 & 1 & -2 & 7 \\ 1 & 3 & 1 & 8 \end{array} \right]

Agora o pivô é 2 e os multiplicadores são

m_{21} = \frac{0}{2} = 0

m_{31} = \frac{1}{2}

. Dessa forma, a incógnita

x_1

já está eliminada da equação 2, e eliminamos

x_1

da equação 3 aplicando a operação elementar:

l_3 \longleftarrow l_3 - m_{31}l_1

, ou seja,

l_3 \longleftarrow l_3 - \frac{1}{2}l_1

. No final desta etapa, teremos:

[A^{(1)} | b^{(1)}] = \left[ \begin{array}{rrr|r} 2 & -2 & 3 & -10 \\ 0 & 1 & -2 & 7 \\ 0 & 4 & -\frac{1}{2} & 13 \end{array} \right]

Etapa 2: Na segunda etapa, vamos escolher para pivô o maior elemento, em módulo, entre os coeficientes

a_{i2}^{(1)}

para

i = 2,3

. Nesse caso o maior, em módulo, entre esses coeficientes é

a_{32}^{(1)} = 4

. Logo, no início da etapa 2, permutamos as linhas 2 e 3:

[A^{(1)} | b^{(1)}] = \left[ \begin{array}{rrr|r} 2 & -2 & 3 & -10 \\ 0 & 4 & -\frac{1}{2} & 13 \\ 0 & 1 & -2 & 7 \end{array} \right]

Agora o pivô da segunda etapa é 4 e o multiplicador é

m_{32} = \frac{1}{4}

. Dessa forma, eliminamos a incógnita

x_2

da equação 3 aplicando a operação elementar:

l_3 \longleftarrow l_3 - m_{32}l_2

, ou seja,

l_3 \longleftarrow l_3 - \frac{1}{4}l_2

. No final desta etapa teremos:

[A^{(2)} | b^{(2)}] = \left[ \begin{array}{rrr|r} 2 & -2 & 3 & -10 \\ 0 & 4 & -\frac{1}{2} & 13 \\ 0 & 0 & -\frac{15}{8} & \frac{15}{4} \end{array} \right]

Obtemos então um sistema linear

A^{(2)}x = b^{(2)}

, dado por:

\left\lbrace \begin{array}{rrrrrrr} 2x_1 & - & 2x_2 & + & 3x_3 & = & -10 \\ & & 4x_2 & - & \frac{1}{2}x_3 & = & 13 \\ & & & - & \frac{15}{8}x_3 & = & \frac{15}{4} \end{array}\right.

que é triangular superior e equivalente ao original. Da terceira equação obtemos:

x_3 = -\frac{8}{4} = -2

. Substituíndo na segunda equação, temos:

4x_2 = 13 - 1 \Rightarrow x_2 = \frac{12}{4} = 3

e, substituíndo na primeira equação, temos:

2x_1 = -10 +12 \Rightarrow x_1 = \frac{2}{2} = 1

. Portanto,

(x_1, x_2, x_3) = (1, 3, -2)

é solução do sistema.

Note que escolhendo o pivô como o maior elemento em módulo entre os candidatos fazemos com que os multiplicadores sejam tais que

|m| \leq 1

, ou seja,

m \in [-1,1]

, o que evita a ampliação de erros de arredondamento.

Algoritmo (Eliminação Gaussiana com Pivoteamento): Considere o sistema linear

Ax = b

, onde

A

é uma matriz

n \times n

. O seguinte algoritmo realiza a eliminação Gaussiana nesse sistema, com a estratégia de pivoteamento parcial:
Algoritmo.

Número de operações: Vamos calcular o número de operações efetuadas no algoritmo da eliminação Gaussiana, na fase de triangularização da matriz

A

. A fase de pivoteamento não precisa ser contada, pois apenas realizamos trocas de linha e não efetuamos nenhuma operação.

O primeiro laço

(k = 1, ..., (n-1))

contém um segundo laço na fase de eliminação

(i = (k+1),...,n)

, que é realizado:

quando $k = 1 \longrightarrow (n-1)$ vezes;

quando $k = 2 \longrightarrow (n-2)$ vezes;

\vdots

quando $k = (n-1) \longrightarrow 1$ vez.

Logo, no total o segundo laço é realizado:

1 + 2 + ... + (n-1) = \sum_{x = 1}^{n-1} x = \frac{n(n-1)}{2} \;\;\; vezes

E dentro desse laço são realizadas 3 operações (uma divisão, uma multiplicação e uma soma). Portanto, no total realizamos:

\frac{3n(n-1)}{2} = \frac{3n^2-3n}{2} \;\;\; operações

Mas, ainda não contamos as operações realizadas no terceiro laço

(j = (k+1), ..., n)

. Esse laço está dentro do segundo e é realizado:

quando $k = 1 \longrightarrow (n-1)^2$ vezes ( $(n-1)$ vezes para cada vez que é realizado o segundo laço);

quando $k = 2 \longrightarrow (n-2)^2$ vezes ( $(n-2)$ vezes para cada vez que é realizado o segundo laço);

\vd

quando $k = (n-1) \longrightarrow 1^2$ vez (1 vez para cada vez que é realizado o segundo laço).

Logo, no total o terceiro laço acontece:

1^2 + 2^2 + ... + (n-1)^2 = \sum_{x = 1}^{n-1} x^2 = \frac{n(n-1)(2n-1)}{6} \;\;\; vezes

Em cada repetição realizamos 2 operações (uma multiplicação e uma soma). Portanto, no total realizamos:

\frac{2n(n-1)(2n-1)}{6} = \frac{4n^3-6n^2+2n}{6} \;\;\; operações

Logo, o algoritmo da eliminação Gaussiana realiza um total de:

\frac{3n^2-3n}{2} + \frac{4n^3-6n^2+2n}{6} = \frac{9n^2 - 9n + 4n^3 - 6n^2 + 2n}{6} = \frac{4n^3 +3n^2 - 7n}{6} \;\;\; operações

Como vimos, o número de operações para a resolução do sistema triangular superior é da ordem de

n^2

. Assim, o total de operações para se resolver um sistema linear pelo método da eliminação de Gauss é aproximadamente

\frac{4n^3 +9n^2 -7n}{6}

. Quando

n

é grande, o termo

n^3

predomina e por esta razão é comum afirmar que a eliminação Gaussiana realiza uma ordem de

\frac{2n^3}{3}

operações.

Para resolver um sistema

20\times 20

, por exemplo, realizamos aproximadamente

5910

operações. Considerando um computador que realiza

2000000

(dois milhões) de operações por segundo, levaria, aproximadamente,

3*10^{-3}

segundos para resolver este sistema pela eliminação Gaussiana, o que é muito mais vantajoso se comparado com o método de Cramer.

Voltar ao Topo.

Última Atualização: 02/02/2016.