Métodos iterativos
O tempo tá escasso? A grana tá curta? Vai de método iterativo
Vamos lá?
Já vimos dois métodos para resolver sistemas lineares, o método de eliminação de Gauss e a decomposição LU, com ou sem pivoteamento parcial. Em outra aula descobrimos o custo computacional destes métodos. E se este custo for caro demais?
- 1
- 2
Se apenas 50% das operações de ponto flutuante necessárias para concluir o processo de eliminação de Gauss foram executadas, podemos afirmar que...
Os métodos para resolução de sistemas lineares dividem-se em duas categorias, os diretos e os iterativos. Os métodos diretos são aqueles que, após uma quantidade finita e conhecida de passos, fornecem a solução exata do sistema linear, a menos de erros de cálculo em precisão finita. Nesta classe de métodos temos a eliminação gaussiana e a resolução através da decomposição LU, com e sem pivoteamento. Já os métodos iterativos, constroem um sequência de aproximações para solução do sistema linear, na esperança de que esta sequência convirja para solução.
Os métodos diretos só produzem um resultado uma vez que todos os seus passos tenham sido completados. Caso o método tenha sua execução interrompida antes da conclusão, nenhuma aproximação válida estará disponível. Já os métodos iterativos, quando convergem, gradativamente melhoram a qualidade de uma aproximação inicial. Sendo assim, quanto mais tempo puderem ser executados, melhor será a aproximação conseguida, respeitando-se os limites da aritmética em ponto flutuante.
Em situações onde há escassez de recursos para a execução completa de um método direto, a alternativa é utilizar um método iterativo. Vejamos um exemplo. Já vimos que a eliminação de Gauss precisa da ordem de
Mas nem tudo se restringe a tempo de execução. A limitação pode estar em memória disponível. Na maioria das aplicações, as matrizes que surgem em problemas de grande porte são esparsas, ou seja, apenas uma pequena fração de seus elementos é não nula. Por exemplo, em problemas de propagação de calor em um superfícies planas, o sistema linear que surge da discretização da equação do calor tem apenas 4 elementos não nulos por linha da matriz, que no total pode ter muitos milhares de linhas. A matriz esparsa é usualmente armazenada de forma bem eficiente, consumindo espaço apenas para os elementos não nulos e alguns índices para identificá-los. Entretanto, ao aplicar a decomposição LU ou o processo de eliminação de Gauss, a manipulação das linhas da matriz acaba por destruir o padrão de esparcidade, tornando a matriz densa, o que demandaria muita memória para armazenamento. Em métodos iterativos não há manipulação dos elementos da matriz, portanto a estrutura de esparcidade é preservada.
Na próxima aula construiremos um método iterativo simples e veremos como utilizá-lo de forma intuitiva.
1. Considere uma matriz
2. Considere um computador cuja processador é de 3.0GHz. Isto significa que o número máximo teórico de operações de ponto flutuante capaz de serem executados em 1 segundo é