CÁLCULO NUMÉRICO - IEC082-Módulo II

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

1 Material cedido por Prof. Arilo/Profa. Fabíola do IComp 
}  Conceitos Fundamentais e Sistemas Triangulares 
}  Métodos Diretos 
◦  Método de Eliminação de GAUSS 
◦  Método de Eliminação de JORDAN 
◦  Decomposição LU 
◦  Análise de Erro na solução de sistemas 
}  Métodos Iterativos 
◦  Método de Gauss-Jacobi 
◦  Método de Gauss-Seidel 
2 
3 
}  Um sistema de equações lineares (abreviadamente, 
sistema linear) é um conjunto finito de  equações 
lineares nas mesmas variáveis. 
◦  Equação linear: equação  envolvendo apenas somas ou 
produtos de constantes e variáveis do primeiro grau. 
}  Algoritmos  computacionais para achar soluções são uma 
parte importante da álgebra linear numérica, e tais 
métodos têm uma grande importância em: 
◦  engenharia, física, química, ciência da computação e 
economia. 
4 
}  Forma Geral 
 
 
 
 
 onde: 
 aij à coeficientes 
 xi à incógnitas 
 bi à termos independentes 
 
nnnnnn
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
=+++
=+++
=+++
...
...
...
2211
22222121
11212111
!!"!!
5 
1x5x4x2
2x5x1x4
5x5x4x2
321
321
321
−=++
=−+
=−+
}  Exemplo: 
 
 
 
 
 
 2, 4, -5, 4, 1, -5, 2, 4 e 5 à coeficientes 
 x1, x2 e x3 à incógnitas 
 5, 2 e -1 à termos independentes 
6 
}  Forma Matricial 
 
 na qual: 
 
Ax = b 
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
=
nn3n2n1n
n22221
n112
aaaa
aaa
aaa
A
11
!"!!
…
…
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
=
n
2
1
b
b
b
b
!⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
=
n
2
1
x
x
x
x
!
7 
1x5x4x2
2x5x1x4
5x5x4x2
321
321
321
−=++
=−+
=−+
}  Exemplo 
◦  Forma Geral 
◦  Forma Matricial 
⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
−
=
⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
−
−
1
2
5
x
x
x
.
542
514
542
3
2
1
8 
}  Classificação: 
Sistemas 
Lineares 
Impossível Possível 
Determinado Indeterminado Homogêneo 
9 
}  Classificação: 
◦  Impossível à Não possui solução 
–  Exemplo: 
10 
}  Classificação: 
◦  Possível à Possui 1 ou mais soluções 
–  Determinado à Solução única 
–  Exemplo: 
11 
}  Classificação: 
◦  Possível à Possui 1 ou mais soluções 
–  Indeterminado à Mais de uma solução 
–  Exemplo: 
12 
}  Classificação: 
◦  Possível à Possui 1 ou mais soluções 
–  Homogêneo à Vetor b=0 (x=0 sempre existe 
solução) 
–  Exemplo: 
⎩
⎨
⎧
=+
=+
0x3x2
0xx
21
21
13 
}  Sistema Triangular Inferior: 
nnnnnnn b
b
b
b
xaxaxaxa
xaxaxa
xaxa
xa
!
3
2
1
332211
333232131
222121
111
... =
=
=
=
=
++++
++
+
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎣
⎡
=
nn3n2n1n
333231
2221
11
aaaa
0aaa
00aa
000a
A
…
!"!!!
…
…
…
14 
}  Resolução: 
nn
nnnnnnn
n a
xaxaxaxabx
a
xaxabx
a
xabx
a
bx
11332211
33
2321313
3
22
1212
2
11
1
1
... −−−−−−−=
−−
=
−
=
=
!
Pergunta 
Qual a solução deste sistema? É 
possível elaborar uma fórmula geral 
para encontrar os valores de x? 
15 
}  Considere um Sistema Triangular Inferior de 
ordem 4. 
 
4
3
2
1
444343242141
333232131
222121
111
b
b
b
b
xaxaxaxa
xaxaxa
xaxa
xa
=
=
=
=
+++
++
+
Pergunta 
Qual a solução deste sistema? 
16 
}  Resolução 
44
3432421414
4
33
2321313
3
22
1212
2
11
1
1
a
xaxaxabx
a
xaxabx
a
xabx
a
bx
−−−
=
−−
=
−
=
=
17 
}  Resolução: método de substituições 
sucessivas 
n. ..., 3, 2, 1,i 
a
xab
x
ii
i
j
jiji
i =
−
=
∑
−
= ,
1
1
18 
}  Sistema Triangular Superior 
nnnn
nn
nn
nn
b
b
b
b
xa
xaxa
xaxaxa
xaxaxaxa
!
3
2
1
3333
2323222
1313212111
...
...
...
=
=
=
=
=
++
+++
++++
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎣
⎡
=
nn
n333
n22322
n1131211
a000
aa00
aaa0
aaaa
A
…
!"!!!
…
…
…
19 
}  Resolução 
11
13132121
1
22
24243232
2
33
34343
3
...
...
...
a
xaxaxabx
a
xaxaxabx
a
xaxabx
a
bx
nn
nn
nn
nn
n
n
−−−−
=
−−−
=
−−−
=
=
!
20 
}  Elaborar a fórmula geral para encontrar o 
valor de x para um sistema triangular 
superior. 
21 
}  Resolução: método de substituições 
retroativas 
n. ..., 3, 2, 1,i ,1 =
−
=
∑
+=
ii
n
ij
jiji
i a
xab
x
22 
}  Exemplo: 
◦  Dado o sistema: 
◦  Primeiro passo para sua resolução: 
2x2
3x5x4
1x2xx
10xx5x4x3
4
43
432
4321
=
=−
−=−+
−=+−+
1
2
2x4 ==
23 
}  Exemplo: 
◦  Segundo passo: 
◦  Terceiro passo: 
2x
315x4
3x5x4
3
3
43
=
=⋅−
=−
1x
1122x
1x2xx
2
2
432
−=
−=⋅−+
−=−+
24 
}  Exemplo: 
◦  Último passo: 
1x
10125)1(4x3
10xx5x4x3
1
1
4321
=
−=+⋅−−⋅+
−=+−+
25 
}  Sistemas Lineares Equivalentes 
◦  Sistema Lineares equivalentes são sistemas que 
possuem a mesma solução, ou seja, o mesmo vetor 
x satisfaz as equações tanto de um quanto de 
outro. 
26 
}  Exercício: Verificar quais destes sistemas 
lineares são equivalentes. 
⎥
⎦
⎤
⎢
⎣
⎡
=⎥
⎦
⎤
⎢
⎣
⎡
⎥
⎦
⎤
⎢
⎣
⎡
− 7
6
41
22
)
2
1
x
x
A ⎥
⎦
⎤
⎢
⎣
⎡−
=⎥
⎦
⎤
⎢
⎣
⎡
⎥
⎦
⎤
⎢
⎣
⎡
− 1
2
41
22
)
2
1
x
x
B ⎥
⎦
⎤
⎢
⎣
⎡
=⎥
⎦
⎤
⎢
⎣
⎡
⎥
⎦
⎤
⎢
⎣
⎡
− 0
7
12
31
)
2
1
x
x
C
⎥
⎦
⎤
⎢
⎣
⎡
−
−
=⎥
⎦
⎤
⎢
⎣
⎡
⎥
⎦
⎤
⎢
⎣
⎡
1
2
41
32
)
2
1
x
x
D ⎥
⎦
⎤
⎢
⎣
⎡
−
−
=⎥
⎦
⎤
⎢
⎣
⎡
⎥
⎦
⎤
⎢
⎣
⎡−
6
10
52
41
)
2
1
x
x
E ⎥
⎦
⎤
⎢
⎣
⎡
−
=⎥
⎦
⎤
⎢
⎣
⎡
⎥
⎦
⎤
⎢
⎣
⎡
− 3
5
21
13
)
2
1
x
x
F
Pergunta 
Esses sistemas têm solução única? Por quê? 
27 
}  Exercício: Verificar quais destes sistemas 
lineares são equivalentes. 
⎥
⎦
⎤
⎢
⎣
⎡
=∴⎥
⎦
⎤
⎢
⎣
⎡
=⎥
⎦
⎤
⎢
⎣
⎡
⎥
⎦
⎤
⎢
⎣
⎡
− 2
1
7
6
41
22
)
2
1 x
x
x
A ⎥
⎦
⎤
⎢
⎣
⎡−
=∴⎥
⎦
⎤
⎢
⎣
⎡−
=⎥
⎦
⎤
⎢
⎣
⎡
⎥
⎦
⎤
⎢
⎣
⎡
− 0
1
1
2
41
22
)
2
1 x
x
x
B
⎥
⎦
⎤
⎢
⎣
⎡
=∴⎥
⎦
⎤
⎢
⎣
⎡
=⎥
⎦
⎤
⎢
⎣
⎡
⎥
⎦
⎤
⎢
⎣
⎡
− 2
1
0
7
12
31
)
2
1 x
x
x
C ⎥
⎦
⎤
⎢
⎣
⎡−
=∴⎥
⎦
⎤
⎢
⎣
⎡
−
−
=⎥
⎦
⎤
⎢
⎣
⎡
⎥
⎦
⎤
⎢
⎣
⎡
0
1
1
2
41
32
)
2
1 x
x
x
D
⎥
⎦
⎤
⎢
⎣
⎡
−
=∴⎥
⎦
⎤
⎢
⎣
⎡
−
−
=⎥
⎦
⎤
⎢
⎣
⎡
⎥
⎦
⎤
⎢
⎣
⎡−
2
2
6
10
52
41
)
2
1 x
x
x
E ⎥
⎦
⎤
⎢
⎣
⎡
=∴⎥
⎦
⎤
⎢
⎣
⎡
−
=⎥
⎦
⎤
⎢
⎣
⎡
⎥
⎦
⎤
⎢
⎣
⎡
− 2
1
3
5
21
13
)
2
1 x
x
x
F
28 
}  Operações l-Elementares 
◦  Sistema Lineares podem ser transformados em
sistemas equivalentes por meio de 3 operações 
 l-elementares. 
