Métodos Iterativos - Sistemas Lineares

Métodos Iterativos para Sistemas Lineares

Neste parágrafo, o objectivo é encontrar métodos que permitam aproximar a solução de um sistema linear, de 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 utilidade é evitar definir ou armazenar a matriz, ou ainda, evitar os problemas de instabilidade numérica, que podem ocorrer num método directo.

Consideremos um sistema genérico A x = b escrito na forma A = M + N.
Supondo que M é invertível, 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⁽⁰⁾

Iterar x^(k+1) = M^-1b - M^-1 N x^(k)

É importante que a matriz M seja 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, iremos abordar os seguintes métodos:

método de Jacobi

método de Gauss-Seidel.

método SOR

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 deverá 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⁽⁰⁾

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⁽⁰⁾

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 a iguladade, obtemos

e^(k) = C^k e⁽⁰⁾

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.

Observação:
Se existir uma norma induzida ||.|| : ||C|| < 1 então é claro que que isso se irá verificar,
porque ||e^(k) || = || C^k e⁽⁰⁾|| < || C ||^k ||e⁽⁰⁾|| ® 0, quando k tende para infinito,
qualquer que seja o e⁽⁰⁾, fixo pela iterada inicial.

Teorema : ( Condições Necessárias e Suficientes de Convergência )
Os métodos iterativos convergem, qualquer que seja o vector inicial x⁽⁰⁾ ,
sse r(C)<1.
Notando que:

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

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

dem:
Se r(C)<1, então tomando e = 1-r(C)>0, sabemos que existe uma norma induzida ||.|| tal que
||C|| < r(C) + e = 1.
Resta ver que r(C)<1 é condição necessária.
Supondo que existia um valor próprio z tal que |z| > 1,
então se x⁽⁰⁾= x - v, onde x é a solução e v o vector próprio associado a z, obtemos
e^(k) = C^k e⁽⁰⁾ = C^k v = z^k v,
e como v está fixo e |z|^k > 1, então e^(k) não tende para zero, não havendo convergência para o x⁽⁰⁾ definido.

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

|| e^(k+1) || < || C || || e^(k) ||

|| e^(k) || < || C ||^k || e⁽⁰⁾ ||

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

dem:
Notamos apenas que a última estimativa resulta de
||e^(k) || = || x - x^(k+1) + x^(k+1) - x^(k) || < || x - x^(k+1) || + || x^(k+1) - x^(k) ||
< ||C|| || e^(k) || + || x^(k+1) - x^(k) ||
e portanto
||e^(k) || (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 do máximo 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.

De forma análoga (usando uma norma semelhante à das colunas), 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⁽⁰⁾ 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, normalmente 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, habitualmente o método de Gauss-Seidel converge mais rapidamente. Há, no entanto, casos em que isso não acontece, e um método pode convergir e o outro não!

Número de Operações: A menos que as matrizes possuam zonas apreciáveis com elementos nulos, ambos os métodos iterativos exigem um cálculo total de ~2n² operações, por cada iterada, o que implica que, se forem necessárias mais que ~n/3 iterações, exigimos mais operações do que num método directo.

Método SOR

Apresentamos finalmente uma variante do método de Gauss-Seidel, denominado método SOR (succesive over relaxation) que consiste em considerar um parâmetro real w não nulo, e definir M_w = L + (1/w)D
N_w = (1-1/w)D+ U notando que no caso em que w=1 obtemos o método de Gauss-Seidel. A utilização deste parâmetro permite obter uma convergência mais rápida, havendo um valor w* que é o parâmetro optimal, no sentido em que minimiza o raio espectral da matriz C_w = M_w^-1N_w.

Portanto, o método consiste em

Iterada inicial x⁽⁰⁾

Iterar x^(k+1) = (1-w) x^(k) + w D^-1(b - Lx^(k+1) - U x^(k))

e os seguintes teoremas dão-nos resultados acerca da convergência.

Teorema (Kahan - condição necessária)
Para que haja convergência do método SOR, qualquer que seja a iterada inicial,
é necessário que w esteja em ]0,2[.

Teorema (Ostrowski-Reich - condição suficiente)
Se a matriz A for simétrica e definida positiva, e considerarmos w em ]0,2[,
há convergência do método SOR, qualquer que seja a iterada inicial.

Observação: Em particular, conclui-se que no caso em que A é simétrica e definida positiva o método de Gauss-Seidel converge.