Eliminação de Gauss

Eliminação de Gauss

(Parte 1 de 2)

rpp@impa.br Professor:

Cursos: Engenharia Agrícola, Engenharia da Produção, Matemática

Disciplina: Cálculo Numérico Data: 9 de Agosto de 2005

Método de Eliminação de Gauss

1. Introdução

A resolução de sistemas de equações lineares e o cálculo de determinantes são dois exemplos de problemas fundamentais da álgebra linear que foram estudados desde longa data. Leibnitz encontrou em 1693 a fórmula para o cálculo de determinantes, e em 1750 Cramer apresentou um método para resolver sistemas de equações lineares, conhecida desde então como a Regra de Cramer, primeira pedra na construção da álgebra linear e da teoria das matrizes. No inicio da evolução dos computadores digitais, o cálculo matricial recebeu a atenção merecida. John von Neumann e Alan Turing eram os pioneiros mundialmente famosos da ciência da computação, e introduziram contribuições notáveis para o desenvolvimento da álgebra linear computacional. Em 1947, von Neumann e Goldstein pesquisaram os efeitos dos erros de arredondamento na resolução de equações lineares. Um ano depois, Turing iniciou um método para decompor uma matriz num produto de uma matriz triangular inferior com uma matriz escalonada (conhecida como decomposição LU). Hoje, a álgebra linear computacional é uma área de muito interesse. Isto é devido ao fato que este campo está reconhecido agora como uma ferramenta absolutamente essencial em muitas das aplicações computacionais que requerem cálculos longos e difíceis de desenvolver manualmente, como por o exemplo: em gráficos de computador, em modelagem geométrica, em robótica, etc..

2. Objetivo

BAX=,(1)

Obter uma solução exata de um sistema de equações lineares da forma onde, A é uma matriz quadrada de ordem n, X e B são vetores coluna de ordem n x 1.

1. O método consiste em utilizar um número finito de transformações elementares e considerar elementos da diagonal principal (não nulos) chamados pivôs.

2. Se, por exemplo, 0≠iia, a linha do pivô é mantida e os outros elementos da i-ésima coluna ficam zerados. 3. O transformado de um elemento que não aparece na linha nem na coluna do pivô é igual a este elemento menos o produto contradiagonal dividido pelo pivô. 4. O processo repete-se escolhendo novos pivôs (não nulos) que não figurem na linha nem na coluna anteriores. 5. O processo termina quando já não é possível tomar novos pivôs. 6. Depois, inicia-se o processo de substituição para cima.

3. Exemplo Resolva o seguinte sistema de equações lineares zyx zyx zyx (2)

Podemos escrever este sistema linear na forma matricial:

rpp@impa.br Professor:

Passo 1: A Matriz Aumentada. Define-se primeiro a matriz aumentada:

A(4)

As três primeiras colunas desta matriz coincidem com as colunas da matriz do sistema e a última coluna é a dos termos da direita do sistema de equações lineares (2).

Passo 2. Processo de eliminação

Como ,0211≠=aeste elemento será o nosso primeiro pivô. Define-se 2111 aλ, e calculam-se os outros elementos transformados da segunda linha segundo a regra 3 acima: ( )

De outra parte, define-se 2311 aλ, e determinam-se ou outros elementos transformados da terceira linha:

Desta forma a nova matriz aumentada transformada após esta primeira fase de eliminação fica como

'A(7)

Para a segunda fase de eliminação Gaussiana consideramos como pivô o elemento .02 7'2≠=a Agora, definimos a aλ. Assim, podemos determinar os elementos transformados na terceira linha:

rpp@impa.br Professor:

A nova matriz aumentada fica após esta segunda fase de eliminação da forma seguinte:

Passo 3: Fase de substituição retrocedida Temos obtido o seguinte sistema equivalente de equações lineares:

que é um sistema triangular, isto é a matriz do sistema é uma matriz triangular superior, que pode ser resolvido, facilmente, por substituição das variáveis. Da última equação de (10) temos e substituindo este valor na segunda equação de (10) obtemos,

Finalmente, substituindo estes valores, 3,2==yez, na primeira equação de (10) temos,

O método de eliminação de Gauss consiste de duas fases:

• Fase de eliminação: o objetivo é empregar transformações elementares na matriz aumentada, visando obter uma correspondente a um sistema triangular superior.

• Fase de substituição retrocedida: inicia-se resolvendo a última equação, cuja solução é substituída na penúltima e resolve-se na penúltima variável, e assim em forma consecutiva.

Considerando como operações elementares somas, produtos e divisões entre os elementos da matriz aumentado o na fase de substituição retrocedida, a seguinte tabela reproduz o esforço computacional.

Operações Primeira Fase de eliminação

Segunda Fase de eliminação

Substituição retrocedida

Total Tempo unitário Total

rpp@impa.br Professor:

4. Decomposição LU Definem-se duas matrizes triangulares:

• Matriz L ( de “ lower” ), triangular inferior cujos elementos diagonais são unidades e seus elementos abaixo da diagonal são os coeficientes λ1, λ2, λ3 definidos no processo de eliminação de Gauss.

• Matriz U ( do inglês “ upper”, superior), matriz triangular superior defini da pelo bloco das três primeiras colunas da última matriz aumentada A”.

Em nosso exemplo podemos escrever L e U e proceder à multiplicação matricial LU obtendo:

A matriz do sistema resulta sendo o produto de duas matrizes, uma triangular inferior e outra triangular superior.

5. Cálculo do Determinante

det (L) • det (U) = det ( A)(12)

O determinante do produto de duas matrizes quadradas é o produto dos determinantes mas det(L) = 1, e assim det(A) = det (U) = 117

2 7.2=. Isto é devido ao fato que o determinante de qualquer matriz triangular é o produto dos elementos da diagonal, o que pode ser comprovado em forma fácil.

6. Estratégia de Pivotamento

Um sistema de operações pode ter um zero na diagonal e ainda possuir uma solução bem definida. Por exemplo, o sistema de equação.

possui um zero na diagonal, mas a solução, x1 = 1 e x2 = 2, está bem definida. O problema pode ser resolvido reordenando as equações para obter o sistema.

rpp@impa.br Professor:

Foi “trocada” p2 e p1.

Eliminamos x1 diferentes do elemento privotal.

O novo pivô é o maior elemento da segunda coluna diferente da linha pivotal anterior.

o que pode ser resolvido por meio da retrosubstituição, pois o sistema é agora triangular superior. Assim, o problema de um pivô nulo pode superar-se, isto quer dizer, processando abaixo da coluna pivotante até achar um elemento não nulo e trocando esta linha com a linha pivotal existente. Isto vai funcionar, mas há uma condição consideração adicional. Devido à que ocorrem problemas se um pivô é nulo, resulta razoável supor o que pode acontecer se o pivô é pequeno em comparação com os outros elementos da matriz, e tal é, de fato, neste caso.

(Parte 1 de 2)

Comentários