Solução de matrizem com algoritmos numéricos

Primeiro Trabalho de Algoritmos Num´ricos: Sistemas Lineares e
Cinthia Meireles Aguiar Bruno Guimar˜es Carneiro a

1

Introdu¸˜o ca

O objetivo deste trabalho ´ a implementa¸˜o e a an´lize de algoritmos para a resolu¸˜o de sistemas lineares. e ca a ca Foram implementados dois algoritmos: decomposi¸˜o LU e SOR. Al´m disso, foram implementados dois tipos ca e de armazenamento: denso e CSR.

2
2.1

M´todos Diretos e M´todos Iterativos e e
M´todos Diretos e

O m´todo direto utilizado foi a Decomposi¸˜o LU. A vantagem desse m´todo ´ ter como sa´ o resultado exato e ca e e ıda do vetor solu¸˜o x, a menos por poss´ ca ıveis erros de arredondamento. Por outro lado, este m´todo ´ lento, sendo e e desaconselh´vel para uso em matrizes com grande n´mero de entradas n˜o nulas. a u a

2.2

M´todos Iterativos e

Foi implementado o algoritmo SOR como m´todo iterativo. Este algoritmo tem como sa´ o vetor x com valores e ıda aproximados, dentro de uma margem de erro pr´-determinadae seguindo um n´mero m´ximo de itera¸˜es. e u a co Eventualmente, pode ocorrer de n˜o ser poss´ deixar os valores dentro da margem de erro desejada com o a ıvel n´mero de itera¸˜es permitido. Este m´todo ´ mais r´pido do que o m´todo Decomposi¸˜o LU. u co e e a e ca

3

Armazenamentos Otimizados

Neste trabalho, foi implemetada uma forma de armazenamento otimizado de matrizes chamada CSR. Neste tipo de armazenamento, apenas as entradas n˜o-nulas s˜o guardadas, o que torna o armazenamento de matrizes a a esparsas muito mais r´pido e diminui consideravelmente o consumo de mem´ria. a o Este armazenamento ´ implementado da seguinte forma: cria-se um vetor, onde s˜o armazenados os valores e a n˜o nulos da matriz, seguindo a ordem linha-coluna. Cria-se tamb´m mais dois vetores, sendo um para o a e armazenamento da coluna respectiva a cada elemento armazenado, e outro que armazena a posi¸˜o do vetor em ca que come¸a uma nova linha, e tamb´m a posi¸˜o em que acaba a ultima linha. Dessa