Método iterativo de gauss seidel

Prévia do material em texto

Sistema de Equações 
Lineares
Método Iterativo de Gauss Seidel
Métodos Iterativo
• Dois métodos iterativos específicos
• Diferença entre esses dois métodos está na maneira pela qual os 
novos valores calculados para as incógnitas são utilizados.
• Método de Jacobi: valores das incógnitas no lado direito da são atualizados 
todos de uma vez no final de cada iteração.
Método de Gauss-Seidel
• Os valores atuais das incógnitas são utilizados no cálculo do novo 
valor da próxima incógnita. 
• Em outras palavras, à medida que um novo valor é calculado, ele é 
imediatamente utilizado na próxima equação explícita 
• No método de Jacobi, os valores das incógnitas obtidos em uma 
iteração são utilizados como um conjunto completo no cálculo dos 
novos valores das incógnitas na próxima iteração.
Método de Gauss-Seidel
1. Valor inicial é escolhido
𝑥1
(0)
, 𝑥2
(0)
, 𝑥3
(0)
, … , 𝑥𝑛
0
2. Os valores iniciais das incógnitas são substituídos na equação explicita, da seguinte forma
2.1 Com i = 1 calcular o valor de 𝑥1
(1)
𝑥1
(1)
=
1
𝑎11
𝑏1 − σ𝑗=2
𝑗=𝑛
𝑎1𝑗 𝑥𝑗
(0)
2.2 Com i = 2 calcular o valor de 𝑥2
(1)
, utilizando 𝑥1
(1)
𝑥2
(1)
=
1
𝑎22
𝑏2 − 𝑎21𝑥1
(1)
+ σ𝑗=3
𝑗=𝑛
𝑎2𝑗 𝑥𝑗
(0)
2.3 Com i = 3 calcular o valor de 𝑥3
(1)
, utilizando 𝑥1
(1)
, 𝑥2
(1)
𝑥3
(1)
=
1
𝑎33
𝑏3 − 𝑎31𝑥1
(1)
+ 𝑎32𝑥2
(1)
+ σ𝑗=4
𝑗=𝑛
𝑎3𝑗 𝑥𝑗
(0)
… .
2.n Com i = n calcular o valor de 𝑥𝑛
(1)
, utilizando 𝑥1
(1)
, 𝑥2
(1)
, … , , 𝑥𝑛
(1)
𝑥𝑛
(1)
=
1
𝑎𝑛𝑛
𝑏𝑛 − σ𝑗=1
𝑗=𝑛−1
𝑎𝑛𝑗 𝑥𝑗
(1)
𝑥1
(1)
, 𝑥2
(1)
, 𝑥3
(1)
, … , 𝑥𝑛
1
Método de Gauss-Seidel
3. A primeira estimativa das incógnitas são substituídos na equação explicita, da seguinte forma
3.1 Com i = 1 calcular o valor de 𝑥1
(2)
𝑥1
(2)
=
1
𝑎11
𝑏1 − σ𝑗=2
𝑗=𝑛
𝑎1𝑗 𝑥𝑗
(1)
3.2 Com i = 2 calcular o valor de 𝑥2
(2)
, utilizando 𝑥1
(2)
𝑥2
(2)
=
1
𝑎22
𝑏2 − 𝑎21𝑥1
(2)
+ σ𝑗=3
𝑗=𝑛
𝑎2𝑗 𝑥𝑗
(1)
3.3 Com i = 3 calcular o valor de 𝑥3
(1)
, utilizando 𝑥1
(2)
, 𝑥2
(2)
𝑥3
(2)
=
1
𝑎33
𝑏3 − 𝑎31𝑥1
(2)
+ 𝑎32𝑥2
(2)
+ σ𝑗=4
𝑗=𝑛
𝑎3𝑗 𝑥𝑗
(1)
… .
3.n Com i = n calcular o valor de 𝑥𝑛
(2)
, utilizando 𝑥1
(2)
, 𝑥2
(2)
, … , , 𝑥𝑛
(2)
𝑥𝑛
(2)
=
1
𝑎𝑛𝑛
𝑏𝑛 − σ𝑗=1
𝑗=𝑛−1
𝑎𝑛𝑗 𝑥𝑗
(2)
𝑥1
(2)
, 𝑥2
(2)
, 𝑥3
(2)
, … , 𝑥𝑛
2
Método de Gauss-Seidel
K A estimativa k-1 das incógnitas são substituídos na equação explicita, da seguinte forma
k.1 Com i = 1 calcular o valor de 𝑥1
(𝑘)
𝑥1
(𝑘)
=
1
𝑎11
𝑏1 − σ𝑗=2
𝑗=𝑛
𝑎1𝑗 𝑥𝑗
(𝑘−1)
k.2 Com i = 2 calcular o valor de 𝑥2
(𝑘)
, utilizando 𝑥1
(𝑘−1)
𝑥2
(𝑘)
=
1
𝑎22
𝑏2 − 𝑎21𝑥1
(𝑘)
+ σ𝑗=3
𝑗=𝑛
𝑎2𝑗 𝑥𝑗
(𝑘−1)
k.3 Com i = 3 calcular o valor de 𝑥3
(𝑘)
, utilizando 𝑥1
(𝑘−1)
, 𝑥2
(𝑘−1)
𝑥3
(𝑘)
=
1
𝑎33
𝑏3 − 𝑎31𝑥1
(𝑘)
+ 𝑎32𝑥2
(𝑘)
+ σ𝑗=4
𝑗=𝑛
𝑎3𝑗 𝑥𝑗
(𝑘−1)
… .
k.n Com i = n calcular o valor de 𝑥𝑛
(𝑘)
, utilizando 𝑥1
(𝑘−1)
, 𝑥2
(𝑘−1)
, … , , 𝑥𝑛
(𝑘−1)
𝑥𝑛
(𝑘)
=
1
𝑎𝑛𝑛
𝑏𝑛 − σ𝑗=1
𝑗=𝑛−1
𝑎𝑛𝑗 𝑥𝑗
(𝑘)
𝑥1
(𝑘)
, 𝑥2
(𝑘)
, 𝑥3
(𝑘)
, … , 𝑥𝑛
𝑘
Método de Gauss-Seidel
Forma Geral
A (k + 1)-ésima estimativa da solução é calculada a partir da k- ésima
estimativa usando
𝑥1
(𝑘+1)
=
1
𝑎11
𝑏1 − σ𝑗=2
𝑗=𝑛 𝑎1𝑗 𝑥𝑗
(𝑘)
, para i =1
𝑥𝑖
(𝑘+1)
=
1
𝑎𝑖𝑖
𝑏𝑖 − σ𝑗=1
𝑗=𝑖−1
𝑎𝑖𝑗𝑥𝑗
(𝑘+1)
+σ𝑗=𝑖+1
𝑗=𝑛
𝑎𝑖𝑗 𝑥𝑗
(𝑘)
, para i = 2,3,..., n-1
𝑥𝑛
(𝑘+1)
=
1
𝑎𝑛𝑛
𝑏𝑛 − σ𝑗=1
𝑗=𝑛−1
𝑎𝑛𝑗 𝑥𝑗
(𝑘+1)
, para i = n
Método de Gauss-Seidel
As iterações continuam até 
• Máxima diferença entre os valores de qualquer incógnita atual e 
anterior for menor que um ERRO 
𝑚á𝑥|𝑥𝑖
(𝑘)
- 𝑥𝑖
(𝑘+1)
| ≤ ∈ , para i = 1,2,3,...,n
• Atingir um número máximo M de iterações.
𝑘 >M
Exercício: Resolver pelo método de Jacobi
ቊ
2𝑥1 − 𝑥2 = 1
𝑥1 + 2𝑥2 = 3
Com ∈< 10−2 ou k > 10
Método de Jacobi
ቊ
2𝑥1 − 𝑥2 = 1
𝑥1 + 2𝑥2 = 3
Forma explicita método de Jacobi
ቐ
𝑥1
(𝑘+1)
= 1/2(1 + 𝑥2
(𝑘)
)
𝑥2
(𝑘+1)
= 1/2(3 − 𝑥1
(𝑘)
)
𝑘 = 0,1,2, , …
Forma explicita método de Gauss-Seidel
ቐ
𝑥1
(𝑘+1)
= 1/2(1 + 𝑥2
(𝑘)
)
𝑥2
(𝑘+1)
= 1/2(3 − 𝑥1
(𝑘+1)
)
𝑘 = 0,1,2, , …
Método de Gauss-Seidel
k 𝑥1
(𝒌)
𝑥𝟐
(𝑘) E
0 0 0 0
1
0,5000 1,2500 1,2500
2
1,1250 0,9375 0,6250
3
0,9688 1,0156 0,1563
4
1,0078 0,9961 0,0391
5
0,9980 1,0010 0,0098
k 𝑥1
(𝒌)
𝑥𝟐
(𝑘) E
0 0 0
1 0,5 1,5 1,5
2 1,25 1,25 0,75
3 1,125 0,875 0,375
4 0,938 0,938 0,187
5 0,969 1,031 0,093
6 1,016 1,016 0,047
7 1,008 0,992 0,024
8 0,996 0,996 0,012
9 0,998 1,002 0,006
Método de Jacobi
Método de Gauss-Seidel
Exercício: Resolver pelo método de Gauss-Seidel
9𝑥1 − 2𝑥2 + 3𝑥3 + 2𝑥4 = 54,5
2𝑥1 + 8𝑥2 − 2𝑥3 + 3𝑥4 = −14
−3𝑥1 + 2𝑥2 + 11𝑥3 - 4𝑥4 = 12,5
−2𝑥1 + 3𝑥2 + 2𝑥3 + 10𝑥4 = −21
Com ∈< 10−2 ou k > 10
Método de Gauss-Seidel
9𝑥1 − 2𝑥2 + 3𝑥3 + 2𝑥4 = 54,5
2𝑥1 + 8𝑥2 − 2𝑥3 + 3𝑥4 = −14
−3𝑥1 + 2𝑥2 + 11𝑥3 - 4𝑥4 = 12,5
−2𝑥1 + 3𝑥2 + 2𝑥3 + 10𝑥4 = −21
Forma explicita
𝑥1
(𝑘+1)
= 1/9[54,5 − (−2𝑥2
(𝑘)
+ 3𝑥3
(𝑘)
+ 2𝑥4
(𝑘)
))
𝑥2
(𝑘+1)
= 1/8[−14 − (−2𝑥1
𝑘+1 − 2𝑥3
(𝑘)
+ 3𝑥4
(𝑘)
))
𝑥2
(𝑘+1)
= 1/11[12,5 − (−3𝑥1
𝑘+1 + 2𝑥2
𝑘+1 − 4𝑥4
(𝑘)
))
𝑥2
(𝑘+1)
= 1/10[−21 − (−2𝑥1
(𝑘+1)
+ 3𝑥2
(𝑘+1)
+ 2𝑥3
(𝑘+1)
))
𝑘 = 0,1,2, , …
Vetor inicial 
𝑥
(0)
= [0 0 0 0]
Método de Gauss-Seidel
1𝑥1
(1)
𝑥2
(1)
𝑥3
(1)
𝑥4
(1)
1𝑥1
(2)
𝑥2
(2)
𝑥3
(2)
𝑥4
(2)
Método de Gauss-Seidel
k 𝑥1
(𝒌)
𝑥𝟐
(𝑘)
𝑥𝟑
(𝒌)
𝑥𝟒
(𝑘) E
0 0 0 0 0 0
1 6,05556 -3,26389 3,38131 -0,58598 6,05556
2 4,33336 -1,76827 2,42661 -1,18817 1,7222
3 5,11778 -1,97723 2,45956 -0,97519 0,78442
4 5,01303 -2,02267 2,51670 -0,99393 0,10475
5 4,98805 -1,99511 2,49806 -1,00347 0,02756
6 5,00250 -1,99981 2,49939 -0,99943 0,01445
7 5,00012 -2,00040 2,50031 -0,99992 0,00238
Convergência
• condição suficiente para a convergência ocorre se, em cada uma das 
linhas da matriz de coeficientes [a], o valor absoluto do elemento 
diagonal for maior que a soma dos valores absolutos dos elementos 
fora da diagonal.
|𝑎𝑖𝑖| > ෍
𝑗=𝑖,
𝑗≠𝑖
𝑗=𝑛
|𝑎𝑖𝑗|
condição é suficiente mas não necessária para a convergência.
matriz [a] é classificada como diagonalmente dominante
Qual o melhor método?
• Não se pode garantir a priori qual método é mais eficiente.
• Métodos Diretos: 
• Sistema de pequeno porte
• Sistema com matrizes de coeficiente densas.
• Métodos iterativos
• Quando existe convergência garantida
• Sistema de grande porte
• Matriz de coeficientes com grandes proporções de zeros