33
Cálculo Numérico Curso de Engenharia - UTFPR Sistemas Lineares – Métodos Iterativos

Sistemas Lineares – Métodos Iterativos

Embed Size (px)

DESCRIPTION

Calculo Numérico - métodos interativos

Citation preview

Page 1: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

Sistemas Lineares – Métodos Iterativos

Page 2: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

Profs.: Tina Andreolla(UTFPR)

Bruno Correia da Nóbrega Queiroz (UFCG)José Eustáquio Rangel de Queiroz(UFCG)Marcelo Alves de Barros(UFCG)

Sistemas de Equações Lineares (SEL ) – Parte

II

Sistemas de Equações Lineares (SEL ) – Parte

II

Page 3: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

• É bastante comum encontrar sistemas lineares que envolvem uma grande porcentagem de coeficientes nulos.

• Esses sistemas são chamados de sistemas esparsos.

• Para esses tipos de sistemas, o método de Eliminação de Gauss não é o mais apropriado, pois ele não preserva essa esparsidade, que pode ser útil por facilitar a resolução do sistema.

• Método mais apropriado para esse tipo de sistema métodos iterativo de Gauss-Seidel.

Page 4: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

Métodos Iterativos

Page 5: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

• Métodos Iterativos: Consistem em encontrar uma seqüência de estimativas xi

k (dada uma estimativa inicial xi0)

que após um número suficientemente grande de iterações convirja para a solução do sistema de equações.

nnnn x x x x

x x x x

x x x x

x x x x

x x x x

210

424

14

04

323

13

03

222

12

02

121

11

01

Page 6: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

• Outra vantagem destes métodos não são tão suscetíveis ao acúmulo de erros de arredondamento como o método de Eliminação de Gauss.

• É importante lembrar que:

– Como todo processo iterativo, estes métodos sempre apresentarão um resultado aproximado, que será tão próximo do resultado real conforme o número de iterações realizadas.

– Além disso, também é preciso ter cuidado com a convergência desses métodos.

Page 7: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

Métodos Iterativos

• Transforma o sistema linear Ax=b em x = Cx +g

– A: matriz dos coeficientes, n x m– x: vetor das variáveis, n x 1;– b: vetor dos termos constantes, n x 1.

• Métodos utilizados:– Gauss-Jacobi– Gauss-Seidel

C: matriz n x n

g: vetor n x 1

Page 8: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

Método de Gauss-Jacobi

• Conhecido x(0) (aproximação inicial) obtém-se

consecutivamente os vetores:

etc. o),aproximaçã (segunda ,

o)aproximaçã (primeira ,)()(

)()(

gCxx

gCxx

12

01

De um modo geral, a aproximação x(k+1) é calculada pela fórmula

x(k+1) = C x(k)+g, k=0, 1, ...

Page 9: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

Método de Gauss-Jacobi

Da primeira equação do sistema

a11 x1 + a12 x2 + ... +a1n x2 = b1

obtém-se

x1 = (1/a11) (b1 - a12 x2 - ... -a1n x2)analogamente

x2 = (1/a22 (b2 - a21 x1 - ... -a2n xn) . .

. .

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

)

Page 10: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

Método de Gauss-Jacobi

Desta forma para x = C x + g

0 - a12 /a11 ... - a1n /a11

- a21 /a22 0 ... - a2n /a22

. . .

- an1 /ann - an2 /ann 0

C =

g = ( b1 /a11 b2 /a22 . . . bn /ann ) -1

Page 11: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

Método de Gauss-Jacobi - Critério de parada

Distância entre duas iterações

d(k) = max xi(k) - xi

(k-1)

Critério de parada

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

(k) ) <

Page 12: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

Método de Gauss-Jacobi - EXEMPLO

Seja o sistema 10 x1 + 2x2 + x3 = 7

x1 + 5x2 + x3 = -8

2x1 + 3x2 + 10x3 = 6

C = 0 - 2/10 -

1/10

-1/5 0 - 1/5

-1/5 – 3/10 0

g =

-7/10

8/5

-6/10

Page 13: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

Método de Gauss-Jacobi - EXEMPLO

