calculo numerico2

Prévia do material em texto

1
CCáálculo Numlculo Numééricorico
Resolução Numérica de
Sistemas Lineares – Parte 
II
Prof. Jorge Cavalcanti – jorge.cavalcanti@univasf.edu.br
MATERIAL ADAPTADO DOS SLIDES DA DISCIPLINA CÁLCULO 
NUMÉRICO DA UFCG - www.dsc.ufcg.edu.br/~cnum/
2
� É 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. 
� Maneira mais apropriado para esse tipo de sistema ⇒
métodos iterativos
Sistemas Lineares – Métodos Iterativos
3
� Consistem em encontrar uma seqüência de estimativas xik
(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.
Métodos Iterativos
nnnn x x x x
 
 x x x x
 x x x x
 x x x x
 x x x x
210
4
2
4
1
4
0
4
3
2
3
1
3
0
3
2
2
2
1
2
0
2
1
2
1
1
1
0
1
MMMM
→→→
4
� 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.
Métodos Iterativos
5
� 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
Métodos Iterativos
6
Método de Gauss-Jacobi
� Conhecido x(0) (aproximação inicial) obtém-se 
consecutivamente os vetores:
etc. o),aproximaçã (segunda gCxx
o)aproximaçã (primeira gCxx
,
,
)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, ...
� São geradas novas aproximações até que um dos 
critérios de parada seja satisfeito:
• Máx xi(k+1) - xi(k)  ≤ εεεε (Tolerância), com 1 ≤i ≤n, ou:
• k > M, com M=Número máximo de iterações
7
Método de Gauss-Jacobi
� Da primeira equação do sistema
a11 x1 + a12 x2 + ... +a1n x2 = b1
obtém-se x1 = b1 - ( a12 x2 + a13 x3 ... +a1n xn)
a11
analogamente x2 = b2 – (a21 x1 + a23 x3 + ... + a2n xn)
a22
Ou: xn = (1/ann) (bn - an1 x1 - ... - an,n-1 xn-1 )
8
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 ) T
xn = (1/ann) (bn - an1 x1 - ... - an,n-1 xn-1 )
9
Método de Gauss-Jacobi
� Então como x = C x + g
g = (b1 /a11 b2 /a22 . . . bn /ann ) T
- a21 /a22 0 ... - a2n /a22
. . .
- an1 /ann - an2 /ann 0








C = 
0 - a12 /a11 ... - a1n /a11
x1(k+1) = (1/a11)(b1 - a12 x2(k) - ... -a1nxn(k))
x2(k+1) = (1/a22)(b2 - a21 x1(k) - ... -a2n xn(k))
...
xn(k+1) = (1/ann)(bn - an1 x1(k) - .. - an,n-1 xn-1(k))
x = 
10
Método de Gauss-Jacobi – EXEMPLO 1
� Seja o sistema 10 x1 + 2x2 + 3x3 = 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
- a21 /a22 0 ... - a2n /a22
. . .
- an1 /ann - an2 /ann 0








