Escalonamento De Gauss

Escalonamento ou o Método da Eliminação de Gauss

Kleber Kilhian 16.10.12 Álgebra Linear 15 Comentários

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×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×20!×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×105 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

a1x1+a2x2+a3x3+⋯+anxn=b(1)

onde ai,b∈R e os xi são indeterminados, ou seja as incógnitas ou variáveis. Os escalares ai são chamados coeficientes de xi 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×n, onde o número de equações é igual ao número de incógnitas.

Considere o sistema linear Ax=b:

⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪a11x1+a12x2+⋯+a1nxna21x1+a22x2+⋯+a2nxn⋮an1x1+an2x2+⋯+annxn===b1b2nn(2)

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×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′x=b′ de modo que os sistemas Ax=b e A′x=b′ 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 a11 seja não-nulo;

2) Para cada i>1, aplicamos a operação:

Li⟶−aikLk+akkLi(3)

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 Li pela equação equivalente resultante da multiplicação da equação Lk por −aik somada ao produto da equação Li por akk. Com isso eliminamos o termo aik da equação Li:

⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪a11x1+a12x2a22x2++⋯⋯⋮++a1nxna2nxnannxn===b1b2bn(4)

A cada etapa desse processo elimina uma incógnita de equações sucessivas até, por fim, encontrarmos somente:

annxn=bn(5)

Que nos dá imediatamente o valor de xn.

Substituindo xn na equação Li−1, obteremos o valor de xn−2 e assim sucessivamente.

Exemplo 1:

Considere o sistema de equações abaixo. Encontre os valores de x, y e z.

⎧⎩⎨⎪⎪2x3x5x+++y2y4y−++2z2z3z===1014

Primeiramente, vemos que o termo a11 é não-nulo e igual a 2. Vamos identificar cada equação como:

L1⟶L2⟶L3⟶2x3x5x+++y2y4y−++2z2zz===1014

Etapa k=1: Eliminando a incógnita x da segunda e terceira equações

Primeiramente vamos eliminar a incógnita x da equação L2. Assim, devemos aplicar a operação:

Li⟶−aikLk+akkLi

Então, fazemos:

L2⟶−a21L1+a11L2=−3L1+2L2

Desse modo:

−3L1==−3(2x+y−2z)−6x−3y+6z==−3(10)−30

e

2L2==2(3x+2y+2z)6x+4y+4z==2(1)2

Somando termo a termo:

−3L1+2L2==−6x−3y+6z+6x+4y+4zy+10z==−30+2−28

Assim, a equação L2 será equivalente a L2⟶y+10z=−28

Eliminemos agora a incógnita x da terceira equação:

L3⟶−a31L1+a11L3=−5L1+2L3

Desse modo:

−5L1==−5(2x+y−2z)−10x−5y+10z==−5(10)−50

e

2L3==2(5x+4y+3z)10x+8y+6z==2(4)8

Somando termo a termo:

−5L1+2L3==−10x−5y+10z+10x+8y+6z3y+16z==−50+8−42