Aula4 Metodos Iterativos

Prévia do material em texto

SOLUÇÃO DE SISTEMAS DE EQUAÇÕES 
LINEARES
Objetivo:
• Formas de resolver os sistemas de equações lineares 
resultantes do processo de discretização
• Rever os seguintes métodos: Gauss‐Seidel, Jacobi e SOR
• Apresentar o método: TDMA
MATRIZES ESPECIAIS
Matriz Banda: é uma matriz
quadrada que tem todos os
elementos zero, exceto uma
banda centrada na diagonal
principal.
HBW: half band width
BW: band width
BW: 2HBW + 1
aij=0 se |i‐j|>HBW
MATRIZES ESPECIAIS
Matriz Simétrica: é uma matriz quadrada cuja transposta
é igual à própria matriz.
[A]=[A]T aij=aji
Matriz Tridiagonal: é uma matriz quadrada cujos elementos são nulos, exceto em
três diagonais, a diagonal principal e nas diagonais imediatamente à esquerda e
imediatamente à direita da principal.
AUTORES
SISTEMA DE EQUAÇÕES LINEARES




























15
21
7
.
512
184
114
3
2
1
x
x
x
    bxA .
1552
2184
74
321
321
321



xxx
xxx
xxx
1552
2184
74
321
321
321



xxx
xxx
xxx
SISTEMA DE EQUAÇÕES LINEARES
5
152
8
214
4
7
21
3
31
2
32
1



xxx
xxx
xxx




























15
21
7
.
512
184
114
3
2
1
x
x
x




































3
8
21
4
7
.
05
1
5
2
8
102
1
4
1
4
10
3
2
1
3
2
1
x
x
x
x
x
x
bAx  dCxx 
MÉTODO JACOBI
Divulgado em 1845, é um método iterativo baseado na transformação do sistema linear
Ax=b em um sistema x=Cx+d , onde a matriz C tem zeros na diagonal principal. O
vetor x é atualizado usando os valores do vetor x estimados na iteração anterior. Assim:
    dCxx kk  1







































3
8
21
4
7
.
05
1
5
2
8
102
1
4
1
4
10
1
3
1
2
1
1
3
2
1
k
k
k
k
k
k
x
x
x
x
x
x
bAx 




























15
21
7
.
512
184
114
3
2
1
x
x
x
1552
2184
74
321
321
321



xxx
xxx
xxx
5
152
8
214
4
7
21
3
31
2
32
1



xxx
xxx
xxx
MÉTODO JACOBI
Em notação matricial, a matriz A pode ser decomposta em A=L+D+U

UDLA







 































000
100
110
500
080
004
012
004
000
512
184
114
E Ax=b pode ser reescrita na forma: Dx=b‐(L+U)x
 
xULbxD
x
x
x
x
x
x

























 





































3
2
1
3
2
1
000
100
110
012
004
000
15
21
7
.
500
080
004