C = 
0 - a12 /a11 ... - a1n /a11
e εεεε = 0,05
11
Método de Gauss-Jacobi – EXEMPLO 1
x1(k+1) = (1/a11)(b1 - a12 x2(k) - ... -a1nxn(k))
x2(k+1) = (1/a22)(b2 - a21 x1(k) - ... -a2n xn(k))
...
xn(k+1) = (1/ann)(bn - an1 x1(k) - .. - an,n-1 xn-1(k))
x1(k+1) = (1/10)(7 - 2x2(k) –x3(k)) =(0x1(k) – 0.2x2(k) –0.1x3(k) +0,7)
x2(k+1) = (1/5)(-8 - x1(k) –x3(k)) =(-0.2x1(k) – 0x2(k) –0.2x3(k) – 1.6)
x3(k+1) = (1/10)(6 - 2x1(k) -3x2(k) =(-0.2x1(k) – 0.3x2(k) –0x3(k)+ 0.6)
� O Processo iterativo é: 
Equações de Iteração
12
Método de Gauss-Jacobi – EXEMPLO 1
Com x0 = 
0,7 
-1,6
0,6








x1(k+1) = 0x1(k) – 0.2x2(k) –0.1x3(k) +0,7 = -0.2(-1.6)-0.1(0.6)+0,7=0.96
x2(k+1) = -0.2x1(k) – 0x2(k) –0.2x3(k) – 1.6 = -0.2(0.7)-0.2(0.6)-1.6=-1.86
x3(k+1) =-0.2x1(k) – 0.3x2(k) –0x3(k) – 0.6=-0.2(0.7)-0.3(-1.6)+0.6=0.94
Para k=0: 
Obs: X0 estimado por (bn/ann), muito embora possa ser adotado 
qualquer valor inicial, como por exemplo x0 = [0 0 0]T
Obtemos então: 
x(1) = Cx(0) + g = 
0,96 
-1,86
0,94
13
Método de Gauss-Jacobi – EXEMPLO 1
Avaliando o critério de parada para εεεε = 0,05 :
|x1(1) – x1(0)| = 0,26
|x2(1) – x2(0)| = 0,26
|x3(1) – x3(0)| = 0,34
Máx  xi(k+1) - xi(k) = 0,34 > εεεε
• Máx xi(k+1) - xi(k)  ≤ εεεε (Tolerância), com 1 ≤i ≤n, ou:
x1(2) = 0x1(1) – 0.2x2(1) –0.1x3(1) +0,7 = -0.2(-1.86)-0.1(0.94)+0,7=0.978
x2(2) = -0.2x1(1) – 0x2(1) –0.2x3(1) – 1.6 = -0.2(0.96)-0.2(0.94)-1.6=-1.98
x3(2) =-0.2x1(1) – 0.3x2(1) –0x3(1) – 0.6=-0.2(0.96)-0.3(-1.86)+0.6=0.966
Prosseguindo com as iterações, para k=1: 
x(1) = Cx(0) + g = 
0,96 
-1,86
0,94
14
Método de Gauss-Jacobi – EXEMPLO 1
x(2) =
0,978 
-1,98
0,966








x(3) =
0,9997 
-1,9888
0,984








|x1(2) – x1(1)| = 0,018
|x2(2) – x2(1)| = 0,12
|x3(2) – x3(1)| = 0,026
Máx  xi(k+1) - xi(k) = 0,12 > εεεε
|x1(3) – x1(2)| = 0,0021
|x2(3) – x2(3)| = 0,008
|x3(3) – x3(2)| = 0,018
Máx  xi(k+1) - xi(k) = 0,018 < εεεε
Para k=2: 
x* =
0,9997 
-1,9888
0,984








15
Método de Gauss-Jacobi – Resumindo:
1. Escolhe-se a aproximação inicial x(0):
• x(0) = [x1(0), x2(0), ..., xn(0)]T
2. Calculam-se as aproximações sucessivas x(k), a partir da 
iteração:
• x(k+1) = Cx(k) + g
3. Continua-se a gerar aproximações até que um dos critérios de 
parada seja satisfeito:
• Máx xi(k+1) - xi(k)  ≤ εεεε (Tolerância), com 1 ≤i ≤n, ou:
• K > M, com M=Número máximo de iterações
• Observar que os elementos do sistema original aii ≠≠≠≠ 0, ∀∀∀∀i. Caso isso não 
ocorra, deve-se reorganizar as equações para que se consiga essa condição.
• É importante também que na diagonal principal estejam os maiores valores 
absolutos, para acelerar o processo de convergência e dar mais precisão ao 
resultado final.
16
Método de Gauss-Jacobi – EXEMPLO 2
� Resolver o sistema abaixo, com εεεε ≤ 10-2 ou k >10:
2x1 - x2 = 1
x1 + 2x2 = 3
� Encontrando as equações de iteração:
� 2x1 = 1+x2 ⇒ x1 = ½(1+x2)
� 2x2 = 3-x1 ⇒ x2 = ½(3 - x1)
� Então:
� x1(k+1) = ½(1+x2(k))
� x2(k+1) = ½(3-x1(k)), k= 0, 1, 2, ….n
17
Método de Gauss-Jacobi – EXEMPLO 2
� Fazendo x(0) = [ 0 0 ]T como solução inicial:
� Então, para k=0:
� x1(k+1) = ½(1+x2(k))
x1(1) = ½(1+x2(0)) = ½(1 + 0) = 0,5
� x2(k+1) = ½(3-x1(k))
x2(1) = ½(3-x1(0)) = ½(3 - 0) = 1,5
� Para k=1:
� x1(2) = ½(1+x2(1)) = ½(1 + 1,5) = 1,25
� x2(2) = ½(3-x1(1)) = ½(3 – 0,5) = 1,25
ε = Máx xi(k+1) - xi(k) ≤ εεεε = |1,25 – 0,5| = 0,75 > 10-2
18
Método de Gauss-Jacobi – EXEMPLO 2
� Para k=2:
� x1(3) = ½(1+x2(2))
x1(3) = ½(1 + 1,25) = 1,125
� x2(3) = ½(3-x1(2))
x2(3) = ½(3-x1(2)) = ½(3 – 1,25) = 0,875
ε = | 0,875 - 1,25 | = 0,375 > 10-2
19
Método de Gauss-Jacobi - EXEMPLO
0,0061,0020,9989
0,0120,9960,9968
0,0230,9921,0087
0,0471,0161,0166
0,0941,0310,9695
0,1880,9380,9384
0,3750,8751,1253
0,7501,2501,2502
1,5001,5000,5001
-000
εX2(k)x1(k)k
� Prosseguindo com as iterações para k=3, 4…:
0,06 ≤ 10-2
Ou k > 10?
Então pare!
x1 = 0,998
x2 = 1,002
x = 0,998
1,002
20
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.
1+k
jx
1
1
1
1
+
−
+ k
j
k xx ,...,
k
n
k
j xx ,...,1+
Sistemas de Equações Lineares
21
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
Métodos Iterativos – Gauss Seidel
22
� Isolando xi a partir da linha i, tem-se:
( )
( )
( )
( )1121
31132322313
33
3
21123231212
22
2
11113132121
11
1
21
1
1
1
1
−−
−−
−−
−−
−−−−=
−−−−=
−−−−=
−−−−=
nnnnnn
nn
n
nnnn
nnnn
nnnn
xaxaxab
a
x
xaxaxaxab
a
x
xaxaxaxab
a
x
xaxaxaxab
a
x
......
 
....
....
....
,
,
,
,
M
Métodos Iterativos – Gauss Seidel
23
� O processo iterativo é obtido a partir das equações, fazendo:
( )
( )
( )
( )111,1221111
311,3
1
232
1
1313
33
1
3
211,2323
1
1212
22
1
2
111,13132121
11
1
1
......
1
.......
1
.......
1
.......
1
+
−−
+++
−−
+++
−−
++
−−
+
−−−−=
−−−−−=
−−−−−=
−−−−−=
k
nnn
k
n
k
nn
nn
k
n
k
nn
k
nn
kkk
k
nn
k
nn
kkk
k
nn
k
nn
kkk
xaxaxab
a
x
xaxaxaxab
a
x
xaxaxaxab
a
x
xaxaxaxab
a
x
Métodos Iterativos – Gauss Seidel
24
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 dRk+1
pequeno o bastante para a precisão desejada.
)(
|)(|
|,|
RelativaDiferença
k
i
Xmáx
kd1k
Máx
k
r
k
i
1k
i
d
ni1xxd
====
++++
==== ≤≤≤≤≤≤≤≤−−−−++++
Métodos Iterativos – Gauss Seidel
25
Ex.: Resolva:
.. 2kR 105 D com
0z6y3x3
6zy4x3
5zyx5
−−−−≤≤≤≤
====++++++++
====++++++++
====++++++++
(((( ))))
(((( ))))
(((( )))) (((( ))))yx
2
1
zy3x3
6
1
z
zx36
4
1
y
zy5
5
1
x
++++−−−−====⇒⇒⇒⇒++++−−−−====
−−−−−−−−====
−−−−−−−−====
Solução:
Métodos Iterativos – Gauss Seidel
26
kx
 
k
xD 
ky
 
k
yD 
kz
 
k
zD 
k
RD 
-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 ok
3.(1,002) + 4.(0,998) + (-1) = 5,998 ≅ 6 ok
3.(1,002) + 3.(0,998) + 6.(-1) = 0 ok
Métodos Iterativos – Gauss Seidel
27
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.
28
Critério de Sassenfeld
� Sejam as quantidades βi dadas por:
para i = 2, 3, ..., n.
∑
=
⋅=
n
j
ja
a 2
1
11
1
1β 





+⋅⋅= ∑∑
+=
−
=
n
ij
ij
i
j
jij
ii
i aa
a 1
1
1
1 ββe
n - ordem do sistema linear que se deseja resolver
aij - 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:
i
ni
M βmax
1 ≤≤
= for menor que 1 (M<1).
29
� Exemplo: Seja A, a matriz dos coeficientes e b
o vetor dos termos constantes dados por:
444434241
334333231
224232221
114131211
baaaa
baaaa
baaaa
baaaa
 
 
 
 
( )
( )
( )
( )343242141
44
4
34232131
33
3
2423121
22
2
141312
11
1
1
1
1
1
ββββ
βββ
ββ
β
aaa
a
aaa
a
aaa
a
aaa
a
++⋅=
++⋅=
++⋅=
++⋅=
Critério de Sassenfeld
30
Exemplo: Mostre se 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
31
� Solução: critério de Sassenfeld
� Calcular os valores das quantidades βi. 
( )
( )
( )
( ) 2736.0358.08.044.02.17.04.0
4
1
358.02.044.02.07.01.0
1
1
44.03.06.07.06.0
3
1
7.02.02.01
2
1
4
3
2
1
=⋅+⋅+⋅⋅=
=+⋅+⋅⋅=
=++⋅⋅=
=++⋅=
β
β
β
β
7.0max
41
==
≤≤
i
i
M β M é menor que 1 ⇒ a solução desse sistema irá convergir usando 
o 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
Critério de Sassenfeld
32
Critério das Linhas
� Segundo esse critério, um determinado sistema 
irá convergir pelo método de Gauss-Seidel, se:
ii
n
ij
j
ij aa <∑
≠
=1
, para i=1, 2, 3, ..., n.
33
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
ij
j
ij aa <∑
≠
=1
para i=1, 2, 3, 4.
Critério das Linhas
34
É importante saber que:
� A convergência de um sistema INDEPENDE dos 
valores iniciais estimados.
� 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
35
Exemplo: 
Seja o sistema:
18x2x6
23xx10
21
21
====++++
====++++
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.06
2
1
1.01
10
1
2
1
=⋅⋅=
=⋅=
β
β 13.0max
41
<==
≤≤
i
i
M β
⇒ Convergência garantida.
Considerações Finais
36
Outra observação importante
�A ordem com que as equações aparecem no 
sistema pode ser alterada para se avaliar a 
convergência.
�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
37
Exemplo: 
Seja o sistema:
15x3x5
19x10x4
21
21
====++++
====++++−−−−
� 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).
Considerações Finais