SISTEMAS LINEARES

Convergência dos Métodos Iterativos

Quero lembrar que nos exemplos que apresentei as raízes estão sendo números inteiros e a convergência está se dando rapidamente, fatos que não ocorrerão necessariamente. Na imensa maioria dos casos reais, os valores das raízes x_i não serão inteiros. Precisaremos parar quando a precisão estiver dentro da desejada. Isso se dará quando a diferença entre os valores calculados para x₁ , x₂, x₃ , etc... estiverem dentro da precisão desejada.

Para tanto, comparamos os valores obtidos para duas iterações seguidas e vemos se esses valores variaram muito ou se estão quase que se repetindo. Nesse caso, estamos próximos das raízes desejadas.

Assim, abs(x_j⁽ⁱ⁾ – x_j^(i-1) ) deve ser menor que o erro permitido para todas as variáveis x_j , onde x_j⁽ⁱ⁾  é o valor calculado para a variável x_j após i iterações e x_j^(i-1) o valor da variável x_j após i-1 iterações.

Vejamos, agora, dois exemplos muito simples.

Primeiro exemplo:

5 x₁ + 2 x₂ = 9

2 x₁ + 4 x₂ = 10

Vamos resolver por Gauss-Seidel.

x₁ = (9 – 2 x₂)/5

x₂ = (10-2 x₁)/4

Seqüência de solução: (0,0) à (1,8 , 1,6) à (1,16 , 1,92) à (1,032 , 1,984) à

(1,0064 , 1,9968) à .......(1,0000 , 2,0000)

É clara a convergência para as raízes x₁ = 1   e   x₂ = 2.

Vamos, agora, resolver o mesmo sistema, simplesmente trocando as ordens das equações.

2 x₁ + 4 x₂ = 10

5 x₁ + 2 x₂ = 9

x₁ = (10 – 4 x₂) / 2

x₂ = (9 – 5 x₁) / 2

Partindo de (0,0) , temos a seqüência:

(0,0) à (5 , -8) à (21 , -48) à (101 , -248) .....

Como vemos não há convergência para as raízes 1 e 2 .

O que está acontecendo ?

É, que pena !!! Nem sempre há convergência.

Pode-se demonstrar, que a condição suficiente para convergência é que a matriz A seja Diagonalmente Dominante, o que significa que para cada linha o termo da diagonal principal seja, em módulo, maior ou igual à soma dos módulos dos demais termos dessa linha, garantido que, em pelo menos numa linha, o módulo seja maior.

Essa condição é suficiente mas não necessária, podendo ocorrer convergência sem que a matriz seja diagonalmente dominante.

Seja uma sistema

a₁₁x₁ + a₁₂x₂ +....+a_1nx_n = b₁

a₂₁x₁ + a₂₂x₂ +....+a_2nx_n = b₂

_.....

a_n1x₁ + a_n2x₂ +....+a_nnx_n = b_n    

_Isolemos x1 na primeira equação, x₂  na segunda, x₃ na terceira etc. Temos:

x₁  = (b₁  - (a₁₂ x₂ +....+a_1n x_n))/ a₁₁

x₂  = (b₂  - (a₂₁ x₁ +....+a_2n x_n))/ a₂₂

_.....

x_n = (b_{n – (}a_n1 x₁ + a_n2 x₂ +....+ a_{n n-1} x_{n-1 ))/} a_nn

Se colocarmos os valores exatos dos x_i ‘s no lado direito, obteremos os valores exatos dos x_i ‘s no lado esquerdo. Entretanto, estamos entrando com valores incorretos, com erros, logo, obteremos valores incorretos do lado esquerdo.

Assim, os x_i ’s com que se entra são x_i + e_i . Assim,

x₁ + e₁ = (b₁  - (a_{12 (}x₂ + e₂)+....+a_{1n (}x_{n + en))/} a₁₁

x₂ + e₂ = (b₂  - (a₂₁₍x₁ + e₁) +....+a_{2n (}x_{n + en)))/} a₂₂

_.....

x_n + e_n = (b_{n – (}a_{n1 (}x₁ + e₁)+ a_{n2 (}x_{2 + e2)} +....+ a_{n n-1 (}x_{n-1 + en-1)))/} a_nn

Assim,

e₁ = - (a₁₂ e₂ +....+ a_{1n en)/} a₁₁

e₂ = - (a₂₁ e₁ +....+ a_{2n en)/} a₂₂

_....

e_n = _{– (}a_n1 e₁ + a_{n2 e2} +....+ a_{n n-1 en-1)/} a_nn

_{Se tomarmos, no lugar dos ei ‘s o erro de maior valor absoluto, seja eM , teremos:}

|e₁|<|a₁₂ e_M +....+ a_{1n eM|/ |}a_11| < | e_M| . (|a_{12| + .... +|} a_1n|)/|a_11|

|e₂|<|a₂₁ e_M +....+ a_{2n eM)|/ |}a_22| < | e_M|.( |a_{21| + ...+ |} a_2n|)/| a_22|

_....

|e_n| <_|a_n1e_M+a_n2eM+....+a_{nn-1eM|/ |}a_nn| <

< | e_M|.(_|a_n1| +| a_{n2| + ... + |} a_{n n-1|)/|}a_nn|

_{Sendo |} a_ii | ³ |a_i1| +| a_{i2| + ... + |} a_{i i-1|}

_{para todos os i’s de 1 a n, temos que o erro de cada nova variável calculada é menor que o maior erro até então existente, mostrando que os erros estão diminuindo.}

_{Com facilidade, demonstra-se que os erros tendem a zero se}

_| a_ii | ³ |a_i1| +| a_{i2| + ... + |} a_{i i-1|}

_{para todos os i’s.}