Upload
others
View
4
Download
0
Embed Size (px)
Citation preview
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éricoMódulo III
2
◼ Motivação I
◼ Ocorrência em larga escala de sistemas linearesem 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 egeoambientais
◼ 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
◼ Grandes Comum para n > 100.000
◼ Esparsas Maioria dos coeficientes nulos
◼ Resolução de sistemas esparsos por métodosdiretos
◼ Processos de triangularização e fatoraçã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 desistemas 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 cheiaem matriz esparsa
◼ >>help full Conversão de matriz esparsaem matriz cheia
◼ Geração de Matrizes Esparsas:
◼ >>help sprand Geração de matriz esparsaaleatória
◼ >>help sparndsym Geração de matriz esparsasimétrica aleatória
Métodos Iterativos
6
◼ Métodos para Sistemas Esparsos no MATLAB
◼ >> help pcg Gradiente Conjugado
◼ >> help cgs Gradiente ConjugadoQuadrático (CGS)
◼ >> help bicg Gradiente BiConjugado (BiCG)
◼ >>help bicgstab Gradiente BiConjugadoEstabilizdo (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úmerosuficientemente 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 deerros de arredondamento do que o método de
Eliminação de Gauss.
◼ Lembretes importantes:
◼ Como todo processo iterativo, estes métodossempre 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 aconvergência destes métodos.
Métodos Iterativos
9
Métodos Iterativos
◼ Transformação do sistema linear Ax=b emx = 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;
◼ 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, x(0), obtém-se
consecutivamente os vetores:
o)aproximaçã ésima-(k ,gCxx
o)aproximaçã (segunda ,gCxx
o)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:
a11 x1 + a12 x2 + ... +a1n x2 = b1
obtém-se: x1 = (1/a11) (b1 - a12 x2 - ... -a1n x2)
e, analogamente,
x2 = (1/a22) (b2 - a21 x1 - ... -a2n xn)
xn = (1/ann) (bn - an1 x1 - ... - ann-1 xn-1)
Método de Gauss-Jacobi
12
▪ Método de Gauss-Jacobi
▪ Desta forma, para x = C x + g, obtém-se:
=
nn
n
33
3
22
2
11
1
a
b
a
b
a
b
a
b
g
−−−
−−−
−−−
−−−
=
0aaaaaa
aa0aaaa
aaaa0aa
aaaaaa0
C
nn3nnn2nnn1n
33n333323331
22n222232221
11n111131112
e
Método de Gauss-Jacobi
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
=
Método de Gauss-Jacobi
14
▪ Método de Gauss-Jacobi – Exemplo 13
▪ Seja o sistema:
▪ Determinação de C e g
6 10x 3x 2x
8 x 5x x
7 3x 2x x 10
321
321
321
=++
=++
=++
=
10
6
5
8
10
7
g
=
03/10 –1/5-1/5-01/5-3/10 -2/10 -0
C
Método de Gauss-Jacobi
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)
|x1(1) – x1
(0)| = 0,14
|x2(1) – x2
(0)| = 2,94
|x3(1) – x3
(0)| = 0,34
Método de Gauss-Jacobi
16
▪ Método de Gauss-Jacobi – Exemplo 13
▪ Assim:
e, analogamente:
=+=
0,0301,2440,150
g Cx x (1)(2) == 0,7315 1,244
0,91 d
(2)
r
0,19681,56400,4422
g Cx x (2)(3)
=+= == 0,2046 1,5640
0,32 d
(3)
r
Método de Gauss-Jacobi
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,5259
0,0647 d
(5)
r
Método de Gauss-Jacobi
18
Método de Gauss-Seidel
◼ Similarmente ao método de Gauss-Jacobi, conhecida a
estimativa inicial, x(0), obtém-se consecutivamente os
vetores x(1), x(2), ..., x(k)
▪ Todavia, ao se calcular xj(k+1), usa-se todos os valores
x1(k+1), x2
(k+1), ..., xj-1(k+1) que já foram calculados e os
valores xj+1(k), xj+2
(k), ..., xn(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
b x.a x.a x.a x.a x.a
b x.a x.a x.a x.a x.a
b x.a x.a x.a x.a x.a
=+++++
=+++++
=+++++
=+++++
−−
−−
−−
−−
Método de Gauss-Seidel
20
Método de Gauss-Seidel
◼ Descrição II
◼ Isolando xi a partir da linha i, tem-se:
( )
( )
( )
( )1n1nn22n11nn
nn
n
nn31n1n32322313
33
3
nn21n1n23231212
22
2
nn11n1n13132121
11
1
x.ax.ax.aba
1x
x.ax.ax.ax.aba
1x
x.ax.ax.ax.aba
1x
x.ax.ax.ax.aba
1x
−−
−−
−−
−−
−−−−=
−−−−−=
−−−−−=
−−−−−=
Método de Gauss-Seidel
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.aba
1x
x.ax.a...x.ax.aba
1x
x.ax.a...x.ax.aba
1x
x.ax.a...x.ax.aba
1x
+−−
+++
−−+++
−−++
−−+
−−−−=
−−−−−=
−−−−−=
−−−−−=
Método de Gauss-Seidel
22
Método de Gauss-Seidel
◼ Critério de Parada I
◼ Diferença relativa 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
Método de Gauss-Seidel
23
Método de Gauss-Seidel
◼ Critério de Parada II
◼ Fim do processo iterativo Valor de MRk+1
suficientemente pequeno para a precisão desejada
Método de Gauss-Seidel
24
▪ Método de Gauss-Seidel – Exemplo 14
▪ Resolver:
▪ Solução:
.10.5 M com,0z6y3x3
6zy4x3
5zyx5
2kR
−=++
=++
=++
( )
( )
( ) ( )yx2
1zy3x3
6
1z
zx364
1y
zy55
1x
+−=−−=
−−=
−−=
Método de Gauss-Seidel
25
▪ Método de Gauss-Seidel – Exemplo 14
▪ Quadro de resultados do processo iterativo
kxk
xM kyk
yM kzk
zM k
RM
-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
Método de Gauss-Seidel
26
▪ Método de Gauss-Seidel – Exemplo 14
▪ Verificação (substituição no sistema)
x = 1,002 y = 0,998 z = -1
5.(1,002) + 1.(0,998) + 1.(-1) = 5,008 5 OK3.(1,002) + 4.(0,998) + 1.(-1) = 5,998 6 OK
3.(1,002) + 3.(0,998) + 6.(-1) = 0 OK
Método de Gauss-Seidel
27
▪ Critérios de Convergência
▪ Processo iterativo Convergência para a soluçãoexata não garantida para qualquer sistema.
▪ Necessidade de determinação de certas condiçõesque 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
Método de Gauss-Seidel
28
▪ Critério de Sassenfeld I
▪ Sejam as quantidades i dadas por:
n - ordem do sistema linear que se deseja resolveraij - coeficientes das equações do sistema
Método de Gauss-Seidel
para i = 2, 3, ..., n
=
=
n
2j
j1
11
1 aa
1
+= +=
−
=
n
1ij
ij
1i
1j
jij
ii
i aaa
1e
29
▪ Critério de Sassenfeld II
▪ Este critério garante que o método de Gauss-Seidelconvergirá para um dado SEL se a quantidade M,definida por:
for menor que 1 (M<1).
Método de Gauss-Seidel
imaxM
ni1
=
30
▪ Critério de Sassenfeld III
▪ Exemplo 15: Seja A a matriz dos coeficientes e b ovetor dos termos constantes, dados por:
for menor que 1 (M<1).
444434241
334333231
224232221
114131211
b a a a a
b a a a a
b a a a a
b a a a a
( )
( )
( )
( )343242141
44
4
34232131
33
3
2423121
22
2
141312
11
1
aaaa
1
aaaa
1
aaaa
1
aaaa
1
++=
++=
++=
++=
Método de Gauss-Seidel
31
▪ Critério de Sassenfeld IV
▪ Exemplo 15: Seja A a matriz dos coeficientes e b ovetor 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 a
b a a a a
b a a a a
b a a a a
( )
( )
( )
( )343242141
44
4
34232131
33
3
2423121
22
2
141312
11
1
aaaa
1
aaaa
1
aaaa
1
aaaa
1
++=
++=
++=
++=
Método de Gauss-Seidel
32
▪ Critério de Sassenfeld V
▪ Exemplo 15:
Método de Gauss-Seidel
0,10x0,4x8,0x2,1x4,0
0,1x2,0xx2,0x1,0
8,7x3,0x6,0x3x6,0
4,0x2,0x2,0xx0,2
4321
4321
4321
4321
−=+++
=++−−
−=−−+
=+−+
33
( )
( )
( )
( ) 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
=++=
=++=
=++=
=++=
M < 1 Convergência dasoluçã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
A b
Método de Gauss-Seidel
▪ Critério de Sassenfeld VI
▪ Exemplo 15: Solução
7,0M imaxni1
==
34
Método de Gauss-Seidel
▪ 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
Método de Gauss-Seidel
▪ Critério das Linhas
▪ Exemplo 16: O SEL do Exemplo 14 satisfaz o Critériodas Linhas, sendo a verificação quase imediata, se forobservado que:
4,28,02,14,0aaa4a
5,02,02,01,0aaa1a
5,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 Sassenfeld quanto o Critériodas Linhas são condições suficientes, porém nãonecessárias, para a convergência do método deGauss-Seidel para um dado SEL
◼ Um dado SEL pode não satisfazer estes critérios eainda convergir
◼ Um sistema pode não satisfazer o Critério dasLinhas, porém sua convergência será garantida sesatisfizer o Critério de Sassenfeld
Considerações Finais
37
Método de Gauss-Seidel
▪ Critério das Linhas x Critério de Sassenfeld
▪ Exemplo 17: Seja o seguinte SEL:
▪ O Critério das Linhas não é satisfeito, visto que:
▪ Todavia, o Critério de Sassenfeld é satisfeito, umavez que:
18x2x6
23xx10
21
21
=+
=+
6a2a 2122 ==
( ) 3,01,062
1e1,01
10
121 ====
38
Método de Gauss-Seidel
▪ Critério das Linhas x Critério de Sassenfeld
▪ Exemplo 17: Assim sendo, a convergência do SEL é
garantida.
39
◼ Embora não altere a solução do SEL, a ordem deaparecimento das equações pode alterar suaconvergência pelo método da Gauss-Seidel.
◼ Exemplo 18: Seja o SEL:
◼ Observa-se que na ordem atual de aparecimento dasequações, o SEL não satisfaz o Critério das Linhas(verificar!!!); logo, sua convergência não é garantida.
◼ A inversão da ordem das duas equações do SEL fará comque o Critério das Linhas seja satisfeito e suaconvergência pelo método de Gauss-Seidel garantida(verificar também!!! ).
Considerações Finais
15x3x5
19x10x4
21
21
=+
=+−
40
◼ Ruggiero, M. A. Gomes & Lopes, V. L. da R. CálculoNumérico: Aspectos teóricos e computacionais.
MAKRON Books, 1996, 2ª ed.
◼ Asano, C. H. & Colli, E. Cálculo Numérico:Fundamentos e Aplicações. Departamento de
Matemática Aplicada – IME/USP, 2007.
◼ Sanches, I. J. & Furlan, D. C. Métodos Numéricos.DI/UFPR, 2006.
◼ Paulino, C. D. & Soares, C. Erros e Propagação deErros, Notas de aula, SE/ DM/ IST [Online]http://www.math.ist.utl.pt/stat/pe/qeb/semestre_1_2004-2005/PE_erros.pdf [Último acesso 07
de Junho de 2007].
Bibliografia