Apostila Método de Gauss Jacobi

Prévia do material em texto

UNIVERSIDADE FEDERAL DE MATO GROSSO 
FACULDADE DE ARQUITETURA, ENGENHARIA E TECNOLOGIA 
ENGENHARIA ELÉTRICA 
 
LUCAS NAVES SCALEZ 
RAFAEL KOVALSKI DE LIMA 
 
 
 
 
 
 
 
 
 
 
 
MÉTODO DE GAUSS - JACOBI 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
CUIABÁ-MT 
2016 
 
 
 
LUCAS NAVES SCALEZ 
RAFAEL KOVALSKI DE LIMA 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
MÉTODO DE GAUSS - JACOBI 
 
 
 
 
 
 
Apostila apresentada na disciplina de Métodos 
Computacionais, no curso de Engenharia Elétrica, 
da Universidade Federal de Mato Grosso, com o 
objetivo de compreender o método numérico de 
Gauss – Jabobi e aplica-lo por meio de software. 
Professor: Antonio de Padua Finazzi. 
 
 
 
 
 
 
 
 
 
 
 
 
 
CUIABÁ- MT 
2016
3 
 
Sumário 
 
1 – AUTORES DO MÉTODO...........................................................................4 
1.1 - Carl Friedrich Gauss......................................................4 
1.2 - Gustav Jacobi..................................................................4 
 
2- MÉTODO DE ELIMINAÇÃO DE GAUSS.................................................5 
3 – PROBLEMÁTICA.......................................................................................6 
4 – MÉTODOS INTERATIVOS.......................................................................6 
4.1– Método interativo de Gauss- Jacobi.............................8 
 
 
5- MÉTODO DE GAUSS – JACOBI – RESUMO........................................14 
6- APLICAÇÕES – ENGENHARIA ELÉTRICA........................................14 
7- FLUXOGRAMA..........................................................................................15 
8- REFERÊNCIAS BIBLIOGRÁFICAS.......................................................16 
 
 
 
 
 
 
 
 
 
 
 
 
4 
 
 
 1 – AUTORES DO MÉTODO 
 
 1.1- Carl Friedrich Gauss 
 
Johann Carl Friedrich Gauss (1777 - 1855) foi um matemático astrônomo e 
físico alemão que contribuiu muito em diversas áreas da ciência, dentre elas 
a estatística, análise matemática, geofísica, eletroestática, astronomia 
e óptica. 
 
 1.2- Gustav Jacobi 
 
Carl Gustav Jakob Jacobi (1804 - 1851) foi um matemático alemão que fez 
contribuições fundamentais para funções elípticas, dinâmica, equações 
diferenciais e teoria dos números. Seu nome está escrito 
Jacobi foi o primeiro matemático judeu a ser nomeado professor em uma 
universidade alemã. 
 
 
 
 
 
 
 
 
 
 
5 
 
 
 2- MÉTODO DE ELIMINAÇÃO DE GAUSS 
 
Tem como objetivo transformar um sistema linear Ax =b em um sistema 
equivalente e apresenta-lo na forma de uma matriz triangular superior dos 
coeficientes. 
 
 a11 a12 ... a1n x1 b1 
 a21 a22 ... a2n x2 b2 
Ax= * = 
 an1 an2 ... ann xn bn 
 
 
 Triangulação de matrizes 
 
Existem 3 formas básicas para triangular uma matriz: 
 
• Trocar duas equações (linhas); 
• Multiplicar uma equação por uma constante não nula; 
• Adicionar um múltiplo de uma equação a uma outra equação 
 
 3 2 1 -1 
 A= 0 1 0 3 
 0 0 -5 7 
 0 0 0 8 
6 
 
 Figura 01 - Exemplo de matriz triangular superior 
3 - PROBLEMÁTICA 
• É 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. 
 
 4 – MÉTODOS INTERATIVOS 
 
Seja os Sistema Linear 
bxA 
 onde: 
 
A
 matriz de coeficientes 
nn
 
x
 vetor de variáveis 
1n
 
b
 vetor independente (constantes) 
1n
 
 
Idéia Geral dos Métodos Iterativos 
 
