Um estudo sobre eficiência de métodos numéricos para soluções de sistemas lineares

Resumo

 Resolver sistemas lineares de equações é uma etapa na resolução de problemas científicos tais como os de difusão de calor, elasticidade e mecânica de fluidos. Assim, é importante conhecer alguns métodos de resolução e suas particularidades. Neste trabalho realiza-se uma comparação entre alguns métodos de resolução de sistemas lineares através de análise experimental, onde buscamos a máxima eficiência. Os métodos numéricos para solução de sistemas lineares é dividido basicamente em duas classes: métodos diretos e métodos iterativos. Os métodos diretos fornecem a solução exata, a menos de erros de arredondamento, após um número finito de operações. Já os iterativos fornecem uma sequência de aproximações da solução, cada uma obtida da anterior pela repetição do mesmo processo. Em outro trabalho, [5], estudamos métodos diretos básicos como o LU parcial e um método de alto desempenho, a transformada rápida de Fourier (FFT). Estes métodos serão comparados com alguns iterativos. A abordagem computacional será usada para implementar e compreender os algoritmos usados na resolução. Inicialmente estudamos os métodos iterativos clássicos: Jacobi e Gauss-Seidel. Estes métodos resolvem o sistema linear Ax  b através de uma decomposição da matriz A. Os métodos são parecidos, e foi possível ver que o método de Gauss-Seidel é mais eficiente do que o método de Jacobi pois utiliza melhor as informações obtidas a cada iteração na resolução do sistema linear. Numa comparação destes com os métodos LU parcial e FFT, notamos que os métodos diretos apresentam melhor desempenho. Em seguida estudamos métodos de projeção: método de máxima descida e método do gradiente conjugado, [1] e [3]. Um processo de projeção é uma maneira canônica de obter uma aproximação para a solução do sistema em um subespaço especıfico. A solução aproximada x de Ax  b é obtida como o ponto de mínimo de um funcional quadrático associado à matriz A positiva definida. O gradiente conjugado é uma variação do método de máxima descida que utiliza melhor as informações nas iterações. O modelo usado foi a equação de Laplace com condição de Dirichet na fronteira, discretizada por elementos finitos com funções lineares por elementos e contınuas em todo domínio. O domínio, D1 [0, 1] em dimensão um e D2  [0, 1]  [0, 1] em dimensão dois, foi dividido formando uma malha uniforme. O gradiente conjugado apresentou-se mais eficiente do que o método de máxima descida. Ambos foram melhor do que o LU parcial, porém não superaram a FFT. Mas a FFT só funciona em malhas estruturadas, [4]. Já o método do gradiente conjugado pode ser usado em malhas mais flexíveis. O método do gradiente conjugado converge conforme a condição da matriz do sistema. Quanto mais próxima de um a condição Cond(A) estiver, melhor a convergência. Estudamos então o método do gradiente conjugado precondicionado, onde ao invés de resolver Ax  b resolvemos M1Ax M1b, onde M é simétrica positiva definida. E o número de condição Cond(M1A) é mais próximo de um do que o número de condição Cond(A). Note que o cálculo de M1 não deve ser muito custoso, [2]. Passamos a estudar precondicionadores de decomposição de domínios. A ideia é decompor o domínio da equação diferencial em subdomínios e a solução nos subdomínios ser utilizada para obter a solução no domínio original. Considere a partição do domínio D  [a, b] em subdomínios disjuntos [...]