ESTUDO E ANÁLISE DE MÉTODOS ITERATIVOS PARA SOLUÇÃO DE SISTEMAS LINEARES GRANDES E ESPARSOS

ANHANGUERA EDUCACIONAL S.A.

Faculdade Anhanguera de Anápolis

Curso de Ciência da Computação

Brenner Rangel Cardoso Santos

Irlando da Silva Campos

Jonathan Soares Martins Rodrigues

Lucas Constante

ESTUDO E ANÁLISE DE MÉTODOS ITERATIVOS PARA SOLUÇÃO DE SISTEMAS LINEARES GRANDES E ESPARSOS

Anápolis

2014

Brenner Rangel Cardoso Santos

Irlando da Silva Campos

Jonathan Soares Martins Rodrigues

Lucas Constante

ESTUDO E ANÁLISE DE MÉTODOS ITERATIVOS PARA SOLUÇÃO DE SISTEMAS LINEARES GRANDES E ESPARSOS

Monografia apresentada como exigência parcial para a obtenção do grau de Bacharel em Ciência da Computação, na Faculdade Anhanguera de Anápolis, sob a orientação do Prof. Me. Lauro Cássio Martins de Paula.

Anápolis

2014

Brenner Rangel Cardoso Santos

Irlando Da Silva Campos

Jonathan Soares Martins Rodrigues

Lucas Constante

ESTUDO E ANÁLISE DE MÉTODOS ITERATIVOS PARA SOLUÇÃO DE SISTEMAS LIENARES GRANDES E ESPARSOS

Trabalho de Conclusão de Curso apresentado como exigência parcial para a obtenção do grau de Bacharel em Ciência da Computação da Faculdade Anhanguera de Anápolis.

Apresentado em 27 de Novembro de 2014.

________________________________

Prof. Me. Lauro Cássio Martins de Paula

Faculdade Anhanguera de Anápolis

Orientador

________________________________

Prof. Esp. Eder de Paula Bento

Faculdade Anhanguera de Anápolis

Avaliador

________________________________

Prof. Esp. Roberto Dib Bittar

Faculdade Anhanguera de Anápolis

Avaliador

Anápolis

2014

Este trabalho é dedicado em primeiro lugar а Deus, que iluminou о nosso caminho durante esta caminhada.

AGRADECIMENTOS

Ao Professor Me. Lauro Cássio Martins de Paula, orientador acadêmico, pela paciência, disponibilidade, apoio e confiança depositada.

“O sucesso nasce do querer, da determinação e persistência em se chegar a um objetivo. Mesmo não atingindo o alvo, quem busca e vence obstáculos, no mínimo, fará coisas admiráveis."

José de Alencar

RESUMO

Apresenta-se neste trabalho um estudo e análise de métodos iterativos para solução de sistemas lineares grandes e esparsos. Um sistema linear é um conjunto finito de equações lineares aplicadas em um mesmo conjunto finito de variáveis. O mesmo ocorre com frequência em diversos processos de otimização. Por exemplo, sistemas lineares são comumente aplicados na computação gráfica durante o processo de geração de imagem digital. Para solucionar tais sistemas, métodos iterativos de solução são mais indicados, pois tendem a diminuir o número de operações, o que é bastante útil quando se trata de um sistema com um grande número de equações. Nesse contexto, o objetivo deste trabalho é comparar os resultados e a velocidade de solução entre os seguintes métodos iterativos: Jacobi, Gauss-Seidel, Gradientes Bi-conjugados Estabilizados (BiCGStab) e Gradientes Bi-conjugados Estabilizados Híbrido (BiCGStab(2)). Para isso, será utilizado um software chamado SisLLLin, proposto por Paula et al. (2013), que utiliza os quatro métodos para solucionar sistemas lineares. Os resultados esperados para este trabalho consistirá na comparação dos métodos utilizados na solução dos sistemas tratados, destacando aquele que apresenta um melhor desempenho.

Palavras-chave: Sistemas lineares. Jacobi. Gauss-Seidel. BiCGStab. BiCGStab(2).

ABSTRACT

This paper presents a study and analysis of iterative methods for solving large and sparse linear systems. A linear system is a finite set of linear equations applied to the same finite set of variables. It happens with frequency in several optimization processes. For example, linear systems are commonly applied in computer graphics during the process of digital imaging. To solve these systems, iterative solution methods are more suitable because they tend to decrease the number of operations, which is quite useful when it comes to a system with a large number of equations. In this context, the goal of this work is to compare the results and the speed of solution from the following iterative methods: Jacobi, Gauss-Seidel, Bi-conjugate Gradient Stabilized (BiCGStab) and Hybrid Bi-conjugate Gradient Stabilized (BiCGStab (2)). For this, a software called SisLLLin proposed by Paula et al. (2013), will be used which uses four methods for solving linear systems. The expected results for this work will consist in the comparison of the methods which are used in the solution of treated systems, highlighting the one that has a better performance.

Keywords: Linear Systems. Jacobi. Gauss-Seidel. BiCGStab. BiCGStab(2).

LISTA DE FIGURAS

Figura 1 – Tela inicial do software SisLLLin . 20

LISTA DE ALGORITMOS

1 – Método Iterativo de Jacobi 15

2 – Método Iterativo de Gauss-Seidel 16

3 – Método dos Gradientes

...