Solução Numérica de Sistemas Lineares

Prévia do material em texto

Capítulo 3 
Solução Numérica de Sistemas de Equações Lineares 
 
 
Neste capítulo estudaremos alguns métodos numéricos para encontrar a solução 
numérica de sistemas com n equações lineares e n incógnitas. 
Seja o sistema 
 
 










nnnnnn
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
...
...
...
2211
22222121
11212111

 (3.1) 
 
Escrito na forma matricial como 
 
 bA x (3.2) 
 
onde 
 
11 12 1 1 1
21 22 2 2 2
1 2
. .
. .
. . . . . x . e .
. . . . . . .
. .
n
n
n n nn n n
a a a x b
a a a x b
A b
a a a x b
     
     
     
       
     
     
    
    
 
ou nnjiaA  ][ , 
 
 Para a existência de uma única solução, é necessário que a matriz A seja não 
singular, isto é det( ) 0A  , além disso, podemos assegurar a existência da inversa da 
matriz A , 1A , encontraríamos então a solução , mas os métodos que 
envolvem inversão de matrizes (método de Cramer) não é aconselhável pois envolvem 
um número grande de operações, muitas vezes inviáveis computacionalmente, daí a 
necessidade de outras técnicas numéricas de resolução. Em alguns métodos utilizaremos 
operações elementares nas matrizes do sistema (3.1), para isto lembraremos da seguinte 
propriedade para SEL. 
 
Propriedade: A solução de um sistema linear não se altera se subtrairmos de uma 
equação outra equação multiplicada por uma constante ou permutamos duas equações. 
 
 
Os métodos numéricos de resolução de sistemas lineares são divididos em dois 
grupos: Métodos Diretos e Métodos Indiretos ou Iterativos. 
 
a) Métodos Diretos: Usamos operações elementares no sistema para 
chegarmos num sistema mais simples onde é obtida a solução exata (com exceção dos 
erros de arredondamento) do Sistema de Equações Lineares, como por exemplo: o 
método de eliminação de Gauss, Crout (LU), Cholesky (Khaletsky), etc. 
 
b) Métodos Indiretos: A aproximação da solução do sistema bA x é obtido 
iterativamente partindo de uma aproximação inicial e gerando uma sequencia de 
vetores que deve convergir à solução para uma precisão prefixada . Os métodos 
iterativos são usados para sistemas lineares de grande porte, sistemas esparsos (i.é. para 
matrizes que representam os sistemas onde a maioria dos elementos são nulos). 
Estudaremos os métodos iterativos mais conhecidos: método de Jacobi, método de 
Gauss-Seidel e S.O.R. (Successive Over Relaxation). 
 
3.1 Métodos Diretos 
 
3.1.1. Método de Eliminação de Gauss 
Para um sistema linear com n equações lineares e n incógnitas, computacionalmente, o 
método de Gauss (método já conhecido) é muito mais conveniente que o método de 
Cramer, pois para encontrar a solução do sistema linear, no método de escalonamento 
de Gauss, são efetuadas aproximadamente 
6
7
2
3
3
2 23 nnn
 operações, já no método 
