Embed Size (px)
DESCRIPTION
Â
Citation preview
[email protected] 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 Obter uma solução exata de um sistema de equações lineares da forma
BAX = , (1)
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
033
1223
132
=−+
=++−
−=−+
zyx
zyx
zyx
(2)
Podemos escrever este sistema linear na forma matricial:
[email protected] Professor: ����������������������������
−
=
−
−
−
0
12
1
313
231
312
z
y
x
(3)
Passo 1: A Matriz Aumentada. Define-se primeiro a matriz aumentada:
−
−
−−
=
0313
12231
1312
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 ≠=a este elemento será o nosso primeiro pivô. Define-se 21
11
211 −==
aa
λ , e calculam-se os
outros elementos transformados da segunda linha segundo a regra 3 acima:
( )( ) ( )( ) 2
2321
14124'24
21
21
13123'23
27
21
12122'22
)1(12
32
13
=−⋅−−=−=
=−⋅−−=−=
=⋅−−=−=
aaa
aaa
aaa
λ
λ
λ
(5)
De outra parte, define-se 23
11
312 ==
aa
λ , e determinam-se ou outros elementos transformados da terceira
linha:
23
23
14234'34
23
23
13233'33
21
23
12232'32
)1(0
)3(3
11
=−⋅−=−=
=−⋅−−=−=
−=⋅−=−=
aaa
aaa
aaa
λ
λ
λ
(6)
Desta forma a nova matriz aumentada transformada após esta primeira fase de eliminação fica como
−
−−
=
23
23
21
223
21
27
0
0
1312
'A (7)
Para a segunda fase de eliminação Gaussiana consideramos como pivô o elemento .027'
22 ≠=a Agora,
definimos 71
27
21
122
'32
3 −=−==aa
λ . Assim, podemos determinar os elementos transformados na terceira
linha:
[email protected] Professor: �!�"�#�$%�&�$�'�&�%�&�(�)�*
( )( ) 7
22223
71
23'
243'34
"34
711
21
71
23'
233'33
"33
=⋅−−=−=
=⋅−−=−=
aaa
aaa
λ
λ (8)
A nova matriz aumentada fica após esta segunda fase de eliminação da forma seguinte:
−−
=
722
711
223
21
27
00
0
1312
"A (9)
Passo 3: Fase de substituição retrocedida Temos obtido o seguinte sistema equivalente de equações lineares:
722
711
223
21
27
132
=
=+
−=−+
z
zy
zyx
(10)
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
27
11
722
==z ,
e substituindo este valor na segunda equação de (10) obtemos,
31
,,227
223
223
21
27 =
−==⋅+ yficaypararesolvendoey .
Finalmente, substituindo estes valores, 3,2 == yez , na primeira equação de (10) temos,
12
631,,12332 =+−−=−=⋅−+ xficaxpararesolvendoex .
+-,/.�021436587:98;=< 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.
>8?�@BADCBE�AGFHA=IKJ2L/MON/P�QRADSTN2UWV 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 X:Y8Z-[:\ ] ^ _ `a` bdc bdbdceafWgdh6ikjlgdm n o p qaq o�rdr s8tus:vavwHx ydx z�{a|:z } ~ � � �a�:� ���u�:�a��2�T����� �T�����d�
[email protected] 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.
=
1
01
001
32
1
λλ
λL (11)
• 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=
−
−
−
=
−
−
−
313
231
312
711
00
21
27
0
312
171
23
0121
001
(12)
L U
A matriz do sistema resulta sendo o produto de duas matrizes, uma triangular inferior e outra triangular superior.
5. Cálculo do Determinante O determinante do produto de duas matrizes quadradas é o produto dos determinantes
det (L) • det (U) = det ( A) (12)
mas det(L) = 1, e assim det(A) = det (U) = 11711
.27
.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.
x2 = 1
x1 + x2 = 2 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.
[email protected] Professor: ������ �¡¢�£�¡�¤�£�¢�£�¥�¦�§
Foi “trocada” p 2 e p1. Eliminamos x1 diferentes do elemento privotal. O novo pivô é o maior elemento da segunda coluna diferente da linha pivotal anterior.
x1 + x2 = 2 x2 = 1
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.
Assim é melhor antes de procurar o primeiro elemento não nulo, pesquisar a coluna inteira para determinar o elemento de módulo máximo e depois trocar as linhas, se for necessário, de modo que este elemento converte-se no pivô. Tal processo se chama Pivotamento Parcial, constituindo um passo fundamental na seleção de sistema de equações lineares.
Existe também um processo de Pivotamento Completo segundo o qual localizamos o elemento de maior módulo na submatriz ija para i, j ≥ k no sistema.
22222
1212111
......................................
.........................................
bxaxa
bxaxaxa
nn
nn
=++
=+++
nnnnkkn
knnkknk
knknkkk
bxaxa
bxaxa
bxaxa
=++=++
=++
+++
,,
1,1,1
............
............
............
depois do qual trocam-se a linha e a coluna para que este elemento ocupe a posição pivotal. Em termos de computação, isto resulta num alto esforço computacional e na pratica, pouco se precisa. Em geral, o mais conveniente é o pivotamento parcial. Caso não encontrar nenhum elemento diferente de zero na coluna pivotal, então a matriz é simgular, de modo que pode usar-se como uma prova de singularidade.
Exemplo:
→→→
3
2
1
p
p
p
=
312811
17421034312
z
y
x
Procura-se o elemento de módulo máximo na primeira coluna. Primeiro Pivô
4 3 10 28 2 1 3 11 2 4 17 31
Ou também P1 0 - 0.5 - 2 - 3 P2 4 3 10 28 P3 0 25 12 17 Segundo Pivô
[email protected] Professor: ¨�©�ª�«�¬�®�¬�¯�®��®�°�±�²
P1 0 0 0.4 0.4 P2 4 3 10 28 P3 0 25 12 17
Agora temos a forma triangular superior. Para levar adiante a substituição retrocedida, trabalhamos com as linhas em ordem inversa,
14.04.0
:,, 3123 ==xppp
Da linha p2 obtém-se.
25.2
55.21217 3
2 ==−
=x
x
Da linha p2 obtêm-se:
34
124
106284
10328 321 ==−−=
−−=
xxx
7. Escalonamento A estratégia dos pivôs pode ser mudada re-escalando as equações. Por exemplo, dado o sistema de
equações seguinte: x1 + x2 = 2 0,0001 x1 + 0,1 x2 = 1
o multiplicador é 0,0001. Mas, se multiplicamos a segunda equação por 100 000 resultará,
x1 + x2 = 2 10 x1 + 10000 x2 = 100 000
Então deveriam ser trocadas as linhas, e o multiplicador será 0,1. Assim a estratégia de pivotamento foi alterada com o escalamento e, além disso, os cálculos realizados no processo de eliminação mudam, dando uma acumulação distinta dos erros de arredondamento. Até o momento não existe acordo sobre a “melhor” maneira de escalonamento de um sistema linear visando reduzir a acumulação de erros de arredondamento, mas um método muito empregado é chamado de “equilíbrio”. Nesta técnica, as equações são escalonadas de modo que os elementos máximos nas linhas e colunas da matriz A tenhan mais ou menos a mesma grandeza, e em geral, escolhe-se a unidade. Um balanço do sistema (*) seria assim,
x1 + x2 = 2 0,001 x1 + x2 = 10.
(*)
