Métodos iterativos

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 ${2\over 3}n^3$ para resolver um sistema linear quadrado de ordem $n.$ Digamos que $n=30.000,$ então serão necessárias 18.000 bilhões de operações para a resolver o sistema. Um laptop com processador de 3.0GHz, capaz de realizar quatro operações de ponto flutuante por ciclo de máquina, realiza 12 bilhões de operações por segundo. Logo, seria necessários pelo menos 25 minutos de execução dedicada para resolver o sistema linear. Caso seu laptop tenha bateria para apenas 20 minutos, não será possível resolver o sistema. Entretanto, cada passo de um método iterativo é bem rápido. Nos métodos que veremos a seguir, um passo custa da ordem de $n^2$ operações, 90 bilhões, no nosso exemplo. Logo, dentro dos 20 minutos disponíveis, seria possível realizar 160 passos, ou seja, construir 160 aproximações gradativamente melhores para a solução do sistema linear. Com sorte, talvez isso seja o suficiente para o problema em questão.

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 $A,$ de ordem $n$, cujos elementos da primeira linha, primeira coluna e diagonal principal são todos iguais a $1,$ exceto por $a_{11}=n.$ Todos os demais elementos são nulos. Por exemplo, para $n=5,$ a matriz $A$ seria $$ \begin{bmatrix} 5 & 1 & 1 & 1 & 1\\ 1 & 1 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 0 & 0 & 1 \end{bmatrix}. $$ Compute quantos elementos de $A$ são não nulos, em função da dimensão $n.$ Quantos seriam os elementos não nulos nos fatores $L$ e $U$ da $A$? Em um computador com 4Gb de memória RAM, qual a maior matriz $A$ que pode ser armazenada? Qual a maior ordem $n$ para a qual ainda é possível armazenar os fatores $L$ e $U$? Para as duas perguntas anteriores considere apenas os elementos não nulos e saiba que cada número de ponto flutuante em precisão dupla ocupa 8 bytes.

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 é $3.0 \cdot 4\cdot 10^9.$ Em 5 minutos, qual o maior sistema linear que o método de eliminação de Gauss é capaz de resolver? Quanta memória é necessária para armazenar uma matriz dessa ordem?