Aula 11 e 12 Metodos Iterativos parte 1

Prévia do material em texto

Métodos Iterativos para
Solução de Sistemas Lineares 
• Método de Jacobi 
• Método de Gauss-Seidel
Métodos Iterativos
• Encontrar métodos que permitam aproximar a 
solução de um sistema linear, de forma a diminuir o 
número de operações (relativamente aos métodos 
diretos), o que pode ser útil no caso de se tratar de 
um sistema com um grande número de equações, 
especialmente se a matriz possuir muitos elementos 
nulos. 
• Definir ou armazenar a matriz, ou ainda, evitar os 
problemas de instabilidade numérica, que podem 
ocorrer num método direto.
Métodos Iterativos
• Consideremos um sistema genérico A x = b escrito na forma
A = M + N.
Supondo que M é invertível, obtemos 
• (M+N) x = b ⇔ x = M-1b - M-1N x
• Daqui podemos retirar um método iterativo que consiste em: 
• Escolher um vetor inicial x(0) tal que
x(k+1) = M-1b - M-1N x(k)
Método de Jacobi
• No caso do método de Jacobi, consideramos 
• M = D 
N = L+ U
• O método consiste em iterada inicial x(0),
x(k+1) = D-1b - D-1 (L + U) x(k)
ou ainda
Método de Jacobi
AX = B
n = 3 
a11x1 + a12x2 + a13x3 = b1
a21x1+ a22x2 + a23x3 = b2
a31x1 + a32x2 + a33x3 = b3
Preprocessamento:
1. Organizar todas as equações de forma que os termos da diagonal 
principal sejam diferentes de zero. 
2. Realizar transformações nas linhas de forma que os elementos da
diagona principal sejam os maiores possiveis. 
Primeira Iteração
x1 = (b1 - a12x2 - a13x3) / a11
x2 = (b2 - a21x1 - a23x3) / a22
x3 = (b3 - a31x1 - a23x3) / a33
Segunda Iteração
x1 = (b1 - a12x2 - a13x3) / a11
x2 = (b2 - a21x1 - a23x3) / a22
x3 = (b3 - a31x1 - a32 x2) / a33
x1 = (b1 - a12x2 - a13x3) / a11
x2 = (b2 - a21x1 - a23x3) / a22
x3 = (b3 - a31x1 - a23x3) / a33
Pseudo Códico de Jacobi
Método de Gauss - Jacobi
)(11 ∑−=
≠
+
ij
k
jiji
ii
k
i xaba
x
• Escolha de um vetor como
aproximação inicial (x0, x1, x2).
• Se nenhuma informação esta
disponivel então (x0, x1, x2) = (0, 0, 0)
Iteração:
<∈−
−
100
x
xx
j
i
ij
i
j
i
Parar quando:
O Método de Jacobi
• Sistema de Equações Lineares
a x
a x
a x
a x
a x a x a x
a x a x a x
a x a x a x
a x a x a x
b
b
b
b
11 1
21 1
31 1
n1 n
12 2 13 3 1n n
22 2 23 3 2n n
32 2 33 3 3n n
n2 2 n3 3 nn n
1
2
3
n
+
+
+
+
+ +
+ +
+ +
+ +
=
=
=
=
⎫
⎬
⎪⎪⎪
⎭
⎪⎪⎪
#
"
"
"
# # % #
"
#
a x
a x
a x
a x
a x a x a x
a x a x a x
a x a x a x
a x a x a x
b
b
b
b
11 1
21 1
31 1
n1 n
12 2 13 3 1n n
22 2 23 3 2n n
32 2 33 3 3n n
n2 2 n3 3 nn n
1
2
3
n
+
+
+
+
+ +
+ +
+ +
+ +
=
=
=
=
⎫
⎬
⎪⎪⎪
⎭
⎪⎪⎪
#
"
"
"
# # % #
"
#
Iteração de Jacobi
x (b
x (b
x (b
x (b
a x a x a x )/a
a x a x a x )/a
a x a x a x )/a
a x a x a x )/a
1
(k+1)
1
2
(k+1)
2
3
(k+1)
3
n
(k+1)
n
12 2
(k)
13 3
(k)
1n n
(k)
11
21 1
(k)
23 3
(k)
2n n
(k)
22
31 1
(k)
32 2
(k)
3n n
(k)
33
n1 1
(k)
n2 2
(k)
n,n 1 n 1
(k)
nn
= −
= −
= −
= −
− −
− −
− −
− −
⎫
⎬
⎪⎪⎪
⎭
⎪⎪⎪
− −
#
"
"
"
# # % #
"
x (b
x (b
x (b
x (b
a x a x a x )/a
a x a x a x )/a
a x a x a x )/a
a x a x a x )/a
1
(k+1)
1
2
(k+1)
2
3
(k+1)
3
n
(k+1)
n
12 2
(k)
13 3
(k)
1n n
(k)
11
21 1
(k)
23 3
(k)
2n n
(k)
22
31 1
(k)
32 2
(k)
3n n
(k)
33
n1 1
(k)
n2 2
(k)
n,n 1 n 1
(k)
nn
= −
= −
= −
= −
− −
− −
− −
− −
⎫
⎬
⎪⎪⎪
⎭
⎪⎪⎪
− −
#
"
"
"
# # % #
"
Método de Jacobi
• Após k iterações deste processo tem-se:
nn
k
nnn
k
n
k
nnk
n
k
nn
k
k
k
nn
k
k
a
x a x a xab x
a
x a xab x
a
x a xab x
)(
)(
)(
1122111
22
212121
2
11
121211
1
−−+
+
+
+++−=
++−=
++−=
"
#
"
"
Exemplo: Método de Jacobi
52
83
12
32
321
21
−=+−
=−+−
=−
 x x
 x x x
 x x
2
5
2
)(5
3
8
3
)(8
2
1
2
)(1
221
3
31311
2
221
1
kk
k
kkkk
k
kk
k
xx
 x
xxxx
 x
xx
 x
+−=−−−=
++=−−−=
+=−−=
+
+
+
Organizando:
• Estimativa inicial: 0,0,0 03
0
2
0
1 === xxx
5.2
2
05
2
5
667.2
3
008
3
8
5.0
2
01
2
1
0
21
3
0
3
0
11
2
0
21
1
−=+−=+−=
=++=++=
=+=+=
x
x
xx
x
x
 x
1667.1
2
833335.15
2
5
2
3
)5.2(5.08
3
8
833335.1
2
6667.21
2
1
1
22
3
1
3
1
12
2
1
22
1
−=+−=+−=
=−++=++=
=+=+=
x
x
xx
x
x
x
1,3,2 321 −=== xxx• Após 20 iterações:
Exemplo: Método de Jacobi
• Número máximo de 
repetições do conjunto de 
equações.
• Medida de erro entre os 
valores calculados entre 
duas aproximações 
sucessivas.
Método iterativo: Gauss-Jacobi
•Vetor nulo:
•Vetor unitário:
•Vetor qualquer: ),,(),,(
33
3
22
2
11
10
3
0
2
0
1 a
b
a
b
a
bxxx =
=),,( 030201 xxx (1,1,1)
=),,( 030201 xxx (0,0,0)
Matrizes Diagonalmente Dominante
∑>
≠=
n
ij
j
ijii aa
1
O elemento da diagonal principal de cada linha é maior do que a 
soma dos valores absolutos de outros elementos da linha. 
Matriz diagonalmente dominante é uma condição suficiente
porém não necessária para a convergência do método de Jacobi e 
do método de Gauss-Seidel.
	Métodos Iterativos para Solução de Sistemas Lineares 
	Métodos Iterativos
	Métodos Iterativos
	Método de Jacobi
	Método de Jacobi
	Método de Gauss - Jacobi
	O Método de Jacobi
	Iteração de Jacobi
	Método de Jacobi
	Exemplo: Método de Jacobi
	Exemplo: Método de Jacobi
	Matrizes Diagonalmente Dominante