de Cramer são aproximadamente !)1)(1( nnn  operações. 
 
 Se temos, por exemplo, uma matriz A
1010
, pelo método de Gauss realizamos 805 
operações para gerar a solução e no Cramer realiza 359.251.200 operações . Se 
tivermos uma matriz A
2020
, por Gauss realiza 5910 operações e no Cramer 
970.727.901.262.479.360.000 operações. Muita diferença! Estas quantidades aumentam 
mais ainda quando n é grande. 
 
 
 
 
 
 
 
 
 
 
 
 
O matemático, astrônomo e físico 
alemão Gauss (1777-1855) contribuiu 
em diversas áreas da ciência, é 
conhecido como o “Príncipe da 
Matemática”. 
 
 
 
 
 
Johann Carl Friedrich Gauss. 
 (1777-1855) 
 
 
 
 O método de eliminação de Gauss consiste em transformara a matriz principal 
que representa o sistema linear (3.1) a uma matriz triangular superior obtendo um 
sistema equivalente, i.e. 
bA x cU x 
 
Para isto, em cada etapa usaremos operações elementares na matriz aumentada e 
organizaremos os elementos da diagonal tal que resultem ser não nulos (aii  0, 
i=1,2,...,n), caso o sejam, permutaremos as linhas, então na etapa 1, eliminamos a 
variável na 2
a
, 3
a
, ...,enésima equações. Na etapa 2, eliminamos na 3
a
, 4
a
, 
...,enésima equações. E assim por diante. 
 
Por motivos didáticos, vamos descrever o método para um exemplo de uma matriz 33. 
Assim, Consideremos o seguinte SEL (Sistema de Equações Lineares): 








3333232131
2323222121
1313212111
bxaxaxa
bxaxaxa
bxaxaxa
 
na forma matricial 































3
2
1
3
2
1
333231
232221
131211
b
b
b
x
x
x
aaa
aaa
aaa
 
A matriz aumentada que representa o sistema 










3
2
1
333231
232221
131211
b
b
b
aaa
aaa
aaa
 










)0(
3
)0(
2
)0(
1
)0(
33
)0(
32
)0(
31
)0(
23
)0(
22
)0(
21
)0(
13
)0(
12
)0(
11
b
b
b
aaa
aaa
aaa
 
Etapa 1. Eliminação de da segunda e terceira equação: 
 Se 
 
 então trocar linhas 
 Se não: 
 
 elmto pivô da etapa 1. 
i) Calcular 
 
 
 
 e trocamos a linha 2 pela linha 2 menos vezes a 
linha 1, ou seja: 2 2 21 1:L L m L  
{
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
ii) Calcular 
 
 
 
 e trocamos a linha 3 pela linha 3 menos vezes a 
linha 1, i.e: 
 
3 3 31 1:L L m L  
{
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Nesta etapa a matriz aumentada ficou da seguinte forma: 
 










)1(
3
)1(
2
)0(
1
)1(
33
)1(
32
)1(
23
)1(
22
)0(
13
)0(
12
)0(
11
0
0
b
b
b
aa
aa
aaa
 
 
Etapa 2. Eliminação de da terceira equação: 
 Se 
 
 então trocar a linha 2 com a linha 3 
 Se não: 
 
 elmto pivô da etapa 2. 
i) Calcular 
 
 
 
 e trocamos a linha 3 pela linha 3 menos vezes a 
linha 2, ou seja: {
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
e a matriz aumentada ficou: 
 
 
 
 
 
 Que na forma de sistema fica: 
 








)2(
33
)2(
33
)1(
23
)1(
232
)1(
22
)0(
13
)0(
132
)0(
121
)0(
11
bxa
bxaxa
bxaxaxa
 (3.3) 
 
 
Assim encontramos os valores de 3x , 2x e 1x pelo processo retroativo: 
 
)2(
33
)2(
3
3
a
b
x  
 
)1(
22
3
)1(
23
)1(
2
2
)(
a
xab
x

 










)2(
3
)1(
2
)0(
1
)2(
33
)1(
23
)1(
22
)0(
13
)0(
12
)0(
11
00
0
b
b
b
a
aa
aaa
 
)0(
11
3
)0(
132
)0(
12
)0(
1
1
)(
a
xaxab
x

 . 
 
 
Exemplo 1: Dado o sistema 
 
1
2
3
2 1 3 2
5 6 1 1
1 3 8 3
x
x
x
    
    
 
    
    
    
 
Vamos a determinar a solução através do método de eliminação de Gauss, 
triangularizando a matriz estendida, temos: 
2 1 3 2
5 6 1 1
1 3 8 3
 
 
 
 
 
2 1 3 2
0 8.5 6.5 6
0 3.5 6.5 2
 
 
  
 
 
2 1 3 2
0 8.5 6.5 6
0 0 9.1765 4.4706
 
 
  
 
 
 
Foram calculados na 
Etapa 1: 2 2 21 1:L L m L  com 
 
 
 
 
 
 
 e 3 3 31 1:L L m L  com 
 
 
 
 
 
 
 
Etapa2: com 
 
 
 
 
 
 
 
 
Então 
 2x1 - x2 + 3 x3 = 2 
 8.5x2 - 6.5 x3 = -69.1765x3 = 4.4706 
Daí, obtemos a solução : x3 = 0.48718, x2 = -0.33333 e x1= 0.10256 
 
Estratégia de Pivoteamento 
 
Em cada etapa k devemos observar os elementos pivô pois ao calcular os 
multiplicadores: 
 
 
 
 
 
 
poderia acontecer que 
 
 ou 
 
 levando o sistema a ser instável, 
nestes casos deve-se utilizar a seguinte estratégia: 
No início da etapa k do processo de eliminação, escolher para pivô o maior elemento 
em módulo 
entre os coeficientes aik, i= k, k+1,...,n , isto é, o {| | | | | |} ou seja 
o maior elemento em modulo entre todos os elementos da coluna que estivermos 
trabalhando, que ainda atuam no processo de eliminação, fazendo a troca de linhas se 
for necessário. Esta estratégia é conhecida como condensação pivotal. Vejamos o 
seguinte exemplo: 
 
Exemplo 2: Resolva o sistema: 
 








324
14.02
121.0
321
321
321
xxx
xxx
xxx
 (3.4) 
Se no sistema aplicamos diretamente o método de eliminação de Gauss, sem 
condensação pivotal teríamos: 
 
 













3
1
1
124
4.012
211.0












43
21
1
81420
6.39210
211.0











1
21
1
8.100
6.39210
211.0
 
logo: 
x3 =0.555555 
x2 = -0.04762 
x1 = -1.587 
 
Se verificamos em qualquer equação do sistema (3.4) devemos ter a igualdade, mas se 
substituímos na 3
a
 equação: 
 -4 (-1.587) + 2(-0.04762) + 0.55555 = 6.8083  3 
 
Portanto a solução achada é incorreta, devido ao pivô a11 = 0.1 tem valor próximo a 
zero, assim deu origem a multiplicadores altos, que por sua vez ampliaram erros de 
arredondamento. 
 
Nestes casos é recomendável aplicar o método de eliminação de Gauss com 
condensação pivotal temos: 
 
 













3
1
1
124
4.012
211.0
(trocar L1 e L3) 












1
1
3
211.0
4.012
124
 
 










075.1
5.0
3
025.205.10
9.000
124
  (trocar L2 e L3) 










5.0
075.1
3
9.000
025.205.10
124
 
assim obtemos: 
 x3 = 0.555555; 
 x2 = -0.047619 
 x1 = -0.6349206 
podemos verificar em qualquer equação do sistema (3.4), por exemplo: 
 2x1 -x2 +0.4x3 = 2(-0.6349206) - (-0.047619) + (0.4)(0.555555) = -1 
 0.1x1 + x2 + 2x3 = (0.1)( -0.6349206) - 0.044719 + 2(0.555555) = 0.999999999  1 
 
 
Exercício 1: Determine a solução do seguinte sistema pelo método de eliminação 
Gauss: 
 
{
 
 
 
 7532 4321  xxxx
6111246 4321  xxxx
681024 4321  xxxx
601082 432  xxx
 
Solução X = (1, -2, 3, -4) 
 
Exercício 2: Supondo sempre que os coeficientes ajj  0, escreva um programa em 
Pascal ou em outra linguagem de programação que determine a solução do sistema 
linear A
nn
 x = b
n1
, considerando o seguinte algoritmo: 
 
 
Algoritmo: 
inicio: 
Para k=1,2,...,n-1 faça 
 para i = k+1,k+ 2,...,n faça 
 m =aik /akk 
 aik = 0 
 para j = k+1,..., n faça 
 aij = aij - m akj 
 bi = bi – m bk 
 fim-para 
fim-para 
 
 
 
 
 
para k = n-1,..., 1 faça 
 s=0 
 para j=(k+1),...,n faça 
 
 
 
 
 
fim. 
 
3.1.2. Método de Crout (ou Método de Decomposição LU) 
Foi desenvolvido pelo matemático americano Prescott Durand Crout (1907 – 
1984) este método também é conhecido como o método LU, pois descompõe a matriz 
quadrada A (não singular) como o produto de duas matrizes L e U, onde L é uma 
matriz triangular inferior e U uma matriz triangular superior da forma: A=LU 
 
11 12 13 1
21 22 23 2
31 32 33 3
1 2 3
.
n
n
n
n n n nn
a a a a
a a a a
a a a a
a a a a
 
 
 
 
 
 
 
 
 = 
















1
01
001
0001
321
3231
21





nnn lll
ll
l
 
















nn
n
n
n
u
uu
uuu
uuuu
000
00
0
333
22322
1131211





 
 
Assim Ax b LUx b 
 {
 
 
 (3.5) 
 
Então para resolver o sistema Ax b , primeiro resolvemos em (3.5) o sistema 
e posteriormente o sistema , uma vez que as matrizes L e U já foram 
triangularizadas. 
Assim, seja o SEL: 
(*) 











444443242141
343433232131
2424323222121
1414313212111
bxaxaxaxa
bxaxaxaxa
bxaxaxaxa
bxaxaxaxa
n
n
 
 
 a matriz inicial dos coeficientes associado ao sistema (*) é 
 
 
(
 
 
 
 )0(
12a 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
)
 
 
 e o vetor 
(
 
 
 
 
 
 
 
 
 
 
)
 
 
 
 
Para encontrar as matrizes L e U seguiremos o mesmo raciocínio do Método de Gauss. 
Etapa 1. Calcular 
 
 
 
 , com 
 
 e 
 obtendo o sistema onde 
 
 com para i=2,3,4, 
i.e. 
 
 
(
 
 
)0(
11a
)0(
12a 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
)
 
 
 
(
 
 
 
 
 
 
 
 
 
 
)
 
 
 
 
Seja a matriz triangular inferior (
 
 
 
 
 
 
 
) 
então e 
Etapa 2. Calcular 
 
 
 
 , com 
 
 e 
 Assim obtemos onde 
 
 com para i=3,4, i.e. 
 
 
(
 
 
)0(
11a
)0(
12a 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
)
 
 
 
(
 
 
 
 
 
 
 
 
 
 
)
 
 
 
 
 e (
 
 
 
 
 
 
 
) 
 
 onde = e 
 
Etapa 3. Calcular 
 
 
 
 com 
 
 e 
 Assim obtemos com 
 
 i.e. 
 
 
(
 
 
)0(
11a
)0(
12a 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
)
 
 
 
(
 
 
 
 
 
 
 
 
 
 
)
 
 
 
 
 e (
 
 
 
 
 
 
 
) 
 
 onde = (3.6) 
 e 
 
 pode ser observado que se ( )
 
 (
 
 
 
 
 
 
 
) 
 ( )
 
 (
 
 
 
 
 
 
 
) 
 
 e ( )
 
 (
 
 
 
 
 
 
 
) 
então podemos obter L, assim 
 
 ( )
 
( )
 
( )
 
 ( )
 
 
 
 (
 
 
 
 
 
 
 
) 
e 
 
(
 
 
)0(
11a
)0(
12a 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
)
 
 
 
 
ou seja em (3.6) temos ( )
 
 ou 
 
por tanto, para resolver Ax b LUx b resolvemos o sistema 
{
 
 
 
 
Exemplo 1: Considere o sistema Ax b , onde 
 
 











114
123
112
A e 











5
4
1
b 
A matriz A é não singular e pode ser decomposta da forma: 
 

UL
A
































 
200
0
112
122
01
001
114
123
112
2
1
2
1
2
3 
Pois 










114
123
112
 
 
 
 
 
 (
 
 21 21
 
)
 
 (
 
 21 21
 
) 
 
Primeiramente resolvemos os sistema Ly=b, uma vez obtido y, resolvemos o sistema 
Ux=y. 
 
1
o
 Resolvendo o sistema Ly b , 
 
 
































 5
4
1
122
01
001
3
2
1
2
3
y
y
y
 
Tem-se: ,y 11  
 
 
 
 
 
 
 
Logo 
 






















2
1
2
5
3
2
1
y
y
y
 
 
2
o
 Resolvendo o sistema Ux y , pelo processo retroativo 
 
 












200
0
112
2
1
2
1






















2
1
2
5
3
2
1
x
x
x
 
 
De onde obtemos 
 13 x 
 532  xx , então 62 x 
 12 321  xxx , logo 31 x 
 
Portanto a solução do sistema dado Ax=b é dado por 
 





















1
6
3
3
2
1
x
x
x
. 
Observação: A principal vantagem do método é que pode ser computacionalmente 
econômico para o caso de diferentes sistemas k onde só difere o vetor b, ou seja para 
diferentes , pois só será calculado uma única vez L e U . 
 
Estrategia de Pivoteamento (Parcial) 
 
Seguindo a ideia do Método de Gauss, no Método de Crout usamos apenas a matriz de 
coeficientes A e calculamos os multiplicadores para encontrar as matrizes L e U, 
para evitar a instabilidade do sistema podemos aplicar a estratégia de pivoteamento 
parcial na matriz dos coeficientes e guardar as devidas permutações de linhas numa 
matriz auxiliar P para depois aplicar ao vetor b que não foi alterado no calculo de L e U, 
i.e. 
Sem estratégia: Ax b LUx b 
 {
 
 
 
Agora seja P a matriz de permutações, aplicando a estratégia de pivoteamento parcial: 
se 
 
 {
 
 
 
 
vejamos num exemplo: 
 
Exemplo: Seja o sistema Ax b , onde 
 













304
221
143
A e 












2
3
9
b 
 
Sejam (
 
 
 
) 
 
(
 
 
 
) (
 
 
 
) com (
 
 
 
) 
 
Se 
 
 
 , 
 
 
 , e 
 
 (
 
 
 
 ⁄
 
 
 ⁄
) (
 
 
 
⌉ 
 ⁄
 ⁄
) com (
 
 
 
) 
 
Se 
 
 
 , 
 
 (
 
 
 
⌉ 
 ⁄
 
 
 ⁄
) 
 
 Por tanto (
 
 
 
) (
 
 
 ⁄ 
 
 ⁄ 
 
 ⁄ 
) U=(
 
 ⁄
 ⁄
) 
 
e (
 
 
 
)(
 
 
 
) (
 
 
 
) 
 
Resolvendo 
 {
 
 
 ⁄ 
 
 ⁄ 
 
 ⁄ 
 
 ⁄ 
 
 ⁄ 
 
 
Para 
 {
 
 
 
 ⁄ 
 
 ⁄ 
 
 ⁄ 
 
 ⁄ 
 
3.1.3. Método de Cholesky 
 
Foi desenvolvido pelo cartografo francês André-Louis Cholesky (1875-1918). Dado o 
sistema Ax y , onde A é uma matriz simétrica (A = At) e definida positiva, então 
existe uma matriz L triangular inferior tal que a matriz A possa ser decomposta como 
tA L L  . (3.7) 
Definição: Dizemos que uma matriz é definida positiva, se seus autovalores são 
positivos. 
 
Dado o sistema Ax y e considerando que tA L L  , então temos: 
 
 bxLL t )( 
 
denotando por 
 bLy  (3.8) 
 yxLt  (3.9) 
ficamos novamente com 2 sistemas, onde as matrizes são triangulares, o que torna fácil 
encontrar a solução. Primeiro resolvemos o sistema bLy  na eq.(3.8) e uma vez obtida 
a matriz y, resolvemos o sistema (3.9). 
http://pt.wikipedia.org/wiki/1875
http://pt.wikipedia.org/wiki/1918
 
Exemplo: Decomponha a matriz A da forma tA L L  
 












923
241
316
A 
Como a matriz A é simétrica e definida positiva, pois seus autovalores são positivos, 
então procuramos uma matriz triangular inferior L, tal que tLLA  
    
tLL
A



















































23
1383
00
46
1385
6
138
0
2
6
6
6
6
23
1383
46
1385
2
6
0
6
138
6
6
006
923
241
316
 
Exercício: Resolva o sistema Ax=b, se 
 











2673
752
321
A e 











12
11
10
b 
A matriz dada é simétrica e definida positiva, pois seus autovalores são positivos, então 
 
 
1 2 3 1 0 0 1 2 3
2 5 7 2 1 0 0 1 1
3 7 26 3 1 4 0 0 4
tL L
A
     
     
 
     
     
     
 
Resolvemos o sistema Ly = b 
 































12
11
10
413
012
001
3
2
1
y
y
y
, 
de onde obtemos pelo processo retroativo 






















4
9
3
2
1
9
10
y
y
y
, logo resolvemos o sistema 
































4
9
3
2
1
9
10
400
110
321
x
x
x
 
de onde obtemos pelo processo retroativo a solução do sistema dada por: 
 























16
9
16
135
16
457
3
2
1
x
x
x
. 
 
3.2 Métodos Iterativos 
 
Quando temos matrizes do tipo 
 
(
 
 
 
 
 
 
 
 
 
 
 
 
 
 )
 
 
 
 
 
ou outra qualquer com esparsidade visível o método de Gauss não é aconselhável pois 
não preserva a esparsidade, já os métodos iterativos preservam a esparsidade na 
aproximação da solução. Em geral, sistemas de grande porte são esparsos. A ideia 
central dos métodos iterativos é generalizar o MIL estudado antes ( 
 , i.e. 
 C 
 matriz de iteração 
 
 Para mostrar isto, consideremos a matriz A da forma: 
 NMA  nnKNM , 
 então bNxMxbAx  
 NxbMx  (3.10) 
No método iterativo partimos de uma aproximação inicial x
(0)
  1nK  , qualquer, e a 
partir da equação (3.10) definimos a sequência: 
 
 bNxMx kk  )()1( 
logo 
d
k
C
k bMxNMx 1)(1)1(   (3.11) 
 
Para isto é necessário que det( ) 0M  , e que a sequência )(kx convirja para x (solução 
exata do sistema linear), assim sendo: 
bxNxMbNxMx k
k
k
k




)()1( limlim 
o que implica que : ̅ ̅ b (3.12) 
 
Conclusão: Se há convergência, então a sequência converge para a solução .x 
 
Observações: 
 Os métodos iterativos tem convergência assegurada desde que cumpram algum 
critério de convergência 
 A vantagem principal: mantém a esparsidade da matriz dos coeficientes.3.2.1. Critérios de Convergência 
Vamos abordar alguns critérios que permitam determinar quando existe convergência 
para estes métodos iterativos. Previamente recordemos algumas propriedades das 
normas de matrizes. 
Seja n nK  o espaço vetorial de todas as matrizes quadradas n n , com coeficientes 
reais. Se ,
n nA B K  , então 
1) 0 0A A   (matriz nula) 
2) | | ;rA r A r IR  
3) A B A B   
Repare, na equação (3.11) temos: bMNxMx kk 1)(1)1(   . 
e de (3.12) obtemos: ̅ ̅ (3.13) 
 
Definamos como erro das iterações as matrizes coluna: 
xxe kk  )()( , (3.14) 
 
 Assim se o 0lim
)( 

k
k
e então a sequencia convergirá para a solução do sistema. 
Subtraindo (3.13) de (3.11), temos: 
 
 de onde deduzimos que: 
)0(11)2(31)1(21)(1)1( )(...)()( eNMeNMeNMNeMe kkkkk   (3.15) 
 
 entao (3.15) pode ser escrita como 
 
)0()( eCe kk  , para algum k >1 e NMC
1 
 
assim 
)0(eC k quando independentemente dos valores da matriz 
inicial )0(e . 
 
Observação: Se para uma determinada norma matricial temos 1|||| C , então 
0||||lim 

k
k
C e o erro tende a zero, pois 
 ||||||||||||||||
)0()0()( eCeCe kkk  . 
Definição: Seja nnKB  uma matriz quadrada, o raio espectral da matriz B é igual ao 
maior autovalor de B. Denotemos por 
   |,|max
,...,1
j
nj
B 

 (3.16) 
onde j é um autovalor da matriz B, isto é satisfaz a relação 0)det(  IB j , 
nnKI  é matriz identidade. 
 O Primeiro Critério de Convergência: Raio Espectral 
Dado pelo teorema: 
Teorema : ( Condições Necessárias e Suficientes de Convergência ) 
Os métodos iterativos convergem, qualquer que seja o vector inicial )0(x se e somente se 
o raio espectral da matriz NMC 1 dada na equação (3.15) é menor que um. 
Portanto podemos concluir que o método é convergente se e somente se 1)(  C , onde 
 é o raio espectral da matriz C. Este teorema nos fornece uma condição necessária e 
suficiente para assegurar a convergência dos métodos de Jacobi e Gauss-Seidel. 
Observe que a matriz C pode ser escrita como: 
 . 
 Segundo Critério de Convergência: Critério das Linhas 
Baseado na seguinte definição: 
Definição: Dizemos que a matriz A é diagonal dominante estritamente por linhas (ou 
colunas) se 
 



n
ij
j
ijii aa
1
|||| para i =1,2,...,n (3.17) 
A desigualdade (3.17) implica que se 0|| iia então 
 1
||
||
1



n
ij
j ii
ij
a
a
. 
 
Teorema: (Condição Suficiente de Convergência ) 
 Se A é uma matriz diagonal dominante por linhas ou por colunas, i.e. se 
 , então os métodos de Jacobi e de Gauss-Seidel geram uma sequencia 
{ } que converge para a solução do sistema dado, independente da escolha da 
aproximação inicial . 
3.2.1. Método de Jacobi 
 Este método foi ideado pelo matemático alemão judeo Carl Gustv Jakob Jacobi (1804-
1851), consiste em considerar a matriz M (acima mencionada) como matriz diagonal 
da matriz A e AMN  . 
Caso que algum elemento da diagonal iia (para i =1,2,...,n) seja nulo, então 
permutamos as linhas. Uma vantagem deste método é que é fácil calcular x
(k+1)
 , pois 
Mx
(k+1)
 = Nx
(k)
 +b, logo a i-ésima componente de x
(k+1)
 é da forma 
 










 



n
ij
j
k
jiji
ii
k
i xab
a
x
1
)()1( 1
 (3.18) 
 ou 
 
 
 
 , C matriz de iteração. 
 
É necessário manter a ordem para encontrar a solução. Este método converge se e 
somente se: 
 ou equivalentemente se   11   NM 
 Quanto menor seja o valor de , mas rápida será a convergência do método iterativo. 
 
Critério de Parada: Quando devemos parar? 
 
O processo iterativo é repetido ate que o vetor x
(k) 
 esteja o suficientemente próximo do 
vetor x
(k-1)
, ou seja, se )(kR é a maior distância entre os elementos dos vetores x
(k)
 e x
(k-1)
, 
usamos como critério de parada para uma precisão prefixada : 
 ||max
)1()(
1
)( 

 ki
k
i
ni
k xxR < . (3.19) 
Então a solução aproximada do sistema será o vetor x(k) desde que R(k) < . 
Computacionalmente pode-se também usar como teste de parada um numero máximo 
de iterações. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Carl Gustav Jacob Jacobi 
(1804-1851) 
Carl Gustav Jacobi 
Nasceu na atual Alemanha. Estudo na Universidade de Berlim, 
destacando-se em Filosofia e Matemática. 
Jacobi, com apenas 12 anos, já havia conseguido o conhecimento 
necessário para ingressar na universidade, mas na Universidade de Berlim 
só aceitava estudantes a partir de 16 anos, o que fez que ele tivesse que 
continuar na mesma classe até 1821, durante este período, Jacobi recebeu 
prêmios por seus destaques em latim, grego e história, mas preferia 
estudar os textos de Euler, entre outros textos avançados. Jacobi era um 
professor nato e gostava de transmitir suas ideias. Aos 21 anos obteve o 
título de Ph.D. e depois foi professor de matemática na Universidade de 
Königsberg até sua morte. Seus principais trabalhos foram no campo da 
Teoria das Funções Elípticas e da Teoria dos Determinantes. 
 
Exemplo 1: Resolver o seguinte sistema pelos métodos de Jacobi, com  = 0.001 
 
 








3824
6482
328
321
321
321
xxx
xxx
xxx
 (3.20) 
 
Pelo método de Jacobi temos: 
)243(
8
1
)246(
8
1
)23(
8
1
)(
2
)(
1
)1(
3
)(
1
)(
3
)1(
2
)(
3
)(
2
)1(
1
kkk
kkk
kkk
xxx
xxx
xxx






 
Será que esta sequência iterativa converge para a solução do sistema? 
Vejamos, usando o critério de linhas: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Então a sequencia de Jacobi converge para a solução do sistema. 
 
 
Considerando como ponto inicial a origem (0,0,0), temos 
 
 
k 
)(
1
kx )(2
kx 
)(
3
kx 
)(kR 
0 0 0 0 - 
1 0.375002 -0.75002 0.37500 0.75 
2 0.375003 -1.031253 0.75000 0.375 
3 0.316414 -1.218754 0.82031 0.1875 
4 0.322275 -1.239265 0.83789 0.02051 
5 0.320436 -1.249516 0.84595 0.01025 
6 
7 
0.319707 
0319736 
-1.253087 
-1.25372 
0.84760 
0.84812 
0.00357 
0.000641<  
 
Logo a solução aproximada do sistema dado (3.20) é encontrada na sétima iteração e é: 
)84812.0,253772.1,319737.0( x . 
 
Exemplo 2: Seja o SEL: 
{
 
 
 
 
 
as duas primeiras linhas da matriz dos coeficientes do sistema anterior não satisfazem o 
critério de linhas então trocamos as linhas, assim a matriz dos coeficientes 
 
(
 
 
 
) 
 
satisfaz o critério de linhas então pode ser aplicado o método de Jacobi que a sequencia 
iterativa irá a convergir para a solução exata do sistema. 
 
Exemplo 3: Seja o SEL: 
 
 {
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
O método de Jacobi gera uma sequencia que converge para a solução exata (
 
 ⁄
 
 ⁄
) 
(verifique!) 
Não entanto, o critério de linhas não é satisfeito, i.e. entao a condição do 
teorema é apenas suficiente. 
 
Interpretação geométrica do método de Jacobi 
 
Seja o SEL 
{
 
 
 
 
Supondo que a matriz dos coeficientes associado ao sistema satisfaz o critério de linhas 
então o método de Jacobi gera a sequencia iterativa: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Observe que dada uma aproximação inicial os novos valores das 
variáveis não são usados até uma próxima iteração, isto significaque o avanço na 
aproximação é simultânea como é mostrada na figura 3.1: 
 
Figura 3.1 Processo na aproximação do método Jacobi 
 
Uma pequena variação do método Jacobi no avanço da aproximação é visto no método 
de Gauss-Seidel. 
 
3.2.2. Método de Gauss-Seidel (GS) 
 
Foi ideado em 1874 por Philipp Ludwig von Seidel e Johann Carl Friedrich Gauss. 
Neste método é considerada a matriz M como M= D + L, onde D é a diagonal e L é a 
matriz triangular inferior da matriz A, da forma: 
 
 

















 0..
0....
..0
..00
0..00
11
3231
121
nnn aa
aa
a
L e 

















nna
a
a
D
0..0
0....
...0.
..00
0..0
22
11
; det D  0 
 
A solução do sistema Ax=b é aproximada da seguinte forma: 
 
 bxMALxDx kkk   )()1()1( )( 
 bLxxMADx kkk   )1()()1( )( 
  bLxxMADx kkk   )1()(1)1( )( 
 
Onde a i-ésima componente de x
(k+1) 
 é da forma: 
 
 
 








  

 

1
1 1
)()1()1( 1
i
j
n
ij
k
jij
k
jiji
ii
k
i xaxab
a
x i=1,2,...,n (3.21) 
 
Caso que algum elemento da diagonal aii se anule ou seja próximo de zero, então 
permutamos as linhas antes de aplicar o método de Gauss-Seidel. 
 
A ordem é muito importante, observe que este método usa o dado mais recente. As 
vantagens deste método são a tolerância de erros operacionais e que a convergência é 
mais rápido que o método de Jacobi em geral, existem casos em que isto não acontece. 
 
O teste de parada é o mesmo que o de Jacobi. 
 
Analisando a convergência: O método de Gauss-Seidel converge se e somente se 
 1)( 1   NM (3.22) 
onde DLM  e AMN  , observe que UN  (matriz triangular superior) 
Note que neste método a matriz C é dada por 
C = - ( L + D )
-1
 U 
 


































 0..
.0....
..0
..00
0..00
;
0..0
0....
...0.
..00
0..0
11
3231
2122
11
nnnnn aa
aa
a
L
a
a
a
D e 




















00..0
.....
.00.
..00
..0
3
2
112
n
n
n
a
a
aa
U 
 
Em particular se a matriz A é simétrica e definida positiva, o método de GS converge. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Philipp Ludwig von Seidel 
(1821-1896) 
Matemático e astrônomo alemão. Em 1874 
publicou seu trabalho sobre a resolução 
iterativa de sistemas de equações lineares, 
atualmente conhecido como o Método de 
Gauss-Seidel. 
 
 
Exemplo 1: Resolver o sistema (4.20) pelo método de Gauss-Seidel. Com =0.001 
 








3824
6482
328
321
321
321
xxx
xxx
xxx
 
 
Observe que a matriz dos coeficientes é (estritamente) diagonal dominante (verifique!). 
Isolando cada variável 3,2,1; jx j e colocando no esquema de Gauss Seidel, assim 
temos a sequencia iterativa: 
 
)243(
8
1
)246(
8
1
)23(
8
1
)1(
2
)1(
1
)1(
3
)1(
1
)(
3
)1(
2
)(
3
)(
2
)1(
1






kkk
kkk
kkk
xxx
xxx
xxx
 
 
Considerando como ponto de partida a origem (0,0,0), e tabelando os dados, segue 
 
k 
)(
1
kx )(2
kx 
)(
3
kx 
)(kR 
0 0 0 0 - 
1 0.375002 -0.843752 0.77344 0.84375 
2 0.287113 -1.208496 0.82068 0.36475 
3 0.320894 -1.240562 0.84559 0.03378 
4 0.318674 -1.252462 0.84745 0.01189 
5 0.319695 -1.2536497 0.84826 0.001188 
6 0.319641 -1.254040 0.84833 0.0004 <  
 
Logo a solução do sistema (4.20) é: ).,.,.(x 8433025404013196410  . 
 
Interpretação geométrica do método de Gauss Seidel 
 
Seja o SEL 
{
 
 
 
 
Supondo que a matriz dos coeficientes associado ao sistema satisfaz o critério de linhas 
então o método de Gauss Seidel gera a sequencia iterativa: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Assim, dada uma aproximação inicial os novos valores das variáveis são 
atualizados usando os valores dos já atualizados na mesma iteração, isto significa que a 
atualização na aproximação é sequencial como é mostrada na figura: 
 
 
Figura 3.1 Processo na aproximação do método Gauss-Seidel 
 
Existem outros critérios de convergência para este método como por exemplo o critério 
de Sassenfeld. 
 
 O Terceiro Critério de Convergência: Critério de Sassenfeld 
 
Critério de Sassenfeld: 
Sem perda de generalidade, vamos supor que A é uma matriz 44, então considere os 
valores reais 
 |a||a||a|
|a|
141312
11
1
1
 
 |a||a||a|
|a|
2423121
22
2
1
 (3.23) 
 |a||a||a|
|a|
34232131
33
3
1
 
 343242141
44
4
1
 |a||a||a|
|a|
 
Se 1max
41


i
i
 , então o método de Gauss Seidel gera uma sequência convergente. 
 
Observações: 
 
 Se A satisfaz o critério de linhas então o critério de Sassenfeld é satisfeito, a 
recíproca não é verdadeira (i.e., o critério de Sassenfeld pode ser satisfeito 
mesmo que o critério de linhas não seja satisfeito). 
 O critério de Sassenfeld é apenas suficiente pois para 
 {
 
 
 
o método de Gauss-Seidel gera uma sequencia convergente, o entanto 
 
 
 
 , 
 
 
 e 
 
Exemplo 2: Dado o seguinte sistema, analise os testes de convergência para o método 
de Gauss-Seidel e resolva o sistema com uma precisão <10
-3
, com a aproximação 
inicial )0,1,0(
)0( x 
 








736
6539
1632
321
321
321
xxx
xxx
xxx
 
 
Reorganizando o sistema dado temos o sistema 
 
 








1634
736
6539
321
321
321
xxx
xxx
xxx
 (3.24) 
 
a) Vamos analisar o sistema (3.24) através dos critérios de convergência ao sistema 
(3.24) p: 
a1) Critérios das linhas j: 
|5||3|9|| 11 a 
|3||1|6|| 22 a 
|3||4||6||| 33 a 
Portanto este critério não é satisfeito e nada podemos afirmar. 
 
a2) Critério de Sassenfeld: 
   
9
8
53
9
1
||||
||
1
1312
11
1  aa
a
 
 
54
35
3
9
8
6
1
||||
||
1
23121
22
2 





 aa
a
 
 
12
11
324
297
54
353
9
84
6
1
||||
||
1
232131
33
3 




 


 aa
a
 
 
Então: 191667.0}91667.0,64815.0,88889.0max{max
41


i
i
 
Portanto é satisfeito o Critério de Sassenfeld, observe que  está muito próximo de um, 
o que pode indicar que a convergência será lenta. 
a3) Critério do raio espectral 
No método de GS temos 
 




















 

















27
2
36
7
27
16
18
1
9
5
3
1
1
0
0
0
C então ,
000
300
530
634
061
009
NMNM 
Calculando os autovalores da matriz M
-1
N 
 






27
2
36
7
27
16
18
1
9
5
3
1
0
0 = 






9
1
54
72 =0 
De onde obtemos os autovalores: 27476.0,0 21  , e 40439.03  , logo o raio 
espectral é 
  40439.0}40439.0,27476.0,0max{  C 
Sabemos que este método é convergente se e somente se   1 C , portanto está 
garantida a convergência. 
b) Isolando as variáveis da diagonal principal em cada equação do sistema dado 
temos: 
  321 536
9
1
xxx  
  312 37
6
1
xxx  
  213 341
6
1
xxx 

 
 
c) A sequência convergente é : 
 
 
 
 
 













)(
2
)(
1
)(
3
)1(
3
)(
1
)(
2
1(
3
)1(
2
)(
1
341
6
1
37
6
1
536
9
1
kkk
kkk
kkk
xxx
xxx
xxx
 
 
Consideremos a aproximação inicial como )0,1,0(
)0( x , então vamos preencher a 
tabela 
 
k )(1
kx )(2
kx 
)(
3
kx )(kR 
0 0 1 0 - 
1 -0.333333 1.222222 0.5555555 0.555555 
2 -0.567901 0.983539 0.2757983 
 
 
02757202 
3 -0.49428441.1091297 0.3917086 0.1255906 
4 -0.5145726 1.0565745 0.3519055 0.0525555 
5 -0.5090782 1,0757103 0.3645363 0.0191358 
6 -0.51061676 1.0695013 0.3645363 0.019136 >  
 
7 -0.51072520 1.0712546 0.36182543 0.001783 >  
8 -0.51058597 1.07085462 0.36170183 0.000433 <  
 
Portanto a solução aproximada do sistema dado é 
36170183.0 ,1.07085462,51058597.0 321  xxx . 
3.2.3. Método SOR (Successive Over Relaxation) 
Este método também conhecido como Método de Sobre-Relaxação sucessiva, acelera a 
convergência do método de Gauss-Seidel em alguns casos, usando a relaxação, resulta 
da combinação linear da forma: 
 
)()1( )1( ki
GS
k
i XX 


 (3.25) 
 
 
Onde é um fator real ponderado. 
No método de Gauss-Seidel temos: 








  

 

1
1 1
)()1()1( 1
i
j
n
ij
k
jij
k
jiji
ii
k
i xaxab
a
x i=1,2,...,n 
No método SOR a i-esima coordenada é da forma: 
 )(
1
1 1
)()1()1( )1(
1 k
i
i
j
n
ij
k
jij
k
jiji
ii
k
i xxaxab
a
x 








  

 
 i=1,2,...,n (3.26) 
Observe que se =1, então SOR = GS; se =0 não há chances de convergência. 
 Critério de convergência para o método SOR 
Dado pelos seguintes teoremas: 
Teorema (Kahan - condição necessária) 
Se 0iia e |1|)(  C , então para que haja convergência do método SOR, 
qualquer que seja a primeira aproximação é necessário que 20  . 
Teorema (Ostrowski-Reich - condição suficiente) 
Se a matriz A for simétrica e definida positiva, 20  , então há convergência do 
método SOR, qualquer aproximação inicial. 
Conclusão: Dado o sistema Ax=b,    C , onde )(1 ULDC   se 20  
então a sequência gerada por (4.21) converge à solução exata, 
Se a matriz A é definida positiva e tri diagonal, uma opção para a escolha de  é dada 
por 
)(11
2
2 C
 onde )(
1 ULDC   (3.27) 
 
Exemplo 1: Resolver o seguinte sistema pelo método SOR, considere =1.25 e 
=0.001 
 
 








3824
6482
328
321
321
321
xxx
xxx
xxx
 
 
No método SOR temos 
 
)(
3
)1(
2
)1(
1)1(
3
)(
2
)1(
1
)(
3)1(
2
)(
1
)(
3
)(
2)1(
1
)1(
8
243
)1(
8
246
)1(
8
23
k
kk
k
k
kk
k
k
kk
k
x
xx
x
x
xx
x
x
xx
x







 









 








 






 
Considerando como a primeira aproximação o ponto (0,0,0), se fazemos =1.5, 
diverge, 
Se =0.75 demora em convergir, mas =1.022171629, temos a sequência convergente: 
 
 
k 
)(
1
kx )(2
kx 
)(
3
kx 
)(kR 
0 0 0 0 0 
1 0.3833143609 0.8001586880 
 
0.8645819880 
2 0.2808096771 -1.228168207 
 
0.8229410560 0.3635862190 
3 0.3237164400 -1.242715171 0.8480823452 0.0429067629 
4 0.3181991358 -1.253832090 0.8475459558 0.011116919 
5 0.3198789588 -1.253740736 0.8483930371 0.0016798230 
6 0.3196135764 -1.254107876 0.8483324429 0.000367 <  
 
Comparando os três métodos para o sistema do ex. 1 (SOR): 
a) Resolvendo pelo método de Eliminação de Gauss temos a solução 
 
 
 )84360656.0,25409836.1,31967213.0( x . 
 
b) Por Jacobi: )84812.0,253772.1,319737.0( x , em 7 iterações. 
c) Por Gauss-Seidel )8433.0,254040.1,319641.0( x em 6 iterações 
d) SOR: )84833244.0,2541079.1,31961358.0( x em 6 iterações. 
Neste exemplo o mais aproximado foi o GS. 
Exemplo 2: Dado o seguinte sistema, analise o teste de convergência para o método de 
SOR e resolva o sistema com uma precisão <10
-3
, com a aproximação inicial 
)0,1,0()0( x 
 








1634
736
6539
321
321
321
xxx
xxx
xxx
 
 
As equações que geram uma sequência convergente pelo método SOR é através das 
equações 
 
 
 
 
 




















)1(
3
)(
2
)(
1
)(
3
)1(
2
)1(
3
)(
1
)(
2
)1(
1
1(
3
)1(
2
)(
1
)1(341
6
)1(37
6
)1(536
9
kkkk
kkkk
kkkk
xxxx
xxxx
xxxx
 
 
desde que 20  . Como vimos anteriormente, uma opção para a escolha de  é 
dada por 
 
)(11
2
2 C
 
 onde )(
1 ULDC   , a matriz C é da forma: 
 C= 
Os autovalores de C são: 
 
 
 
então 60288.0)(  C < 1 e 2112454.1  , com este valor são necessárias 19 
iterações para obter a solução aproximada, mas considerando 75.0 são apenas 
necessárias 8 iterações. Com 5.0 são necessárias 12 iterações, conforme mostra a 
tabela. 
 
k )(1
kx )(2
kx 
)(
3
kx )(kR 
0 0 1 0 - 
1 
 
 
0.5972222222 0.1770833334 0.4027777778 
2 
 
0.3682002314 0.1418185764 0.2290219908 
3 
 
0.2731888382 0.05769969798 0.1282009549 
4 
 
0.2514269741 
 
 
0.06635635679 
⁞ ⁞ ⁞ ⁞ ⁞ 
10 
 
0.2847592104 
 
0.00159026656 
11 
 
0.2843468476 0.05316722382 0.0007295111< 
 
Portanto a solução aproximada é ( ,0.2843468476, 0.05316722382). 
 
 
Observação: 
Um critério para determinar o número mínimo de iterações é o seguinte: 


 
)(1
||||)( 1
(())1
C
XC k
, (3.28) 
onde  é a precisão desejada e 0||max|||| )0(
0
1
(()) 

j
nj
xX , 
então isolando k temos: 
))(1ln(ln||||ln)(ln)1( 1
(()) CXCk  
Como )(C < 1, então 0)(ln  C ,inverte a desigualdade, assim 
 
 1
)(ln
||||ln))(1ln(ln 1
(())




C
XC
k . (3.29) 
 
 Se considerarmos o sistema dado no exemplo 2 do G-S, temos 
2021.71
40439112.0ln
1ln)40439112.01ln(10ln 3




k 
Portanto serão necessárias pelo menos 8 iterações. Exatamente como mostra o exemplo. 
 
 Se considerarmos o sistema dado no exemplo 2 do SOR, temos 
476.141
6028865.0ln
1ln)6028865.01ln(10ln 3




k 
Portanto serão necessárias pelo menos 15 iterações. Mas no SOR, depende fortemente 
do valor de w. 
 
Observações: 
1. A convergência dos métodos iterativos depende fortemente da posição das 
equações. 
2. Antes de realizar os testes de convergência, recomendasse reorganizar o sistema. 
3. Quando os métodos iterativos convergem, independentemente da aproximação 
inicial. 
4. Para garantir a convergência método de Jacobi, basta que seja satisfeito o critério 
das linhas (colunas) ou o critério do raio espectral. 
5. Para garantir a convergência método de de Gauss Seidel, deve ser satisfeito um 
dos critérios: o critério das linhas (colunas) ou o critério do raio espectral ou de 
Sassenfeld. 
6. No método de Gauus Seidel , o cálculo do raio espectral é mais trabalhoso que do 
Jacobi. 
7. No método SOR a convergência pode ser mais rápida que GS ou não! Depende de 
w. 
8. Quando se tem um sistema muito grande, estes métodos geram certa incerteza. 
 
 
 EXERCÍCIOS 
1) Determine a solução do sistema a seguir, com erro =0.05. Através dos métodos de 
Jacobi, Gauss-Seidel e SOR. 
 








10924
3283
523
321
321
321
xxx
xxx
xxx
 
 
Solução: xjacobi=( 1.03958, 0.55804 ,0.77389 ) ; xgauss-seidel =(1.04718, 0.57365, 0.77318) 
 
 
2) Resolvendo o seguinte sistema pelo método de eliminação Gauss, obtemos a solução: 
X = (1, -2, 3, -4) 
 












601082
681024
7532
6111246
432
4321
4321
4321
xxx
xxxx
xxxx
xxxx
 
Para este sistema é possível aplicar os métodos iterativos de Jacobi ou GS? Por quê? 
Solução: No Jacobi os autovalores em valor absoluto são maiores que 1. Troque a ordem das equações. 
 
3) Resolva o sistema 
 






























 
3
1
2
831
165
312
3
2
1
x
x
x
 
pelos métodos iterativos de GS e SOR. 
Solução: (0.08202, -0.31948, 0.484178) com erro menor que 0.05. 
 
4) Através do critério de Sassenfeld, determine os valores de m para poder assegurar a 
convergência do GS? (não permuteas equações) 
 
 








43
34
22
321
321
321
mxxx
mxxx
xxx
.