Métodos iterativos para sistemas lineares. - alan.pro.br · PDF fileM etodos iterativos para sistemas lineares. Alan Costa de Souza 7 de Setembro de 2017 Alan Costa de Souza M etodos

Metodos iterativos para sistemas lineares.

Alan Costa de Souza

7 de Setembro de 2017

Alan Costa de Souza Metodos iterativos para sistemas lineares. 7 de Setembro de 2017 1 / 46

Introducao.

A ideia central e generalizar o metodo do ponto fixo utilizado nabusca por raızes de uma funcao.

Seja o sistema linear A~x = ~b.

A e a matriz de coeficientes.~x e o vetor de variaveis.~b e o vetor de constantes.

O sistema e convertido de alguma forma em outro sistema do tipo~x = C~x + ~g .

Podemos definir φ(~x) = C~x + ~g , como uma ”funcao”de iteracao.


Introducao.

Entao podemos propor um sistema iterativo:

Iniciamos com um vetor ~x0.

Obtemos uma sequencia de vetores atraves de φ(~x).

~x1 = C~x0 + ~g = φ(~x0)

~x2 = C~x1 + ~g = φ(~x1)

~x3 = C~x2 + ~g = φ(~x2)

~xk+1 = C~xk + ~g = φ(~xk)

Se limk→∞ ~xk = ~α.

~α = C~α + ~g .

A~α = ~b.


Testes de parada.

O metodo iterativo segue ate ~xk esteja suficiente proximo de ~xk+1.

O que isso significa?

No metodo do ponto fixo: |xk+1 − xk | < ε.

E com vetores?

podemos utilizar por exemplo a norma infinito.

Seja ~x um vetor, sua norma infinito e:

|~x |∞ = max1≤i≤n |xi |.Entao:

|~xk+1 − xk |∞ = max1≤i≤n |~xk+1i − xki |

|~xk+1 − xk |∞ < ε

Outra alternativa e estipular um numero de iteracoes maxima.


Metodo iterativos.

Veremos nessa aula dois metodos iterativos:

Metodo de Gauss-Jacobi.

Metodo de Gauss-Seidel.

A diferenca entre eles e a forma como φ(~x) e calculada.



Resolver o sistema: 10x1 + 2x2 + 1x3 = 71x1 + 5x2 + 1x3 = −82x1 + 3x2 + 10x3 = 6

, usando

~x0 =

+ 710−8

5+ 6

10

com erro maximo ε =0,05.



10x1 + 2x2 + 1x3 = 71x1 + 5x2 + 1x3 = −82x1 + 3x2 + 10x3 = 6

10x1 + 2x2 + 1x3 = 7

x1 =1

10(7− 2x2 − 1x3)

xk+11 =

1

10(7− 2xk2 − 1xk3 )



10x1 + 2x2 + 1x3 = 71x1 + 5x2 + 1x3 = −82x1 + 3x2 + 10x3 = 6

1x1 + 5x2 + 1x3 = −8

x2 =1

5(−8− 1x1 − 1x3)

xk+12 =

1

5(−8− 1xk1 − 1xk3 )



10x1 + 2x2 + 1x3 = 71x1 + 5x2 + 1x3 = −82x1 + 3x2 + 10x3 = 6

2x1 + 3x2 + 10x3 = 6

x3 =1

10(6− 2x1 − 3x2)

xk+13 =

1

10(6− 2xk1 − 3xk2 )


xk+11 =

1

10(7− 2xk2 − 1xk3 ) = 0xk1 −

2

10xk2 −

1

10xk3 +

7

10.

xk+12 =

1

5(−8− 1xk1 − 1xk3 ) = −1

5xk1 + 0xk2 −

1

5xk3 −

8

5

xk+13 =

1

10(6− 2xk1 − 3xk2 ) = − 2

10xk1 −

3

10xk2 + 0xk3 +

6

10 xk+11

xk+12

xk+13

=

0 − 210 − 1

10−1

