Sistemas Lineares – Métodos Iterativos

  • View
    258

  • Download
    2

Embed Size (px)

DESCRIPTION

Calculo Numérico - métodos interativos

Text of Sistemas Lineares – Métodos Iterativos

Clculo Numrico

Sistemas Lineares Mtodos Iterativos

Curso de Engenharia - UTFPR

Clculo Numrico

Sistemas de Equaes Lineares (SEL ) Parte IIProfs.:Tina Andreolla(UTFPR) Bruno Correia da Nbrega Queiroz (UFCG) Jos Eustquio Rangel de Queiroz(UFCG) Marcelo Alves de Barros(UFCG)

Curso de Engenharia - UTFPR

Clculo Numrico

bastante comum encontrar sistemas lineares que envolvem uma grande porcentagem de coeficientes nulos. Esses sistemas so chamados de sistemas esparsos. Para esses tipos de sistemas, o mtodo de Eliminao de Gauss no o mais apropriado, pois ele no preserva essa esparsidade, que pode ser til por facilitar a resoluo do sistema. Mtodo mais apropriado para esse tipo de sistema mtodos iterativo de Gauss-Seidel.

Curso de Engenharia - UTFPR

Clculo Numrico

Mtodos Iterativos

Curso de Engenharia - UTFPR

Clculo Numrico

Mtodos Iterativos: Consistem em encontrar uma seqncia de estimativas xik (dada uma estimativa inicial xi0) que aps um nmero suficientemente grande de iteraes convirja para a soluo do sistema de equaes.x100 x2 1 x1

x 122 x2

x1 x2 p x3 x4 / xn

x1 2 p1 x3

0 x3

p

2 x3

0 x4

x1 4 / x1 n

2 x4

/0 xn

/2 xn

Curso de Engenharia - UTFPR

Clculo Numrico

Outra vantagem destes mtodos no so to suscetveis ao acmulo de erros de arredondamento como o mtodo de Eliminao de Gauss. importante lembrar que: Como todo processo iterativo, estes mtodos sempre apresentaro um resultado aproximado, que ser to prximo do resultado real conforme o nmero de iteraes realizadas. Alm disso, tambm preciso ter cuidado com a convergncia desses mtodos.

Curso de Engenharia - UTFPR

Clculo Numrico

Mtodos Iterativos Transforma o sistema linear Ax=b em x = Cx +g A: matriz dos coeficientes, n x m x: vetor das variveis, n x 1; b: vetor dos termos constantes, n x 1.

C: matriz n x n

Mtodos utilizados: Gauss-Jacobi Gauss-Seidel

g: vetor n x 1

Curso de Engenharia - UTFPR

Clculo Numrico

Mtodo de Gauss-Jacobi Conhecido x(0) (aproximao inicial) obtm-se consecutivamente os vetores:

x (1) ! Cx ( 0) g , x ( 2) ! Cx (1) g ,

(primeira aproximao) (segunda aproxima o), etc.

De um modo geral, a aproximao x(k+1) calculada pela frmula

x(k+1) = C x(k)+g, k=0, 1, ...Curso de Engenharia - UTFPR

Clculo Numrico

Mtodo de Gauss-Jacobi

Da primeira equao do sistema

a11 x1 + a12 x2 + ... +a1n x2 = b1 obtm-se x1 = (1/a11) (b1 analogamente x2 = (1/a22 (b2 - a21 x1 . . . . )Curso de Engenharia - UTFPR

- a12 x2 - ... -a1n x2) ... -a2n xn)

