Profs.: Bruno Correia da Nóbrega Queiroz José Eustáquio Rangel de Queiroz Marcelo Alves de Barros Sistemas de Equações Lineares (SEL ) – Parte II Cálculo

Profs.: Bruno Correia da Nóbrega Queiroz

José Eustáquio Rangel de Queiroz

Marcelo Alves de Barros

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

II

Cálculo NuméricoCálculo NuméricoMódulo IIIMódulo III

2

Motivação I Ocorrência em larga escala de sistemas

lineares em cálculos de Engenharia e modelagem científica Exemplos:

Simulações de processos químicos Simulações de dispositivos e circuitos Modelagem de processos geocientíficos e

geoambientais Análise estrutural Biologia estrutural Modelagem de processos físicos

Métodos Iterativos

3

Motivação II Tendência à existência de matrizes de

coeficientes à grandes e esparsas GrandesGrandes Comum para n > 100.000n > 100.000 EsparsasEsparsas Maioria dos coeficientes nulosnulos

Resolução de sistemas esparsos por métodos diretosdiretos Processos de triangularizaçãotriangularização e fatoraçãofatoração

Onerosos, por não preservarem a esparsidade original, que pode ser útil por facilitar a resolução do sistema.

Métodos Iterativos

4

Motivação III Métodos mais apropriados para a resolução de

sistemas de natureza esparsa Métodos iterativos

Gauss-Jacobi Gauss-Seidel

Métodos Iterativos

5

Sistemas Esparsos no MATLAB >>help issparse Teste de esparsidade >>help sparse Conversão de matriz

cheia em matriz esparsa >>help full Conversão de matriz

esparsa em matriz cheia Geração de Matrizes Esparsas:

>>help sprand Geração de matriz esparsa aleatória

>>help sparndsym Geração de matriz esparsa simétrica aleatória

Métodos Iterativos

6

Métodos para Sistemas Esparsos no MATLAB >> help pcg Gradiente Conjugado >> help cgs Gradiente Conjugado

Quadrático (CGS) >> help bicg Gradiente BiConjugado

(BiCG) >>help bicgstab Gradiente BiConjugado

Estabilizdo (BiCGSTAB) >>help gmres Resíduo Mínimo

Generalizado (GMRES) >>help qmr Resíduo Quase Mínimo

(QMR)

Métodos Iterativos

7

A partir de uma estimativa inicial xi0, consistem

em encontrar uma seqüência de estimativas xik

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