5 0 − 15

− 210 − 3

10 0

xk1xk2xk3

+

+ 710−8

5+ 6

10

~xk+1 = C~xk + ~g .


~x1 = C~x0 + ~g .

~x1 =

0 − 210 − 1

10−1

5 0 − 15

− 210 − 3

10 0

+ 710−8

5+ 6

10

+

+ 710−8

5+ 6

10

.

~x1 =

+0, 96−1, 86+0, 94

.

Continua?

|~x1 − ~x0|∞ < 0, 05?

~x1 − ~x0 =

+0, 96−1, 86+0, 94

− +0, 7−1, 6+0, 6

=

+0, 26−0, 26+0, 34

|~x1 − ~x0|∞ = 0, 34 > 0, 05.


~x2 = C~x1 + ~g .

~x2 =

0 − 210 − 1

10−1

5 0 − 15

− 210 − 3

10 0

+0, 96−1, 86+0, 94

+

+ 710−8

5+ 6

10

.

~x2 =

+0, 978−1, 98

+0, 966

.

Continua?

|~x2 − ~x1|∞ < 0, 05?

~x2 − ~x1 =

+0, 978−1, 98

+0, 966

− +0, 96−1, 86+0, 94

=

+0, 018−0, 12

+0, 026

|~x2 − ~x1|∞ = 0, 12 > 0, 05.


~x3 = C~x2 + ~g .

~x3 =

0 − 210 − 1

10−1

5 0 − 15

− 210 − 3

10 0

+0, 978−1, 98

+0, 966

+

+ 710−8

5+ 6

10

.

~x3 =

+0, 9994−1, 9888+0, 9984

.

Continua?

|~x3 − ~x2|∞ < 0, 05?

~x3 − ~x2 =

+0, 9994−1, 9888+0, 9984

− +0, 978−1, 98

+0, 966

=

+0, 0214−0, 0088+0, 0324

|~x3 − ~x2|∞ = 0, 0324 < 0, 05.


~x ≈ ~x3 =

+0, 9994−1, 9888+0, 9984


Convergencia do metodo de Gauss-Jacobi.

No exemplo anterior usamos ~x0 = ~g

A convergencia do metodo e independente do ~x0 escolhido.

Veremos adiante que a convergencia depende apenas da matriz decoeficientes A.


Teorema 1: Criterio das Linhas.

Seja A ~x = ~b um sistema linear. Seja:

αk =

∑nk 6=j=1 |akj ||akk |

.

Se α = max1≤k≤n αk < 1, entao o metodo de Gauss-Jacobi gera umasequencia {~xk} que converge para a solucao do sistema, independente do~x0 escolhido.


Exemplo 2

10x1 + 2x2 + 1x3 = 71x1 + 5x2 + 1x3 = −82x1 + 3x2 + 10x3 = 6

A =

10 2 11 5 1

2 3 10

α1 =

2 + 1

10= 0, 3 < 1.

α2 =1 + 1

5= 0, 4 < 1.

α3 =2 + 3

10= 0, 5 < 1.

max1≤k≤3

αk = 0, 5 < 1.


Exemplo 3