xn = (1/ann) (bn - an1 x1 - ... - an,n-1 xn-1

Clculo Numrico

Mtodo de Gauss-Jacobi

Desta forma para

x= Cx+g... - a1n /a11 - a2n /a22 . 0

C=

... - a21 /a22 0 . . - an1 /ann - an2 /ann ( b1 /a11 b2 /a22

0

- a12 /a11

g=

bn /ann ) -1 ...

Curso de Engenharia - UTFPR

Clculo Numrico

Mtodo de Gauss-Jacobi - Critrio de parada Distncia entre duas iteraes

d(k) = max xi(k) - xi(k-1) Critrio de parada

dr(k) = d(k)/ (max xi(k) ) < I

Curso de Engenharia - UTFPR

Clculo Numrico

Mtodo de Gauss-Jacobi - EXEMPLO

Seja o sistema

10 x1 + 2x2 + x3 = 7 x1 + 5x2 + x3 = -8 2x1 + 3x2 + 10x3 = 6

C=

- 2/10 - 1/10 -1/5 0 - 1/5 -1/5 3/10 0 0

g=

-7/10 8/5 -6/10

Curso de Engenharia - UTFPR

Clculo Numrico

Mtodo de Gauss-Jacobi - EXEMPLO

Com

x0 =

0,7 -1,6 0,6

e I = 0,05

C=

- 2/10 - 1/10 -1/5 0 - 1/5 -1/5 3/10 0 0

g=

-7/10 8/5 -6/10

Curso de Engenharia - UTFPR

Clculo Numrico

Mtodo de Gauss-Jacobi - EXEMPLO

I = 0,05

obtemos

x(1) = Cx(0) + g =

0,96 -1,86 0,94

|x1(1) |x2(1) |x3(1)

x1(0)| = 0,26 x2(0)| = 0,26 dr(1) = 0,34/ (max xi(1) ) = 0,1828 > I

x3(0)| = 0,34Curso de Engenharia - UTFPR

Clculo Numrico

Mtodo de Gauss-Jacobi - EXEMPLO

I = 0,05

x(2) =

0,978 -1,98 0,966

dr(1) = 0,12/ 1,98 = 0,0606 > I

x(3) =

0,9997 -1,9888 0,984

dr(1) = 0,0324/ 1,9888 = 0,0163 < I

Curso de Engenharia - UTFPR

Clculo Numrico

Mtodo de Gauss-Seidel Conhecido x(0) (aproximao inicial) obtm-se x1, x2, ...xk.

x k 1 usa-se todos os valores Ao se calcular j k 1 k 1 x1 ,..., x j 1 que j foram calculados e os valoresk x k1 ,..., x n restantes. j

Curso de Engenharia - UTFPR

Clculo Numrico

Mtodos Iterativos

Gauss Seidel

Descrio do Mtodo Seja o seguinte sistema de equaes:a11 . x1 a12 . x 2 a13 . x 3 ... a1n 1 . x n 1 a1n 1 . x n ! b1 a 21 . x1 a 22 . x 2 a 23 . x 3 ... a 2 n 1 . x n 1 a 2 n 1 . x n ! b2 a 31 . x1 a 32 . x 2 a 33 . x 3 ... a 3 n 1 . x n 1 a 3 n 1 . x n ! b3 / a n1 . x1 a n 2 . x 2 a n3 . x 3 ... a n1n 1 . x n 1 a nn . x n ! bnCurso de Engenharia - UTFPR

Clculo Numrico

Isolando xi a partir da linha i, tem-se:x1 ! 1 b 1 a 12 . x 2 a 13 . x 3 a 1 , n 1 . x n 1 a 1 n . x n a 11 1 a 22 1 a 33

x2 !

b 2 b 3

a 21 . x 1 a 23 . x 3 a 2 , n 1 . x n 1 a 2 n . x n

x3 !

a 31 . x 2 a 32 . x 2 a 3 , n 1 . x n 1 a 3 n . x n

/ xn ! 1 a nn

b n

a n 1 . x 1 a n 2 . x 2 ... a n , n 1 . x n 1

Curso de Engenharia - UTFPR

Clculo Numrico

O processo iterativo obtido a partir das equaes, fazendo:

x

k 1 1

1 k k k k ! b1 a12 .x 2 a13 .x 3 ... a1, n 1 .x n 1 a1n . x n a11

x

k 1 2

1 k k k ! b2 a 21 .x1k 1 a 23 . x3 ... a 2 , n 1 . x n 1 a 2 n . x n a 22

k x3 1 !

1 k k k b3 a 31 .x1k 1 a 32 .x 2 1 ... a 3,n 1 .x n 1 a 3 n . x n a 33

x

k 1 n

1 k k 1 ! bn a n1 .x1k 1 a n 2 .x 2 1 ... a n , n 1 . x n 1 a nn

Curso de Engenharia - UTFPR

Clculo Numrico

Critrio de Parada Diferena relativa entre duas iteraes consecutivas. Define-se por diferena relativa a expresso: Mx. 1eien 0 k M R1 ! xik 1 xik xik 1 se xik 1 { 0

se xik 1

!

xik ! 0

xik 1 ! 0 k xi { 0

Fim do processo iterativo - valor de MRk+1 pequeno o bastante para a preciso desejada.Curso de Engenharia - UTFPR

Clculo Numrico

Exemplo: Resolva:

5x y z ! 5 3x 4 y z ! 6 3x 3 y 6z ! 0

Soluo:1 5 y z 5 1 y ! 6 3 x z 4 1 1 z ! 3 x 3 y z ! x y 6 2 x!

com

M

k

e 5 . 10 2 .

Curso de Engenharia - UTFPR

Clculo Numrico

xk-1 0,8 1,015 1,009 1,002

k Mx

yk0 0,65 0,92 0,985 0,998

k My

zk1 -0,725 -0,967 -0,997 -1

M zk2,379 0,250 0,030 0,003

k MR

2,25 0,212 0,006 0,007

1 0,293 0,066 0,0013

2,379 0,293 0,066 0,0013

x = 1,002

y = 0,998

z = -1

Verificao (substituio no sistema): 5.(1,002) + (0,998) + (-1) = 5,008 $ 5 3.(1,002) + 4.(0,998) + (-1) = 5,998 $ 6 3.(1,002) + 3.(0,998) + 6.(-1) = 0Curso de Engenharia - UTFPR

ok ok ok

Clculo Numrico

Mtodo de Gauss-Seidel -

Critrios de Convergncia

Processo iterativo a convergncia para a soluo exata no garantida para qualquer sistema. Existem certas condies que devem ser satisfeitas por um sistema de equaes lineares para se garantir a convergncia do mtodo. As condies podem ser determinadas por dois critrios: Critrio de Sassenfeld Critrio das Linhas.Curso de Engenharia - UTFPR

Clculo Numrico

Critrio de Sassenfeld Sejam as quantidades Fi dadas por:n 1 F1 ! a1 j a11 j ! 2

e

1 Fi ! aii

i 1 aij F j j !1

1 aij j !i n

para i = 2, 3, ..., n.n - ordem do sistema linear que se deseja resolver aij - so os coeficientes das equaes que compem o sistema.

Este critrio garante que o mtodo de Gauss-Seidel convergir para um dado sistema linear se a quantidade M, definida por:

M ! max F i1e i e n

for menor que 1 (M