Obtendo a inversa (D‐1) de D e reescrevendo: x(k) = D‐1[b‐(L+U) x(k‐1)]
 
 
 
 
 
 



































 









































  
)1(
1
)(
1
3
1
2
1
1
3
2
1
000
100
110
012
004
000
15
21
7
5
100
08
10
004
1
kk x
k
k
k
ULb
Dx
k
k
k
x
x
x
x
x
x
UDLA 
 xULbDx 
      11   kk xULbDx
MÉTODO JACOBI
Iteração 1
Iteração 2
Iteração 3
sk
i
k
i
k
i
xa x
xx
i
 

%100
1
,
Critério de convergência
Estimativa inicial: x1=1; x2=2; x3=2
5
152
8
214
4
7
21
3
31
2
32
1



xxx
xxx
xxx
3
5
1521.2
375,3
8
2121.4
75,1
4
722
3
2
1



x
x
x
025,3
5
15375,375,1.2
875,3
8
21375,1.4
84375,1
4
73375,3
3
2
1



x
x
x
9625,2
5
15875,384375,1.2
925,3
8
21025,384375,1.4
9625,1
4
7025,3875,3
3
2
1



x
x
x
%33,33%100
3
23
%74,40%100
375,3
2375,3
%86,42%100
75,1
175,1
3
2
1
,
,
,



xa
xa
xa



%%83,0%100
025,3
3025,3
%90,12%100
875,3
375,3875,3
%08,5%100
84375,1
75,184375,1
3
2
1
,
,
,



xa
xa
xa



%11,2%100
9625,2
025,39625,2
%27,1%100
925,3
875,3925,3
%05,6%100
9625,1
84375,19625,1
3
2
1
,
,
,



xa
xa
xa



MÉTODO GAUSS‐SEIDEL
Divulgado em 1874, é um método iterativo baseado na transformação do sistema linear
Ax=b em um sistema x=Cx+d , onde a matriz C tem zeros na diagonal principal. O
vetor x é atualizado à medida que os cálculos são feitos (atualização sequencial) e não
somente ao final de cada passo iterativo, como ocorre no método de Jacobi. Assim:






































3
8
21
4
7
.
05
1
5
2
8
102
1
4
1
4
10
1
3
1
2
1
3
2
1
k
k
k
k
k
k
x
x
x
x
x
x







































3
8
21
4
7
.
05
1
5
2
8
102
1
4
1
4
10
1
3
1
2
1
1
3
2
1
k
k
k
k
k
k
x
x
x
x
x
x




































 3
8
21
4
7
.
05
1
5
2
8
102
1
4
1
4
10
1
3
2
1
3
2
1
k
k
k
k
k
k
x
x
x
x
x
x
1552
2184
74
321
321
321



xxx
xxx
xxx
5
152
8
214
4
7
21
3
31
2
32
1



xxx
xxx
xxx
MÉTODO GAUSS‐SEIDEL
Iteração 1
Iteração 2
Iteração 3
sk
i
k
i
k
i
xa x
xx
i
 

%100
1
,
Critério de convergência
Estimativa inicial: x1=1; x2=2; x3=2
5
152
8
214
4
7
21
3
31
2
32
1



xxx
xxx
xxx
95,2
5
1575,375,1.2
75,3
8
21275,1.4
75,1
4
722
3
2
1



x
x
x
98625,2
5
1596875,395,1.2
96875,3
8
2195,295,1.4
95,1
4
795,275,3
3
2
1



x
x
x
99903,2
5
1599609,3995625,1.2
99609,3
8
2198625,2995625,1.4
995625,1
4
798625,296875,3
3
2
1


x
x
x
%20,32%100
95,2
295,2
%67,46%100
75,3
275,3
%86,42%100
75,1
175,1
3
2
1
,
,
,



xa
xa
xa



%%21,1%100
98625,2
95,298625,2
%51,5%100
96875,3
75,396875,3
%26,10%100
95,1
75,195,1
3
2
1
,
,
,



xa
xa
xa



%%43,0%100
99903,2
98625,299903,2
%68,0%100
99609,3
96875,399609,3
%29,2%100
995625,1
95,1995625,1
3
2
1
,
,
,



xa
xa
xa



COMPARAÇÃO GAUSS‐SEIDEL e JACOBI
COMPARAÇÃO GAUSS‐SEIDEL e JACOBI
Iteração 1
Iteração 2
Iteração 3
Iteração 1
Iteração 2
Iteração 3
JACOBI GAUSS‐SEIDEL
3
5
1521.2
375,3
8
2121.4
75,1
4
722
3
2
1



x
x
x
025,3
5
15375,375,1.2
875,3
8
21375,1.4
84375,1
4
73375,3
3
2
1



x
x
x
9625,2
5
15875,384375,1.2
925,3
8
21025,384375,1.4
9625,1
4
7025,3875,3
3
2
1



x
x
x
95,2
5
1575,375,1.2
75,3
8
21275,1.4
75,1
4
722
3
2
1



x
x
x
98625,2
5
1596875,395,1.2
96875,3
8
2195,295,1.4
95,1
4
795,275,3
3
2
1



x
x
x
99903,2
5
1599609,3995625,1.2
99609,3
8
2198625,2995625,1.4
995625,1
4
798625,296875,3
3
2
1



x
x
x
COMPARAÇÃO GAUSS‐SEIDEL e JACOBI
Iteração 1
Iteração 2
Iteração 3
Iteração 1
Iteração 2
Iteração 3
JACOBI GAUSS‐SEIDEL
%33,33%100
3
23
%74,40%100
375,3
2375,3
%86,42%100
75,1
175,1
3
2
1
,
,
,



xa
xa
xa



%%83,0%100
025,3
3025,3
%90,12%100
875,3
375,3875,3
%08,5%100
84375,1
75,184375,1
3
2
1
,
,
,



xa
xa
xa



%11,2%100
9625,2
025,39625,2
%27,1%100
925,3
875,3925,3
%05,6%100
9625,1
84375,19625,1
3
2
1
,
,
,



xa
xa
xa



%20,32%100
95,2
295,2
%67,46%100
75,3
275,3
%86,42%100
75,1
175,1
3
2
1
,
,
,



xa
xa
xa



%%21,1%100
98625,2
95,298625,2
%51,5%100
96875,3
75,396875,3
%26,10%100
95,1
75,195,1
3
2
1
,
,
,



xa
xa
xa



%%43,0%100
99903,2
98625,299903,2
%68,0%100
99609,3
96875,399609,3
%29,2%100
995625,1
95,1995625,1
3
2
1
,
,
,



xa
xa
xa



CONVERGÊNCIA DO GAUSS‐SEIDEL







yx
xgy
xy
xgy )()(
CONDIÇÃO DE CONVERGÊNCIA
Os métodos iterativos de Jacobi e Gauss‐Seidel convergem se a matriz A (do 
sistema Ax=b) é diagonalmente dominante, ou seja:



n
ij
j
ijii aa
1
CRITÉRIO DE SCARBOUROGH






equações das uma menos pelo para1
equações as todaspara11
ii
n
ij
j
ij
a
a
Esta é uma condição suficiente, mas não necessária para convergência, ou 
seja, a matriz pode não ser diagonal dominante e o processo ainda assim 
convergir.
É uma condição de convergência para qualquer método iterativo. 
É uma condição suficiente, mas não necessária. 
OBSERVAÇÕES
De um modo geral o método de Gauss‐Seidel tem convergência mais rápida 
que o método de Jacobi, porém não pode‐se generalizar esta afirmação;
Em alguns casos o método Gauss‐Seidel pode não convergir, enquanto o 
Jacobi converge;
O Jabobi tem sido bastante usado em arquitetura paralela para 
computadores;
EXERCÍCIO
1) Resolver com Gauss‐Seidel o sistema:




