Trabalho Sistemas Lineares Algoritmos Numéricos

Guilherme Artém dos Santos

José Mauro Nazareth Cardoso Neto

1º Trabalho de Algoritmos Numéricos

Sistemas Lineares

Vitória

27 de Janeiro de 2013

1º Trabalho de Algoritmos Numéricos

Sistemas Lineares

Guilherme Artém dos Santos

José Mauro Nazareth Cardoso Neto

Trabalho referente à disciplina de Algoritmos Numéricos do quinto período do curso de Graduação em Engenharia de Computação da Universidade Federal do Espírito Santo ministrado pela Professora Lucia Catabriga.

Vitória

27 de Janeiro de 2013

Sumário

1. Introdução

        O cálculo Numérico é a disciplina que aborda o conjunto de métodos utilizados para resolver problemas matemáticos utilizando-se de um ou mais computadores, a solução do problema por estes métodos é sempre numérica e possuí um erro associado ao resultado exato, embora muitas vezes este erro possa ser calculado e mantido sob certo grau de exatidão, uma das vantagens destes métodos é que seu resultado pode ser obtido mesmo quando o problema não possui uma solução analítica.

        Um sistema de equações lineares é definido como um conjunto finito de equações lineares contendo um conjunto finito de variáveis e soluções. Abstraindo-se o polinômio da equação pode-se obter uma matriz e esta pode ser resolvida por métodos diretos como um sistema linear.

        Problemas reais muitas vezes são trabalhosos (possuem muitas variáveis e equações) ou não possuem soluções analíticas de modo que é interessante obter-se as respostas dos mesmos utilizando-se de soluções numéricas, seja ele um problema de engenharia, mecânica dos fluídos, estatística, cálculo, economia ou outras áreas interessadas.

        Neste trabalho serão estudados dois métodos numéricos que utilizam-se de um sistema de equações lineares, o método direto da Decomposição LU e o método iterativo da Sobre-Relaxação Relativa(SOR, do inglês Succesive Over Relaxation) junto com dois formatos de armazenamento de matrizes esparsas, o formato denso e o formato CSR (Compressed Sparse Row), dos quais irão ser programados códigos para resolução do método SOR pelos dois formatos de armazenamento e a resolução do método da Decomposição LU para o armazenamento denso, o código será escrito e compilado utilizando a linguagem C e o sistema operacional GNU/Linux com a distribuição Ubuntu 12.04.

2. Métodos Diretos e Métodos Iterativos

2.1 Métodos Diretos

        Os métodos diretos são aqueles pelos quais se obtém o sistema de soluções através de um número finito de operações. A principal vantagem dos mesmos é que eles não possuem erros fora os de arredondamento eu suas soluções obtidas. A pivoteação é uma prática comum nos métodos diretos e protege os mesmos de alguns erros que podem acontecer caso um dos pivôs originais seja nulo, além de evitar o aumento dos erros de arredondamento por ter multiplicadores muito maiores do que um.

        O método direto a ser utilizado neste trabalho será o método da Decomposição LU, que consiste em realizar inicialmente a decomposição da matriz densa para uma matriz superior, a vantagem deste método é que após obter-se a matriz superior pode-se resolvê-la mais facilmente para vários conjuntos de termos independentes de modo a diminuir a complexidade do algoritmo a ser resolvido nestes casos. A principal desvantagem deste método é que a complexidade do algoritmo é da ordem de n³ para a resolução inicial fora a complexidade para encontrar o vetor de variáveis livres após a mesma.

2.2 Métodos Iterativos

        Os métodos iterativos requerem um número infinito de operações para alcançar a solução, porém a vantagem do mesmo é que não há a necessidade para alcançar a solução exata e sim uma solução aproximada com uma tolerância pré-definida a ser utilizada como critério de parada das iterações do mesmo. A grande vantagem do método iterativo é que a complexidade é de n², para cada iteração.

        Basicamente os métodos iterativos utilizam-se de uma sequência de operações com o vetor de solução de modo que a cada iteração este vetor se aproxima mais do vetor resposta, uma das desvantagens do mesmo é que as operações em alguns casos não convergem, em outros casos há uma necessidade muito grande de iterações de modo que mesmo com a complexidade maior esta não é mais barata computacionalmente do que um método direto.

        Neste trabalho utilizou-se o método iterativo da sobre-relaxação relativa, que tem como principal vantagem em relação aos outros métodos iterativos a existência de um parâmetro ômega. Este parâmetro é responsável por uma possível otimização dos métodos ao diminuir o número de iterações para a convergência.

3. Armazenamentos Otimizados

        O método mais simples e fácil de ser entendido para o armazenamento de uma matriz é o que chama-se de armazenamento denso, onde todos os valores da matriz são armazenados na memória RAM do computador antes que trabalhe-se com os elementos da mesma. É compreensível, porém, abordar outros métodos de armazenamento por motivos de economia de espaço utilizado ou otimização do código. Neste trabalho as matrizes abordadas como base de testes são denominadas matrizes esparsas, sua principal característica é possuírem uma grande quantidade de elementos nulos que não interferem na resolução dos sistemas lineares e consequentemente não precisam ser armazenados, representando um mal aproveitamento da memória do computador, que pode em alguns casos estourar e não ser o suficiente para resolver o problema, bem como também em uma gama de operações que serão resolvidas pelo processador a fim de resolver o sistema linear que resultarão em outros elementos nulos, ou seja, um gasto desnecessário de poder computacional.

...