Raízes de Sistemas Lineares - Cálculo Numérico - Instituto Tecnológico de Aeronáutica

Prévia do material em texto

CCI-22
á lMatemática Computacional
Carlos Alberto Alonso Sanches
Juliana de Melo Bezerra
CCI-22
3) Raízes de Sistemas Lineares)
El d G G d Eliminação de Gauss, Gauss-Jordan, 
Decomposição LU, Gauss-Jacobi, Gauss-Seidel
CCICCI--2222
ƒ Introdução
ƒ Métodos diretos
ƒ Regra de Cramerƒ Regra de Cramer
ƒ Eliminação de Gauss
ƒ Gauss-Jordan
ƒ Resíduos e Condicionamento de Sistemas
ƒ Decomposição LU
ƒ Métodos iterativos
ƒ Gauss-Jacobi
ƒ Gauss Seidelƒ Gauss-Seidel
ƒ Considerações finais
CCICCI--2222
ƒ Introdução
ƒ Métodos diretos
ƒ Regra de Cramerƒ Regra de Cramer
ƒ Eliminação de Gauss
ƒ Gauss-Jordan
ƒ Resíduos e Condicionamento de Sistemas
ƒ Decomposição LU
ƒ Métodos iterativos
ƒ Gauss-Jacobi
ƒ Gauss Seidelƒ Gauss-Seidel
ƒ Considerações finais
Métodos de resoluçãoMétodos de resoluçãoçç
ƒ Para a resolução de um sistema linear de 
equações, há dois grupos de métodos:
ƒ Métodos diretos: a solução é obtida através da ç
aplicação de um número finito de operações 
aritméticas
ƒ Regra de Cramer
ƒ Eliminação de Gauss e de Gauss-Jordan
ƒ Decomposição LUƒ Decomposição LU
ƒ Métodos iterativos: a solução é obtida através de 
uma sequência de aproximações sucessivas até se uma sequência de aproximações sucessivas, até se 
alcançar uma resposta que satisfaça a precisão 
exigidag
ƒ Gauss-Jacobi
ƒ Gauss-Seidel
Sistemas de Equações LinearesSistemas de Equações Linearesm q çm q ç
ƒ Forma geral:
nn
bxaxaxa
bxaxaxa
=+++
=+++ ... 11212111 onde:
aaijij são os coeficientes
nnnnnn
nn
bxaxaxa
bxaxaxa
=+++
=+++
...
...
2211
22222121
M
jj
xxii são as incógnitas
bbii são os termos independentesii p
nn é a ordem do sistema
ƒ Forma matricial:
⎤⎡ ⎤⎡b⎤⎡
Ax = bAx = b ⎥⎥
⎥⎤
⎢⎢
⎢⎡
= n
n
aaa
aaa
A MOMM
L
L
22221
11211
⎥⎥
⎥⎤
⎢⎢
⎢⎡
= b
b
b M
2
1
⎥⎥
⎥⎤
⎢⎢
⎢⎡
= x
x
x M
2
1
onde:onde:
⎥⎥⎦⎢
⎢
⎣ nnnn aaa L
MOMM
21
⎥⎥⎦⎢
⎢
⎣ nb
M⎥⎥⎦⎢
⎢
⎣ nx
M
ExemploExemplompmp
ƒ Forma geral:
5x5x4x2 321 =−+
ƒ Forma geral:
1x5x4x2
2x5x1x4
321
321
−=++
=−+
1x5x4x2 321 ++
F t i i lƒ Forma matricial:
⎤⎡⎤⎡⎤⎡ − 5542 1x
⎥⎥
⎤
⎢⎢
⎡
=⎥⎥
⎤
⎢⎢
⎡
⎥⎥
⎤
⎢⎢
⎡
− 2
5
.514
542
2
1
x
x
⎥⎥⎦⎢
⎢
⎣−⎥
⎥
⎦⎢
⎢
⎣⎥
⎥
⎦⎢
⎢
⎣ 1542 3x
Cálculo das forças em uma treliçaCálculo das forças em uma treliçaf ç m m çf ç m m ç
ƒ Um exemplo: 4 8 122 4 6 8Um exemplo:
1
2
3
5
6
7 9
10
11
13
14
15
16
171 10F1, F2 e F3 2 6 10 14 17
3 5 7 9
F1 F2 F3
,
são dadas
F1 F2 F3
ƒ Condições de equilíbrio:
ƒ Na junção 2: N junçã 3:
⎪⎪
⎧ =°++°−=∑ 045cos45cos 541 fffF
aa
x 4342143421
ƒ Na junção 2: ƒ Na junção 3:
⎪
⎪⎨
⎧ =+−=
∑
∑
0
0 62
fFF
ffFx
⎪⎪⎩
⎪⎨
=−−−=
=++−=
∑
∑
0
0 
531
541
faffaF
faffaF
y
x
⎪⎩ =+−=∑ 031 fFFy
ƒ Idem para demais junções⎩
ƒ Gerará um sistema de ordem 17
CCICCI--2222
ƒ Introdução
ƒ Métodos diretos
ƒ Regra de Cramerƒ Regra de Cramer
ƒ Eliminação de Gauss
ƒ Gauss-Jordan
ƒ Resíduos e Condicionamento de Sistemas
ƒ Decomposição LU
ƒ Métodos iterativos
ƒ Gauss-Jacobi
ƒ Gauss Seidelƒ Gauss-Seidel
ƒ Considerações finais
Regra de CramerRegra de Cramerg mg m
ƒ A aplicação da regra de Cramer, em um p ç g ,
sistema de ordem n, exige o cálculo de quantos 
determinantes?
ƒ n para os numeradores e 1 para o denominador
Tempo de processamentoTempo de processamentomp p mmp p m
ƒ Seja m o tempo gasto para realizar uma multiplicação
ƒ Seja detn o número de multiplicações presentes no 
cálculo do determinante de uma matriz de ordem n
P d m s l l t mp T st p n s m ƒ Podemos calcular o tempo T gasto apenas com 
multiplicações, no caso de 17 equações:
ƒ T = m.18.det17 m. 8.det17
ƒ T = m.18.(17 + 17.det16)
ƒ T = m.18.(17 + 17.(16 + 16.det15)) 
 1 (1 1 (16 16 (15 15 d ))) ƒ T = m.18.(17 + 17.(16 + 16.(15 + 15.det14))) 