{1x1 + 1x2 = 3

1x1 − 3x2 = −3

A =

(1 1

1 − 3

)α1 =

1

1= 1 ≥ 1.

α2 =1

3= 0, 3 < 1.

max1≤k≤3

αk = 1.

O metodo de Gauss-Jacobi converge para a solucao do sistema:x1 = x2 = 1, 5.Isso mostra que a condicao do teorema e apenas suficiente.Se o criterio for satisfeito, entao o metodo converge.Mas se o criterio nao for satisfeito, o metodo pode convergir ou naoconvergir.Alan Costa de Souza Metodos iterativos para sistemas lineares. 7 de Setembro de 2017 18 / 46

Exemplo 4

1x1 + 3x2 + 1x3 = −25x1 + 2x2 + 2x3 = 3

0x1 + 6x2 + 8x3 = −6

A =

1 3 15 2 20 6 8

α1 =

3 + 1

1= 4 > 1.


A =

5 2 21 3 10 6 8

α1 =

2 + 2

5= 0, 8 < 1.

α2 =1 + 1

3= 0, 66... < 1.

α3 =0 + 6

8= 0, 75 < 1.

Conclusao: Se a matriz A nao satisfaz o criterio das linhas, podemospermutar linhas ou colunas para tentar obter uma matriz A2 quesatisfaca.



Da mesma forma que o metodo Gauss-Jacobi, o metodo deGauss-Seidel consiste em transformar A~x = ~b na forma equivalente~x = C~x + ~g .

~xk+1 = C~xk + ~g

A formula de iteracao e parecida, mas com uma pequena diferenca.



Resolver o sistema: 5x1 + 1x2 + 1x3 = 53x1 + 4x2 + 1x3 = 63x1 + 3x2 + 6x3 = 0

, usando

~x0 = ~0.

com erro maximo ε =0,05.



5x1 + 1x2 + 1x3 = 53x1 + 4x2 + 1x3 = 63x1 + 3x2 + 6x3 = 0

5x1 + 1x2 + 1x3 = 5

x1 =1

5(5− x2 − x3) = 1− 0, 2x2 − 0, 2x3

xk+11 = 1− 0, 2xk2 − 0, 2xk3



5x1 + 1x2 + 1x3 = 53x1 + 4x2 + 1x3 = 63x1 + 3x2 + 6x3 = 0

3x1 + 4x2 + 1x3 = 6

x2 =1

4(6− 3x1 − x3) = 1, 5− 0, 75x1 − 0, 25x3

xk+12 = 1, 5− 0, 75xk+1

1 − 0, 25xk3



5x1 + 1x2 + 1x3 = 53x1 + 4x2 + 1x3 = 63x1 + 3x2 + 6x3 = 0

3x1 + 3x2 + 6x3 = 0

x3 =1

6(0− 3x1 − 3x2) = 0− 0, 5x1 − 0, 5x2

xk+13 = 0− 0, 5xk+1

1 − 0, 5xk+12



xk+11 = 1− 0, 2xk2 − 0, 2xk3

xk+12 = 1, 5− 0, 75xk+1

1 − 0, 25xk3

xk+13 = 0− 0, 5xk+1

1 − 0, 5xk+12

x01 = 0 x0

2 = 0 x03 = 0 x1

1 =? x12 =? x1

3 =?

x11 = 1− 0, 2x0

2 − 0, 2x03 = 1.

x01 = 0 x0

2 = 0 x03 = 0 x1

1 = 1 x12 =? x1

3 =?

x12 = 1, 5− 0, 75x1

1 − 0, 25x03 = 1, 5− 0, 75× 1 = 0, 75.

x01 = 0 x0

2 = 0 x03 = 0 x1

1 = 1 x12 = 0, 75 x1

3 =?

x13 = 0− 0, 5x1

1 − 0, 5x12 = −0, 5× 1− 0, 5× 0, 75 = −0, 875

x11 = 1 x1

2 = 0, 75 x13 = −0, 875.


Continua?

|~x1 − ~x0|∞ < 0, 05?

~x1 − ~x0 =

10, 75−0, 875

− 0

00

=

10, 75−0, 875

|~x1 − ~x0|∞ = 1 > 0, 05



x11 = 1 x1

2 = 0, 75 x13 = −0, 875 x2

1 =? x22 =? x2

3 =?

x21 = 1− 0, 2x1

2 − 0, 2x13 = 1, 025.

x11 = 1 x1

2 = 0, 75 x13 = −0, 875 x2

1 = 1, 025 x22 =? x2

3 =?

x22 = 1, 5− 0, 75x2

1 − 0, 25x13 = 0, 95.

x11 = 1 x1

2 = 0, 75 x13 = −0, 875 x2

1 = 1, 025 x22 = 0, 95 x2

3 =?

x23 = 0− 0, 5x2

1 − 0, 5x22 = −0, 9875

x21 = 1, 025 x2

2 = 0, 95 x23 = −0, 9875.


Continua?

|~x2 − ~x1|∞ < 0, 05?

~x2 − ~x1 =

1, 0250, 95−0, 9875

− 1

0, 75−0, 875

=

0, 0250, 2

−0, 1125

|~x2 − ~x1|∞ = 0, 2 > 0, 05



x21 = 1, 025 x2

2 = 0, 95 x23 = −0, 9875 x3

1 =? x32 =? x3

3 =?

x31 = 1− 0, 2x2

2 − 0, 2x23 = 1, 0075.

x21 = 1, 025 x2

2 = 0, 95 x23 = −0, 9875 x3

1 = 1, 0075 x32 =? x3

3 =?

x32 = 1, 5− 0, 75x3

1 − 0, 25x23 = 0, 9912.

x21 = 1, 025 x2

2 = 0, 95 x23 = −0, 9875 x3

1 = 1, 0075 x32 = 0, 9912 x3

3 =?

x33 = 0− 0, 5x3

1 − 0, 5x32 = −0, 9993

x31 = 1, 0075 x3

2 = 0, 9912 x33 = −0, 9993.


Continua?

|~x3 − ~x2|∞ < 0, 05?

~x3 − ~x2 =

1, 00750, 9912−0, 9993

− 1, 025

0, 95−0, 9875

=

−0, 01750, 0412−0, 0118

|~x3 − ~x2|∞ = 0, 0412 < 0, 05.


~x ≈ ~x3 =

1, 00750, 9912−0, 9993


Convergencia do metodo de Gauss-Seidel.

Existem dois criterios que estabelecem condicoes suficientes para aconvergencia do metodo de Gauss-Seidel:

Criterio de Sassenfeld.

Criterio das linhas.


Criterio de Sassenfeld

x1 + 0, 5x2 − 0, 1x3 + 0, 1x4 = 0, 2

0, 2x1 + x2 − 0, 2x3 − 0, 1x4 = −2, 6−0, 1x1 − 0, 2x2 + x3 + 0, 2x4 = 1

0, 1x1 + 0, 3x2 + 0, 2x3 + x4 = −2, 5

β1 =|a12|+ |a13|+ |a14|

|a11|

β1 =0, 5 + 0, 1 + 0, 1

1= 0, 7

β2 =|a21| × β1 + |a23|+ |a24|

|a22|

β2 =0, 2× 0, 7 + 0, 2 + 0, 1

1= 0, 44


Criterio de Sassenfeld

x1 + 0, 5x2 − 0, 1x3 + 0, 1x4 = 0, 2

0, 2x1 + x2 − 0, 2x3 − 0, 1x4 = −2, 6−0, 1x1 − 0, 2x2 + x3 + 0, 2x4 = 1

0, 1x1 + 0, 3x2 + 0, 2x3 + x4 = −2, 5

β3 =|a31| × β1 + |a32| × β2 + |a34|

|a33|

β3 =0, 1× 0, 7 + 0, 2× 0, 44 + 0, 2

1= 0, 358.

β4 =|a41| × β1 + |a42| × β2 + |a43| × β3

|a44|

β4 =0, 1× 0, 7 + 0, 3× 0, 44 + 0, 2× 0, 358

1= 0, 2736.


β1 = 0, 7 β2 = 0, 44 β3 = 0, 358 β4 = 0, 2736

max1≤k≤4

βk = 0, 7 < 1.

Como o maximo entre os bk e menor que um, o metodo deGauss-Seidel converge para qualquer aproximacao inicial.


Exemplo 2.

2x1 + x2 + 3x3 = 90x1 − x2 + x3 = 1

1x1 + 0x2 + 3x3 = 3

β1 =|a12|+ |a13||a11|

β1 =1 + 3

2= 2 > 1.

Viola o criterio de Sassenfeld.

Nao podemos garantir convergencia.


Exemplo 2.

trocando a primeira equacao pela terceira equacao:1x1 + 0x2 + 3x3 = 3

0x1 − x2 + x3 = 12x1 + x2 + 3x3 = 9

Trocando a primeira coluna pela terceira coluna:3x3 + 0x2 + 1x1 = 3x3 − x2 + 0x1 = 1

3x3 + x2 + 2x1 = 9


3x3 + 0x2 + 1x1 = 3x3 − x2 + 0x1 = 1

3x3 + x2 + 2x1 = 9

β1 =|a12|+ |a13||a11|

β1 =0 + 1

3= 0, 33...

β2 =|a21| × β1 + |a23|

|a22|

β2 =1× 0, 33 + 0

1= 0, 33...


3x3 + 0x2 + 1x1 = 3x3 − x2 + 0x1 = 1

3x3 + x2 + 2x1 = 9

β3 =|a31| × β1 + |a32| × β2

|a33|

β3 =3× 0, 33 + 1× 0, 33

2= 0, 66...

max1≤k≤4

βk = 0, 66... < 1.


Exemplo 3.

{x1 + x2 = 3

x1 − 3x2 = −3

β1 = 1 ≥ 1.

O criterio de Sassenfeld nao e satisfeito.

Mas o metodo de Gauss-Seidel converge.


Criterio das linhas.

O criterio das linhas usado para verificar a convergencia do metodo deGauss-Jacobi pode ser usado para verificar a convergencia do metodode Gauss-Seidel.

A prova consiste em demonstrar que satisfazendo o criterio das linhas,tambem satisfaz o criterio de Sassenfeld.

Logo se se satisfizer o criterio das linhas, o metodo de Gauss-Seidelconverge.

Mas o metodo pode nao satisfazer o criterio das linhas e satisfazer ocriterio de sassenfeld e portanto convergir.


Exemplo 1

3x1 + 0x2 + 1x3 = 3x1 − x2 + 0x3 = 1

3x1 + x2 + 2x3 = 9

α1 =0 + 1

3=

1

3< 1.

α2 =1 + 0

1= 1.

Viola criterio das linhas.


Exemplo 1

3x1 + 0x2 + 1x3 = 3x1 − x2 + 0x3 = 1

3x1 + x2 + 2x3 = 9

β1 =0 + 1

3=

1

3< 1.

β2 =|a21| × β1 + |a23|

|a22|

β2 =1× 1

3 + 0

1=

1

3< 1.

β3 =|a31| × β1 + |a32| × β2

|a33|

β3 =3× 1

3 + 1× 13

2=

2

3< 1.


Comparacao dos metodos.

Convergencia: os metodos diretos sempre convergem para a solucaodo sistema, se o determinante da matriz A for diferente de zero. Ja osmetodos iterativos convergem apenas sobre determinadas condicoes.

Matrizes esparsas: Uma matriz esparsa e uma matriz que a maiorparte dos seus elementos sao zeros. Em alguns casos pode-se utilizarestruturas de dados especiais para armazenar apenas as entradasnao-nulas e com isso conseguir um ganho de memoria. Mas utilizandoos metodos diretos, introduz-se na matriz varios elementos nao-nulosque nao tinham na matriz original enquanto que os metodos iterativosnao alteram a matriz. Por isso e mais adequado usar os metodositerativos para matrizes esparsas.


Erros de arredondamento: Os metodos diretos podem gerar grandeserros de arredondamento, que podem ser amenizados com a tecnicade pivoteamento. Mas os metodos iterativos uma vez que aconvergencia e assegurada, sempre converge para a solucao dosistema. Portanto os metodos iterativos garantem que a solucaoencontrada e a solucao do sistema


Documents

Métodos iterativos para sistemas lineares. - alan.pro.br · PDF fileM etodos iterativos para sistemas lineares. Alan Costa de Souza 7 de Setembro de 2017 Alan Costa de Souza M etodos