–  Trocar ordem de duas equações. 
–  Multiplicar uma equação por uma constante não nula. 
–  Somar uma equação à outra. 
29 
}  Operações l-Elementares 
◦  Trocar ordem de duas equações. 
 ⎥⎦
⎤
⎢
⎣
⎡−
=∴⎥
⎦
⎤
⎢
⎣
⎡−
=⎥
⎦
⎤
⎢
⎣
⎡
⎥
⎦
⎤
⎢
⎣
⎡
− 0
1
1
2
41
22
2
1 x
x
x
?
2
1
22
41
2
1 =∴⎥
⎦
⎤
⎢
⎣
⎡
−
=⎥
⎦
⎤
⎢
⎣
⎡
⎥
⎦
⎤
⎢
⎣
⎡− x
x
x
⎥
⎦
⎤
⎢
⎣
⎡−
=
0
1
x
30 
}  Operações l-Elementares 
◦  Multiplicar uma equação por uma constante não nula. 
 ⎥⎦
⎤
⎢
⎣
⎡−
=∴⎥
⎦
⎤
⎢
⎣
⎡
−
=⎥
⎦
⎤
⎢
⎣
⎡
⎥
⎦
⎤
⎢
⎣
⎡−
0
1
2
1
22
41
2
1 x
x
x
?
2
2
22
82
2
1 =∴⎥
⎦
⎤
⎢
⎣
⎡
−
=⎥
⎦
⎤
⎢
⎣
⎡
⎥
⎦
⎤
⎢
⎣
⎡− x
x
x
⎥
⎦
⎤
⎢
⎣
⎡−
=
0
1
x
31 
2 
}  Operações l-Elementares 
◦  Somar uma equação à outra. 
 
?
0
2
100
82
2
1 =∴⎥
⎦
⎤
⎢
⎣
⎡
=⎥
⎦
⎤
⎢
⎣
⎡
⎥
⎦
⎤
⎢
⎣
⎡− x
x
x
⎥
⎦
⎤
⎢
⎣
⎡−
=∴⎥
⎦
⎤
⎢
⎣
⎡
−
=⎥
⎦
⎤
⎢
⎣
⎡
⎥
⎦
⎤
⎢
⎣
⎡−
0
1
2
2
22
82
2
1 x
x
x
⎥
⎦
⎤
⎢
⎣
⎡−
=
0
1
x
32 
}  Equivalência entre sistemas 
 
⎥
⎦
⎤
⎢
⎣
⎡
=⎥
⎦
⎤
⎢
⎣
⎡
⎥
⎦
⎤
⎢
⎣
⎡−
0
2
100
82
2
1
x
x
⎥
⎦
⎤
⎢
⎣
⎡
−
=⎥
⎦
⎤
⎢
⎣
⎡
⎥
⎦
⎤
⎢
⎣
⎡−
2
2
22
82
2
1
x
x
⎥
⎦
⎤
⎢
⎣
⎡
−
=⎥
⎦
⎤
⎢
⎣
⎡
⎥
⎦
⎤
⎢
⎣
⎡−
2
1
22
41
2
1
x
x
⎥
⎦
⎤
⎢
⎣
⎡−
=⎥
⎦
⎤
⎢
⎣
⎡
⎥
⎦
⎤
⎢
⎣
⎡
− 1
2
41
22
2
1
x
x
∼ ∼
∼
33 
Sistemas 
Lineares 
Métodos 
Diretos 
Eliminação de 
Gauss 
Eliminação de 
Jordan 
Decomposição 
LU 
Métodos 
Iterativos 
Método de 
Jacobi 
Método de 
Gauss-Seidel 
Métodos que chegam à 
solução EXATA de sistemas 
lineares em um número 
FINITO de passos. 
Métodos que chegam à 
solução EXATA de sistemas 
lineares em um número 
INFINITO de passos. 
34 
Sistemas 
Lineares 
Métodos 
Diretos 
Eliminação de 
Gauss 
Eliminação de 
Jordan 
Decomposição 
LU 
Métodos 
Iterativos 
Método de 
Jacobi 
Método de 
Gauss-Seidel 
35 
}  Diretos 
◦  Solução pode ser encontrada através de um 
número finito de passos 
–  Método de Gauss 
–  Método da Eliminação de Jordan 
–  Decomposição LU 
36 
}  Iterativos 
◦  Solução a partir de uma sequencia de aproximações 
para o valor do vetor solução x , até que seja obtido um 
valor que satisfaça à precisão pré-estabelecida 
–  Método de Jacobi 
–  Método de Gauss – Siedel 
37 
Método de Gauss 
38 
}  Propósito 
◦  Transformação do sistema linear a ser resolvido 
em um sistema linear triangular; 
◦  Resolução do sistema linear triangular de forma 
retroativa (método que resolve sistemas 
triangulares superiores). 
39 
}  Triangularização 
xA b= x d=
n 
~
40 
}  Resolução 
x d=
n 
41 
}  Transformação do Sistema Linear 
◦  Troca da ordem das linhas; 
◦  Multiplicação de uma das equações por um número real 
não nulo; 
◦  Substituição de uma das equações por uma combinação 
linear dela mesma com outra equação. 
◦  Transforma um sistema de Ax=b via operações l-
elementares em um sistema equivalente Ux = d, onde U é 
uma matriz triangular superior. 
–  Tem-se então Ax=b ∼ Ux = d 
42 
}  Elementos do método 
◦  Pivô: elemento da diagonal da coluna que deseja-se 
eliminar os elementos 
◦  Linha Pivotal: a linha que contém o pivô 
◦  Multiplicador: relacionado ao elemento da linha i 
coluna j 
 
 
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
=
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
−−
−
−
==
==
−==
1
10
6
5
1202
2121
1231
0211
2/
1/
1/
4
3
2
1
414
313
212
x
x
x
x
pivôum
pivôum
pivôum
43 
}  Passos do Método de Gauss 
◦  Construção da matriz aumentada Ab 
[ ]
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
=
nnn3n2n1n
2n22221
1n11211
baaaa
baaa
baaa
Ab
!!"!!
…
…
44 
}  Passos do Método de Gauss 
◦  Passo 1: 
–  Eliminar os coeficientes de x1 presentes nas 
linhas 2,3,...,n - sendo a21 = a31, = ... = an1 = 0 
- sendo a11 chamado de pivô da coluna 
–  Substituir a linha 2, L2, pela combinação linear 
 