Métodos Iterativos

)0(n

)0(3

)0(2

)0(1

x

x

x

x

)1(n

)1(3

)1(2

)1(1

x

x

x

x

)2(n

)2(3

)2(2

)2(1

x

x

x

x

)k(n

)k(3

)k(2

)k(1

x

x

x

x

8

Vantagem Menos suscetíveis ao acúmulo de erros de arredondamento do que o método de Eliminação de Gauss.

Lembretes importantes: 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 disto, também é preciso ter cuidado com a convergência destes métodos.

Métodos Iterativos

9

Métodos Iterativos Transformação do sistema linear AxAx==bb em

xx = = Cx Cx ++gg A: matriz dos coeficientes, n x m x: vetor das variáveis, n x 1; b: vetor dos termos constantes, n x 1; C: matriz, n x n; e g: vetor, n x 1.

Métodos a estudar Gauss-Jacobi Gauss-Seidel

Sistemas de Equações Lineares

10

Método de Gauss-Jacobi Conhecida a estimativa inicial, xx(0)(0), obtém-se

consecutivamente os vetores:

o)aproximaçã ésima-(k ,gCxx

o)aproximaçã (segunda ,gCxxo)aproximaçã (primeira ,gCxx

)1k()k(

)1()2(

)0()1(

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

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

Método de Gauss-Jacobi

11

Método de Gauss-Jacobi Da primeira equação do sistema: aa1111 x x11 + a + a1212 x x22 + ... +a + ... +a1n1n x x22 = b = b11

obtém-se: xx11 = (1/a = (1/a1111) (b) (b11 - a - a12 12 xx22 - ... -a - ... -a1n1n x x22))e, analogamente, xx22 = (1/a = (1/a2222) (b) (b22 - a - a21 21 xx11 - ... -a - ... -a2n2n x xnn))

xxnn = (1/a = (1/annnn) (b) (bnn - a - an1 n1 xx11 - ... - a - ... - ann-1nn-1 x xn-1n-1))


12

Método de Gauss-Jacobi Desta forma, para x = C x + g, obtém-se:

nn

n

33

3

22

2

11

1

ab

ababab

g

0aaaaaa

aa0aaaa

aaaa0aa

aaaaaa0

C

nn3nnn2nnn1n

33n333323331

22n222232221

11n111131112

e


13

Método de Gauss-Jacobi Distância entre duas iterações

Critério de Parada

x - x max d 1)-(ki

(k)i

(k)

x max

d d )k(

i

(k)(k)r


14

Método de Gauss-Jacobi – Exemplo 13 Seja o sistema:

Determinação de CC e gg6 10x 3x 2x 8 x 5x x 7 3x 2x x 10

321

321

321

10658

107

g

03/10 –1/5-1/5-01/5-3/10 -2/10 -0C


15

Método de Gauss-Jacobi – Exemplo 13 Assim, considerando como estimativa inicial:

e = 0,05, obtém-se:

e

0,61,6-0,7

x0

0,941,340,84

g Cx x (0)(1)||xx11

(1)(1) – x – x11(0)(0)|| = 0,14 = 0,14

||xx22(1)(1) – x – x22

(0)(0)|| = 2,94 = 2,94||xx33

(1)(1) – x – x33(0)(0)|| = 0,34 = 0,34


16

Método de Gauss-Jacobi – Exemplo 13 Assim:

e, analogamente:

0,0301,2440,150

g Cx x (1)(2) 0,7315 1,2440,91 d (2)

r

0,19681,56400,4422

g Cx x (2)(3)

0,2046 1,5640

0,32 d (3)r


17

Método de Gauss-Jacobi – Exemplo 13 Igualmente:

e, finalmente:

0,04241,47220,3282

g Cx x (3)(4) 0,1049 1,4722 0,1544 d (4)

r

0,09271,52590,3929

g Cx x (4)(5) 0,0424 1,52590,0647 d (5)

r


18

Método de Gauss-Seidel Similarmente ao método de Gauss-Jacobi, conhecida

a estimativa inicial, xx(0)(0), obtém-se consecutivamente os vetores xx(1)(1), x x(2)(2), ..., xx(k)(k)

Todavia, ao se calcular xj(k+1), usa-se todos os valores

xx1(k+1)(k+1), x x2

(k+1)(k+1), ..., xxj-1(k+1)(k+1) que já foram calculados e os

valores xxj+1(k)(k), x xj+2

(k)(k), ..., xxn(k) (k) restantes.

Método de Gauss-Seidel

19

Método de Gauss-Seidel Descrição I

Seja o seguinte sistema de equações:

nnnn1n1nn33n22n11n

3nn31n1n3333232131

2nn21n1n2323222121

1nn11n1n1313212111

b x.a x.a x.a x.a x.a





20

Método de Gauss-Seidel Descrição II

Isolando xxii a partir da linha i i, tem-se:

1n1nn22n11nnnn

n

nn31n1n3232231333

3

nn21n1n2323121222

2

nn11n1n1313212111

1

x.ax.ax.aba1x

x.ax.ax.ax.aba1x

x.ax.ax.ax.aba1x

x.ax.ax.ax.aba1x


21

Método de Gauss-Seidel Descrição III

O processo iterativo se dá a partir das equações:

1k1n1n,n

1k22n

1k11nn

nn

1kn

knn3

k1n1n,3

1k232

1k1313

33

1k3

knn2

k1n1n,2

k323

1k1212

22

1k2

knn1

k1n1n,1

k313

k2121

11

1k1

x.a...x.ax.aba1x

x.ax.a...x.ax.aba1x

x.ax.a...x.ax.aba1x

x.ax.a...x.ax.aba1x


22

Método de Gauss-Seidel Critério de Parada I

Diferença relativarelativa entre duas iterações consecutivas, dada por:

0 x

0 x se , 1

0 x x se , 0

0 x se , x

xx .Máx

M

ki

1ki

ki

1ki

1ki1k

i

ki

1ki

ni1

1kR


23

Método de Gauss-Seidel Critério de Parada II

Fim do processo iterativo Valor de MMRRk+1k+1

suficientemente pequenosuficientemente pequeno para a precisão desejada


24

Método de Gauss-Seidel – Exemplo 14 Resolver:

Solução: .10.5 M com,0z6y3x3

6zy4x35zyx5

2kR


25

Método de Gauss-Seidel – Exemplo 14 Quadro de resultados do processo iterativo

kx kxM

ky kyM kz k

zMkRM

-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 = -1x = 1,002 y = 0,998 z = -1


26

Método de Gauss-Seidel – Exemplo 14 Verificação (substituição no sistema)x = 1,002 y = 0,998 z = -1x = 1,002 y = 0,998 z = -1

5.(1,002) + 1.(0,998) + 1.(-1) = 5,008 5OK

3.(1,002) + 4.(0,998) + 1.(-1) = 5,998 6OK

3.(1,002) + 3.(0,998) + 6.(-1) = 0 OK


27

Critérios de Convergência Processo iterativo Convergência para a

solução exata nãonão garantida para qualquer sistema.

Necessidade de determinação de certas condições que devem ser satisfeitas por um SEL para a garantia da convergência do método.

Critérios de determinação das condições de convergência Critério de Sassenfeld Critério das Linhas


28

Critério de Sassenfeld ISassenfeld I Sejam as quantidades ii dadas por:

nn - ordem do sistema linear que se deseja resolver

aij - coeficientes das equações do sistema


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

n

2jj1

111 aa

1

n

1ijij

1i

1jjij

iii aaa

1e

29

Critério de Sassenfeld IISassenfeld II Este critério garante que o método de Gauss-

Seidel convergirá para um dado SEL se a quantidade MM, definida por:

for menor que 11 (M<1M<1).


30

Critério de Sassenfeld IIISassenfeld III Exemplo 15: Seja AA a matriz dos coeficientes e

bb o vetor dos termos constantes, dados por:

for menor que 11 (M<1M<1).

444434241

334333231

224232221

114131211

b a a a ab a a a ab a a a ab a a a a

34324214144

4

3423213133

3

242312122

2

14131211

1

aaaa1

aaaa1

aaaa1

aaaa1


31

Critério de Sassenfeld IVSassenfeld IV Exemplo 15: Seja AA a matriz dos coeficientes e

bb o vetor dos termos constantes, dados por:

Mostrar que a solução do SEL a seguir convergirá pelo método de Gauss-Seidel.

444434241

334333231

224232221

114131211

b a a a ab a a a ab a a a ab a a a a

34324214144

4

3423213133

3

242312122

2

14131211

1

aaaa1

aaaa1

aaaa1

aaaa1


32

Critério de Sassenfeld VSassenfeld V Exemplo 15:


0,10x0,4x8,0x2,1x4,00,1x2,0xx2,0x1,0

8,7x3,0x6,0x3x6,04,0x2,0x2,0xx0,2

4321

4321

4321

4321

33

2736,0358,08,044,02,17,04,041

358,02,044,02,07,01,011

44,03,06,07,06,031

7,02,02,0121

4

3

2

1

M < 1M < 1 Convergência da solução do sistema a partir do método de Gauss-Seidel

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

AA bb


Critério de Sassenfeld VISassenfeld VI Exemplo 15: Solução

34


Critério das Linhas Segundo este critério, um determinado sistema

irá convergir pelo método de Gauss-Seidel, se:

n. ..., 3, 2, 1,i para ,aa ii

n

ij1j

ij

35


Critério das Linhas Exemplo 16: O SEL do Exemplo 14 satisfaz o

Critério das Linhas, sendo a verificação quase imediata, se for observado que:

4,28,02,14,0aaa4a5,02,02,01,0aaa1a5,13,06,06,0aaa3a

4,12,02,01aaa2a

43424144

34323133

24232122

14131211

4. 3, 2, 1,i para aa ii

n

ij1j

ij

36

Tanto o Critério de SassenfeldCritério de Sassenfeld quanto o Critério das LinhasCritério das Linhas são condições suficientessuficientes, porém nãonão necessáriasnecessárias, para a convergência do método de Gauss-Seidel para um dado SEL Um dado SEL pode nãonão satisfazer estes critérios

e aindaainda convergir Um sistema pode nãonão satisfazer o Critério das Critério das

LinhasLinhas, porém sua convergência será garantida se satisfizer o Critério de SassenfeldCritério de Sassenfeld

Considerações Finais

37


Critério das Linhas x Critério de Sassenfeld Exemplo 17: Seja o seguinte SEL:

O Critério das LinhasCritério das Linhas nãonão é satisfeitosatisfeito, visto que:

Todavia, o Critério de SassenfeldCritério de Sassenfeld é satisfeitosatisfeito, uma vez que:

18x2x623xx10

21

21

6a2a 2122

3,01,0621e1,0110

121

38


Critério das Linhas x Critério de Sassenfeld Exemplo 17: Assim sendo, a convergência do

SEL é garantidagarantida.

39

Embora não altere a solução do SEL, a ordem de aparecimento das equações pode alterar sua convergência pelo método da Gauss-Seidel. Exemplo 18: Seja o SEL:

Observa-se que na ordem atual de aparecimento das equações, o SEL não satisfaz o Critério das LinhasCritério das Linhas (verificar!!!verificar!!!); logo, sua convergência nãonão é garantidagarantida.

A inversão da ordem das duas equações do SEL fará com que o Critério das LinhasCritério das Linhas seja satisfeitosatisfeito e sua convergência pelo método de Gauss-Seidel garantidagarantida (verificar também!!!verificar também!!! ).

Considerações Finais

15x3x519x10x4

21

21

40

Ruggiero, M. A. Gomes & Lopes, V. L. da R. Ruggiero, M. A. Gomes & Lopes, V. L. da R. Cálculo Numérico: Aspectos teóricos e Cálculo Numérico: Aspectos teóricos e computacionaiscomputacionais. MAKRON Books, 1996, 2. MAKRON Books, 1996, 2ªª ed. ed.

Asano, C. H. & Colli, E. Asano, C. H. & Colli, E. Cálculo Numérico: Cálculo Numérico: Fundamentos e AplicaçõesFundamentos e Aplicações. Departamento de . Departamento de Matemática Aplicada – IME/USP, 2007.Matemática Aplicada – IME/USP, 2007.

Sanches, I. J. & Furlan, D. C. Sanches, I. J. & Furlan, D. C. Métodos Métodos NuméricosNuméricos. DI/UFPR, 2006.. DI/UFPR, 2006.

Paulino, C. D. & Soares, C. Erros e Propagação Paulino, C. D. & Soares, C. Erros e Propagação de Erros, de Erros, Notas de aulaNotas de aula, SE/ DM/ IST , SE/ DM/ IST [Online] [Online] http://www.math.ist.utl.pt/stat/pe/qeb/semesthttp://www.math.ist.utl.pt/stat/pe/qeb/semestre_1_2004-2005/PE_erros.pdfre_1_2004-2005/PE_erros.pdf [Último acesso [Último acesso 07 de Junho de 2007].07 de Junho de 2007].

Bibliografia

Documents

Profs.: Bruno Correia da Nóbrega Queiroz José Eustáquio Rangel de Queiroz Marcelo Alves de Barros Sistemas de Equações Lineares (SEL ) – Parte II Cálculo