ƒ T = m.18.(17 + 17.(16 + 16.(15 + 15.(14 + 14.(... (3 + 3.(2)...))))) 
Lembrando:
Tempo de processamentoTempo de processamentomp p mmp p m
T = m.18.(17 + 17.(16 + 16.(15 + 15.(...(3 + 3.(2)...))))) m. 8.( 7 7.( 6 6.( 5 5.(...( .( )...)))))
T = m.( 2 . 3 . 4 . 5 . .... . 17 . 18 +
+ 3 . 4 . 5 . .... . 17 . 18 +
+ 4 . 5 . .... . 17 . 18 + 
+ 5 . .... . 17 . 18 + 
: :
+ 16 . 17 . 18 +
+ 17 . 18 ))
T = m.18!.(1 + (1/2!) + (1/3!) + ... + (1/16!))
T ≈ m . 9,6 . 1015
Tempo de processamentoTempo de processamentomp p mmp p m
ƒ Quantidade de multiplicações: ≈ 9,6 . 1015Q p ç ,
ƒ Utilizando um supercomputador atual:
1011 l i li õ dƒ 1011 multiplicações por segundo
ƒ Tempo gasto: 9,6 . 104 s ≈ 1 dia
ƒ Se o sistema fosse de ordem 20, exigiria 
cerca de 28 anos de processamento nesse cerca de 28 anos de processamento nesse 
mesmo computador!
ƒ Um algoritmo bem mais eficiente é o ƒ Um algoritmo bem mais eficiente é o 
Método da Eliminação de Gauss, que gasta 
tempo O(n3)tempo O(n3)
CCICCI--2222
ƒ Introdução
ƒ Métodos diretos
ƒ Regra de Cramerƒ Regra de Cramer
ƒ Eliminação de Gauss
ƒ Gauss-Jordan
ƒ Resíduos e Condicionamento de Sistemas
ƒ Decomposição LU
ƒ Métodos iterativos
ƒ Gauss-Jacobi
ƒ Gauss Seidelƒ Gauss-Seidel
ƒ Considerações finais
Método da Eliminação de GaussMétodo da Eliminação de Gaussm çm ç
ƒ Objetivo:Objet vo
ƒ Transformação do sistema linear a ser resolvido 
em um sistema linear triangularem um sistema linear triangular
ƒ Operações válidas:
ƒ Troca da ordem das linhas 
ƒ Troca da ordem das colunas (com exceção dos Troca da ordem das colunas (com exceção dos 
termos independentes)
ƒ Multiplicação de uma equação por um número real Multiplicação de uma equação por um número real 
não nulo
ƒ Substituição de uma equação por uma combinação ƒ Substituição de uma equação por uma combinação 
linear entre ela mesma e outra equação
Sistemas lineares triangularesSistemas lineares triangularesm gm g
ƒ Triangular inferior:
⎥⎥
⎤
⎢⎢
⎡
aa
a
K
K
2221
11
00
000
⎥⎥
⎥⎥
⎢⎢
⎢⎢= aaa
aa
A
MOMMM
K
K
333231
2221
0
00
ƒ Triangular superior:
⎥⎥⎦⎢
⎢
⎣ nnnnn aaaa K321
ƒ Triangular superior:
⎥⎤⎢⎡ naaa
aaaa K
0
1131211
⎥⎥
⎥⎥
⎥
⎢⎢
⎢⎢
⎢
= n
n
aa
aaa
A
MOMMM
K
K
00
0
333
22322
⎥⎥⎦⎢
⎢
⎣ nnaK
MOMMM
000
Resolução de um sistema triangularResolução de um sistema triangularç m m gç m m g
ƒ Exemplo:Exemplo:
3x5x4
1x2xx
0xx5x4x3
43
432
4321
=−
−=−+
P d l ã
2x2
3x5x4
4
43
=
ƒ Passos da resolução:
3x5x4 43 =−2
2x
315x4
3
3
=
=⋅−1
2
2x4 ==
3
1122x
1x2xx 432
=+
−=−+
10125)1(4x3
10xx5x4x3 4321
=+⋅⋅+
−=+−+
1x
1122x
2
2
−=
−=⋅−+
1x
10125)1(4x3
1
1
=
−=+⋅−−⋅+
PassosPassos
ƒ Considere a matriz aumentada [Ab]:
[ ] ⎥⎥
⎥⎤
⎢⎢
⎢⎡
= n
n
baaa
baaa
Ab 222221
111211
K
K Linha L1
Linha L2[ ]
⎥⎥⎦⎢
⎢
⎣ nnnnnn baaaa
Ab
321
MMOMM
Linha Ln
ƒ Passo 1: anular os coeficientes de x1 nas linhas L2 a Ln
ƒ Substituir a linha L2 pela combinação linear:
11
21
211212 , a
amondeLmL =⋅−
ƒ Se a11 = 0 trocar L1 com Lk onde ak1 ≠ 0
Conhecido 
como pivô
Se a11 0, trocar L1 com Lk, onde ak1 ≠ 0
ƒ Se Lk não existir, então o sistema não tem solução
ƒ Continuar analogamente para linhas Lj , 2 < j ≤ nj
ƒ Passo i, 1 < i < n: anular os coeficientes de xi nas linhas 
Li+1 a Ln
Exemplo 1Exemplo 1mpmp
⎤⎡ 5132
3x3x4x4
5xx3x2
321
321
=−+
=−+
[ ]
⎥⎥
⎥⎤
⎢⎢
⎢⎡ −
−
=
1132
3344
5132
Ab
1xx3x2321 −=+− ⎥⎦⎢⎣ −− 1132
a [ ] [ ]513223344L2
a
am,LmLL
11
21
2112122 ==⋅−= [ ] [ ][ ]7120L
513223344L
2
2
−−−=
−⋅−−=
1
a
am,LmLL
11
31
3113133 ==⋅−= [ ] [ ][ ]6260
513211132
3
3
−−=
−⋅−−−=
L
L
[ ] ⎥⎥
⎤
⎢⎢
⎡ −
= 7120
5132
Ab[ ]
⎥⎥⎦⎢
⎢
⎣ −−
−−−=
6260
7120Ab
Exemplo 1Exemplo 1mpmp
[ ]
⎥⎥
⎥
⎦⎢
⎢⎢
⎣ −−
−−−=
6260
7120Ab
⎥⎦⎢⎣ 6260
3amLmLL 32 3
a
m,LmLL
22
32
3223233 ==⋅−=
[ ] [ ]7120362603 −−−⋅−−−=L [ ] ⎥⎥
⎤
⎢⎢
⎡
−−−
−
= 7120
5132
Ab[ ] [ ]
[ ]155003
3
=L
[ ]
⎥⎥⎦⎢
⎢
⎣ 15500
⎪⎨
⎧
=⇒=⇒=
=⇒=
2x73x27xx2
3x15x5 33
⎪⎩
⎨
=⇒=⇒=−+⇒=−⋅+
=⇒−=−−⇒−=−−
1x2x2536x25xx3x2
2x73x27xx2
111321
2232
AlgoritmoAlgoritmo
ƒ Sistema linear Ax = b de ordem n:
g mg m
EliminaçãodeGauss {
para k=1 até n-1 p para i=k+1 até n {m = aik/akk // akk ≠ 0aik = 0para j=k+1 até n Eliminaçãopara j k+1 até n aij = aij – m.akjbi = bi – m.bk}
xn = bn/annpara k=n-1 até 1 {s = 0para j=k+1 até n Sistema triangularpara j=k+1 até n s = s + akj.xjxk = (bk – s)/akk}}
Sistema triangular
}
Complexidade de tempo: O(n3)
Exemplo 2Exemplo 2mpmp
⎥⎤⎢⎡ 575241
38x14x2x22
134x3x110x27
321
321
=++
=−+
⎥⎥
⎥
⎦⎢
⎢⎢
⎣
−=
3814222
134311027]Ab[
321 ⎦⎣
Nos cálculos a seguir, consideraremos F(10,3,-5,5):
[ ] [ ]
[ ]1410140020L
575241)1/27(134311027LmLL
2
12122
−−=
⋅−−=⋅−=
[ ]
[ ] ( ) [ ]
[ ]12101130860L
5752411/223814222LmLL
3
13133
2
−−−=
⋅−=⋅−=
[ ]12101130860L3
⎥⎤⎢⎡ 1410140020
575241
]Ab[
⎥⎥
⎥
⎦⎢
⎢⎢
⎣ −−−
−−=
12101130860
1410140020]Ab[
Exemplo 2Exemplo 2mpmp
⎥⎥
⎥
⎦⎢
⎢⎢
⎣ −−−
−−=
12101130860
1410140020][Ab
⎦⎣
[ ] ( ) [ ]
[ ]618006130000L
14101400202/8612101130860LmLL 23233
−−=
−−⋅−−−−−=⋅−=
[ ]618006130000L3 =
⎥⎤⎢⎡ 1410140020
575241
][Ab
⎥⎥
⎥
⎦⎢
⎢⎢
⎣ −−
−−=
618006130000
1410140020][AbApenas 3 algarismos
são representados
x3 = -61800/(-61300) = 1,01
x [ 1410 ( 1400) 1 01]/2 0 0
No entanto, a solução exata é:
ƒ x1 = 1
 1x2 = [-1410 – (-1400)⋅1,01]/2 = 0,0
x1 = [57 - 52⋅1,01 - 4⋅0,0]/1 = 4,5
ƒ x2 = 1
ƒ x3 = 1
PivoteamentosPivoteamentos parcial e completoparcial e completomm p mpp mp
ƒ Pivôs pequenos geram multiplicadores grandes, que 
aumentam os erros de arredondamento...
ƒ Uma simples alteração na Eliminação de Gauss é 
lh i ô l d i ód l escolher como pivô o elemento de maior módulo :
ƒ em cada coluna (pivoteamento parcial)
ƒ dentre todos os elementos possíveis no processo ƒ dentre todos os elementos possíveis no processo 
(pivoteamento completo): exige um maior esforço 
computacional (tempo total será O(n4))
ƒ Voltemos a resolver o exemplo anterior com precisão 
de 3 casas decimais, mas com pivoteamento parcial:
⎥⎥
⎤
⎢⎢
⎡
− 134311027
575241
⎥⎥
⎤
⎢⎢
⎡ −
575241
134311027
⎥⎥⎦⎢
⎢
⎣ 3814222
134311027
⎥⎥⎦⎢
⎢
⎣ 3814222
575241
Exemplo 2 com Exemplo 2 com pivoteamentopivoteamento parcialparcialmp mmp m p mp m pp
]134311027[)27/22(]3814222[LmLL
]521,5207,00[L
13133
2
−⋅−=⋅−=
−=
]715,166,870[L3 −−=
⎤⎡ − 134311027 ⎤⎡ − 134311027
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−−
−
715,166,870
521,5207,00
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−
−−
521,5207,00
715,166,870
7
⎦⎣ ⎦⎣
]15215200[L
]715,166,870[)6,87/07,0(]521,5207,00[LmLL
3
23233
=
−−⋅−−=⋅−=
]1,521,5200[L3
⎥⎤⎢⎡ − 715166870
134311027 x3 = 52,1/52,1 = 1
[ 71 16 5 1]/( 87 6) 0 999
⎥⎥
⎥
⎦⎢
⎢⎢
⎣
−−
1,521,5200
715,166,870 x2 = [-71-16,5⋅1]/(-87,6) = 0,999
x1 = [134 – (-3)⋅1 – 110⋅0,999]/27 = 1,00
CCICCI--2222
ƒ Introdução
ƒ Métodos diretos
ƒ Regra de Cramerƒ Regra de Cramer
ƒ Eliminação de Gauss
ƒ Gauss-Jordan
ƒ Resíduos e Condicionamento de Sistemas
ƒ Decomposição LU
ƒ Métodos iterativos
ƒ Gauss-Jacobi
ƒ Gauss Seidelƒ Gauss-Seidel
ƒ Considerações finais
Método de GaussMétodo de Gauss--JordanJordan
ƒ Consiste em efetuar operações sobre as p ç
equações do sistema com a finalidade de 
transformá-lo em um sistema diagonal g
equivalente, isto é, são nulos todos os 
coeficientes aik, quando i≠kik, q
⎥⎤⎢⎡
a K 00011
⎥⎥
⎥
⎢⎢
⎢
= a
a
A
K
000
000 22
11
⎥⎥
⎥⎥
⎢⎢
⎢⎢= aA KOMMM
L 000 33
⎥⎦⎢⎣ nnaK000
ExemploExemplompmp
⎥⎤⎢⎡
1151 ⎥⎤⎢⎡
2325Pivoteamento
4x2x3x2
2x3x2x5
321
321
321
=++
=++ [ ]
⎥⎥
⎥
⎦⎢
⎢⎢
⎣
=
4232
2325Ab
⎥⎥
⎥
⎦⎢
⎢⎢
⎣ 4232
1151
Pivoteamento
321
[ ] [ ]
[ ]
2325511151LmLL 12122 )/( ⋅−=⋅−= [ ]6040640L2 ,,,= [ ] [ ]2325524232LmLL 13133 )/( ⋅−=⋅−= [ ] [ ][ ]2380220L
2325524232LmLL
3
13133
,,,
)/(
=
[ ] ⎥⎥
⎤
⎢⎢
⎡
= 6040640
1325
Ab[ ]
⎥⎥⎦⎢
⎢
⎣
=
2380220
6040640Ab
,,,
,,,
ExemploExemplompmp
[ ]
⎥⎥
⎥
⎦⎢
⎢⎢
⎣
=
2380220
6040640Ab
,,,
,,,
⎦⎣
[ ] [ ]
[ ]9132609000L
604064064222380220LmLL 23233 ,,,),/,(,,,
=
⋅−=⋅−=
[ ]9132609000L3 ,,=
⎤⎡ 1325
[ ]
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
=
9132609000
6040640Ab
,,
,,,
⎦⎣ ,,
[ ] [ ]91326090006090406040640LmLL 32322 ,,),/,(,,, ⋅−=⋅−= [ ] [ ][ ]31310640L2
32322
,,
,,),,(,,,
−=
ExemploExemplompmp
[ ]
⎥⎥
⎥
⎦⎢
⎢⎢
⎣
−=
9132609000
31310640Ab
,,
,,
⎦⎣
[ ] [ ]
[ ]
9132609000609035711305L1 ,,),/(, ⋅−=
[ ] [ ]313106406421325L )/( ⋅=
[ ]7812005L1 ,−=
[ ] [ ]
[ ]5711305L
313106406421325L
1
1
,
,,),/(
=
−⋅−=
[ ] ⎥⎥
⎤
⎢⎢
⎡
−
−
= 31310640
7812005
Ab
,
A solução é:
ƒ x1 = -2,556
 0 54[ ] ⎥⎥⎦⎢⎢⎣ 9132609000
31310640Ab
,,
,, ƒ x2 = -0,2854
ƒ x3 = 4,783
Outra aplicaçãoOutra aplicaçãop çp ç
ƒ Uma variação do método de Gauss-Jordan ç
pode ser utilizada para se encontrar a inversa 
de uma matriz A quadrada de ordem nq
ƒ Basta transformar a matriz A na 
correspondente matriz identidade aplicando correspondente matriz identidade, aplicando 
essas mesmas operações em uma matriz 
identidade de ordem nidentidade de ordem n
| |
Gauss-Jordan
[A|I] [I|A-1]
Gauss Jordan
CCICCI--2222
ƒ Introdução
ƒ Métodos diretos
ƒ Regra de Cramerƒ Regra de Cramer
ƒ Eliminação de Gauss
ƒ Gauss-Jordan
ƒ Resíduos e Condicionamento de Sistemas
ƒ Decomposição LU
ƒ Métodos iterativos
ƒ Gauss-Jacobi
ƒ Gauss Seidelƒ Gauss-Seidel
ƒ Considerações finais
Refinamento por resíduosRefinamento por resíduosf m pf m p
ƒ Se x(1) for encontrado como solução do sistema ç
Ax = b, então o erro dessa solução é x – x(1)
ƒ Multiplicando esse erro por A:Multiplicando esse erro por A
ƒ A(x - x(1)) = b – Ax(1) = r(1)
ƒ O resíduo pode ser utilizado para se encontrar 
resíduo
ƒ O resíduo pode ser utilizado para se encontrar 
uma solução melhorada x(2):
ƒ x(2) = x(1) + δ(1) onde δ(1) é um vetor de correçãoƒ x(2) = x(1) + δ(1), onde δ(1) é um vetor de correção
ƒ Ax(2) = b ⇔ A(x(1) + δ(1)) = b ⇔ Aδ(1) = b - Ax(1) = r(1)
ƒ δ(1) é encontrado resolvendo se o sistema Aδ = r(1)ƒ δ(1) é encontrado resolvendo-se o sistema Aδ = r(1)
ƒ Esses cálculos permitem um processo de 
fi t d l ã d i t A brefinamento da solução do sistema Ax = b
ExemploExemplompmp
ƒ Considere o sistema abaixo, que será resolvido 
em uma máquina que trabalha com apenas dois 
dígitos decimais significativos :
5,5x5,2x0,3
21x0,5x16
21
21
=+
=+
,,, 21
ƒ Através da Eliminação de Gauss, podemos 
encontrar a solução abaixo:encontrar a solução abaixo:
⎥⎦
⎤⎢⎣
⎡=
940
0,1
x )1(
ƒ Cálculo do resíduo:
⎤⎡ 300 Nã tá
⎦⎣ 94,0
⎥⎦
⎤⎢⎣
⎡=−=
15,0
30,0
Axbr )1()1( Não estábom...
ExemploExemplompmp
ƒ Cálculo do vetor de correção δ(1): 
⎥⎦
⎤⎢⎣
⎡=⎥⎦
⎤⎢⎣
⎡
⎥⎦
⎤⎢⎣
⎡
15,0
30,0
δ
δ
5,20,3
0,516
)1(
2
)1(
1
⎦⎣⎦⎣⎦⎣ ,δ,, 2
ƒ Vetor de correção: ⎤⎡ 00063,0δ )1(
Arredondamento 
aquiVetorde correção: ⎥⎦
⎤⎢⎣
⎡=
058,0
6,
δ )1(
⎤⎡ 01ƒ Solução melhorada: ⎥⎦
⎤⎢⎣
⎡=+=
0,1
0,1
δxx )1()1()2(
ƒ Novo resíduo:
Portanto x(2)⎤⎡ 00 Portanto, x( )
é solução exata⎥⎦
⎤⎢⎣
⎡=−=
0,0
0,0
Axbr )2()2(
Melhor aproximaçãoMelhor aproximaçãop m çp m ç
ƒ Dado um sistema Ax = b, sejam y e z duas aproximações 
d l ã t C b l d l é lh ?da solução exata x. Como saber qual delas é melhor?
ƒ A estratégia mais lógica parece ser comparar os 
respectivos resíduos: o menor seria da melhor soluçãorespectivos resíduos: o menor seria da melhor solução
ƒ Infelizmente, isso nem sempre é verdade...
E l s á i d 2 dí it s d i isƒ Exemplo na mesma máquina de 2 dígitos decimais:
⎪⎨
⎧
=++
=++
520x240x160x120
840x120x360x240
321
321
,,,,
,,,,
⎥⎥
⎤
⎢⎢
⎡
−= 14
25
y ⎥⎥
⎤
⎢⎢
⎡−
= 4
3
z ⎥⎥
⎤
⎢⎢
⎡
= 000
000
ry ,
,
⎥⎥
⎤
⎢⎢
⎡
= 240
120
rz ,
,
⎥⎥
⎤
⎢⎢
⎡−
= 4
3
x
⎪⎩
⎨
=++
++
640x250x210x150
520x240x160x120
321
321
,,,,
,,,,
ƒ Conclusão: nem sempre a aproximação de menor 
⎥⎥⎦⎢
⎢
⎣ −1
14y
⎥⎥⎦⎢
⎢
⎣ 0
4z
⎥⎥⎦⎢
⎢
⎣ 080
000ry
,
,
⎥⎥⎦⎢
⎢
⎣ 250
240rz
,
,
⎥⎥⎦⎢
⎢
⎣ 1
4x
p p ç
resíduo é a mais exata
ƒ Se a busca por resíduos menores não garante melhores p g
soluções, como saber se o processo de refinamento por 
resíduos funciona?
Condicionamento de sistemasCondicionamento de sistemasm mm m
ƒ Um sistema linear é dito mal condicionado se pequenas alterações 
nos dados de entrada (A ou b) ocasionam grandes erros no resultado nos dados de entrada (A ou b) ocasionam grandes erros no resultado 
final
ƒ Exemplo em outra máquina de 3 dígitos decimais:
⎩⎨
⎧
=+
=+
060,0y422,0x481,0
119,0y844,0x961,0
Solução: x=1,00 e y=-0,998
ƒ Suponha que os valores desse sistema sejam obtidos 
experimentalmente, e por isso os termos independentes possam 
variar de ±0 001: l b dvariar de ±0,001:
⎩⎨
⎧
=+
=+
060,0y422,0x481,0
120,0y844,0x961,0
Valor perturbado
Solução: x=0,00 e y=0,142⎩ y
Erro na entrada: (|0,119-0,120|/|0,119|) ≈ 0,8%
Erro no resultado: (|-0,998-0,142|/|-0,998|) ≈ 114%
ƒ Quando há mal condicionamento, alta precisão nos cálculos não 
significa quase nada, pois os resultados obtidos não são confiáveis...
Interpretação geométricaInterpretação geométricap ç g mp ç g m
ƒ Considere os seguintes sistemas:g
⎩⎨
⎧
=+
=+
50016y5014x51
11y3x
,,,⎩⎨
⎧
=+
=+
50316y5014x51
11y3x
,,,
(a)
(b)
(a)
(c)
Solução: x=2 e y=3
⎩ y⎩ y
Solução: x=10,28 e y=0,24
y
(a)
( )
(b)
x
(c)
x
Uma métrica de condicionamentoUma métrica de condicionamentom m mm m m
ƒ Em máquinas com grande precisão, geralmente não faz 
sentido refinar os resultados...
ƒ No entanto, empiricamente, os refinamentos ajudam a , mp m , f m j m
identificar o condicionamento de um sistema linear:
ƒ Se as correções δ(1), δ(2), ..., δ(n) forem grandes, então o Se as correções δ , δ , ..., δ forem grandes, então o 
sistema será mal condicionado
ƒ Em sistemas bem condicionados, bastam dois refinamentos: ,
δ(3), ..., δ(n) serão próximos do épsilon da máquina
ƒ Importante: nesse processo de verificação, o vetor b p p ç ,
não pode ser nulo 
ƒ Caso contrário, mesmo em um sistema mal condicionado, a Caso contrário, mesmo em um sistema mal condicionado, a 
solução exata será nula, com correções também nulas...
ExemploExemplompmp
ƒ Considere o sistema abaixo em F(10,5,-98,100):
⎪
⎪⎨
⎧
=−+
=++
04731x32531x958900x47251
0647000x62314x62351x47592
321
321
,,,,
,,,,
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−=
244190
07172
84061
x 1 ,
,
)(
⎪⎩ −=−+ 678900x47941x89652x69512 321 ,,,, ⎥⎦⎢⎣− 244190,
ƒ Primeiro refinamento em F(10 10 -98 100):Primeiro refinamento em F(10,10, 98,100):
⎥⎥
⎥⎤
⎢⎢
⎢⎡−
−
=
⎥⎥
⎥⎤
⎢⎢
⎢⎡−
⎥⎥
⎥⎤
⎢⎢
⎢⎡=−= 000055377,0
00012180,0
047355377,1
064821801,0
0473,1
0647,0
Axbr )1()1(
Resíduos 
pequenos
ƒ Resolução de 
⎥⎦⎢⎣−⎥⎦⎢⎣−⎥⎦⎢⎣− 000076696,0678823304,06789,0
ƒ Solução melhorada 
p q
Resolução de 
Aδ = r(1):
⎥⎤⎢⎡
− 00000422820,
Solução melhorada 
x(2) = x(1) + δ(1):
⎤⎡ 84051
Correções 
relativamente 
⎥⎥
⎥
⎦⎢
⎢⎢
⎣ −
=δ
0000577650
00002511001
,
,)(
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−
−=
244190
07172
84051
x 2
,
,
,
)(
relativamente 
pequenas
Outra métrica de condicionamentoOutra métrica de condicionamentom mm m
ƒ Mostraremos agora outra maneira de identificar o mal 
di i d i li ã i l A bcondicionamento de um sistema linear não singular Ax = b
ƒ Vamos supor que os dados estão sujeitos a certas 
b õ li f i l ãperturbações, e analisaremos seus efeitos na solução
ƒ Inicialmente, seja b + ∆b uma perturbação no vetor de 
 i d dtermos independentes
ƒ Desse modo, a solução também será perturbada, ou seja, 
 A( ∆ ) b ∆bteremos A(x + ∆x) = b + ∆b
ƒ Desejamos encontrar uma relação entre ∆x e ∆b, pois, 
h d h d b ã ∆b d conhecendo o tamanho da perturbação ∆b, poderemos 
estimar ∆x, e verificar então se o sistema é ou não mal 
condicionadocondicionado
ƒ Para isso, teremos que rever o conceito de normas
Normas de vetoresNormas de vetoresmm
ƒ Dado um vetor x do espaço vetorial E, chama-se norma de p ç ,
x (denotada por ||x||) qualquer função definida em E com 
valores em R que satisfaz as seguintes condições: 
ƒ ||x|| ≥ 0
ƒ ||x|| = 0 se e somente se x for o vetor nulo
ƒ ||λx|| = |λ|.||x||, para todo escalar λ
ƒ ||x+y|| ≤ ||x|| + ||y||, onde y є E
ƒ Exemplos de normas de vetores em E = Rn:
ƒ ||x||∞ = máxi |xi|i i
ƒ ||x||1 = Σi|xi|
ƒ ||x||E = (Σixi2)1/2E ( i i )
Normas de matrizesNormas de matrizesm mm m
ƒ Dada uma matriz A do espaço vetorial E de matrizes p ç
quadradas de ordem n, chama-se norma de A (denotada 
por ||A||) qualquer função definida em E com valores em
R ti f i t di õ R que satisfaz as seguintes condições: 
ƒ ||A|| ≥ 0
|| || lƒ ||A|| = 0 se e somente se A for a matriz nula
ƒ ||λA|| = |λ|.||A||, para todo escalar λ
|| || || || || ||ƒ ||A+B|| ≤ ||A|| + ||B||, onde B є E
ƒ Exemplos de normas de matrizes, onde A = (aij):
ƒ Norma linha: ||A||∞ = máxi Σj|aij| 
ƒ Norma coluna: ||A||1 = máxj Σi|aij| 
ƒ Norma euclidiana: ||A||E = (Σi,jaij2)1/2
Usando normasUsando normasmm
ƒ Desenvolvendo a equação A(x + ∆x) = b + ∆b :
∆ ∆ƒ Ax + A∆x = b + ∆b
ƒ Como Ax = b, então A∆x = ∆b
D d A é ã i l tã ∆ A 1∆bƒ Desde que A é não singular, então ∆x = A-1∆b
ƒ Se uma norma de matriz e uma norma de vetor estão 
relacionadas de tal modo que satisfaça a desigualdade relacionadas de tal modo que satisfaça a desigualdade 
||Ax|| ≤ ||A||.||x||, para qualquer vetor x de ordem n, 
então dizemos que as duas normas são consistentesentão d zemos que as duas normas são cons stentes
ƒ Usando normas consistentes:
ƒ ||∆x|| ≤ ||A-1|| ||∆b||||∆x|| ≤ ||A ||.||∆b||
ƒ De Ax = b, também temos ||b|| ≤ ||A||.||x||
ƒ Multiplicando as inequações membro a membro:ƒ Multiplicando as inequações membro a membro:
ƒ ||∆x||.||b|| ≤ ||A||.||A-1||.||∆b||.||x||
Número de condiçãoNúmero de condiçãom çm ç
ƒ ||∆x||.||b|| ≤ ||A||.||A-1||.||∆b||.||x||
ƒ ||∆x||/||x|| ≤ ||A||.||A-1||.||∆b||/||b||
ƒ ||∆x||/||x|| ≤ cond(A).||∆b||/||b|||| || || || ( ) || || || ||
ƒ Observações:
ƒ Número de condição de A: Número de condição de A: 
cond(A) = ||A||.||A-1|| ≥ ||A.A-1|| = ||I|| = 1
ƒ ||∆b||/||b|| é uma medida do erro relativo em b
ƒ O erro em ||∆x||/||x|| dependerá de cond(A), que é maior ou 
igual a 1
ƒ Se cond(A) for grande, então pequenas perturbações relativas 
em b produzirão grandes perturbações relativas em x, e o 
sistema Ax = b será mal condicionadot ma rá ma c n c na
ƒ Geralmente, sistemas com cond(A) ≥ 104 são considerados mal 
condicionadosOutro caso possívelOutro caso possívelpp
ƒ Consideremos agora outro caso possível: o vetor b é 
conhecido exatamente mas ocorre uma perturbação na conhecido exatamente, mas ocorre uma perturbação na 
matriz A. Teremos, portanto, (A + ∆A)(x + ∆x) = b
ƒ Desenvolvendo:Desenvolvendo:
ƒ (x + ∆x) = (A + ∆A)-1b Equação (*)
ƒ Como x = A-1b, temos: ∆x = (A + ∆A)-1b - A-1b( )
ƒ ∆x = [(A + ∆A)-1 - A-1]b = [B-1 – A-1]b, onde A + ∆A = B
ƒ B-1 – A-1 = (A-1A)B-1 – A-1(BB-1) = A-1(A – B)B-1
∆ 1 1 1 1 1 ∆ ∆ 1ƒ ∆x = (B-1 - A-1)b = [A-1(A – B)B-1]b = [A-1(A – (A + ∆A))(A + ∆A)-1]b
ƒ ∆x = -A-1∆A(A + ∆A)-1b
ƒ Utilizando a equação (*): ∆x = A-1∆A(x + ∆x)ƒ Utilizando a equação ( ): ∆x = -A 1∆A(x + ∆x)
ƒ Aplicando normas consistentes em ambos os membros: 
||∆ || ||A 1|| ||∆A|| ||( ∆ )||ƒ ||∆x|| ≤ ||A-1||.||∆A||.||(x + ∆x)||
ƒ ||∆x|| /||(x + ∆x)|| ≤ cond(A).||∆A||/||A||: semelhante ao anterior
ExemploExemplompmp
ƒ Analisar o sistema linear abaixo:
⎥⎦
⎤⎢⎣
⎡=⎥⎦
⎤⎢⎣
⎡⎥⎦
⎤⎢⎣
⎡
1440,0
8642,0
x
x
1441,02161,0
8648,02969,1
2
1
ƒ Através de Gauss-Jordan, podemos calcular A-1:
⎦⎣⎦⎣⎦⎣
⎥⎦
⎤⎢⎣
⎡
−
−=−
2969,12161,0
8648,01441,0
10A 81
⎦⎣
ƒ Usando a norma linha, que é consistente:
ƒ ||A||∞ = 2,1617
ƒ ||A-1||∞ = 1,5130.108
ƒ cond(A) = ||A|| ||A-1|| ≈ 3 3 108ƒ cond(A) = ||A||∞.||A 1||∞ ≈ 3,3.108
ƒ Conclusão: sistema mal condicionado
Alguns comentáriosAlguns comentários
ƒ Um sistema é mal condicionado se for excessivamente 
í l t b õ d d d t d
g mg m
sensível a perturbações em seus dados de entrada
ƒ A solução de um sistema mal condicionado, mesmo 
calculada com grande precisão pode ser pouco exatacalculada com grande precisão, pode ser pouco exata
ƒ Geralmente, essa situação pode ser detectada quando: 
ƒ no processo de refinamento as correções permanecem grandes ƒ no processo de refinamento, as correções permanecem grandes 
ƒ o número de condição da matriz A for muito maior que a unidade
ƒ Importante:ƒ Importante:
ƒ Resíduos pequenos não garantem a qualidade de uma solução
ƒ A precisão da máquina influi no condicionamento do sistema prec são da máqu na nflu no cond c onamento do s stema
ƒ Há sistemas lineares em que o processo de refinamento 
converge para uma solução, mas a matriz A tem um número de 
c ndiçã rande (p r exempl da rdem de 102 u 103) Nestes condição grande (por exemplo, da ordem de 102 ou 103). Nestes 
casos, o sistema está próximo de ser mal condicionado, ou seja, a 
solução encontrada pode não ser confiável...
CCICCI--2222
ƒ Introdução
ƒ Métodos diretos
ƒ Regra de Cramerƒ Regra de Cramer
ƒ Eliminação de Gauss
ƒ Gauss-Jordan
ƒ Resíduos e Condicionamento de Sistemas
ƒ Decomposição LU
ƒ Métodos iterativos
ƒ Gauss-Jacobi
ƒ Gauss Seidelƒ Gauss-Seidel
ƒ Considerações finais
Outra forma de ver...Outra forma de ver...f mf m
ƒ Consideremos o sistema de 3 equações Ax = b:
)(0
232221
131211
Aaaa
aaa
A =
⎥⎥
⎥⎤
⎢⎢
⎢⎡=
⎥⎥
⎥⎤
⎢⎢
⎢⎡= 2
1
b
b
b
⎥⎥
⎥⎤
⎢⎢
⎢⎡= 2
1
x
x
x
333231 aaa ⎥
⎥
⎦⎢
⎢
⎣ ⎥⎦⎢⎣ 3b⎥⎦⎢⎣ 3x
ƒ Após a primeira fase da Eliminação de Gauss:p p ç
⎥⎥
⎤
⎢⎢
⎡
−==⎥⎥
⎤
⎢⎢
⎡
= 01m
001
MondeAMaa0
aaa
A 21000123122
1
13
1
12
1
11
1 )()()()()(
)()()(
)( ,.
⎥⎥⎦⎢
⎢
⎣−⎥
⎥
⎦⎢
⎢
⎣ 10maa0 31
21
1
33
1
32
2322
)()(
ƒ Após a segunda fase da Eliminação de Gauss:ƒ Após a segunda fase da Eliminação de Gauss:
⎥⎤⎢⎡⎥
⎤⎢⎡ 010
001
MdAM0
aaa
A 11122
2
13
2
12
2
11
2 )()()()()(
)()()(
)(
⎥⎥
⎥
⎦⎢
⎢⎢
⎣ −
==
⎥⎥
⎥
⎦⎢
⎢⎢
⎣
=
1m0
010MondeAM
a00
aa0A
32
111
2
33
2
23
2
22
2 )()()(
)(
)()()( ,.
Outra forma de ver...Outra forma de ver...f mf m
ƒ Resumindo:
ƒ A = A(0)
ƒ A(1) = M(0).A(0) = M(0).A
ƒ A(2) = M(1) A(1) = M(1) M(0) Aƒ A(2) = M(1).A(1) = M(1).M(0).A
ƒ A = (M(1).M(0))-1.A(2)
ƒ A = (M(0))-1.(M(1))-1.A(2)( ) ( )
ƒ É fácil comprovar que:
⎥⎤⎢⎡
001
⎥⎥
⎥
⎦⎢
⎢⎢
⎣
=−−
1
01)()(
3231
21
1)1(1)0(
mm
mMM
ƒ Portanto:ƒ Portanto:
ULaa0
aaa
01m
001
A 223222
2
13
2
12
2
11
21 .
)()(
)()()(
=⎥⎥
⎤
⎢⎢
⎡
⎥⎥
⎤
⎢⎢
⎡
= UL
a00
aa0
1mm
01mA
2
33
2322
3231
21 .
)( ⎥⎥⎦⎢
⎢
⎣⎥
⎥
⎦⎢
⎢
⎣
Decomposição LUDecomposição LUmp çmp ç
ƒ A comprovação anterior pode ser generalizada em um 
tteorema:
⎥⎥
⎤
⎢⎢
⎡
⎥⎥
⎤
⎢⎢
⎡
2222
n1131211
21 uuu0
uuuu
001m
0001 KK
⎥⎥
⎥⎥
⎥
⎢⎢
⎢⎢
⎢
⋅
⎥⎥
⎥⎥
⎥
⎢⎢
⎢⎢
⎢
== n333
n22322
3231
21
uu00
uuu0
0
01mm
001m
ULA
MOMMM
K
K
OMMM
K
K
.
⎥⎦⎢⎣⎥⎦⎢⎣ nn3n2n1n u0001mmm KK
ƒ Dada uma matriz quadrada de ordem n, seja Ak a matriz 
íd d k l h l d constituída das primeiras k linhas e colunas de A. 
Suponha que det(Ak) ≠ 0, 0 ≤ k ≤ n-1. Então:
ƒ Existe uma única matriz triangular inferior L=(m ) com m = 1 ƒ Existe uma única matriz triangular inferior L=(mij), com mii = 1, 
1 ≤ i ≤ n. Os demais são os multiplicadores da Eliminação de Gauss 
ƒ Existe uma única matriz triangular superior U=(uij), tais que j
L.U = A
ƒ det(A) = u11.u22. ... .unn
Decomposição LUDecomposição LUmp çmp ç
ƒ Portanto, dados o sistema linear Ax = b e a 
d si ã ( f t ã ) LU d t i A t s:decomposição (ou fatoração) LU da matriz A, temos:
ƒ Ax = b ⇔ (L.U)x = b
ƒ Chamando Ux = y o sistema original passa a ser Ly = b Chamando Ux = y, o sistema original passa a ser Ly = b, 
ou seja, surgem dois sistemas triangulares
ƒ Por outro lado, é fácil verificar que y = L-1.b é o vetor b , q y
acumulando as operações da Eliminação de Gauss
ƒ Por exemplo, no caso de um sistema com 3 equações:
ƒ Como L = (M(0))-1.(M(1))-1, então L-1 = M(1).M(0)
ƒ Portanto, y = M(1).M(0).b
ƒ Vantagem da decomposição A = L U: uma vez calculadas ƒ Vantagem da decomposição A = L.U: uma vez calculadas 
as matrizes L e U (em tempo cúbico), resolvemos mais 
rapidamente (em tempo quadrático) outros sistemas p m ( m mp q ) m
com a mesma matriz A. Isso é útil, por exemplo, no 
refinamento por resíduos
ExemploExemplompmp
1x4x2x3 321 =++
3x2x3x4
2x2xx
321
321
321
=++
=++ multiplicadores
3x2x3x4 321 =++
⎤⎡ 423 ⎤⎡ 423 ⎤⎡ 423⎤⎡ 423
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
=
234
211
423
A
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
310310
32310
423
//
//
⎥⎥
⎥⎤
⎢⎢
⎢⎡
4134
323131
423
/
///
⎥⎥
⎥⎤
⎢⎢
⎢⎡
3103134
323131
423
///
///
⎥⎦⎢⎣ 234 ⎥⎦⎢⎣ − 310310 // ⎥⎦⎢⎣ − 4134 /
⎤⎡ 001 ⎤⎡ 423
⎥⎦⎢⎣ − 3103134 ///
⎥⎥
⎤
⎢⎢
⎡
= 0131
001
L / ⎥⎥
⎤
⎢⎢
⎡
= 32310
423
U // Tempo cúbico
⎥⎥⎦⎢
⎢
⎣ 1134 / ⎥
⎥
⎦⎢
⎢
⎣ − 400
ExemploExemplompmp
1x4x2x3 321 =++ ⎤⎡ 001 ⎤⎡ 423
3x2x3x4
2x2xx
1x4x2x3
321
321
+
=++
++
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
=
1134
0131
001
L
/
/
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
=
400
32310
423
U //
3x2x3x4 321 =−+ ⎥⎦⎢⎣ 1134 / ⎥⎦⎢⎣ − 400
Ax = b LUx = b
231
1y1 =
/ ⎥
⎤⎢⎡ 35
1
/
 L 
L b
3yyy34
2yy31
321
21
=++
=+
/
/
⎥⎥
⎥
⎦⎢
⎢⎢
⎣
=
0
35y /Ly = b
Tempo 
d á i
⎥⎥
⎤
⎢⎢
⎡−
= 5
3
x35x32x31
1x4x2x3 321
+
=++
///Ux = y
quadrático
⎥⎥⎦⎢
⎢
⎣
=
0
5x
0x4
35x32x31
3
32
=−
=+ ///Ux = y
Outra aplicaçãoOutra aplicaçãop çp ç
ƒ A decomposição LU também é útil no cálculo p ç
da matriz inversa
ƒ Resolver o sistema AX = B, onde A, X e B são Resolver o s stema AX B, onde A, X e B são 
matrizes de ordem n, é o mesmo que resolver 
n sistemas Ax = b, onde x e b são vetores de n s st mas , on são tor s 
tamanho n
ƒ A inversa A-1 da matriz A pode ser A inversa A da matriz A pode ser 
encontrada através da resolução do sistema 
AX = I onde I é a matriz identidadeAX I, onde I é a matrizidentidade
ƒ Nesse caso, basta realizar uma única vez a 
decomposição LU da matriz A e depois decomposição LU da matriz A, e depois 
utilizá-la na resolução de n sistemas
Decomposição LU com pivoteamentoDecomposição LU com pivoteamentomp ç m p mmp ç m p m
ƒ É possível incorporar as estratégias de pivoteamento 
i l l t à d i ã LUparcial ou completo à decomposição LU
ƒ Uma matriz quadrada P de ordem n é uma matriz de 
permutação se for obtida da correspondente matriz permutação se for obtida da correspondente matriz 
identidade através de permutações em suas linhas ou 
colunas
ƒ As eventuais permutações de linhas ou colunas na 
matriz A(k), obtida em um passo intermediário da 
Eliminação de Gauss, podem ser realizadas através da 
multiplicação por uma matriz de permutação
E lƒ Exemplo:
⎥⎤⎢⎡⎥⎤⎢⎡⎥⎤⎢⎡ 562
951
951
413
100
010
AP k )(⎥
⎤⎢⎡ 951
413
A k )(
⎥⎥
⎥
⎦⎢
⎢⎢
⎣
=
⎥⎥
⎥
⎦⎢
⎢⎢
⎣⎥
⎥⎥
⎦⎢
⎢⎢
⎣
=
413
562
562
951
001
100AP k .. )(
⎥⎥
⎥
⎦⎢
⎢⎢
⎣
=
562
951A k )(
Exemplo com pivoteamento parcialExemplo com pivoteamento parcialmp m p m pmp m p m p
9xx4x3 =+
234
3x2x2x
9xx4x3
321
321
=++
=+−
2x3x4 31 −=−
⎤⎡ 143 ⎤⎡ ⎤⎡ 304
⎥⎥
⎥⎤
⎢⎢
⎢⎡
−
=
304
221
143
A 0)(
⎥⎥
⎥⎤
⎢⎢
⎢⎡=
001
010
100
P 0)(
⎥⎥
⎥⎤
⎢⎢
⎢⎡ −==
143
221
304
A.PA )0()0()0('
⎥⎦⎢⎣ −304 ⎥⎦⎢⎣ 001 ⎥⎦⎢⎣ − 143
⎥⎥
⎥⎤
⎢⎢
⎢⎡
−
= 411241
304
A 1 //)( ⎥⎥
⎤
⎢⎢
⎡
= 100
001
P 1)( ⎥⎥
⎤
⎢⎢
⎡
−
−
== 413443
304
APA 111 //. )()()('
⎥⎥⎦⎢
⎢
⎣ − 413443 // ⎥
⎥
⎦⎢
⎢
⎣ 010 ⎥
⎥
⎦⎢
⎢
⎣ 411241 //
Exemplo com pivoteamento parcialExemplo com pivoteamento parcialmp m p m pmp m p m p
⎥⎤⎢⎡
−304
⎥⎥
⎥
⎦⎢
⎢⎢
⎣ −
−=
8352141
413443A 2
///
//)(
⎦⎣ 85
⎥⎥
⎤
⎢⎢
⎡
= 0143
001
L / ⎥⎥
⎤
⎢⎢
⎡ −
= 41340
304
U /
⎥⎥⎦⎢
⎢
⎣ −
=
12141
0143L
//
/
⎥⎥⎦⎢
⎢
⎣
−=
83500
41340U
/
/
L U A’ P A d P P(1) P(0)ƒ L.U = A’ = P.A, onde P = P(1).P(0):
⎥⎤⎢⎡⎥⎤⎢⎡
−
⎥⎤⎢⎡
304143100
⎥⎥
⎥
⎦⎢
⎢⎢
⎣
−=
⎥⎥
⎥
⎦⎢
⎢⎢
⎣ −⎥
⎥⎥
⎦⎢
⎢⎢
⎣
==
221
143
304
221
010
001APA ..'
⎦⎣⎦⎣⎦⎣
ƒ A’x = b’ ⇔ PAx = Pb ⇔ LUx = Pb
Exemplo com pivoteamento parcialExemplo com pivoteamento parcialmp m p m pmp m p m p
9xx4x3 321 =+− ⎤⎡ 001 ⎤⎡ −304
2x3x4
3x2x2x
9xx4x3
321
321
=++
+
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
=
12141
0143
001
L
//
/
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−=
83500
41340
304
U
/
/
2x3x4 31 −=− ⎥⎦⎢⎣ − 12141 // ⎥⎦⎢⎣ 83500 /
Ax = b LUx = Pb
⎥⎤⎢⎡
−
221
2
/⎥
⎤⎢⎡⎥⎤⎢⎡⎥⎤⎢⎡⎥⎤⎢⎡ 3
9
001
100y
0143
001 1
/Ly Pb
⎥⎥
⎥
⎦⎢
⎢⎢
⎣
=
435
221y
/
/
⎥⎥
⎥
⎦⎢
⎢⎢
⎣−⎥
⎥⎥
⎦⎢
⎢⎢
⎣
=
⎥⎥
⎥
⎦⎢
⎢⎢
⎣⎥
⎥⎥
⎦⎢
⎢⎢
⎣ − 2
3
010
001
y
y
12141
0143
3
2 ..
//
/Ly = Pb
⎥⎤⎢⎡ 1
1⎥⎤⎢⎡⎥⎤⎢⎡⎥⎤⎢⎡
−
221
2
x
x
41340
304 1
//Ux = y
⎥⎥
⎥
⎦⎢
⎢⎢
⎣
−=
2
1x
⎥⎥
⎥
⎦⎢
⎢⎢
⎣
=
⎥⎥
⎥
⎦⎢
⎢⎢
⎣⎥
⎥⎥
⎦⎢
⎢⎢
⎣
−
435
221
x
x
83500
41340
3
2
/
/.
/
/Ux = y
AlgoritmoAlgoritmo
ƒ Decomposição LU com pivoteamento parcial em um 
sistema de ordem n
g mg m
sistema de ordem n
ƒ Saída: matriz D = L+U-I e matriz de permutação P
LUPivotParcial {
D = A // matriz de ordem n// id id d d dP = I // identidade de ordem n
para j=1 até n-1 {
q = jmax = |djj|para k=j+1 até n {se |dkj| > max então { Escolha do pivô| kj| {max = |dkj|q = k}
Escolha do pivô
\\ continua...
Algoritmo (continuação)Algoritmo (continuação)g m ( ç )g m ( ç )
LUPivotParcial {
// continuação
se q ≠ j então {para k=1 até n {para k 1 até n {t = djkdjk = dqkdqk = t}
Troca das linhas q e j
}trocar linhas q e j em Pse |djj| = 0 então parar (A é singular)senão {r = 1/dr = 1/djjpara i=j+1 até n {m = dij.rdij = mpara k=j+1 até n Eliminaçãopara k=j+1 até n dik = dik – m.djk}}}}return D, P} Complexidade de tempo: O(n3)
MatLabMatLab
ƒ No MatLab 7.8 (2009), os números reais são armazenados em 64 
bit ( i ã d l d IEEE) j 16 dí it d i ibits (precisão dupla da IEEE), ou seja, possuem 16 dígitos decimais
ƒ A\b
ƒ Vetor coluna com a solução do sistema linear Ax = bƒ Vetor coluna com a solução do sistema linear Ax = b
ƒ inv(A)
ƒ Inversa da matriz A
ƒ [L,U] = lu(A)
ƒ Matrizes L e U recebem a decomposição LU da matriz A, usando pivoteamento 
p i l nd L m l p m t ãparcial, onde L acumula a permutação
ƒ [L,U,P] = lu(A)
ƒ Idem, retornando também a matriz de permutação P tal que P.A = L.UIdem, retornando também a matriz de permutação P tal que P.A L.U
ƒ linsolve(A,b)
ƒ Vetor coluna com a solução de Ax = b, usando LU com pivoteamento parcial
ƒ cond(A,x)
ƒ Número de condição da matriz A (x =1: norma coluna ; x = Inf: norma linha)
CCICCI--2222
ƒ Introdução
ƒ Métodos diretos
ƒ Regra de Cramerƒ Regra de Cramer
ƒ Eliminação de Gauss
ƒ Gauss-Jordan
ƒ Resíduos e Condicionamento de Sistemas
ƒ Decomposição LU
ƒ Métodos iterativos
ƒ Gauss-Jacobi
ƒ Gauss Seidelƒ Gauss-Seidel
ƒ Considerações finais
Métodos iterativosMétodos iterativos
ƒ Como foi inicialmente comentado, os métodos iterativos 
para resolução de sistemas lineares consistem em 
encontrar uma sequência de aproximações sucessivas
ƒ Dada uma estimativa inicial x(0), calcula-se a sequência 
x(1), x(2), x(3) ..., até que determinado critério de parada 
j ti f itseja satisfeito
ƒ O sistema Ax = b é transformado em x(k) = Cx(k-1) + g, 
k 0 d C é i k>0, onde C é uma matriz e g um vetor
ƒ Possíveis critérios de parada:
ƒ máximo erro absoluto ou relativo
ƒ número de iterações
ƒ Principais métodos: Gauss-Jacobi e Gauss-Seidel
CCICCI--2222
ƒ Introdução
ƒ Métodos diretos
ƒ Regra de Cramerƒ Regra de Cramer
ƒ Eliminação de Gauss
ƒ Gauss-Jordan
ƒ Resíduos e Condicionamento de Sistemas
ƒ Decomposição LU
ƒ Métodos iterativos
ƒ Gauss-Jacobi
ƒ Gauss Seidelƒ Gauss-Seidel
ƒ Considerações finais
Método de GaussMétodo de Gauss--JacobiJacobi
ƒ Considere o sistema linear em sua forma inicial:
1nn1212111 bxaxaxa =+++ ...
2nn2222121 bxaxaxa =+++ ...
MMOMM
nnnn22n11n bxaxaxa =+++ ...
ƒ Isolando a i-ésima incógnita na i-ésima equação:
ƒ x1 = (b1 - a12 x2 - ... - a1n xn)/a11
ƒ x2 = (b2 - a21 x1 - ... - a2n xn)/a22
...
ƒ xn = (bn - an1 x1 - ... - an,n-1 xn-1)/ann
Método de GaussMétodo de Gauss--JacobiJacobi
iteração calculada iteração anterior
ƒ Dessa forma, seja x(k) = Cx(k-1) + g, onde k>1:
iteração calculada iteração anterior
⎥⎥
⎤
⎢⎢
⎡
−−
−−
aa0aa
aaaa0
C 22n22221
11n11112
L
L
//
//
⎥⎥
⎤
⎢⎢
⎡
222
111
ab
ab
/
/
⎥⎥
⎥
⎦⎢
⎢⎢
⎣ −−
=
0aaaa
aa0aa
C
nn2nnn1n
22n22221
L
MOMM
//
//
⎥⎥
⎥
⎦⎢
⎢⎢
⎣
=
nnn
222
ab
g
/
M
⎦⎣ ⎦⎣
ƒ Exemplos de critérios de parada:Exemplos de critérios de parada:
ƒ Erro absoluto: d(k) = máx1≤i≤n|xi(k) – xi(k-1)| < ε
E l (k) (k)/( á | (k)|) ƒ Erro relativo: dr(k) = d(k)/(máx1≤i≤n|xi(k)|) < ε
ExemploExemplompmp
⎤⎡ 1011020 // ⎤⎡ 10/77xx2x10 ++
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−−
−−
−−
=
010351
51051
1011020
C
//
//
//
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−=
10/6
5/8
10/7
g
6x10x3x2
8xx5x
7xx2x10
321
321
++
−=++
=++
70 ⎤⎡
⎥⎦⎢⎣ 010351 // ⎥⎦⎢⎣ 10/66x10x3x2 321 =++
⎤⎡ 960
g
60
6,1
7,0
x )0( =
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−=ε = 0,05
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−=+=
940
861
960
gCxx 01 ,
,
)()(
escolha 6,0 ⎥⎦⎢⎣ ⎥⎦⎢⎣ 940,
|x1(1) – x1(0)| = 0,26
escolha 
arbitrária
| 1 1 | ,
|x2(1) – x2(0)| = 0,26 dr(1) = 0,34/(máx |xi(1)|) = 0,1828 > ε
|x3(1) – x3(0)| = 0,34
ExemploExemplompmp
⎤⎡ −− 1011020 // ⎥⎤⎢⎡
107 /
⎥⎤⎢⎡
960,
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣⎡
−−
−−=
010351
51051C
//
//
⎥⎥
⎥
⎦⎢
⎢⎢
⎣
=
106
58g
/
/
⎥⎥
⎥
⎦⎢
⎢⎢
⎣
−=
940
861x 1
,
,)(
⎤⎡ 9780
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−=+=
9660
981
9780
gCxx 12
,
,
,
)()( dr(2) = 0,12/1,98 = 0,0606 > ε
⎥⎦⎢⎣ 9660,
dr(3) = 0,0324/1,9888 = 0,0163 < ε⎥⎥
⎤
⎢⎢
⎡
−=+= 98881
99940
gCxx 23 ,
,
)()(
⎥⎥⎦⎢
⎢
⎣ 99840,
Critério das linhasCritério das linhas
ƒ Em um método iterativo, a convergência para a Em m m , g p
solução exata não é garantida: é preciso que o 
sistema satisfaça alguns requisitosm f ç g q
ƒ Há uma condição suficiente para a convergência 
d Mét d de Gauss Jac bi c nhecid c m do Método de Gauss-Jacobi, conhecido como o 
critério das linhas :
n,...,2,1ipara,aa ii
n
ij =<∑
ij
1j
≠
=
ExemplosExemplosmpmp
ƒ Considere o exemplo anterior:
8xx5x
7xx2x10
321
321
−=++
=++ 2+1 < 10
1+1 < 5 Garantia de 
ê i
6x10x3x2
8xx5x
321
321
=++ 2+3 < 10 convergência
3xx 21 =+
ƒ Considere o exemplo abaixo:
1 = 1 Não há garantia 
3x3x 21
21
−=− 1 < 3
Não há garantia 
de convergência
N t t ét d d G J bi t i t ƒ No entanto, o método de Gauss-Jacobi converge neste sistema 
para a solução exata x1 = x2 = 3/2. Verifique!
ƒ Isso mostra que o critério das linhas é suficiente, mas não q
necessário
DemonstraçãoDemonstraçãom çm ç
ƒ Sejam:
ƒ x* = [x1, x2, ..., xn]T: a solução exata de Ax = b
ƒ x(k) = [x(k)1, x(k)2, ..., x(k)n]T: a k-ésima aproximação de x*
(k) (k) éƒ e(k) = x(k) – x*: erro na k-ésima aproximação
ƒ Queremos garantir que limk→∞ e(k)i = 0, 1≤i≤n
ƒ Sabemos que:
ƒ x*1 = (b1 - (a12x*2 + a13x*3 + ... + a1nx*n))/a11
ƒ x(k)1 = (b1 - (a12x(k-1)2 + a13x(k-1)3 + ... + a1nx(k-1)n)/a11
ƒ Calculando e(k)1 = x(k)1 – x*1, temos:
ƒ e(k)1 = -(a12e(k-1)2 + a13e(k-1)3 + ... + a1ne(k-1)n)/a11
ƒ Analogamente:
ƒ e(k)2 = -(a21e(k-1)1 + a23e(k-1)3 + ... + a2ne(k-1)n)/a22
ƒ e(k)n = -(an1e(k-1)1 + an2e(k-1)2 + ... + an(n-1)e(k-1)n-1)/ann
Demonstração (continuação)Demonstração (continuação)m ç ( ç )m ç ( ç )
ƒ Sejam:
ƒ E(k) = máx {|e(k) |}ƒ E(k) = máx1≤i≤n{|e(k)i|}
ƒ αi = (|ai1| + ... + |ai(i-1)| + |ai(i+1)| + ... + |ain|)/|aii|, 1≤i≤n 
Quando o critério das linhas é satisfeito, αi < 1
ƒ Quando k→∞, x(k)→x* é equivalente a E(k)→0
ƒ Demonstraremos que E(k) ≤ α.E(k-1), onde α = máx1≤i≤n{αi}
ƒ Para 1 ≤ i ≤ n:
ƒ e(k)i = -(ai1e(k-1)1 + ... + ai(i-1)e(k-1)i-1 + ai(i+1)e(k-1)i+1 + ... + aine(k-1)n)/aii
| (k) | (| | | (k 1) | | | | (k 1) | | | | (k 1) | ƒ |e(k)i| ≤ (|ai1|.|e(k-1)1| + ... + |ai(i-1)|.|e(k-1)i-1| + |ai(i+1)|.|e(k-1)i+1| + ... + 
|ain|.|e(k-1)n|)/|aii|
ƒ |e(k)i| ≤ (|ai1| + ... + |ai(i-1)| + |ai(i+1)| + ... + |ain|).E(k-1)/|aii|| i| (| i1| | i(i-1)| | i(i+1)| | in|) | ii|
ƒ |e(k)i| ≤ αi.E(k-1)
ƒ Portanto, E(k) ≤ α.E(k-1)
ƒ Consequentemente, E(k)/E(k-1) ≤ α
Como α<1, então E(k)→0 quando k→∞: há convergência!
Mais um exemploMais um exemplom mpm mp
ƒ Considere o sistema a seguir:
3x2x2x5
2xx3x
321
321
=++
−=++ 3+1 > 1
5+2 > 2 Não há garantia 
d ê i
6x8x6
3x2x2x5
32
321
−=+
++
6 < 8
de convergência
ƒ No entanto, uma permutação entre as duas primeiras linhas 
garante a convergência:
3225 2 2 5
686
2xx3x
3x2x2x5
321
321
−=++
=++ 2+2 < 5
1+1 < 3
6 8
Garantia de 
convergência
6x8x6 32 −=+ 6 < 8
ƒ Quando o critério das linhas não for satisfeito, convém tentar 
uma permutação de linhas e/ou colunas
CCICCI--2222
ƒ Introdução
ƒ Métodos diretos
ƒ Regra de Cramerƒ Regra de Cramer
ƒ Eliminação de Gauss
ƒ Gauss-Jordan
ƒ Resíduos e Condicionamento de Sistemas
ƒ Decomposição LU
ƒ Métodos iterativos
ƒ Gauss-Jacobi
ƒ Gauss Seidelƒ Gauss-Seidel
ƒ Considerações finais
Método de Método de GaussGauss--SeidelSeidel
ƒ Analogamente ao Método de Gauss-Jacobi Analogamente ao Método de Gauss Jacobi, 
calcula-se x(k) = Cx(k-1) + g:
⎥⎥
⎥⎤
⎢⎢
⎢⎡ −−
−−
= aa0aa
aaaa0
C 22n22221
11n11112
L
L
//
//
⎥⎥
⎥⎤
⎢⎢
⎢⎡
= 222
111
ab
ab
g
/
/
⎥⎥⎦⎢
⎢
⎣ −− 0aaaa
C
nn2nnn1n L
MOMM
// ⎥
⎥
⎦⎢
⎢
⎣
=
nnn ab
g
/
M
ƒ No entanto, utiliza-se no cálculo de :)k(ix
ƒ valores da iteração anterior: 
ƒ valores calculados na mesma iteração: )k( 1i)k(1 x,...,x −
)1k(
n
)1k(
1i x,...,x
−−
+
ç 1i1 , ,
ExemploExemplompmp
⎤⎡05xxx5 321 =++
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
=
0
0
0
x 0)(ε = 0,05
0x6x3x3
6xx4x3
321
321
321
=++
=++
⎦⎣0x6x3x3 321 ++
⎥⎤⎢⎡ −− 2,02,00 ⎥
⎤⎢⎡ 51
1
⎥⎥
⎥
⎦⎢
⎢⎢
⎣ −−
−=
05,05,0
25,0075,0C
⎥⎥
⎥
⎦⎢
⎢⎢
⎣
=
0
5,1g
ƒ Processo iterativo:
)1k(
3
)k(
1
)k(
2
)1k(
3
)1k(
2
)k(
1
x25,0x75,05,1x
x2,0x2,01x
−−=
−−=
−
−−
)k(
2
)k(
1
)k(
3 x5,0x5,0x −−=
ExemploExemplompmp
)1k(
3
)1k(
2
)k(
1 x2,0x2,01x −−= −−
)k()k(
1
)k(
)1k(
3
)k(
1
)k(
2
321
x50x50x
x25,0x75,05,1x
,,
−−=
−−= −
ƒ Primeira iteração:
213 x5,0x5,0x =
7500175051x
1001x
1
2
1
1
,.,,)(
)(
=−−=
=−−=
⎥⎥
⎤
⎢⎢
⎡
= 750
1
x 1 ,)(
875075050150x 13 ,,.,.,)( −=−−=
| (1) (0)| 1
⎥⎥⎦⎢
⎢
⎣− 8750,
|x1(1) – x1(0)| = 1
|x2(1) – x2(0)| = 0,75 dr(1) = 1/(máx |xi(1)|) = 1 > ε
|x3(1) – x3(0)| = 0,875
r ( i )
ExemploExemplompmp
)1k(
3
)1k(
2
)k(
1 x2,0x2,01x −−= −−
)k()k(
1
)k(
)1k(
3
)k(
1
)k(
2
321
x50x50x
x25,0x75,05,1x
,,
−−=
−−= −
ƒ Segunda iteração:
213 x5,0x5,0x =
9508750250025175051x
0251875020750201x
2
2
2
1
,),.(,,.,,
,),.(,,.,
)(
)(
=−−−=
=−−−=
⎥⎥
⎤
⎢⎢
⎡
= 950
0251
x 2 ,
,
)(
9875095050025150x 23 ,,.,,.,)( −=−−=
|x (2) x (1)| = 0 025
⎥⎥⎦⎢
⎢
⎣− 98750,
|x1(2) – x1(1)| = 0,025
|x2(2) – x2(1)| = 0,20 dr(2) = 0,2/(máx |xi(2)|) = 0,1951 > ε2 2
|x3(2) – x3(1)| = 0,1125
r ( i )
ExemploExemplompmp
)1k(
3
)1k(
2
)k(
1 x2,0x2,01x −−= −−
)k()k(
1
)k(
)1k(
3
)k(
1
)k(
2
321
x50x50x
x25,0x75,05,1x
,,
−−=
−−= −
ƒ Terceira iteração:
213 x5,0x5,0x =
99120987502500075175051x
007519875020950201x
3
2
3
1
,),.(,,.,,
,),.(,,.,
)(
)(
=−−−=
=−−−=
⎥⎥
⎥⎤
⎢⎢
⎢⎡= 99120
00751
x 3 ,
,
)(
9993099120500075150x 33 ,,.,,.,)( −=−−=
| (3) (2)| 0 0175
⎥⎦⎢⎣− 99930,
|x1(3) – x1(2)| = 0,0175
|x2(3) – x2(2)| = 0,0412 dr(3) = 0,0412/(máx |xi(3)|) = 0,0409 < ε2 2
|x3(3) – x3(2)| = 0,0118
Critério de SassenfeldCritério de Sassenfeldff
ƒ Sejam os seguintes valores:
∑
=
⋅=β
n
2j
j1
11
1 aa
1
=2j11a
⎥⎥
⎤
⎢⎢
⎡ +β⋅⋅=β ∑∑− n ij1i jiji aa1 para 1 < i ≤ n⎥⎥⎦⎢⎢⎣ ββ ∑∑ +== 1ij ij1j jijiii a , para 1 < i ≤ n
β = máx {β } 1 ≤ j ≤ n
ƒ Se β < 1, então o Método de Gauss-Seidel gera 
β = máx {βj}, 1 ≤ j ≤ n
uma sequência convergente, qualquer que seja 
x(0)
ƒ Quanto menor for β, mais rápida será a convergência
ExemploExemplompmp
87x30x60x3x60
40x20x20xx2
4321
4321
,,,,
,,,
−=−−+
=+−+
010x4x80x21x40
01x20xx20x10
4321
4321
,,,,
,,,,
−=+++
=++−−
4321
β = (1 + 0 2 + 0 2)/2 = 0 7β1 = (1 + 0,2 + 0,2)/2 = 0,7
β2 = (0,6.0,7 + 0,6 + 0,3)/3 = 0,44 β = 0,7 < 1
β3 = (0,1.0,7 + 0,2.0,44 + 0,2)/1 = 0,358
β4 = (0 4 0 7 + 1 2 0 44 + 0 8 0 358)/4 = 0 2736
β ,7 
β4 (0,4.0,7 1,2.0,44 0,8.0,358)/4 0,2736
DemonstraçãoDemonstraçãom çm ç
ƒ Sejam:
ƒ x* = [x1, x2, ..., xn]T: a solução exata de Ax = b
ƒ x(k) = [x(k)1, x(k)2, ..., x(k)n]T: a k-ésima aproximação de x*
ƒ e(k) = x(k) – x*: erro na k-ésima aproximação
ƒ Queremos garantir que limk→∞ e(k)i = 0, 1≤i≤n
ƒ No método de Gauss-Seidel, podemos constatar que: 
ƒ e(k)1 = -(a12e(k-1)2 + a13e(k-1)3 + ... + a1ne(k-1)n)/a11
ƒ e(k)2 = -(a21e(k)1 + a23e(k-1)3 + ... +a2ne(k-1)n)/a22
ƒ e(k)n = -(an1e(k)1 + an2e(k)2 + ... + an(n-1)e(k)n-1)/ann
ƒ Sejam:
ƒ E(k) = máx1≤i≤n{|e(k)i|}
ƒ β1 = (|a12| + |a13| + ... + |a1n|)/|a11|
ƒ βi = (β1.|ai1| + ... + βi-1.|ai(i-1)| + |ai(i+1)| + ... + |ain|)/|aii|, 1<i≤n
Demonstração (continuação)Demonstração (continuação)m ç ( ç )m ç ( ç )
ƒ Quando k→∞, x(k)→x* é equivalente a E(k)→0
ƒ Demonstraremos por indução no índice i (1≤i≤n) que E(k) ≤ β.E(k-1), 
onde β = máx1≤i≤n{βi}
ƒ Base (i=1): ƒ Base (i=1): 
ƒ |e(k)1| ≤ (|a12|.|e(k-1)2| + |a13|.|e(k-1)3| + ... + |a1n|.|e(k-1)n|)/|a11|
ƒ |e(k)1| ≤ [(|a12| + |a13| + ... + |a1n|)/|a11|]. máx1≤i≤n{|e(k-1)i|}≤ ≤
ƒ |e(k)1| ≤ β1.E(k-1) ≤ β.E(k-1)
ƒ Hipótese (1<i≤n): |e(k)i-1| ≤ βi-1.E(k-1) ≤ β.E(k-1)
ƒ Passo (1<i≤n):
ƒ |e(k)i| ≤ (|ai1|.|e(k)1| + ... + |ai(i-1)|.|e(k)i-1| + |ai(i+1)|.|e(k-1)i+1| + ... + 
|ain|.|e(k-1)n|)/|aii||ain|.|e n|)/|aii|
ƒ |e(k)i| ≤ (|ai1|.β1 + ... + |ai(i-1)|.βi-1 + |ai(i+1)| + ... + |ain|).E(k-1)/|aii|
ƒ |e(k)i| ≤ βi.E(k-1) ≤ β.E(k-1)
ƒ Portanto, E(k)/E(k-1) ≤ β
ƒ Como β<1, então E(k)→0 quando k→∞: há convergência!
ExemplosExemplosmpmp
ƒ Considere o sistema abaixo, anteriormente visto:
3x3x
3xx
21
21
−=−
=+ ( ) 31311
111
2
1
==β
==β
//.
/
Não há garantia 
de convergência21
ƒ No entanto, o Método de Gauss-Seidel converge neste sistema 
para a solução exata x1 = x2 = 3/2 Verifique!
1=β g
para a solução exata x1 = x2 = 3/2. Verifique!
ƒ Isso mostra que o critério de Sassenfeld, como o critério das 
linhas, é suficiente, mas não necessário
23xx10 +
ƒ Considere outro sistema:
101011 ==β ,/
18x2x6
23xx10
21
21
=−
=+ ( )
130
3021062
1
<=β
==β
β
,
,/,.
,
ƒ Neste caso, o critério de Sassenfeld garante a convergência, 
mas o critério das linhas, não...
Relação entre os critériosRelação entre os critériosçç
ƒ Se um sistema satisfaz o critério das linhas, então 
t mbém s tisf á ité i d S ss nf ldtambém satisfará o critério de Sassenfeld
ƒ Demonstração:
 } 1 ƒ Seja α = máx1≤i≤n{αi} < 1, 
onde αi = (|ai1| + ... + |ai(i-1)| + |ai(i+1)| + ... + |ain|)/|aii|
ƒ Vamos provar por indução em i que βi ≤ αi < 1 1≤i≤nVamos provar por indução em i que βi ≤ αi < 1, 1≤i≤n
ƒ Base (i=1): 
ƒ β1 = (|a12| + |a13| + ... + |a1n|)/|a11| = α1 < 1β1 (| 12| | 13| | 1n|) | 11| 1
ƒ Hipótese (1<i≤n): βi-1 ≤ αi-1 < 1
ƒ Passo (1<i≤n):
ƒ βi = (β1.|ai1| + ... + βi-1.|ai(i-1)| + |ai(i+1)| + ... + |ain|)/|aii|
ƒ βi ≤ (|ai1| + ... + |ai(i-1)| + |ai(i+1)| + ... + |ain|)/|aii| = αi < 1
ƒ Portanto, α < 1 ⇒ β < 1
ƒ A volta nem sempre é verdadeira...
CCICCI--2222
ƒ Introdução
ƒ Métodos diretos
ƒ Regra de Cramerƒ Regra de Cramer
ƒ Eliminação de Gauss
ƒ Gauss-Jordan
ƒ Resíduos e Condicionamento de Sistemas
ƒ Decomposição LU
ƒ Métodos iterativos
ƒ Gauss-Jacobi
ƒ Gauss Seidelƒ Gauss-Seidel
ƒ Considerações finais
Considerações finaisConsiderações finaisç fç f
ƒ Tanto o critério das linhas como o critério de 
Sassenfeld são condições suficientes para a 
convergência, mas não necessáriasg ,
ƒ Em sistemas esparsos (com grande número de 
fi i t l ) Mét d d Eli i ã d coeficientes nulos), o Método da Eliminação de 
Gauss não é apropriado, pois não preserva esta 
t j lid d N é vantajosa qualidade. Nesses casos, convém 
utilizar métodos iterativos
ƒ Os métodos iterativos são menos suscetíveis ao 
acúmulo de erros de arredondamentoacúmulo de erros de arredondamento
Métodos diretos Métodos diretos versusversus iterativositerativos
ƒ Convergênciag
ƒ Diretos: não faz sentido considerar essa questão, 
pois calculam a solução exatap ç
ƒ Iterativos: ocorre sob determinadas condições
ƒ Esparsidade da matriz de coeficientesƒ Esparsidade da matriz de coeficientes
ƒ Diretos: alteram a estrutura da matriz
ƒ Iterativos: utilizam sempre a matriz inicial
ƒ Erros de arredondamento
ƒ Diretos: ocorrem a cada etapa e acumulam-se
ƒ Iterativos: somente os erros da última etapa ƒ Iterativos: somente os erros da última etapa 
afetam a solução