11
21
2122 :, a
amqualnaLmL =⋅−
45 
}  Passos do Método de Gauss 
◦  Substituir a linha 3, L3, pela combinação 
linear: 
11
31
31333 :, a
amqualnaLmLL =⋅−=
46 
}  Passos do Método de Gauss 
◦  Deve-se continuar a substituição até a linha n; 
◦  Caso algum elemento app=0, achar outra linha k 
onde akp≠ 0 e trocar tais linhas. Caso a linha k 
não exista, o sistema linear não possui solução. 
47 
}  Passos do Método de Gauss 
◦  Eliminar os coeficientes de x2 nas linhas 3, 
4, ..., n (fazer a32=a42=...=an2 = 0); 
◦  Eliminar os coeficientes de x3 nas linhas 4, 
5, ..., n (fazer a43=a53=...=an3 = 0) e assim 
sucessivamente. 
48 
}  Exemplo: 
◦  Resolver o sistema: 
–  Matriz aumentada Ab 
1xx3x2
3x3x4x4
5xx3x2
321
321
321
−=+−
=−+
=−+
[ ]
⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
−−
−
−
=
1132
3344
5132
Ab
49 
}  Exemplo: 
◦  Faz-se: 
◦  Assim: 
2,
11
21
21222 ==⋅−= a
amLmLL
[ ] [ ]
[ ]7120L
513223344L
2
2
−−−=
−⋅−−=
50 
}  Exemplo: 
◦  Faz-se: 
◦  Assim: 
1,
11
31
31333 ==⋅−= a
amLmLL
[ ] [ ]
[ ]6260L
513211132L
3
3
−−=
−⋅−−−=
51 
}  Exemplo: 
◦  Obtém-se a matriz: 
[ ]
⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
−−
−−−
−
=
6260
7120
5132
Ab
52 
}  Exemplo: 
◦  Substituindo a linha 3 por: 
◦  Têm-se: 
 
3,
22
32
32333 ==⋅−= a
amLmLL
[ ] [ ]
[ ]15500L
712036260L
3
3
=
−−−⋅−−−=
53 
}  Exemplo: 
◦  A matriz [Ab] fica assim com os seguintes 
valores: 
 
[ ]
⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
−−−
−
=
15500
7120
5132
Ab
54 
}  Exemplo: 
◦  Usa-se a solução retroativa: 
⎪
⎪
⎪
⎩
⎪
⎪
⎪
⎨
⎧
=⇒=⇒=−+⇒
⇒=−⋅+
=⇒=−−⇒−=−−
=⇒=
1x22x5362x
5xx32x
2x732x7x2x
3x155x
111
321
2232
33
55 
}  Exemplo 2: 
◦  Resolver o sistema. 
◦  Representando o sistema pela matriz aumentada: 
9,8x8,7x7,5x7,2
7,11x5,4x3,2x2,4
10x3,3x4,5x5,1
321
321
321
=++
=++
=++
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
=
9,88,77,57,2
7,115,43,22,4
103,34,55,1
][Ab
56 
}  Exemplo 2: 
◦  Escolhendo a primeira linha como pivô, obtém-se: 
[ ] [ ]
[ ]
[ ] [ ]
[ ] 9,11,864,020 L
103,35,41,5(2,7/1,5)8,97,85,72,7LmLL
 16,34,7412,820 L
103,35,41,5(4,2/1,5)11,74,52,34,2LmLL
3
1333
2
1222
−−−=
⋅−=⋅−=
−−−=
⋅−=⋅−=
57 
}  Exemplo 2: 
◦  Representando o sistema pela matriz 
aumentada: 
[AB] =
1,5 5,4 3,3 10
0 −12,82 −4,74 −16,3
0 −4,02 1,86 −9,1
"
#
$
$
$
%
&
'
'
'
58 
}  Exemplo 2: 
◦  Escolhendo agora a segunda linha como pivô, 
têm-se: L3 =L3 −m3 ⋅L1
L3 = 0 −4,02 −1,86 −9,1
#
$
%
&−
−4,02 / −12,82(
) ⋅ 0 −12,82 −4,74 −16,3#$
%
&
L3 = 0 0 3,3463 −3,9888
#
$
%
&
59 
}  Exemplo 2: 
◦  Obtêm-se a seguinte matriz ampliada: 
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
−
−−−=
3,98883,346300
16,34,7412,820
103,35,41,5
[AB]
60 
}  Exemplo 2: 
 
◦  O que termina com a triangulação: 
⎪
⎩
⎪
⎨
⎧
−=⋅+⋅+⋅
−=⋅−⋅−⋅
=⋅+⋅+
3,9888x3,3463x0x0
16,3x4,74x12,82x0
10x3,3x5,41,5x
321
321
321
61 
}  Exemplo 2: 
 
◦  Com solução: 
x3 = -3,9888/3,3463=-1,1918 
x2 =[ -16,3 - (-4,74)⋅(-1,1920)]/(-12,82) = 1,7121 
x1 = [10 - 5,4(1,7122) - 3,3(-1,1920)]/1,5 = 3,1251 
62 
63 
64 
65 
Algoritmo da Triangularização ( Eliminação de Gauss ) 
Inicio 
Entrada: Uma matriz estendida Ann+1 
       Para k = 1, 2, ..., n-1 faça ( k determina o passo ) 
       Para i = k+1 , ..., n ( i determina as linhas que serão alteradas ). 
       Início 
              If akk = 0 then troca_linha(k,k+1) 
              mik := -aik/akk (linha corrente e coluna = coluna do passo k) 
              Para j = 1, ..., n +1 faça (j determina a coluna na linha corrente) 
                     aij:= aij + mik* akj 
       Fim 
Fim 
Saída: Uma matriz triangular Superior Ann+1 
66 
Algoritmo da Retrosubstituição 
Início 
Entrada: Uma matriz triangular superior Ann+1 
       xn:= bn/ann 
       Para k:= n-1, ..., 1 faça 
       Início 
              xk:=bk; 
              Para i = k+1, ..., n faça 
                  xk := xk –aki*xi; 
                  xk := xk/akk; 
       Fim 
Saida: Um vetor x. 
Fim 
}  Semelhante ao método de Gauss; 
}  Minimiza a amplificação de erros de 
arredondamento durante as eliminações; 
}  Consiste em escolher o elemento de maior 
módulo em cada coluna para ser o pivô. 
}  Utilizando tanto na Eliminação de GAUSS 
quanto na Decomposição LU. 
67 
}  Exemplo 3: 
◦  Resolver o sistema com precisão de 4 casas 
decimais 
9,8x8,7x7,5x7,2
7,11x5,4x3,2x2,4
10x3,3x4,5x5,1
321
321
321
=++
=++
=++
68 
}  Exemplo 3: 
◦  Matriz aumentada original deve ser ajustada: 
⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
9,88,77,57,2
7,115,43,22,4
103,34,55,1
⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
9,88,77,57,2
103,34,55,1
7,115,43,22,4
69 
}  Exemplo 3: 
◦  Sistema inalterado, elemento pivô 4,2. 
◦  Encontrar as novas linhas: 
]1,37864,90714,22140[L
]11,74,52,34,2[(2,7/4,2)
]8,97,85,72,7[LmLL
]5,82141,69294,57860[L
]11,74,52,34,2[1,5/4,2)
]103,35,41,5[LmLL
3
1333
2
1222
=
⋅
−=−=
=
⋅
−=⋅−=
.
(
70 
}  Exemplo 3: 
◦  A matriz ampliada fica da forma: 
◦  Como o elemento já é o pivô da 2ª coluna, tem-
se: 
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
1,37864,90714,22140
5,82141,69294,57860
11,74,52,34,2
]3,98863,346300[L
]5,82141,69294,57860[5786)(4,2214/4, 
 ]1,37864,90714,22140[LmLL
3
2333
−=
⋅
−=⋅−=
4,5786
71 
}  Exemplo 3: 
◦  A matriz ampliada fica na forma: 
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
3,9886-3,346300
5,82141,69294,57860
11,74,52,34,2
72 
}  Exemplo 3: 
◦  A solução do sistema triangular que resultou 
dessas operações é: 
 x3 = -3,9886/3,3463 = -1,1919 
 x2 = [5,8214-1,6929⋅(-1,1919)]/(4,5786) = 1,7121 
 x1 = [11,7- 2,3(1,7121)- 4,5(-1,1919)]/4,2 = 3,1252 
