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

...

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 Bi-conjugados Estabilizados (BiCGStab) 18

4 – Método dos Gradientes Bi-conjugados Estabilizados Híbrido (BiCGStab(2)) 19

LISTA DE SIGLAS

BiCGStab Método dos Gradientes Biconjugados Estabilizados

BiCGStab(2) Método dos Gradientes Biconjugados Estabilizados Híbridos

SisLLLin Método para Solução de Sistemas Lineares

SUMÁRIO

AGRADECIMENTOS iv

RESUMO vi

ABSTRACT vii

LISTA DE FIGURAS viii

LISTA DE ALGORITMOS ix

LISTA DE SIGLAS x

Capítulo 1 - Introdução 12

Capítulo 2 - Métodos Iterativos 14

2.1 Jacobi 14

2.2 Gauss-Seidel 15

2.3 BiCGStab 17

2.4 BiCGStab(2) ..................................................................................18

Capítulo 3 – Resultados Esperados 20

Capítulo 4 – Considerações Finais 21

Referências 22

Introdução

Um sistema linear é definido por um conjunto finito de equações lineares aplicadas em um mesmo conjunto, igualmente finito, de variáveis. Ferreira (2007) afirma que os sistemas lineares são bastante utilizados em problemas de equações diferenciais parciais, otimização e regressões. Segundo Burden e Faires (2008), os sistemas de equações lineares estão associados a muitos problemas no campo da engenharia e da ciência, bem como com aplicações da matemática às ciências sociais e aos estudos quantitativos nos problemas relacionados à administração e economia.

Um método iterativo é um procedimento que gera uma sequencia de soluções aproximadas que vão melhorando conforme iterações são executadas, e resolvem uma classe de problemas estabelecida.

Para solucionar tais sistemas, métodos iterativos de solução são mais indicados do que métodos exatos por usarem menos memória e reduzirem erros de arredondamento do computador (FRANCO, 2006).Para sistemas grandes e esparsos, essas técnicas são eficientes em termos tanto de armazenamento no computador quanto de cálculos (BURDEN; FAIRES, 2008). Na prática, um sistema linear pode auxiliar em aspectos como, por exemplo, comparar custos e valores, aferir juros e relacionar preços (ARAÚJO, 2009). Sistemas lineares também são comumente aplicados na computação gráfica. Por exemplo, em operações com combinações de cores (LOPES, 2013).

Devido ao progresso da computação, mediante uma sequência de passos lógicos, torna-se possível a adequação de tais métodos para uma linguagem que possa ser captada pelos computadores, sendo representada por meio de algoritmos. De acordo com Campos (2007), no processo de adequação, em vez de implementar um método diretamente em uma linguagem de programação, é preferível descrevê-lo por meio de uma notação algorítmica. Com isso, torna-se possível abstrair os detalhes da linguagem de programação do computador e concentrar apenas nos aspectos matemáticos, além de facilitar a sua implementação em qualquer linguagem de programação. Após isso, deve ser feita uma codificação do programa, que consiste na implementação matemática na linguagem de programação escolhida (CAMPOS, 2007). Tendo em vista o custo computacional, alguns métodos iterativos são considerados ótimos (Diene; Bhaya, 2007). Entretanto, dependendo do tamanho do sistema que a ser solucionado, o desempenho computacional pode ser afetado (PAULA et al, 2013). Há casos em que o processamento computacional pode durar vários dias. Nesse contexto, levando tais fatos em consideração, torna-se necessário a implementação e utilização de métodos iterativos eficientes para solucionar sistemas lineares em um tempo não proibitivo (PAULA, 2013). Portanto, o objetivo deste trabalho consiste em fornecer uma análise e um estudo de quatro métodos iterativos utilizados para solução de sistemas lineares grandes e esparsos: Jacobi (JUDICE et al., 1996), Gauss-Seidel (CLAUDIO; MARINS, 1989), Gradientes Bi-conjugados Estabilizados (BiCGStab) (VORST, 1992) e Gradientes Bi-conjugados Estabilizados Híbrido (BiCGStab(2)) (VORST;

...