Embed Size (px)
Citation preview
ESTUDO DO MÉTODO DE SOBRE RELAXAÇÃO SUCESSIVA NA
RESOLUÇÃO DE SISTEMAS DE EQUAÇÕES LINEARES
Anderson Reis da Silva [email protected]
Matheus da Silva Menezes [email protected]
Érico Vinicius de Castro Alves [email protected]
Universidade Federal Rural do Semi-Árido - UFERSA
59015-000, Campus Angicos, RN
www.ufersa.edu.br
Palavras-chave: Métodos, Iterativos, Sistemas de equações lineares, Sobrerelaxação, Algoritmo
Resumo: A resolução de sistemas de equações lineares é de suma importância em diversas áreas de
estudos. Existe hoje um grande número de métodos numéricos, que possuem a finalidade de resolver
problemas que envolvam sistemas de equações lineares. Nesse trabalho é estudado um método
iterativo denominado de Método de Sobre Relaxação Sucessiva. É testada sua eficiência em problemas
de médio e grande porte, comparando-o com outros métodos iterativos já consagrados como os
métodos de Jacobi e Gauss-Seidel. Constatou-se que de acordo com a escolha adequada do parâmetro
de controle, o Método de Sobre Relaxação Sucessiva obtém um desempenho superior aos demais
métodos nos problemas considerados.
1. Introdução
Os sistemas de equações lineares são encontrados em várias áreas de estudos, como por exemplo,
engenharia, matemática, computação, administração, economia e outras [1]. É possível deparar com
problemas envolvendo sistemas lineares de grande porte em diversos processos dessas áreas, como
exemplo, na análise estrutural de uma aeronave [6]. A resolução de um sistema de equação linear
envolvidos nestes processos necessita de auxilio de métodos numéricos. Os métodos numéricos são
divididos em métodos diretos e iterativos [3]. Levando em consideração o estudo de sistemas lineares
de grande porte os métodos iterativos se sobressaem em relação aos métodos diretos [3]. O método de
sobre relação sucessiva é um método iterativo que se encaixa nesse padrão.
2. Métodos Iterativos de Jacobi Gauss-Seidel
Os métodos de Jacobi e Gauss-Seidel são classificados como métodos iterativos estacionários pelo
fato de possuírem uma matriz de iteração fixa durante todo o processo. Como todos os métodos
iterativos, esses métodos partem de uma solução inicial , e tendem a convergir para uma solução
aproximada do sistema em um número de iterações [2].
Para a utilização dos métodos iterativos de Jacobi e Gauss-Seidel é utilizado como condição de
convergência, o chamado critério das linhas e/ou colunas [5]. Assim como atribuído critério de parada
em relação ao número de iteração e distância relativa [1,2,3].
As equações de atualização de variáveis destes métodos é vista no quadro 1 a seguir:
Quadro 1 – Equações de iterações dos métodos de Jacobi e Gauss-Seidel
Método de Jacobi Método de Gauss-Seidel
ij
ii
k
jjii
k
i axabx ,
)1(
,
)( /)(
ij ij
ii
k
jji
k
jjii
k
i axaxabx ,
)1(
,
)(
,
)( /)(
Analisando o quadro 1, é possível notar que o método de Gauss-Seidel executa uma atualização
dos dados na própria iteração, já o método de Jacobi só realiza a atualização dos dados na iteração
seguinte. Essa é a principal diferença entre os dois métodos iterativos [3]. A implementação destes
métodos se deu de acordo com [7] e [8].
508
3. Método de Sobre Relaxação Sucessiva - SRS
Este método é classificado como um método iterativo estacionário [2], que é derivado do método
de Gauss-Seidel [6]. O método consiste na multiplicação da equação de iteração por um fator de
correção denominado . A equação de iteração do método é mostrada no quadro 2:
Quadro 2 – Equação de Iteração do SRS
Método de SRS
O método SRS é controlado pelo fator , sendo atribuído valor para no intervalo de zero a dois.
Quando o valor de for menor que um, o método é classificado como sub relaxação, se o valor de
for um, o método é determinado de Gauss-Seidel, e se o valor de for maior que um, o método é
denominado de sobre relaxação [1].
Visando analisar o funcionamento do método SRS em relação ao método de Jacobi e Gauss-Seidel,
foi implementado algoritmo para cada método iterativo, usando o software SCILAB em um
computador com processador Intel core i5 e 4GB de memória RAM. Em seguida foi coletado no
banco de dados do Matrix Market, disponível em [4], seis problemas com características distintas para
a realização dos testes, detalhados no quadro 3 a seguir:
Quadro 3 – Características dos problemas utilizados nos testes
Nome Tamanho Diagonal
Dominante Tipo da Matriz Esparso
BCSSTRUC1 48x48 Não Real, simétrica e positiva definida Não
pde225 225x225 Não Real e assimétrico Sim
MCFE 765x765 Não Real e Assimétrico Sim
GR3030 900x900 Sim Real, simétrico, positiva def. Sim
SHERMAN1 1000x1000 Não Real e simétrica Sim
SHERMAN4 1104x1104 Sim Real e simétrica Sim
Foram selecionados problemas com características distintas com o intuito de testar a eficiência do
método em diferentes problemas. É importante destacar que alguns problemas se enquadram nas
condições de convergência do método SRS e alguns não se enquadram.
Em relação ao método SRS foram utilizados dez valores de listados no quadro 4:
Quadro 4 – Valores de utilizados nos testes
1.05 1.15 1.25 1.35 1.45 1.55 1.65 1.75 1.85 1.95
Para a realização do teste foi utilizado um número de iteração máxima de 5000, e uma precisão
para problemas com um número de equação inferior a 1000, e para problemas
com o número de equação superior ou igual a 1000. O critério que será analisado nos resultados será o
número de iterações obtidas em cada método. Com a realização dos testes foram obtidos os resultados listados na Tabela 1, considerando apenas
o melhor valor de .
Tabela1 – Resultados Obtidos
Algoritmo # iterações
BCSSTRUC1 pde225 MCFE GR3030 SHERMAN1 SHERMAN4
Jacobi NÃO
CONVERGIU 623 217 792 NÃO
CONVERGIU 1780
Gauss-Seidel 1866 327 207 445 3229 1058
SRS 182 NÃO
CONVERGIU
NÃO
CONVERGIU
72 181 126 1.95 1.85 1.95 1.85
509
Os resultados mostram que em quatro dos seis problemas analisados o método SRS convergiu com
um número menor de iterações. Em dois problemas o método não obteve a convergência, pelo fato dos
problemas pde225 e MCFE não satisfazerem a condição de convergência do método, que necessita de
ser formado por uma matriz definida positiva. Nos problemas SHERMAN1 e SHERMAN4 a condição
de convergência não foi atendida, mas mesmo assim o método obteve convergência.
Nos problemas em que o método SRS obteve um melhor desempenho, o número de iterações é
bem inferior aos demais métodos, chegando a utilizar em alguns casos apenas 5,6% do número de
iterações dos demais métodos. Quanto ao tempo de execução os resultados podem ser visualizados
pelo Gráfico 1, a seguir:
Gráfico 1 - Gráfico dos problemas em função do tempo de execução em segundos
Em relação ao fator de correção nos quatro problemas em que o método SRS obteve convergência,
o melhor valor do fator foi localizado próximo de dois. Em nenhum caso o melhor foi encontrado
próximo de um. Os resultados obtidos para o método SRS em relação aos demais métodos analisados
foram satisfatórios, levando em consideração a utilização do melhor fator de correção. A única
inconveniência da utilização do método SRS é a determinação do melhor valor para o fator de
correção .
Referências
[1] BURDEN, Richard L; FAIRES, Douglas. Análise Numérica. São Paulo: Cengage, 2008.
[2] CAMPOS, Filho; FERREIRA, Frederico. Algoritmos Numéricos. 2. ed. Rio de Janeiro: Ltc, 2010.
[3] FRANCO, Neide Bertold. Cálculo Numérico. São Paulo: Prentice Hall, 2006.
[4] MATRIX MARKET - Um repositório visual de dados de teste para uso em estudos comparativos
de algoritmos para álgebra linear numérica, disponível em http://math.nist.gov/MatrixMarket/,
acesso em 05/01/2013, 15h.
[5] RUGGIERO, Márcia A. Gomes; LOPES, Vera Lúcia da Rocha. Cálculo Numérico: Aspectos
Teóricos e Computacionais. 2. ed. São Paulo: Makron Books, 1996.
[6] SPERANDIO, Délcio. Cálculo Numérico: Características matemáticas e computacionais dos
métodos numéricos. São Paulo: Pearson Pretice Hall, 2003.
[7] NETLIB, método iterativo de Gauss Jacobi, disponível Em
http://netlib.org/linalg/html_templates/node12.html, acesso em 15/01/2012, 16h
[8] NETLIB, método iterativo de Gauss Seidel, disponível em
http://netlib.org/linalg/html_templates/node14.html, acesso em 15/01/2012, 17h
BCSSTRUC1 GR3030 SHERMAN1 SHERMAN4
JACOBI 173,067 10119,881 76528,376 35310,688
GAUSS-SEIDEL 75,707 6632,399 53223,876 23938,813
SRS 7,472 1093,484 3370,495 3215,166
0
10000
20000
30000
40000
50000
60000
70000
80000
90000
TEM
PO
DE
CO
NV
ERG
ÊNC
IA (
s)
510
