Aula 13 e 14 Metodos Iterativos parte 2

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 
 Considere o sistema linear 
b Ax 
or 





































nnnnnn
n
n
b
b
b
 
x
x
x
aaa
aaa
aaa




2
1
2
1
21
22221
11211
nnnnnn
nn
nn
 b x a x a xa
 b x a x a xa
 b x a x a xa







2211
22222121
11212111
Iterative Methods 
 Escrevendo-se as equações de outra forma: 
nn
nnnnnn
n
nn
nn
a
x a x a xab
 x
a
x a xab
 x
a
x a xab
 x
)(
)(
)(
112211
22
21212
2
11
12121
1









 Ponto inicial 
00
2
0
1
,,, nxxx 
Método de Gauss Seidel 
 A aproximação de uma das variáveis é aplicada para 
o uso do outro passo. 
 Esta informação pode ser usada no cálculo da 
varíavel seguinte: 
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
)(
)(
)(
1
11
1
22
1
111
22
2
1
12121
2
11
121211
1

















Iteração de Gauss-Seidel 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+1)
23 3
(k)
2n n
(k)
22
31 1
(k+1)
32 2
(k+1)
3n n
(k)
33
n1 1
(k+1)
n2 2
(k+1)
n,n 1 n 1
(k+1)
nn
 
 
 
 
 
 
 
 



 




   







• A = L + D + U 
• M = L + D, N = –U 
• Mx = Nx + b 
Expresión matricial 
» M = tril(A) 
» N = M - A 
» x = M\(N*x0 + b) 
Consiste em repetir um 
conjunto de fórmulas até 
atingir-se a solução do sela. 
Tem-se dois passo para 
aplicar o método: 
Método iterativo: Gauss-Seidel 
2opasso: escolher uma aproximação inicial, isto é 
um vetor inicial para iniciar o processo iterativo. Por 
exemplo, o vetor nulo, unitário ou um vetor com 
componente aleatórias. 
3opasso: repetir os cálculos determinados pelas 
equações, atualizando os valores das componentes 
dos vetores, até atingir um critério de parada. 
Resolver o sela abaixo pelo método de 
Gauss-Seidel, usando como critério de 
parada 5 repetições. Durante os cálculos as 
operações aritméticas serão efetuadas em 
FL(10,5, -10,10) e arredondamento corte. 
12
5.15.0
32
04
41
31
43
421




xx
xx
xx
xxx
1opasso: escolher as equações que irão determinar a 
solução, de modo que cada equação informe a solução de 
uma das componentes do vetor solução. 
Método iterativo: Gauss-Seidel 
)5.1(
5.0
1 1
31
 kk xx
)0(
4
1
2 1
1
4
kk xxkx 

)23(
1
1
3 4
kxkx 
)21(
1
1
4 1
kxkx 
Isolando x1 na 3
a equação 
Isolando x2 na 1
a equação 
Isolando x3 na 2
a equação 
Isolando x4 na 4
a equação 
As equações podem ser reescritas como: 
Método iterativo: Gauss-Seidel 
1
31 23
 kk xx
)(25.0
2
1
41
 kk xxkx
1
4233
 kxkx
)21(
4 1
kxkx 
• 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-Seidel 
•Vetor nulo: 
•Vetor unitário: 
•Vetor qualquer: 
),,(),,(
33
3
22
2
11
10
3
0
2
0
1
a
b
a
b
a
b
xxx 
),,( 03
0
2
0
1 xxx
(1,1,1) 
),,( 03
0
2
0
1 xxx
(0,0,0) 
2opasso: escolher o chute inicial, o valor que 
inicializará as variáveis. Escolhemos: 
Método iterativo: Gauss-Seidel 
),,,( 04
0
3
0
2
0
1 xxxx
(0,0,0,0) 
2opasso: escolher o chute inicial, o valor que 
inicializará as variáveis. Escolhemos: 
Método iterativo: Gauss-Seidel 
),,,( 04
0
3
0
2
0
1 xxxx
(0,0,0,0) 
Escolher outro conjunto de 
equações para o processo 
iterativo. 
Com esta escolha de equações e chute 
inicial o processo iterativo não está 
convergindo para a solução do sela. 
Método iterativo: Gauss-Seidel 
1opasso: escolher as equações que irão determinar a 
solução, de modo que cada equação informe a solução de 
uma das componentes do vetor solução. 
Método iterativo: Gauss-Seidel 
)0(
4
1
2 1
1
4
kk xxkx 

Isolando x1 na 4
a equação 
Isolando x2 na 1
a equação 
Isolando x3 na 3
a equação 
Isolando x4 na 2
a equação 
)1(
2
1 1
41
 kk xx
)5.05.1(
1
1
3 1
kxkx 
)3(
2
1
4 3
kxkx 
2opasso: escolher o chute inicial, o valor que 
inicializará as variáveis. Escolhemos: 
Método iterativo: Gauss-Seidel 
),,,( 04
0
3
0
2
0
1 xxxx
(0,0,0,0) 
Processo de repetição (iterativo) 
está apresentando aproximações 
da solução (1, 0.5, 1, -1) 
Gauss-Seidel Method - 
Example 
52
83
12
32
321
21



 x x
 x x x
 x x
0,0,0 0
3
0
2
0
1
 xxx
2
5
3
8
2
1
1
21
3
3
1
11
2
21
1











k
k
kk
k
k
k
x
 x
xx
 x
x
 x
after 1 iteration of the method 
convenient initial guess 
08333.1
2
83333.25
2
5
8333.2
3
05.08
3
8
5.0
2
01
2
1
1
21
3
0
3
1
11
2
0
21
1















x
x
xx
x
x
 x
Gauss-Seidel Method 
• after 2 iterations 
0278.1
2
9444.25
2
5
9444.2
3
)0833.1(9167.18
3
8
9167.1
2
5.01
2
1
2
22
3
1
3
2
12
2
1
22
1















x
x
xx
x
x
x
08333.1
8333.2
5.0
1
3
1
2
1
1



x
x
x
1
3
2
3
2
1



x
x
x
after 9 iterations 
after 1 iteration