73 
Soluções dos Exemplos 2 e 3 (com pivotação): 
 
EXEMPLO 1 EXEMPLO 2 
x3 = -1,1918 x3 = -1,1919 
x2 = 1,7121 x2 = 1,7121 
x1 = 3,1252 x1 = 3,1251 
 
Solução encontrada no Octave: 
x3 = -1,19198135198135 
x2 = 1,71216783216783 
x1 = 3,12522144522145 
74 
Método de Eliminação de Jordan 
75 
}  Consiste em efetuar operações sobre as 
equações do sistema, com a finalidade de 
obter um sistema diagonal equivalente; 
}  Um sistema diagonal é aquele em que os 
elementos aij da matriz coeficiente [A] são 
iguais a zero, para i≠j, 
 i, j = 1,2,...,n. 
 
76 
}  Sistema diagonal equivalente: 
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎣
⎡
=
nn
33
22
11
a000
0a00
00a0
000a
]A[
…
…!"""
#
…
…
77 
}  Exemplo: 
◦  A partir do sistema: 
◦  Com matriz aumentada: 
4x2x3x2
2x3x2x5
1xx5x
321
321
321
=++
=++
=++
[ ]
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
=
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
=
4232
1151
2325
4232
2325
1151
Ab
78 
}  Exemplo: 
◦  Substituindo a linha 2 por: 
◦  Substituindo a linha 3 por : 
[ ] [ ]
[ ] 0,21/5
a
am0,60,44,60L
,2325(1/5)1151LmLL
11
21
22
12122
====
⋅−=⋅−=
,
[ ] [ ]
[ ] 0,42/5
a
am3,20,82,20L
2325(2/5)4232LmLL
11
31
33
1333
====
⋅−=⋅−=
,
79 
}  Exemplo: 
◦  A matriz ampliada resulta em: 
◦  Substituindo a linha 3 por: 
[ ]
⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
=
3,20,82,20
0,60,44,60
2325
Ab
[ ] [ ]
[ ] 8, 0,472,2/4,6
a
am2,9130,60900L
0,60,44,60(2,2/4,6)3,20,82,20LmLL
22
32
33
2333
====
⋅−=⋅−=
80 
}  Exemplo: 
◦  A matriz ampliada resulta em: 
◦  Substituindo a linha 2 por 
[ ]
⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
=
913,2609,000
6,04,06,40
1325
Ab
[ ]
[ ]
[ ]1,31304,60L
2,9130,60900)(0,4/0,609
0,60,44,60LmLL
2
3322
−=
⋅
−=⋅−=
81 
}  Exemplo: 
◦  Matriz ampliada resulta em: 
◦  Substituindo a linha 1 por 
Ab[ ] =
5 2 3 1
0 4,6 0 −1,313
0 0 0,609 2,913
"
#
$
$
$
%
&
'
'
'
[ ] [ ]
[ ] 2/4,6
a
am,1,571305L
,1,31304,60(2/4,6)1325L
22
12
11
1
===
−⋅−=
82 
errado 
}  Exemplo: 
 
◦  Substituindo a linha 1 por: 
◦  A matriz ampliada fica da seguinte forma: 
[ ]
[ ]
[ ] 3/0,609
a
am12,779005L
2,9130,60900(3/0.609)
1,571305L
33
13
11
1
==−=
⋅
−=
[ ]
⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
−
−
=
2,9130.60900
1,31304,60
12,779005
Ab
83 
}  Exemplo: 
 
◦  E as soluções são: 
–  x1 =-2,556 , x2= -0,285, x3=4,783 
84 
85 
Método de Decomposição LU 
86 
}  Uma matriz A quadrada pode ser escrita com 
o produto de duas matrizes L e U, 
t r i a n g u l a r e s i n f e r i o r e s u p e r i o r 
respectivamente. 
}  No Método de Decomposição LU, o primeiro 
passo é encontrar as matrizes L e U tais que 
A = LU, sendo L uma matriz triangular 
inferior com lij = 1, ∀ i=j. 
 
 
 
87 
}  Decomposição 
A =
n 
L ×
88 
}  Decomposição 
xA b= → x =
n 
L b
89 
}  Resolução 
Fazendo 
x =
n 
y
=L by
x =
n 
y
Sistema 
Triangular 
Inferior. 
Sistema 
Triangular 
Superior. 
90 
}  A Matriz U é a mesma encontrada via 
Eliminação de GAUSS. 
}  A Matriz L é formada pelos multiplicadores 
mij. 
91 
}  O objetivo é fatorar a matriz dos coeficientes 
A em um produto de duas matrizes L e U. 
◦  Seja: 
[ ]
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎣
⎡
⋅
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎣
⎡
=
nn
n333
n22322
n1131211
3n2n1n
3231
21
u000
uu00
uuu0
uuuu
1lll
0
01ll
001l
0001
LU
…
!"!!!
…
…
…
…
"!!!
…
…
…
92 
}  E a matriz coeficiente A: 
◦  Tem-se, então: 
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
=
nn3n2n1n
n22221
n11211
aaaa
aaa
aaa
A
!"!!
…
…
[ ]
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎣
⎡
⋅
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎣
⎡
==
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
=
nn
n333
n22322
n1131211
3n2n1n
3231
21
nn3n2n1n
n22221
n11211
u000
uu00
uuu0
uuuu
1lll
0
01ll
001l
0001
]LU[
aaaa
aaa
aaa
A
…
!"!!!
…
…
…
…
"!!!
…
…
…
!"!!
…
…
93 
}  Para se obter os elementos da matriz L e da matriz U, 
deve-se calcular os elementos das linhas de U e os 
elementos da colunas de L seguindo os passos: 
◦  Encontrar as matrizes L e U tal que 
–  A = LU 
◦  Resolver o sistema triangular inferior 
–  Ly = b 
◦  Resolver o sistema triangular superior 
–  Ux = y 
◦  A solução deste último sistema é a solução do problema 
original. 
94 
}  1ª linha de U: Faze-se o produto da 1ª linha 
de L por todas as colunas de U e a iguala com 
todos os elementos da 1ª linha de A, assim: 
95 
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
− 1...
0.:
:1
0...01
0...001
)1(21
.
.3231
21
.
nnnn lll
ll
l
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
nnu
uu
uuu
uuuu
0......0
:.:
...00
...0
...
.
3333
232322
13131211
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
nnnnn
n
n
n
αααα
αααα
αααα
αααα
...
:::::
...
...
...
321
3333231
2232221
1131211
X = 
L U A 
}  1ª linha de U: Faze-se o produto da 1ª linha 
de L por todas as colunas de U e a iguala com 
todos os elementos da 1ª linha de A, assim: 
⎪
⎪
⎪
⎪
⎩
⎪⎪
⎪
⎪
⎨
⎧
==
=⇒=⋅
=⇒=⋅
=⇒=+++⋅
.,...,2,1,
...
,1
,1
,0.0...0.01
11
1111
12121212
11111111
njau
ndoGeneraliza
auau
auau
auau
jj
nnnn
!
96 
}  1ª coluna de L: Faz-se o produto de todas as 
linhas de L, (da 2ª a até a nª), pela 1ª coluna 
de U e a iguala com os elementos da 1ª 
coluna de A, (abaixo da diagonal principal), 
obtendo , 
97 
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
− 1...
0.:
:1
0...01
0...001
)1(21
.
.3231
21
.
nnnn lll
ll
l
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
nnu
uu
uuu
uuuu
0......0
:.:
...00
...0
...
.
3333
232322
13131211
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
nnnnn
n
n
n
αααα
αααα
αααα
αααα
...
:::::
...
...
...
321
3333231
2232221
1131211
X = 
L U A 
}  1ª coluna de L: Faz-se o produto de todas as 
linhas de L, (da 2ª a até a nª), pela 1ª coluna 
de U e a iguala com os elementos da 1ª 
coluna de A, (abaixo da diagonal principal), 
obtendo , 
⎪
⎪
⎪
⎪
⎪
⎩
⎪⎪
⎪
⎪
⎪
⎨
⎧
==
=⇒=⋅
=⇒=⋅
=⇒=⋅
.n,...,2,1l,
u
al
,
u
alaul
,
u
alaul
,
u
alaul
11
1l
1l
11
1l
1l1l111l
11
31
31311131
11
21
21211121
!
98 
}  2ª linha de U: Faz-se o produto da 2ª linha de L 
por todas as colunas de U, (da 2ª até a nª), e 
igualando com os elementos da 2ª linha de A, (da 
diagonal principal em diante), obtêm-se , 
99 
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
− 1...
0.:
:1
0...01
0...001
)1(21
.
.3231
21
.
nnnn lll
ll
l
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
nnu
uu
uuu
uuuu
0......0
:.:
...00
...0
...
.
3333
232322
13131211
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
nnnnn
n
n
n
αααα
αααα
αααα
αααα
...
:::::
...
...
...
321
3333231
2232221
1131211
X = 
L U A 
}  2ª linha de U: Faz-se o produto da 2ª linha de L 
por todas as colunas de U, (da 2ª até a nª), e 
igualando com os elementos da 2ª linha de A, (da 
diagonal principal em diante), obtêm-se , 
⎪
⎪
⎪
⎪
⎩
⎪⎪
⎪
⎪
⎨
⎧
=⋅−=
⋅−=⇒=+⋅
⋅−=⇒=+⋅
⋅−=⇒=+⋅
.n,...,3j,ulau
,ulauauul
,ulauauul
,ulauauul
j121j2j2
n121n2n2n2n2n121
1321232323231321
1221222222221221
!
100 
}  2ª coluna de L: Faz-se o produto de todas as 
linhas de L (da 3ª até a nª) pela 2ª coluna de 
U e a iguala com os elementos da 2ª coluna 
de A, (abaixo da diagonal principal), obtendo:, 
101 
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
− 1...
0.:
:1
0...01
0...001
)1(21
.
.3231
21
.
nnnn lll
ll
l
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
nnu
uu
uuu
uuuu
0......0
:.:
...00
...0
...
.
3333
232322
13131211
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
nnnnn
n
n
n
αααα
αααα
αααα
αααα
...
:::::
...
...
...
321
3333231
2232221
1131211
X = 
L U A 
}  2ª coluna de L: Faz-se o produto de todas as 
linhas de L (da 3ª até a nª) pela 2ª coluna de 
U e a iguala com os elementos da 2ª coluna 
de A, (abaixo da diagonal principal), obtendo:, 
⎪
⎪
⎪
⎪
⎪
⎩
⎪⎪
⎪
⎪
⎪
⎨
⎧
=
⋅−
=
⋅−
=⇒=⋅+⋅
⋅−
=⇒=⋅+⋅
⋅−
=⇒=⋅+⋅
.n,...,3l,
u
ulal
,
u
ulalaulul
,
u
ulalaulul
,
u
ulalaulul
22
121l2l
2l
22
121l2l
2l2l222l121l
22
124142
424222421241
22
123132
323222321231
!
102 
}  Temos a seguinte fórmula geral: 
103 
uij = aij − likukj, i ≤ j
k=1
i−1
∑
lij =
aij − likukj
k=1
j−1
∑
ujj
, i > j
$
%
&
&&
'
&
&
&
}  Resumo dos Passos: 
◦  Seja um sistema Ax = b de ordem n, onde A 
satisfaz as condições da fatoração LU. 
◦  Então, o sistema Ax = b pode ser escrito 
como: 
–  LUx = b 
104 
}  Resumo dos Passos: 
 
◦  Fazendo Ux = y, a equação acima reduz-se a 
Ly = b. 
◦  Resolvendo o sistema triangular inferior Ly = 
b, obtém-se o vetor y. 
105 
}  Resumo dos Passos: 
◦  Substituição do valor de y no sistema Ux = y 
⇒ Obtenção de um sistema triangular superior 
cuja solução é o vetor x procurado; 
◦  Aplicação da fatoração LU na resolução de 
sistemas lineares ⇒ Necessidade de solução 
de dois sistemas triangulares 
106 
}  Exemplo: 
◦  Dado o sistema, encontrar a solução. 
107 
 
2 z - 3y 
3 2z x 
4 z - 3y 2
⎪
⎩
⎪
⎨
⎧
=
=+
=+x
}  Exemplo: 
◦  Com esse sistema, formamos 2 matrizes 
108 
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
−
−
130
201
132
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
2
3
4
A = e B = 
Temos a forma Ax = B 
}  Exemplo: 
◦  Então fazemos A= L*U, Sendo: 
109 
L = e U = 
L = Matriz Triangular inferior (lower) de diagonal unitária 
U= Matriz Triangular Superior (upper) 
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
1
01
001
3231
21
ll
l
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
33
2322
131211
00
0
u
uu
uuu
A = 
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
−
−
130
201
132
}  Exemplo: 
◦  # Primeira linha de U 
110 
⎪
⎩
⎪
⎨
⎧
−=⇒=⋅
=⇒=⋅
=⇒=++⋅
11
,31
,20.00.01
131313
121212
111111
uau
uau
uau
}  Exemplo: 
◦  # Primeira coluna de L 
111 
⎪
⎪
⎩
⎪⎪
⎨
⎧
==⇒=⋅
=⇒=⋅
0
2
0
,
2
1
31311131
21211121
laul
laul
}  Exemplo: 
◦  # Segunda linha de U 
112 
⎪
⎪
⎩
⎪⎪
⎨
⎧
=⇒−⋅−=⇒=+⋅
−=⇒⋅−=⇒=+⋅
2
5)1(
2
12
,
2
33
2
10
232323231321
222222221221
uuauul
uuauul
}  Exemplo: 
◦  # Segunda coluna de L 
113 
⎪
⎪
⎩
⎪⎪
⎨
⎧
−=
−
=⇒
−
⋅−
=⇒=⋅+⋅ 2
2
3
3
2
3
303
32323222321231 llaulul
}  Exemplo: 
◦  # Terceira linha de U 
114 
⎪
⎪
⎩
⎪⎪
⎨
⎧
=+−=
⇒⋅−−−⋅−−=
⇒=+⋅+⋅
451
2
5)2()1(01
33
33
333323321331
u
u
auulul
}  Exemplo: 
◦  Matriz fatorada 
115 
L = e U = 
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
− 120
012/1
001
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
−
−
400
2/52/30
132
Voltando à fórmula Ax = B, como A = L* U obtemos LUx = B 
11
6 
}  Exemplo: 
◦  Agora substituiremos Ux por Y e obtemos a 
fórmula LY = B, onde: 
L = Y = 
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
− 120
012/1
001
Solução Retroativa: 
 
Y1 = 4 Y2 = 1 Y3 = 4 
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
3
2
1
Y
Y
Y
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
2
3
4
B = 
}  Exemplo: 
◦  Como Ux = Y e os valores de U e Y já são 
conhecidos, calculamos X. 
117 
U = X = 
Solução Retroativa: 
 
X1 = 1 X2 = 1 X3 = 1 
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
4
1
4
Y = 
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
−
−
400
2/52/30
132
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
3
2
1
X
X
X
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
3
2
1
Y
Y
Y
= 
11
8 
}  Pesquisar sobre o método direto de 
Decomposição de Cholesky, explicando como 
este funciona e quais as restrições para que 
este seja usado. 
}  Entrega: próxima quarta. 
119 
Método de Jacobi 
Método de Gauss-Seidel 
120 
}  Motivação: 
◦  Ocorrência em larga escala de sistemas lineares em 
cálculos de Engenharia e modelagem científica 
◦  Exemplos: 
–  Simulações de processos químicos 
–  Simulações de dispositivos e circuitos 
–  Modelagem de processos geocientíficos e geoambientais 
–  Análise estrutural 
–  Biologia estrutural 
–  Modelagem de processos físicos 
121 
}  Motivação: 
◦  Tendência à existência de matrizes de coeficientes 
grandes e esparsas 
–  Grandes ð Comum para n > 100.000 
–  Esparsas ð Maioria dos coeficientes nulos 
◦  Resolução de sistemas esparsos por métodos diretos 
–  Processos de triangularização e fatoração ð Onerosos, 
por não preservarem a esparsidade original, que pode ser 
útil por facilitar a resolução do sistema. 
122 
}  Motivação: 
◦  Métodos mais apropriados para a resolução de 
sistemas de natureza esparsa ð Métodos iterativos 
–  Gauss-Jacobi 
–  Gauss-Seidel 
123 
}  Como funcionam? 
◦  Partem de uma solução inicial e a partir dela geram 
uma nova solução. O processo então se repete 
gerando um sequência de soluções que deve 
convergir para a solução exata do sistema. 
O que significa convergir para a solução 
do sistema ? 
124 
}  A partir de uma estimativa inicial xi0, consistem em encontrar 
uma sequência de estimativas xik que convirja para uma 
solução do Sistema de Equações Linear (SEL) após um número 
suficientemente grande de iterações. 
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
)0(
n
)0(
3
)0(
2
)0(
1
x
x
x
x
!
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
)1(
n
)1(
3
)1(
2
)1(
1
x
x
x
x
!
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
)2(
n
)2(
3
)2(
2
)2(
1
x
x
x
x
!
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
)k(
n
)k(
3
)k(
2
)k(
1
x
x
x
x
!
!
125 
}  Vantagem ⇒ Menos suscetíveis ao acúmulo de 
erros de arredondamento do que o método direto. 
}  Lembretes importantes: 
◦  Como todo processo iterativo, estes métodos sempre 
apresentarão um resultado aproximado, que será tão 
próximo do resultado real conforme o número de 
iterações realizadas. 
◦  Além disto, também é preciso ter cuidado com a 
convergência destes métodos. 
126 
Elementos de 
um processo 
Iterativo 
Fórmula de 
iteração 
Condição de 
Convergência 
Critério de 
parada 
Solução 
inicial 
127 
}  Fórmula de iteração 
◦  Corresponde às operações matemáticas que a solução atual sofre 
para gerar uma nova solução. 
◦  Para os métodos iterativos estacionários para resolução de 
sistemas lineares tem-se: 
◦  Onde M é a matriz de iteração e c um vetor constante 
◦  O método é chamado de estacionário porque a matriz M não 
muda durante o processo. 
cMxx kk +=+1
128 
Elementos de 
um processo 
Iterativo 
Fórmula de 
iteração 
Condição de 
Convergência 
Critério de 
parada 
Solução 
inicial 
129 
}  Condição de Convergência 
◦  Todo método iterativo tem associado a ele uma condição 
de convergência que irá garantir que a cada iteração o 
método está caminhando em direção da solução do 
sistema. 
◦  Uma vez garantida a convergência, os métodos iterativos 
para resolução de sistemas lineares a cada passo obtêm 
soluções com exatidão crescente. Isso significa que: 
xxk
k
=
∞→
lim
130 
Elementos de 
um processo 
Iterativo 
Fórmula de 
iteração 
Condição de 
Convergência 
Critério de 
parada 
Solução 
inicial 
131 
ε≤
−
=
−
≤≤
−
≤≤
∞
∞
−
||max
||max
||||
||||
1
1
1
1
k
ini
k
i
k
ini
k
kk
x
xx
x
xx
ε≤
− −
||||
|||| 1
k
kk
x
xx
}  Critério de Parada 
◦  Os mé todos i t e r a t i vos não podem con t i nua r 
indefinidamente, ou seja, eles devem ser interrompidos em 
algum momento. 
◦  Alguns critérios de parada para esses métodos podem ser 
 sendo ε um parâmetro de entrada do 
 algoritmo e ||.|| é uma norma vetorial, 
◦  como por exemplo a norma infinita, e neste caso: 
132 
maxkk ≥
}  Critério de Parada 
 onde kmax é um parâmetro de entrada 
 do algoritmo que indica o número 
máximo de iterações do método. 
◦  Os do is c r i té r ios podem ser u t i l i zados 
separadamente ou em conjunto. Neste último caso 
evita-se que o programa entre o loop por não 
conseguir atingir o valor de ε estabelecido. 
133 
Elementos de 
um processo 
Iterativo 
Fórmula de 
iteração 
Condição de 
Convergência 
Critério de 
parada 
Solução 
inicial 
134 
}  Solução Inicial 
◦  Como o método parte de uma solução inicial x0 deve-se 
estabelecer como esse x0 deve ser gerado. 
135 
Métodos Iterativos 
}  Transformação do sistema linear Ax=b em x = Cx +g 
◦  A: matriz dos coeficientes, n x n 
◦  x: vetor das variáveis, n x 1; 
◦  b: vetor dos termos constantes, n x 1; 
◦  C: matriz, n x n; e 
◦  g: vetor, n x 1. 
}  Métodos a estudar 
◦  Gauss-Jacobi 
◦  Gauss-Seidel 
136 
Método de Gauss-Jacobi 
137 
}  Conhecida a solução in ic ia l , x(0) , obtém-se 
consecutivamente os vetores: 
o)aproximaçã ésima-(k ,gCxx
o)aproximaçã (segunda ,gCxx
o)aproximaçã (primeira ,gCxx
)1k()k(
)1()2(
)0()1(
+=
+=
+=
−
!
§  De um modo geral, a aproximação x(k+1) é calculada 
pela fórmula: 
 x(k+1) = C x(k)+g, k=0, 1, ... 
138 
§  Da primeira equação do sistema: 
 a11 x1 + a12 x2 + ... +a1n x2 = b1 
 obtém-se: x1 = (1/a11) (b1 - a12 x2 - ... -a1n x2) 
e, analogamente, 
 x2 = (1/a22) (b2 - a21 x1 - ... -a2n xn) 
xn = (1/ann) (bn - an1 x1 - ... - ann-1 xn-1) 
!
139 
§  Desta forma, para x(1) = C x(0) + g,
obtém-se: 
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
=
nn
n
33
3
22
2
11
1
a
b
a
b
a
b
a
b
g
!⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
−−−
−−−
−−−
−−−
=
0aaaaaa
aa0aaaa
aaaa0aa
aaaaaa0
C
nn3nnn2nnn1n
33n333323331
22n222232221
11n111131112
!
"#
!
#""
!
!
e 
140 
Ò  Condição de Convergência 
Ò  Esta é uma condição necessária! 
TEOREMA 
“ O método iterativo de JACOBI converge 
com qualquer solução inicial x0 se, e 
somente se, ρ(M) < 1, sendo ρ(M) o 
raio espectral (maior autovalor em 
módulo) da matriz de iteração M.” 
141 
Ò  Condição de Convergência 
Ò  Esta condição não é necessária, mas quando acontece garante 
a convergência do método! 
TEOREMA 
“É condição suficiente para a 
convergência do método iterativo de 
JACOBI que a matriz de coeficientes A 
seja diagonal estritamente dominante. 
,...,n,i,||a||a
n
ij
j
ijii 21 
1
=>∑
≠
=
142 
}  Critérios de Parada 
◦  Distância entre as iterações 
◦  Condição de Parada 1 
◦  Condição de Parada 2 (número de iterações) 
 x - x max d 1)-(ki
(k)
i
(k) =
 
 x max
d
 d )k(
i
(k)
(k)
r ε<
⎜⎜
=
maxkk ≥
143 
§  Seja o sistema: 
§  Determinação de C e g 
6 10x 3x 2x 
8 x 5x x 
7 3x 2x x 10
321
321
321
=++
=++
=++
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
=
6
8
7
b⎥
⎦
⎤
⎢
⎣
⎡
=
1032
151
3210
A
144 
§  Transformar no sistema Cx + g: 
§  Determinação de C e g 
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
=
10
6
5
8
10
7
g⎥⎦
⎤
⎢⎣
⎡=
03/10 –1/5-
1/5-01/5-
3/10 -2/10 -0C
145 
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
−−
−−
−−
=
0//
/0/
//0
33323331
22232221
11131112
aaaa
aaaa
aaaa
C
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
=
33
3
22
2
11
1
a
b
a
b
a
b
g
146 
§  Assim, considerando como estimativa inicial: 
 
 e ε = 0,05. 
 
 
⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
=
0,6
1,6-
0,7
x0
}  Iteração 1: 
147 
⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
=+=
0,94
1,34
0,84
 g Cx x (0)(1)
|x1(1) – x1(0)| = 0,14 
|x2(1) – x2(0)| = 2,94 
|x3(1) – x3(0)| = 0,34 
ε 2,19 
1,34
2,94 d (1)r >==
O processo para ou continua? Por quê? 
}  Iteração 2: 
148 
⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
=+=
0,030
1,244
0,150
 g Cx x (1)(2) ε>== 0,7315 1,244
0,91 d (2)r
|x1(2) – x1(1)| = 0,69 
|x2(2) – x2(1)| = 0,096 
|x3(2) – x3(1)| = 0,91 
O processo para ou continua? Por quê? 
}  Iteração 3: 
149 
 
0,1968
1,5640
0,4422
 g Cx x (2)(3)
⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
=+= ε>== 0,2046 
1,5640
0,32 d (3)r
|x1(3) – x1(2)| = 0,2922 
|x2(3) – x2(2)| = 0,3200 
|x3(3) – x3(2)| = 0,1668 
O processo para ou continua? Por quê? 
}  Iteração 4: 
150 
⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
=+=
0,0424
1,4722
0,3282
 g Cx x (3)(4) ε>== 0,1049 
1,4722 
0,1544 d (4)r
O processo para ou continua? Por quê? 
|x1(4) – x1(3)| = 0,114 
|x2(4) – x2(3)| = 0,0918 
|x3(4) – x3(3)| = 0,1544 
}  Iteração 5: 
151 
⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
=+=
0,0927
1,5259
0,3929
 g Cx x (4)(5) ε<== 0,0424 
1,5259
0,0647 d (5)r
O processo para ou continua? Por quê? 
|x1(5) – x1(4)| = 0,0647 
|x2(5) – x2(4)| = 0,0537 
|x3(5) – x3(4)| = 0,0503 
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
=
0927,0
5259,1
3929,0
x
}  Para o seguinte sistema linear, executar o 
método de Jacobi para ε = 0,15 e kmax= 25. 
}  Considere 
152 
[ ]Tx 6,025,23,60 −=
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
−
=
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
−
−
4
20
57
511
182
2310
3
2
1
x
x
x
§  Transformar no sistema Cx + g: 
§  Determinação de C e g 
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
−
=
5
4
2
5
10
57
g⎥
⎦
⎤
⎢
⎣
⎡
=
01/5– 1/5-
1/801/4-
2/103/10-0
C
153 
}  Iteração 1: 
154 
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
=+=
2,51-
0,85
4,905
 g Cx x (0)(1)
|x1(1) – x1(0)| = 1,395 
|x2(1) – x2(0)| = 1,4 
|x3(1) – x3(0)| = 1,91 
20 1 k <=
O processo para ou continua?? 
ε 0,3893 
4,905
1,91 d (1)r >==
}  Iteração 2: 
155 
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
=+=
1,951-
0,96
4,943
 g Cx x (1)(2)
ε 0,113 
4,943
0,559 d (2)r <==
|x1(2) – x1(1)| = 0,038 
|x2(2) – x2(1)| = 0,11 
|x3(2) – x3(1)| = 0,559 
O processo para ou continua?? 
20 2 k <=
}  Solução Inicial 
◦  Como para o método de Jacobi nada restringe o valor da 
solução inicial, por exemplo a convergência independe do 
valor inicial, pode-se iniciar o método com qualquer valor 
para x0. 
◦  Neste caso pode-se então iniciar o sistema com a solução 
trivial 
◦  A diferença entre uma solução inicial e outra está na 
velocidade de convergência. 
[ ]Tx 0000 =
156 
Método de Gauss-Seidel 
157 
}  Similarmente ao método de Gauss-Jacobi, conhecida a 
estimativa inicial, x(0), obtém-se consecutivamente os 
vetores x(1), x(2), ..., x(k) 
§  Todavia, ao se calcular xj(k+1), usa-se todos os valores 
x1(k+1), x2(k+1), ..., xj-1(k+1) que já foram calculados e os 
valores xj+1(k), xj+2(k), ..., xn(k) restantes. 
158 
}  Descrição: 
◦  Seja o seguinte sistema de equações: 
nnnn1n1nn33n22n11n
3nn31n1n3333232131
2nn21n1n2323222121
1nn11n1n1313212111
b x.a x.a x.a x.a x.a
 
 
b x.a x.a x.a x.a x.a
b x.a x.a x.a x.a x.a
b x.a x.a x.a x.a x.a
=+++++
=+++++
=+++++
=+++++
−−
−−
−−
−−
!
"#"
!
!
!
159 
}  Descrição: 
◦  Isolando xi a partir da linha i, tem-se: 
( )
( )
( )
( )1n1nn22n11nn
nn
n
nn31n1n32322313
33
3
nn21n1n23231212
22
2
nn11n1n13132121
11
1
x.ax.ax.ab
a
1x
 
x.ax.ax.ax.ab
a
1x
x.ax.ax.ax.ab
a
1x
x.ax.ax.ax.ab
a
1x
−−
−−
−−
−−
−−−−=
−−−−−=
−−−−−=
−−−−−=
!
"
!
!
!
160 
}  Descrição: 
◦  O processo iterativo se dá a partir das equações: 
( )
( )
( )
( )1k 1n1n,n1k22n1k11nn
nn
1k
n
k
nn3
k
1n1n,3
1k
232
1k
1313
33
1k
3
k
nn2
k
1n1n,2
k
323
1k
1212
22
1k
2
k
nn1
k
1n1n,1
k
313
k
2121
11
1k
1
x.a...x.ax.ab
a
1x
x.ax.a...x.ax.ab
a
1x
x.ax.a...x.ax.ab
a
1x
x.ax.a...x.ax.ab
a
1x
+
−−
+++
−−
+++
−−
++
−−
+
−−−−=
−−−−−=
−−−−−=
−−−−−=
161 
}  Critério de Parada: 
◦  Diferença relativa entre duas iterações consecutivas, dada 
por: 
⎪
⎪
⎪
⎪
⎪
⎩
⎪⎪
⎪
⎪
⎪
⎨
⎧
⎪⎩
⎪
⎨
⎧
≠
=
=
≠
−
=
+
+
+
+
+
≤≤
+ =
 0 x 
 
0 x 
 se , 1 
0 x x se , 0 
0 x se , 
x
xx .Máx 
 
M
 
 
 
 
k
i
1k
i
k
i
1k
i
1k
i1k
i
k
i
1k
i
ni1
1k
R
162 
}  Critério de Parada: 
◦  Fim do processo iterativo ð Valor de MRk+1 suficientemente 
pequeno para a precisão desejada 
163 
§  Resolver: 
§  Solução: 
.10.5 M com,0z6y3x3
6zy4x3
5zyx5
2k
R
−≤=++
=++
=++
( )
( )
( ) ( )yx
2
1zy3x3
6
1z
zx36
4
1y
zy5
5
1x
+−=⇒−−=
−−=
−−=
)1,0,1(−=cialSolucaoIni
164 
}  Passos (primeira iteração): 
1.  calcula-se x1 usando os valores 
de y0 e z0 e da solução inicial 
2.  calcula-se y1 usando o valor de 
x 1 já calculado nesta iteração 
no passo anterior e o valor de z0 
ainda da solução inicial 
3.  calcula-se z1 usando os valores 
de x 1 e y 1 já calculado nesta 
iteração (passos anteriores) 
65,0)18,0.36(
4
11 =−−=y
725,0)65,08,0(
2
11 −=+−=z
8,0)105(
5
11 =−−=x
165 
§  Quadro de resultados do processo iterativo 
kx kxM
ky kyM kz kzM
k
RM
-1 - 0 - 1 - - 
0,8 2,25 0,65 1 -0,725 2,379 2,379 
1,015 0,212 0,92 0,293 -0,967 0,250 0,293 
1,009 0,006 0,985 0,066 -0,997 0,030 0,066 
1,002 0,007 0,998 0,013 -1 0,003 0,013 
x = 1,002 y = 0,998 z = -1 
166 
}  Verificação (substituição no sistema) 
x = 1,002 y = 0,998 z = -1 
5.(1,002) + 1.(0,998) + 1.(-1) = 5,008 ≅ 5 OK 
3.(1,002) + 4.(0,998) + 1.(-1) = 5,998 ≅ 6 OK 
3.(1,002) + 3.(0,998) + 6.(-1) = 0 OK 
167 
}  Resolver 
168 
3x − y+ z = 9
x − 4y+ 2z =17
2x + y+ 6z = 24, com mk ≤ 0,5.
169 
}  Critérios de Convergência 
◦  Processo iterativo ð Convergência para a solução exata não 
garantida para qualquer sistema. 
◦  Necessidade de determinação de certas condições que 
devem ser satisfeitas por um SEL para a garantia da 
convergência do método. 
◦  Critérios de determinação das condições de convergência 
–  Critério de Sassenfeld 
–  Critério das Linhas 
170 
}  Critério de Sassenfeld 
◦  Sejam as quantidades βi dadas por: 
n - ordem do sistema linear que se deseja resolver 
aij - coeficientes das equações do sistema 
para i = 2, 3, ..., n 
∑
=
⋅=β
n
2j
j1
11
1 aa
1 βi =
1
aii
⋅ aij ⋅β j
j=1
i−1
∑ + aij
j=i+1
n
∑
$
%
&
&
'
(
)
)
e 
171 
}  Critério de Sassenfeld 
◦  Este critério garante que o método de Gauss-Seidel 
convergirá para um dado SEL se a quantidade M, 
definida por: 
 for menor que 1 (M<1). 
imaxM ni1 β≤≤=
172 
}  Critério de Sassenfeld 
◦  Exemplo: Seja A a matriz dos coeficientes e b o 
vetor dos termos constantes, dados por: 
444434241
334333231
224232221
114131211
b a a a a
b a a a a
b a a a a
b a a a a
( )
( )
( )
( )343242141
44
4
34232131
33
3
2423121
22
2
141312
11
1
aaa
a
1
aaa
a
1
aaa
a
1
aaa
a
1
β+β+β⋅=β
+β+β⋅=β
++β⋅=β
++⋅=β
173 
}  Critério de Sassenfeld 
◦  Exemplo: Mostrar que a solução do SEL a seguir 
convergirá pelo método de Gauss-Seidel. 
0,10x0,4x8,0x2,1x4,0
0,1x2,0xx2,0x1,0
8,7x3,0x6,0x3x6,0
4,0x2,0x2,0xx0,2
4321
4321
4321
4321
−=⋅+⋅+⋅+⋅
=⋅++⋅−⋅−
−=⋅−⋅−⋅+⋅
=⋅+⋅−+⋅
174 
}  Critério de Sassenfeld 
◦  Exemplo: Solução 
 
( )
( )
( )
( ) 2736,0358,08,044,02,17,04,0
4
1
358,02,044,02,07,01,0
1
1
44,03,06,07,06,0
3
1
7,02,02,01
2
1
4
3
2
1
=⋅+⋅+⋅⋅=β
=+⋅+⋅⋅=β
=++⋅⋅=β
=++⋅=β
M < 1 ⇒ Convergência da 
solução do sistema a partir do 
método de Gauss-Seidel 
 
10.0- 4.0 0.8 1.2 0.4 
1.0 0.2 1.0 0.2- 0.1-
7.8- 0.3- 0.6- 3.0 0.6 
0.4 0.2 0.2- 1.0 2.0
 
A b 
7,0M imaxni1 == β≤≤
175 
}  Critério das Linhas 
◦  Segundo este critério, um determinado sistema irá 
convergir pelo método de Gauss-Seidel, se: 
aij
j=1
j≠i
n
∑ < aii , para i =1, 2, 3, ..., n. 
176 
}  Critério das Linhas 
◦  Exemplo: O SEL anterior satisfaz o Critério das 
Linhas, sendo a verificação quase imediata, se for 
observado que: 
4,28,02,14,0aaa4a
5,02,02,01,0aaa1a
5,13,06,06,0aaa3a
4,12,02,01aaa2a
43424144
34323133
24232122
14131211
=++=++>=
=++=++>=
=++=++>=
=++=++>=
 4. 3, 2, 1,i para aa ii
n
ij
1j
ij =<∑
≠
=
177 
}  Tanto o Critério de Sassenfeld quanto o Critério 
das Linhas são condições suficientes, porém não 
necessárias, para a convergência do método de 
Gauss-Seidel para um dado SEL 
◦  Um dado SEL pode não satisfazer estes critérios e 
ainda convergir 
◦  Um sistema pode não satisfazer o Critério das Linhas, 
porém sua convergência será garantida se satisfizer o 
Critério de Sassenfeld 
178 
}  Critério das Linhas x Critério de Sassenfeld 
◦  Exemplo: Seja o seguinte SEL: 
§  O Critério das Linhas não é satisfeito, visto que: 
§  Todavia, o Critério de Sassenfeld é satisfeito, uma vez que: 
18x2x6
23xx10
21
21
=⋅+⋅
=+⋅
6a2a 2122 =<=
( ) 3,01,06
2
1e1,01
10
1
21 =⋅⋅=β=⋅=β
Assim sendo, a convergência do SEL é garantida. 
179 
}  Embora não altere a solução do SEL, a ordem de 
aparecimento das equações pode alterar sua convergência 
pelo método Gauss-Seidel. 
◦  Exemplo: Seja o SEL: 
◦  Observa-se que na ordem atual de aparecimento das equações, o SEL 
não satisfaz o Critério das Linhas (verificar!!!); logo, sua convergência 
não é garantida. 
◦  A inversão da ordem das duas equações do SEL fará com que o 
Critério das Linhas seja satisfeito e sua convergência pelo método de 
Gauss-Seidel garantida (verificar também!!! ). 
15x3x5
19x10x4
21
21
=⋅+⋅
=⋅+⋅−
180 
◦  Ruggiero, M. A. Gomes & Lopes, V. L. da R. Cálculo 
Numérico: Aspectos teóricos e computacionais. MAKRON 
Books, 1996, 2ª ed. 
◦  Asano, C. H. & Colli, E. Cálculo Numérico: Fundamentos e 
Aplicações. Departamento de Matemática Aplicada – 
IME/USP, 2007. 
◦  Sanches, I. J. & Furlan, D. C. Métodos Numéricos. DI/
UFPR, 2006. 
◦  Paulino, C. D. & Soares, C. Erros e Propagação de Erros, 
Notas de aula , SE/ DM/ IST [Online] http://
w w w . m a t h . i s t . u t l . p t / s t a t / p e / q e b /
semestre_1_2004-2005/PE_erros.pdf [Último acesso 07 
de Junho de 2007]. 
181