Embed Size (px)
DESCRIPTION
Métodos de Eliminação de Gauss;Método de Decomposição LU;Método de Fatoração de Cholesky.
Citation preview
1
Métodos Para Resolver Sistemas de
Equações Lineares
2
SUMÁRIO
1. INTRODUÇÃO ........................................................................................................ 3
2. MÉTODO DE ELIMINAÇÃO DE GAUSS ............................................................ 5
3. DECOMPOSIÇÃO LU ............................................................................................ 8
3.1 Desenvolvimento do Método de Decomposição LU ...................................... 9
4. A FATORAÇÃO DE CHOLESKY ....................................................................... 10
5. REFERÊNCIAS BIBLIOGRÁFICAS ................................................................... 17
3
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. Leibniz 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 início 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. Em1947, 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. [1].
Antes de iniciarmos um estudo sobre os métodos diretos que são utilizados para
encontrar a solução exata para um sistema de Equações Algébricas Lineares, iremos
relembrar alguns conceitos relevantes ao tema deste trabalho.
Para começar vamos falar um pouco sobre os sistemas de equações lineares. Tais
sistemas aparecem frequentemente em matemática aplicada, economia e engenharia ao
modelar certos fenômenos. Por exemplo, em programação linear, geralmente é discutido
como maximizar o lucro quando existem certas restrições relacionadas à dificuldade,
disponibilidade de tempo, ou outras condições. Estas restrições podem ser colocadas na
forma de um sistema de equações lineares [2].
Deste modo, um sistema de equações lineares (ou sistema linear) é uma coleção de
equações lineares envolvendo o mesmo conjunto de variáveis. A solução de um sistema
linear é uma n-upla de valores s = (s1,s2,....,sn) que simultaneamente satisfazem todas as
4
equações do sistema [2]. Observando a Figura 1 podemos visualizar a interseção dos
planos formada pela solução de um sistema:
Figura 1 - Cada equação de um sistema linear em três variáveis determina um plano. Uma solução do
sistema corresponde a um ponto na interseção desses planos.
A solução para os sistemas de Equações Algébricas Lineares é obtida a partir de
técnicas diretas e iterativas estas técnicas são implementadas através de dois métodos:
métodos diretos e métodos iterativos. Neste trabalho iremos tratar apenas dos métodos
diretos.
Os métodos diretos se caracterizam por uma sequência de operações (quantidade
definida de operações), depois da qual se obtém a solução do sistema. No presente
trabalho iremos trabalhar apenas com os métodos diretos de Eliminação de Gauss,
Decomposição LU e Fatoração de Cholesky.
O trabalho esta dividido da seguinte forma: nos Capítulos 2, 3 e 4 teremos uma
revisão bibliográfica sobre os métodos de Eliminação de Gauss, Decomposição LU e
Fatoração de Cholesky respectivamente.
5
2. MÉTODO DE ELIMINAÇÃO DE GAUSS
Em um sistema linear formado por um par de equações, o processo para
descobrir as duas incógnitas consiste em isolar uma delas e substituir na outra equação,
eliminando assim, uma das incógnitas.
Para um sistema maior, podemos estender a abordagem para um número maior de
equações através do método conhecido como “Eliminação de Gauss”, que basicamente
manipula algumas variáveis, a fim de gerar uma eliminação ao longo da execução, ao
tempo que vai substituindo regressivamente nas equações originais, a fim de obter a
solução final.
Sendo assim, o sistema geral que iremos estudar é formado por um conjunto arbitrário
de equações tais que:
(Equação 2.1)
(Equação 2.2)
(Equação 2.3)
Entre os métodos computacionais temos que o processo de diagonalização de
matrizes é uma técnica-chave para solução de sistemas lineares. Sendo assim, a primeira
fase da eliminação de Gauss está em reduzir a matriz dos coeficientes para uma matriz
triangular-superior, eliminando da primeira variável em todas as equações diferentes de
. Para isso, vamos multiplicar a Equação 1 por . Com isso, obtemos
6
(Equação 2.4)
Agora, subtraímos a Equação 4 da Equação 2, O que nos permite obter
(Equação 2.5)
substituindo cada termo dentro dos parênteses por um novo , onde , temos
que a Equação 5 pode ser escrita como
(Equação 2.6)
onde.
Assim como fizemos com a segunda linha do sistema, repetimos o processo para as
demais equações. Ou seja, multiplicamos pela Equação 1 e subtraímos o resultado
da equação 3, e continuamos o processo até a última equação [3].
No processo de eliminação, o termo é conhecido como “pivô”, e a multiplicação
de cada linha pelo elemento é denominada “normalização”. Portanto, podemos
notar que o pivô nulo é um problema no processo de normalização, já que provoca uma
divisão por zero. Por isso, em implementações reais, devemos utilizar algumas técnicas
de “re-normalização” para eliminarmos o pivô nulo do processo [3].
Após a primeira eliminação o sistema linear modificado ficará:
(Equação 2.7)
7
(Equação 2.8)
(Equação 2.9)
Agora, repetimos o mesmo processo de eliminação, mas tomando como coeficiente de
normalização como sendo , aplicando-o à todas equações a partir da terceira. Este
processo deve continuar usando os pivôs obtidos nas equações remanescentes. Ou seja,
repetimos o pivotamento e normalização descritas para até a equação ,
eliminando até o termo da equação [3]. Com isso, obteremos o sistema
triangular a seguir:
(Equação 2.10)
(Equação 2.11)
(Equação 2.12)
(Equação 2.13)
A partir do sistema triangular, a solução é facilmente obtida, a começar por xn :
8
(Equação 2.14)
substituindo esse resultado na equação anterior, isto é, na equação , cuja
dependência está apenas nas variáveis e , podemos determinar também .
Esse processo de ir substituindo as incógnitas já encontradas nas equações anteriores
chamaremos de backtrack. A partir dele, encontramos todos pela da fórmula [3]:
(Equação 2.15)
para [3].
3. DECOMPOSIÇÃO LU
Um sistema linear do tipo:
(Equação 3.1)
(Equação 3.2)
(Equação 3.3)
pode ser representado na seguinte forma matricial:
9
onde é a matriz formada pelos coeficientes , é o vetor formado
pelas variáveis a serem determinadas e é o vetor dos termos
independentes [4].
Para determinação das incógnitas, o método da eliminação de Gauss desenvolve
duas fases: a primeira é a eliminação progressiva, onde reduz o número de variáveis ao
longo da execução para, então, aplicar a segunda fase, chamada de substituição
regressiva, onde utiliza o resultado da primeira para determinar a solução geral do
sistema [4].
Dois passos descritos, o primeiro é o que consome mais tempo de cálculo, uma vez
que é nesta fase que consiste o maior número de operações aritméticas e de trocas de
dados. Por isso, encontrar um método que minimize esta fase crítica implica em
aumentar o desempenho para realizar a tarefa de resolução de sistemas lineares [4].
Os métodos de decomposição LU consistem em separar a fase de eliminação da
matriz dos coeficientes , que consomem maior tempo, das manipulações envolvidas
com o vetor dos termos independentes, . Portanto, devemos deixar claro que, ao
contrário da eliminação de Gauss, uma decomposição de LU é uma estratégia de
melhoria na resolução de sistemas lineares. Sendo assim, não existe “o método” de
decomposição LU, mas sim algumas abordagens a serem tomadas que permitem
decompor o sistema. Uma implicação interessante disso é que a própria eliminação de
Gauss pode ser descrita como uma decomposição LU [4].
3.1 Desenvolvimento do Método de Decomposição LU
A equação pode ser reescrita como . Aplicando a eliminação
de Gauss, sabemos que este sistema pode ser reescrito como uma matriz triangular
superior na forma:
10
Esta notação matricial também pode ser usada da seguinte maneira:
.Agora, vamos supor que existe uma matriz composta apenas pela formula triangular
inferior, tal que
O processo de decomposição LU consiste justamente de em decompor a matriz
dos coeficientes em duas matrizes, onde a primeira está na forma triangular inferior
(Low), enquanto a outra está na forma triangula superior (Upper). Sendo assim, para
e , temos que
(Equação 3.4)
Agora, isolamos os termos dependentes de , temos que
(Equação 3.5)
E
(Equação 3.6)
desta forma, isolamos a dependência dos termos independentes da matriz dos
coeficientes . Desta forma, também livramos as operações efetuadas sobre (agora
) de serem feitas em , diminuindo a demanda de recursos para resolução deste
sistema [4].
4. A FATORAÇÃO DE CHOLESKY
A Fatoração de Cholesky expressa uma matriz simétrica como o produto,de
uma matriz triangular (chamada de Fator de Cholesky) pela sua transposta , na
11
forma:
(equação 4.1)
onde será triangular superior.
Sabendo-se que é simétrica quando seus elementos obedecem à uma formação
para toda linha e coluna . Desta forma, a matriz será idêntica à sua
transposta: . Matrizes com este tipo de formação fornecem algumas vantagens
computacionais, pois favorecem a eficiência na solução de sistemas lineares, quando
usados métodos adequados. Além disso, essa identidade permite a criação de algoritmos
simples de criptografia e verificação de dados [5].
Uma vez que se identifica que uma matriz é simétrica, podemos utilizar a
Equação (4.1) para gerar e a partir de . Ou seja, ao multiplicarmos e igualarmos
seus termos, obtemos as seguintes relações:
(Equação 4.2)
onde . Além disso, o elemento da diagonal será obtido por
(Equação 4.3)
As expressões acima são obtidas como uma especificação da decomposição LU para o
caso da matriz decomposta ser simétrica [5].
12
Exemplo de como resolver um sistema de Equações Algébricas Lineares utilizando o
Método de Eliminação de Gauss:
Questão:
29
17
265
07
3
1132
)(
4
)(
3
)(
2
2)(
1
2
)(
4
)(
3
)(
2
)(
1
)(
4
)(
3
2)(
2
)(
1
2
)(
4
)(
3
)(
2
)(
1
kkkk
kkkk
kkkk
kkkk
gggeg
gggg
ggeegg
ggegg
Escrever a matriz expandida para a etapa (L=0)
29
17
2165
07
3
1132
,
22
22
)0(
44
)0(
43
)0(
42
)0(
41
)0(
34
)0(
33
)0(
32
)0(
31
)0(
24
)0(
23
)0(
22
)0(
21
)0(
14
)0(
13
)0(
12
)0(
11
00
e
ee
e
aaaa
aaaa
aaaa
aaaa
bA
1º)Passo: Definições das multiplicadores e das linhas para a etapa (L=1)
1414,3
0,71185
1414,3
)0(
11
)0(
41)1(
41
)0(
11
)0(
31)1(
31
)0(
11
)0(
21)1(
21
a
am
a
am
a
am
0
1
)1(
41
)0(
4
)1(
4
)0(
1
)1(
31
)0(
3
)1(
3
)0(
1
)1(
21
)0(
2
)1(
2
)0(
1
)1(
1 ;;; LmLLLmLLLmLLLL
* )1(
2L
13
4188,103166,3*1414,30
*
8697,5)73,1(*1414,34286,0
*
8252,114142,1*1414,3)7171,2(
*
2526,11)7171,2(*1414,37171,2
*
)1(
2
)0(
1
)1(
21
)0(
2
)1(
2
)1(
24
)0(
14
)1(
21
)0(
24
)1(
24
2)1(
23
)0(
13
)1(
21
)0(
23
)1(
23
)1(
22
)0(
12
)1(
21
)0(
22
)1(
22
b
bmbb
a
amaa
a
amaa
a
amaa
* )1(
3L
7806,03607,21414,3
*
1813,02328,14142,1
*
0066,04142,1*0,71181
*
0,5155- (-2,7171)* 0,7118 - 2,4495
*
)1(
3
)0(
1
)1(
21
)0(
3
)1(
3
)1(
34
)0(
14
)1(
31
)0(
34
)1(
34
)1(
33
)0(
13
)1(
31
)0(
33
)1(
33
)1(
32
)0(
12
)1(
31
)0(
32
)1(
32
b
bmbb
a
amaa
a
amaa
a
amaa
* )1(
4L
14
0046,94188,104142,1
*
5457,5
*
0871,74426,46445,2
*
15,9181 (-2,7171)*3,1414 - 2,7171)(
*
)1(
4
)0(
1
)1(
21
)0(
4
)1(
4
)1(
44
)0(
14
)1(
31
)0(
44
)1(
44
)1(
43
)0(
13
)1(
31
)0(
43
)1(
43
2)1(
42
)0(
12
)1(
31
)0(
42
)1(
42
b
bmbb
a
amaa
a
amaa
a
amaa
0046,95457,50871,79180,150000,0
7806,01813,00066,05153,00000,0
4188,018697,58252,112526,110000,0
3166,37320,14142,17171,21414,3
, 11
bA
2º) Passo: Definições das multiplicadores e das linhas para a etapa (L=2)
4148,1
0458,0
)1(
22
)1(
42)1(
42
)1(
22
)1(
32)2(
32
a
am
a
am
1
2
)1(
42
)1(
4
)2(
4
)1(
2
)2(
32
)1(
3
)2(
3
)1(
2
)2(
2
)1(
1
2
1 ;;; LmLLLmLLLLLL
2567,1
*
0869,0
*
5350,0)8252,11)(0458,0(0066,0
*
)2(
3
)1(
2
)1(
32
)1(
3
)2(
3
)2(
34
)1(
24
)2(
32
)1(
34
)2(
34
)2(
33
)1(
23
)2(
32
)1(
33
)2(
33
b
bmbb
a
amaa
a
amaa
15
7430,23
*
6328,13
*
6408,9
*
)2(
4
)1(
2
)1(
42
)1(
4
)2(
4
)2(
44
)1(
24
)2(
42
)1(
44
)2(
44
)2(
43
)1(
23
)2(
42
)1(
43
)2(
43
b
bmbb
a
amaa
a
amaa
7450,236328,136432,90000,00000,0
2567,10869,05350,00000,00000,0
4188,018695,58252,112525,110000,0
3166,37320,14142,17171,21414,3
, 22
bA
3º) Passo: Definições dos multiplicadores e linhas para a etapa (L=3)
99,17)2(
33
)2(
43)3(
43 a
am
2
3
)3(
43
)2(
4
)3(
4
)2(
3
)3(
3
)2(
2
)3(
2
)0(
1
3
1 ;;; LmLLLLLLLL
1730,1
*
0721,12
*
)3(
4
)2(
3
)3(
43
)2(
4
)3(
4
)3(
44
)2(
34
)3(
43
)2(
44
)3(
44
b
bmbb
a
amaa
1730,10721,120000,00000,00000,0
2567,10869,05430,00000,00000,0
4188,018695,58252,112525,110000,0
3166,37320,14142,17171,21414,3
, 33
bA
Então o sistema triangular superior é :
1730,10721,12
2567,10869,05430,0
4188,108695,58252,112525,11
3166,37320,14142,17171,21414,3
)(
4
)(
4
)(
3
)(
4
)(
3
)(
2
)(
4
)(
3
)(
2
)(
1
k
kk
kkk
kkkk
g
gg
ggg
gggg
16
As equações iterativas para asvariáveis decisórias )(
1
kg )(
2
kg )(
3
kg )(
4
kg já com os
valores devidamente colocados são:
)(
4
)(
3
)(
2
)(
1
)1(
1 7320,14142,17171,23166,31414,3
1 kkkkk ggggg
)(
4
)(
3
)(
2
)1(
2 8695,58252,114188,102525,11
1 kkkk gggg
)(
4
)(
3
)1(
3 0869,02567,15430,0
1 kkk ggg
,0721,12
1730,1)(
4
)1(
4
kk gg
Para k=0, toma-se como referência o sinal (t).
5782,1
7320,14142,17171,23166,31414,3
1
)1(
1
)0(
4
)0(
3
)0(
2
)0(
1
)10(
1
g
ggggg
9234,0
8695,58252,114188,102525,11
1
)1(
2
)0(
4
)0(
3
)0(
2
)10(
2
g
gggg
2458,3
0869,02567,15430,0
1
)1(
3
)0(
4
)0(
3
)10(
3
g
ggg
4598,4
,0899,12
1730,1
)1(
4
)0(
4
)10(
4
g
gg
17
5. REFERÊNCIAS BIBLIOGRÁFICAS
[1] RUBÉN PANTA PAZOS. Aplicando a Matemática. Disponível em:
rpanta.com/downloads/material/Gauss_01.PDF. Acesso em: 13 Out 2010.
[2] WIKIPÉDIA. A Enciclopédia Livre. Disponível em:
http://pt.wikibooks.org/wiki/%C3%81lgebra_linear/Sistemas_de_equa%C3%A7%C3%
B5es_lineares . Acesso em: 13 Out 2010.
[3] SAWP. Software Advice Working Party. Disponível em:
http://www.sawp.com.br/blog/?p=577. Acesso em: 14 Out 2010.
[4] SAWP. Software Advice Working Party. Disponível em:
http://www.sawp.com.br/blog/?p=586. Acesso em: 14 Out 2010.
[5] SAWP. Software Advice Working Party. Disponível em:
http://www.sawp.com.br/blog/?p=604. Acesso em: 14 Out 2010.