1
2,04,0
12
21
xx
xx
2) Resolver com Gauss‐Seidel o sistema:




5,05,2
1
12
21
xx
xx






































3
8
21
4
7
.
05
1
5
2
8
102
1
4
1
4
10
1
3
1
2
1
3
2
1
k
k
k
k
k
k
x
x
x
x
x
x
MÉTODO SOR
É uma modificação do Gauss‐Seidel
para melhorar a convergência. 







































3
8
21
4
7
.
05
1
5
2
8
102
1
4
1
4
10
1
3
1
2
1
1
3
2
1
k
k
k
k
k
k
x
x
x
x
x
x
       1111 1  kkk xxx 
       1222 1  kkk xxx 
       1333 1  kkk xxx 
1552
2184
74
321
321
321



xxx
xxx
xxx
5
152
8
214
4
7
21
3
31
2
32
1



xxx
xxx
xxx




































 3
8
21
4
7
.
05
1
5
2
8
102
1
4
1
4
10
1
3
2
1
3
2
1
k
k
k
k
k
k
x
x
x
x
x
x
MÉTODO SOR (Sucessive Over Relaxation)
0<ω<2        11  kikiki xxx 
0<ω<1→ Subrelaxação (underrelaxation)
1<ω<2→ Sobrerelaxação (overrelaxation)
Sobrerelaxação (SOR): usado para acelerar a convergência de um sistema que
converge.
Subrelaxação: é uma média ponderada entre o valor atual e o anterior da variável.
Usado para obter a covergência de um sistema que não converge, ou para
acelerar a convergência de um sistema reduzindo as oscilações.
ω=1→ Gauss-Seidel
Se a matriz A do sistema Ax=b é simétrica e positiva definida o método converge
para qualquer 0<ω<2.
MÉTODO TDMA (Tridiagonal matrix algorithm) ou 
algoritmo de Thomas
É um método baseado na eliminação de Gauss. Considerando um sistema de
equações lineares escrito na forma:
iiiiiii dxcxbxa   11
Supondo que se queira determinar um processo de substituição progressiva
escrito na forma:
iiii QxPx  1 (2)
111   iiii QxPx (3)
































