___ Métodos Iterativos ____
para Sistemas Lineares

Neste parágrafo, o objectivo é encontrar métodos que permitam aproximar a solução de um sistema linear, por forma a diminuir o número de operações (relativamente aos métodos directos), o que pode ser útil no caso de se tratar de um sistema com um grande número de equações, especialmente se a matriz possuir muitos elementos nulos.

Outra vantagem dos métodos iterativos é evitar os problemas de instabilidade numérica, que podem ocorrer num método directo.

Consideremos então um sistema genérico

A x = b

vamos escrever A = M + N

e obtemos (M+N) x = b < = > x = M-1b - M-1N x

Daqui podemos retirar um método iterativo que consiste em:

Escolher um vector inicial x(0)
Iterar x(k+1) = M-1b - M-1 N x(k)

É importante que a matriz M seja mais muito mais simples do que A, porque senão não estariamos a simplificar o problema...

Note-se que esta iteração pode ser feita de outra forma, não havendo necessidade de se proceder verdadeiramente ao cálculo da inversa de M.

  • De entre os métodos iterativos, destacam-se dois métodos, o método de Jacobi, e o método de Gauss-Seidel.

    Consideramos a matriz A decomposta na soma de três matrizes A = L + D +U, onde L é a matriz triangular inferior, U a matriz triangular superior, ambas com zeros na diagonal principal e D a matriz diagonal.

    Notamos que a matriz diagonal D não poderá ter zeros na diagonal principal. Caso isso aconteça, deve-se efectuar uma troca de linhas ou colunas na matriz A, para obtermos uma matriz D adequada.

    Método de Jacobi

    No caso do método de Jacobi, consideramos
    M = D
    N = L+ U
    Portanto o método consiste em

    Iterada inicial x(0)
    Iterar x(k+1) = D-1b - D-1 (L + U) x(k)
    ou ainda

    Método de Gauss-Seidel

    No caso do método de Gauss-Seidel, consideramos
    M = L + D
    N = U
    Portanto o método consiste em

    Iterada inicial x(0)
    Iterar x(k+1) = D-1b - D-1 L x(k+1) - D-1 U x(k)
    ou ainda

    Critérios de convergência

    Vamos agora estabelecer critérios que nos permitam determinar quando existe convergência para estes métodos iterativos.
    Começamos por reparar que
    x(k+1) = M-1 b - M-1N x(k)
    x = M-1 b - M-1N x
    de onde retiramos
    e(k+1) = x - x(k+1) = - M-1 N ( x - x(k)) = C e(k)
    designando C = - M-1N .

    Aplicando sucessivamente, obtemos
    e(k) = Ck e(0)

    ou seja, o erro convergirá para o vector nulo (para uma qualquer iterada inicial) se as sucessivas potências da matriz C tenderem para a matriz nula.

    Isto pode ser verificado, mais facilmente, usando o:

    Teorema : ( Condições Necessárias e Suficientes de Convergência )
    Qualquer que seja o vector inicial x(0) os métodos iterativos convergem
    sse

    a) O raio espectral da matriz C fôr menor que 1.
    sse
    b) Existe uma norma ||.|| : ||C|| < 1

  • Método de Jacobi, C = - D-1( L + U )
  • Método de Gauss-Seidel, C = - ( L + D )-1 U

    Corolário:
    Temos as seguintes majorações para os erros:

    || e(k+1) || < || C || || e(k) ||
    || e(k) || < || C ||k || e(0) ||
    || e(k+1) || < || C || / ( 1 - || C || ) || x(k+1) - x(k) ||

    Observação:
    Podemos falar também de ordem de convergência, no caso vectorial, e estas majorações revelam que estes métodos iterativos têm uma convergência linear .

    Critérios Suficientes de Convergência

    Para além do teorema, que nos dá condições necessárias e suficientes de convergência, existem critérios mais simples que asseguram a convergência para qualquer iterada inicial. No entanto, essas condições, que iremos deduzir, são apenas condições suficientes.

    Repare-se, por exemplo, no caso do método de Jacobi. Como C = D-1 ( L + U )

    e relembrando que

    ao exigirmos que a norma seja inferior a 1, isto significa
    Logo, uma condição suficiente que nos garante isso, é
    neste caso, diz-se que a matriz A tem diagonal estritamente dominante por linhas.

    Da mesma forma, considerando a norma ||.||1, podemos concluir que se

    isto é, se a matriz A tem diagonal estritamente dominante por colunas, então o método de Jacobi converge.

    Este raciocínio pode-se aplicar também ao método de Gauss-Seidel e obtemos :

    Teorema : ( Condição Suficiente de Convergência )
    Se a matriz A tiver a diagonal estritamente dominante por linhas ou por colunas, os métodos de Jacobi e de Gauss-Seidel convergem, para qualquer vector inicial x(0) escolhido.

    Observação:
    Como C = M-1N = M-1 ( A - M ) = I - M-1A quanto mais próxima de A fôr a matriz M, mais próximo da matriz zero será valor de C, e consequentemente, mais rápida será a convergência do método iterativo.

    Nos casos dos métodos que estudamos, é intui-se que M está "mais próxima" de A no caso do Método de Gauss-Seidel (M = L + D ) do que no caso do Método de Jacobi ( M = D ).

    Portanto, de um modo geral o método de Gauss-Seidel converge mais rapidamente. Há, no entanto, casos em que um método converge e o outro não!!!