Converter o sistema de equações 
bxA 
 em um processo iterativo 
)(xgxCx 
, onde: 
 
C
 matriz com dimensões 
nn
 
g
 vetor com dimensões 
1n
 
)(x
 função de iteração matricial 
7 
 
 
Esquema Iterativo Proposto 
 
Partindo de uma vetor aproximação inicial 
)(o
x
, constrói-se uma 
seqüência iterativa de vetores: 
)(
)()()1( oo
xgxCx 
 
)(
)1()1()2(
xgxCx 
 

 
)(
)1()1()( 

kkk
xgxCx 
 
 
 
Forma Geral 
)(
)()1( kk
xx 
 
 
Os métodos de solução de sitemas lineares iterativos podem ser considerados 
como uma generalização do Método de Iteração Linear para a solução de raízes. 
 
Observação 
Se a sequência de aproximação 
)(o
x
, 
)1(
x
, 
)2(
x
, ......, 
)(k
x
 é tal que 
gCx
k
k


)(lim
, então 

 é a solução do sistema 
bxA 
. 
 
 
 
 
 
 
 
8 
 
Teste de Parada 
Como em todos os processos iterativos, necessitamos de um critérios 
para a parada do processo. 
 
a) Máximo desvio absoluto: 
 
)1()(
,1
)( max 

 ki
k
i
ni
k xx
 
b) Máximo desvio relativo: 
)(
,1
)(
)(
max ki
ni
k
k
R
x



 
 
Desta forma, dada uma precisão 

 o vetor 
)(k
x
 será escolhido como solução 
aproximada da solução exata, se 
 )(k
, ou dependendo da escolha, 
 )(kR
. 
 
4.1– Método interativo de Gauss- Jacobi 
 
Considere o sistema linear: 
 
 












nnnnnnn
nn
nn
bxaxaxaxa
bxaxaxaxa
bxaxaxaxa
............
..................................................................
..................................................................
............
............
332211
22323222121
11313212111
 
 
 
Supondo 
niaii ,...,2,1,0 
, isola-se o vetor 
x
 mediante a separação 
pela diagonal da matriz de coeficientes. 
9 
 
)..........(
1
)..........(
1
)..........(
1
)(
11
)(
22
)(
11
)1(
)(
2
)(
323
)(
1212
22
)1(
2
)(
1
)(
313
)(
2121
11
)1(
1
k
nnn
k
n
k
nn
nn
k
n
k
nn
kkk
k
nn
kkk
xaxaxab
a
x
xaxaxab
a
x
xaxaxab
a
x








 
 
Assim, tem-se o sistema iterativo 
gxCx 
, onde: 
 
















0///
//0/
///0
321
22222232221
11111131112




nnnnnnnnn
n
n
aaaaaa
aaaaaa
aaaaaa
C 
 













nnn ab
ab
ab
g
/
/
/
222
111

 
 
 
Dado uma aproximação inicial 
)(o
x
, o Método de Gauss-Jacobi 
consiste em obter uma seqüência 
)(o
x
, 
)1(
x
, 
)2(
x
, ......, 
)(k
x
, por meio da relação 
recursiva: 
 
gxCx
kk

 )()1(
 
Observe que o processo iterativo utiliza somente estimativas da 
iteração anterior. 
 
Exemplo: Resolver o sistema de equações lineares, pelo Método de Gauss-
Jacobi com solução inicial 
 Tox 6,06,17,0)( 
 e tolerância 
05,0
.10 
 
61032
85
7210
321
321
321



xxx
xxx
xxx
 
Separando-se os elementos diagonais, tem-se: 
)326(
10
1
)8(
5
1
)27(
10
1
)(
2
)(
1
)1(
3
)(
3
)(
1
)1(
2
)(
3
)(
2
)1(
1
kkk
kkk
kkk
xxx
xxx
xxx






 





























106
5
8
10
7
0
10
3
10
2
5
10
5
1
10
1
10
20
gC 
 
Solução para k=0 
)1()0()1( xgxCx 
 
 



















































94,0
86,1
96,0
106
5
8
10
7
6,0
6,1
7,0
0
10
3
10
2
5
10
5
1
10
1
10
20
1
1
x
x
 
 
Cálculo de 
)1(
R
: 
1828,0
86,1
34,0
max
34,0
34,094,06,0
26,06,186,1
26,096,07,0
)1(
3,1
)1(
)0(
3
)1(
3
)0(
2
)1(
2
)0(
1
)1(
1





i
i
R
x
xx
xx
xx
 
 
11 
 
Para k=1: 











 0606,0
98,1
12,0
966,0
98,1
978,0
)2()2(
Rx
 
Para k=2: 











 0163,0
9888,1
0324,0
99984,0
9888,1
9994,0
)3()2(
Rx
 











9984,0
9888,1
9994,0
x
 é solução com erro menor que 0,05. 
 
 
Condições Suficientes para a Convergência do Método de Gauss-Jacobi 
 
Teorema 
 
Seja o sistema linear
bxA 
 e seja: 
kk
n
kj
j
kj
k
a
a













1
 
Se 
1max
,1


k
nk

, então o método G-J gera uma seqüência 
 )(kx
 convergente para 
a solução do sistema dado, independentemente da escolha da aproximação inicial 
)0(
x
. 
 
 
12 
 
Observe que esta é uma condição suficiente, se for satisfeita o método converge, 
entretanto se não for satisfeita nada se pode afirmar. 
 
Exemplo 1: 
Seja a matriz do exemplo dado anteriormente: 
12,0
10
)32(
14,0
5
)11(
13,0
10
)12(
1032
151
1210
3
2
1























A
 
Tem-se a convergência garantida para qualquer vetor inicial. 
 
Exemplo 2: 
Seja o sistema de equações lineares: 
33
3
21
21


xx
xx
 
3
1
1
1
1
2
1




 
As condições de convergência do teorema não são satisfeitas, 
entretanto o Método de Gauss-Jacobi gera uma seqüência convergente para a 
solução exata 
 Tx
2
3
2
3
. Se as condições de suficiência não são satisfeitas, não 
significa que o método não possa convergir. 
 
Exemplo 3: 
Considere o sistema linear: 
13 
 
6860
3225
23
321
321
321



xxx
xxx
xxx
 
175,0
8
)60(
15,3
2
)25(
14
1
)13(
860
225
131
3
2
1























A
 
As condições do teorema não são satisfeitas. Uma solução possível é 
permutar as equações. Seja no exemplo permutar a primeira equação com a 
Segunda equação: 
175,0
8
)60(
166,0
3
)11(
18,0
1
)22(
860
131
225
3
2
1























A
 
As condições passam a ser satisfeitas e a convergência é garantida para 
qualquer vetor inicial. Este tipo de procedimento nem sempre é possível. 
 
 
 
 
Fórmula Matricial do Método Gauss-Jacobi 
 
Decompõe-se a matriz de coeficientes 
A
 em: 
UDLA 
 
Onde: 
L – Matriz Triangular Inferior 
D – Matriz Diagonal 
U – Matriz Triangular Superior 
 




















































 0000
000
00
0
000
000
000
000
0
00
000
0000
1
223
11312
33
22
11
121
3231
21















nn
n
n
nnnnnn
a
aa
aaa
U
d
d
d
d
D
aaa
aa
a
L
 
14 
 
)(11)1(
)()1(
)(
)(
)(
)(
kk
kk
xULDbDx
xULbxD
xULbxD
bxUxDxL
bxUDL







 
 
 
 5- MÉTODO DE GAUSS – JACOBI - RESUMO 
 
 
• 1- Escolhe-se a aproximação inicial x(0) : • x(0) = [x 1(0), x 2(0), ..., x n 
(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. 
- K > M, com M=Número máximo de iterações. 
 
 
6- APLICAÇÕES – ENGENHARIA ELÉTRICA 
 
• Solução de Fluxo de carga. 
• 2ª Lei de Kirchhoff: Lei das Malhas, calculo da corrente. 
 
 
 
 
 
15 
 
7- FLUXOGRAMA 
 
 
 
Figura 01 – Fluxograma do programa desenvolvido pelo grupo 
 
 
 
 
 
 
 
 
 
 
 
16 
 
8- REFERÊNCIAS BIBLIOGRÁFICAS 
• Cavalcanti, Jorge (2013) “Sitemas Lineares – Métodos Interativos.” 
Univasft. Consultado em 20 de Julho de 2016. 
<http://www.univasf.edu.br/~jorge.cavalcanti/6CN_Sistemas_Parte2.pdf> 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
17