n
n
n
n
nn
nnn
d
d
d
d
x
x
x
x
ac
bac
bac
ba
1
2
1
1
2
1
111
222
11
......
000
00
0.........0
00
000
(1)
A eq.(1) representa o sistema linear Ax=b, onde a matriz dos coeficientes (A) é
uma matriz tridiagonal. Decompondo a matriz A em A=D+L+U, o sistema pode ser
representado como escrito na eq.(1), que na forma matricial é dado por
Dx=(L+U)x+b:

























































n
n
n
n
n
nn
n
n
n
n
d
d
d
d
x
x
x
x
c
bc
bc
b
x
x
x
x
a
a
a
a
1
2
1
1
2
1
11
22
1
1
2
1
1
2
1
......
0000
000
0...0...0
000
0000
...
0000
0000
00...00
0000
0000
MÉTODO TDMA (Tridiagonal matrix algorithm) ou 
algoritmo de Thomas
Substituindo (3) em (1):
  iiiiiiiii dQxPcxbxa   111
Lembrando que a equação (2) é dada por:
iiii QxPx  1 (2)
   111   iiiiiiiii QcdxbxPca





 


 1
1
1
1 iii
iii
i
iii
i
i Pca
QcdxPca
bx (4)
Comparando (2) e (4) tem-se:
1

iii
i
i Pca
bP (5)
1
1




iii
iii
i Pca
QcdQ (6)
MÉTODO TDMA (Tridiagonal matrix algorithm) ou 
algoritmo de Thomas
Para o elemento “1” não existe o elemento “i-1” então “c1=0”, e resulta da eq.(1):
Para o elemento “n” não existe “n+1” então “Pn=0”, logo, a eq. (2) fica:
1
1
1 a
bP 
1
1
1 a
dQ 
121111012111 dxbxadxcxbxa 
Logo, as equações (5) e (6) para i=1 resultam:
 nn
P
niiii QxxQxPx
n
 

 11 0
(8)
nn Qx  (9)
(7)
MÉTODO TDMA (Tridiagonal matrix algorithm) ou 
algoritmo de Thomas
E o algoritmo do TDMA é dado por:
1) Calcular P1 e Q1 com as equações (7) e (8);
2) Calcular Pi e Qi com as equações (5) e (6) para i=2 até n;
3) Calcular “xn” com a equação (9), ou seja, fazer xn=Qn; e
4) Usando a equação (2) achar o valor xi de forma regressiva para i=n-1 até 1.
RESTRIÇÕES
Aplicável somente quando a matriz de coeficientes “A” do sistema Ax=b seja
diagonal dominante.



n
ij
j
ijii aa
1
EXEMPLO DO MÉTODO TDMA
100105
1005155
1005155
1100520
43
432
321
21




xx
xxx
xxx
xx





























100
100
100
1100
.
10500
51550
05155
00520
4
3
2
1
x
x
x
x
Deixando na forma do algoritmo:










































100
100
100
1100
.
0500
5050
0505
0050
.
10000
01500
00150
00020
4
3
2
1
4
3
2
1
x
x
x
x
x
x
x
x
Dado o sistema linear Ax=b:
Montando uma tabela auxiliar e seguindo os passos do algoritmo:
n cn an bn dn Pn Qn xn
1 0 20 5 1100 0,25 55 64,26
2 5 15 5 100 0,364 27,27 37,03
3 5 15 5 100 0,379 17,93 26,80
4 5 10 0 100 0 23,40 23,40
1) Calcular P1 e Q1 com as equações (7) e (8);
2) Calcular Pi e Qi com as equações (5) e (6) para i=2 até n;
3) Calcular “xn” com a equação (9), ou seja, fazer xn=Qn; e
4) Usando a equação (2) achar o valor xi de forma regressiva para i=n-1 até 1.










































100
100
100
1100
.
0500
5050
0505
0050
.
10000
01500
00150
00020
4
3
2
1
4
3
2
1
x
x
x
x
x
x
x
x
1
1
1 a
bP 
1
1
1 a
dQ 
1

iii
i
i Pca
bP
1
1




iii
iii
i Pca
QcdQ
nn Qx 
iiii QxPx  1
(7)
(9)
(2)
(8)
(5) (6)
EXEMPLO DO MÉTODO TDMA