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 se não estaríamos 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

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) + wD^-1(b - Lx^(k+1) - U x^(k))

http://www.math.ist.utl.pt/~calves/cursos/SisLin-Dir.htm

http://www.math.ist.utl.pt/~calves/cursos/SisLin-Iter.htm

pagina anterior

Hosted by www.Geocities.ws