C = 0 - 2/10 -

1/10

-1/5 0 - 1/5

-1/5 – 3/10 0

g =

-7/10

8/5

-6/10

Com x0 = 0,7

-1,6

0,6

e = 0,05

Page 14: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

Método de Gauss-Jacobi - EXEMPLO

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

0,96

-1,86

0,94

= 0,05

|x1(1) – x1

(0)| = 0,26

|x2(1) – x2

(0)| = 0,26

|x3(1) – x3

(0)| = 0,34

dr(1) = 0,34/ (max xi(1) )

= 0,1828 >

Page 15: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

Método de Gauss-Jacobi - EXEMPLO

x(2) =

0,978

-1,98

0,966

= 0,05

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

x(3) = 0,9997

-1,9888

0,984

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

Page 16: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

Método de Gauss-Seidel

• Conhecido x(0) (aproximação inicial) obtém-se x1, x2, ...xk.

• Ao se calcular usa-se todos os valores

que já foram calculados e

os valores restantes.

1kjx

11

11

kj

k xx ,...,

kn

kj xx ,...,1

Page 17: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

Descrição do Método

• Seja o seguinte sistema de equações:

nnnnnnnnnn

nnnn

nnnn

nnnn

bxaxaxaxaxa

bxaxaxaxaxa

bxaxaxaxaxa

bxaxaxaxaxa

. . ... . . .

. . ... . . .

. . ... . . .

. . ... . . .

11321

313113333232131

212112323222121

111111313212111

1321

Métodos Iterativos – Gauss Seidel

Page 18: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

• Isolando xi a partir da linha i, tem-se:

1121

3113232231333

3

2112323121222

2

1111313212111

1

21

1

1

1

1

nnnnnnnn

n

nnnn

nnnn

nnnn

xaxaxaba

x

xaxaxaxaba

x

xaxaxaxaba

x

xaxaxaxaba

x

......

....

....

....

,

,

,

,

Page 19: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

• O processo iterativo é obtido a partir das equações, fazendo:

111,

122

111

1

311,31

2321

131333

13

211,23231

121222

12

111,1313212111

11

......1

.......1

.......1

.......1

knnn

kn

knn

nn

kn

knn

knn

kkk

knn

knn

kkk

knn

knn

kkk

xaxaxaba

x

xaxaxaxaba

x

xaxaxaxaba

x

xaxaxaxaba

x

Page 20: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

Critério de Parada

– Diferença relativa entre duas iterações consecutivas. – Define-se por diferença relativa a expressão:

– Fim do processo iterativo - valor de MRk+1 pequeno o bastante para a precisão

desejada.

se 1

0

0

0

0

0

1

1

11

1

11

ki

ki

ki

ki

kik

i

ki

ki

x

x

xxse

xsex

xx

M

Máxni

kR

.

Page 21: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

Exemplo: Resolva:

.10.5

0633

643

55

2

kRMcom

zyx

zyx

zyx

Solução:

Page 22: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

kx kxM

ky kyM

kz kzM

kRM

-1 - 0 - 1 - -

0,8 2,25 0,65 1 -0,725 2,379 2,379

1,015 0,212 0,92 0,293 -0,967 0,250 0,293

1,009 0,006 0,985 0,066 -0,997 0,030 0,066

1,002 0,007 0,998 0,0013 -1 0,003 0,0013

x = 1,002 y = 0,998 z = -1 Verificação (substituição no sistema): 

5.(1,002) + (0,998) + (-1) = 5,008 5 ok3.(1,002) + 4.(0,998) + (-1) = 5,998 6 ok3.(1,002) + 3.(0,998) + 6.(-1) = 0 ok

Page 23: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

Método de Gauss-Seidel - Critérios de Convergência

• Processo iterativo a convergência para a solução exata não é garantida para qualquer sistema.

• Existem certas condições que devem ser satisfeitas por um sistema de equações lineares para se garantir a convergência do método.

• As condições podem ser determinadas por dois critérios:– Critério de Sassenfeld– Critério das Linhas.

Page 24: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

Critério de Sassenfeld

• Sejam as quantidades i dadas por:

para i = 2, 3, ..., n.

n

jja

a 21

111

1

n

ijij

i

jjij

iii aa

a 1

1

1

1 e

n - ordem do sistema linear que se deseja resolveraij - são os coeficientes das equações que compõem o sistema.

Este critério garante que o método de Gauss-Seidel convergirá

para um dado sistema linear se a quantidade M, definida por:

ini

M max1

for menor que 1 (M<1).

Page 25: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

• Exemplo: Seja A, a matriz dos coeficientes e b o vetor dos termos constantes dados por:

444434241

334333231

224232221

114131211

baaaa

baaaa

baaaa

baaaa

34324214144

4

3423213133

3

242312122

2

14131211

1

1

1

1

1

aaaa

aaaa

aaaa

aaaa

Critério de Sassenfeld

Page 26: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

         Exemplo: Mostre que a solução do sistema linear dado pelas equações:

0104802140

01202010

873060360

4020202

4321

4321

4321

4321

....

....

....

...

xxxx

xxxx

xxxx

xxxx

convergirá pelo método de Gauss-Seidel.

Critério de Sassenfeld

Page 27: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

• Solução: critério de Sassenfeld– calcular os valores das quantidades i.

2736.0358.08.044.02.17.04.04

1

358.02.044.02.07.01.01

1

44.03.06.07.06.03

1

7.02.02.012

1

4

3

2

1

7.0max41

ii

M M é menor que 1 a solução desse sistema irá convergir usando o método de Gauss-Seidel.

Critério de Sassenfeld

10.0- 4.0 0.8 1.2 0.4

1.0 0.2 1.0 0.2- 0.1-

7.8- 0.3- 0.6- 3.0 0.6

0.4 0.2 0.2- 1.0 2.0

A B

Page 28: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

Critério das Linhas

• Segundo esse critério, um determinado sistema irá convergir pelo método de Gauss-Seidel, se:

ii

n

ijj

ij aa 1

, para i=1, 2, 3, ..., n.

Page 29: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

Exemplo: O sistema do exemplo anterior satisfaz o critério das linhas e essa verificação pode ser feita de maneira quase imediata, observando-se que:

4.28.02.14.04

5.02.02.01.01

5.13.06.06.03

4.12.02.012

43424144

34323133

24232122

14131211

aaaa

aaaa

aaaa

aaaa

0104802140

01202010

873060360

4020202

4321

4321

4321

4321

....

....

....

...

xxxx

xxxx

xxxx

xxxx

ii

n

ijj

ij aa 1

para i=1, 2, 3, 4.

Critério das Linhas

Page 30: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

É importante saber que:

• Os Critérios são condições suficientes, porém não necessárias, para a convergência do método de Gauss-Seidel para um dado sistema linear Isso significa que um sistema pode não satisfazer esses critérios e ainda convergir.

• Um sistema pode não satisfazer o critério das linhas e satisfazer o critério de Sassenfeld, o que garantirá sua convergência.

Considerações Finais

Page 31: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

Exemplo:

Seja o sistema: 1826

2310

21

21

xx

xx

Note que esse sistema não satisfaz o critério das linhas, pois:

62 2122 aa

porém, ele satisfaz o critério de Sassenfeld:

3.01.062

1

1.0110

1

2

1

13.0max41

ii

M

Convergência garantida.

Considerações Finais

Page 32: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

Outra observação importante

– A ordem com que as equações aparecem no sistema.

– Apesar da ordem das equações não alterar a solução do sistema, ela pode alterar a convergência do mesmo pelo método da Gauss-Seidel.

Considerações Finais

Page 33: Sistemas Lineares – Métodos Iterativos

Cálculo Numérico

Curso de Engenharia - UTFPR

Considerações FinaisExemplo:

Seja o sistema:1535

19104

21

21

xx

xx

Na forma como o sistema está representado, ele não satisfaz o critério das linhas (verifique isso), portanto sua convergência não é garantida.

Porém, trocando-se a ordem das duas equações, o sistema satisfaz esse critério, e sua convergência pelo método de Gauss-Seidel é garantida (verifique isso também).