SL Metodos Iterativos 1pp

Prévia do material em texto

1
Computação Científica II
(EEL7031)
Resolução de Sistemas de Equações Lineares
(Métodos Iterativos)
2
Objetivos e Tópicos Principais
 Objetivos
 Estudar técnicas iterativas de resolução numérica de sistemas 
de equações lineares algébricas, que surgem nas mais 
diversas áreas do conhecimento científico.
 Tópicos principais
 Introdução
 Normas de vetores e matrizes
 Autovalores e autovetores
Métodos de Jacobi e Gauss-Seidel
O método SOR
O método gradiente conjugado
 Comentários Finais
3
Introdução
 Características dos métodos iterativos
 Necessitam da especificação de uma aproximação inicial.
 Não fornecem solução exata, mesmo usando-se aritmética exata,
mas uma solução aproximada dentro de uma tolerância 
especificada pelo usuário.
 Em muitos casos, os métodos iterativos são mais efetivos que 
os métodos diretos, visto que podem requerer menor esforço 
computacional e, nestes casos, o erro de arredondamento é 
reduzido.
 A sentença anterior é particularmente verdadeira quando a 
matriz de coeficientes é esparsa, ou seja, quando possui 
elevado percentual de elementos nulos.
4
Normas de vetores e matrizes
 Aspectos gerais
 A distância entre números reais x e y é
 Esta medida foi empregada para estimar a precisão da aproximação 
da solução no cálculo de raízes e para determinar quando uma 
aproximação é suficientemente precisa.
 Nos métodos iterativos de resolução de sistemas de equações 
algébricas lineares emprega-se esta mesma lógica, porém aplicada a 
vetores.
 Convenção: A equação descreve todos os vetores 
coluna com dimensão n e coeficientes reais representados por: 
yx 









nx
x
x
x 
2
1









nx
x
x
x 
2
1
t
nxxxx ),,,( 21 
5
Normas de vetores e matrizes
 Norma de vetor no 
 A norma de um vetor no é uma função, , de com as 
seguintes propriedades:
 para todo ,
 se e somente se ,
 para todo ,
 para todo .
 As normas Euclidiana e infinita , para 
são definidas como: 
n
0x
 n
nx 
0x 0)0,,0,0(  tx 
xx .  nx  e 
yxyx  nyx ,
22
xl   xl
2/1
1
2
2 


 

n
i
ixx
2/1
1
2
2 


 

n
i
ixx ini xx   1max ini xx   1max
t
nxxxx ),,,( 21 
n
6
Normas de vetores e matrizes
 Interpretação geométrica da norma euclidiana
A norma fornece a distância em linha reta entre os 
pontos .
,),,(p/ , 3212
txxxxx 
 ),,( e )0,0,0( 321 xxx
1
2
x 1
2
x
7
 Interpretação geométrica da norma infinita
 Exemplo
 Para , tem-se:
Normas de vetores e matrizes
1x 1x
tx )2,1 ,1( 
2 2 2
2
( 1) (1) ( 2)x     2 2 2
2
( 1) (1) ( 2)x       max 1 , 1 , 2x     max 1 , 1 , 2x    6 6 2 2
8
Normas de vetores e matrizes
 Distância entre vetores
 Se e são vetores no , as 
distâncias e entre x e y são definidas por:
t
nxxxx ),,,( 21  tnyyyy ),,,( 21  n
2l l
2/1
1
2
2
)( 


  

n
i
ii yxyx
2/1
1
2
2
)( 


  

n
i
ii yxyx ni
ii yxyx


1
max
ni
ii yxyx


1
maxe
 Exemplo
 Para e , tem-se:(1,1,1)tx  (2,2,2)ty 
2 2 2
2
(2 1) (2 1) (2 1) 3x y       2 2 2
2
(2 1) (2 1) (2 1) 3x y       
  112,12,12max  yx   112,12,12max  yx
9
Normas de vetores e matrizes
 Distância entre vetores (cont.)
 O conceito de distância no é usado para definir o limite de uma 
seqüência de vetores.
 A seqüência de vetores no é dita convergir para com 
respeito a norma se, dado qualquer , existe um inteiro 
tal que:
)( todopara ,  Nkxxk  )( todopara ,  Nkxxk 
n
 1kkx
0
n x
 )(N
10
Normas de vetores e matrizes
 Distância entre vetores (Exemplo) 
 Considere a seqüência de vetores ser definida por: 
 Então:
 Portanto, para qualquer dado , pode ser encontrado um tal que o 
maior valor de é menor que . 
 Este resultado implica que a seqüência converge para com 
respeito a . 
 Um resultado importante neste tema é que todas as normas no são 
equivalentes com respeito a convergência.
4)( kx
  tktkkkkk ke
kk
xxxxx 

   sin ,3 ,12 ,1,,,
24321
)(   tktkkkkk ke
kk
xxxxx 

   sin ,3 ,12 ,1,,,
24321
)(
11lim k 2/12lim  kk 0/3lim 2  kk 0sinlim  ke
k
k
 ,0 e 0 ,2 ,1 )(4
)(
3
)(
2
)(
1  kkkk xxxx 
)(N
)(kx t)0,0,2,1(

n
11
Normas de vetores e matrizes
 Norma de matriz
 Uma norma de matriz no conjunto de todas as matrizes é uma 
função, , definida neste conjunto, satisfazendo para todas as matrizes 
A e B, , e todos os números reais : 
 ,
 , se e somente se , matriz como todos os elem. nulos,
 ,
 ,
 .
 Distância entre matrizes
 Uma distância entre matrizes A e B, , com respeito a esta norma de 
matriz é . 
nn

nn 
0A
0A 0 é A
AA . 
BABA 
BAAB .
nn
BA
12
Normas de vetores e matrizes
 Norma natural de matriz
 Se é uma norma de vetor no , a norma natural de matriz no 
conjunto de matrizes , dada por , é definida como segue: 
 Aplicações para norma euclidiana e norma infinita 
 n
)( nn 
1
max


x
AxA
1
max


x
AxA
1
22
2
max


x
AxA
1
22
2
max


x
AxA
2l l
1
max
  

x
AxA
1
max
  

x
AxAe
13
Normas de vetores e matrizes
 Interpretação geométrica da norma natural euclidiana de matriz
1
22
2
max


x
AxA
1
22
2
max


x
AxA
)22( A )22( A
14
Normas de vetores e matrizes
 Interpretação geométrica da norma natural infinita de matriz
1
max
  

x
AxA
1
max
  

x
AxA
)22( A )22( A
15
Normas de vetores e matrizes
 Cálculo da norma natural infinita de matriz
 Exemplo:
 Se 
 Portanto:



n
j
ijni
aA
1
1
max


n
j
ijni
aA
1
1
max












115
130
121
A












115
130
121
A
4121
3
1
1 
j
ja
4130
3
1
2 
j
ja
7115
3
1
3 
j
ja
  77,4,4max A   77,4,4max A
16
Autovalores e Autovetores
 Aspectos gerais
 Um escalar λ é valor próprio (ou autovalor) de um operador linear A : V -
> V se existir um vector x diferente de zero tal que Ax=λx. O vector x é 
chamado vector próprio.
 Os autovalores de uma dada matriz quadrada A de dimensão nXn são 
os n números que resumem as propriedades essenciais daquela matriz. 
 O autovalor de A é um número λ tal que, se for subtraído de cada 
entrada na diagonal de A, converte A numa matriz singular.
 Subtrair um escalar λ de cada entrada na diagonal de A é o mesmo que 
subtrair λ vezes a matriz identidade I de A.
 Portanto, λé um autovalor se e somente se a matriz (A-λI) for singular.
 Há forte correlação entre esses números λ e a possibilidade de um 
método iterativo convergir.
17
Autovalores e Autovetores
 Definições
 Para uma matriz quadrada , o polinômio característico de A é 
definido por:
 O polinômio tem grau n e, conseqüentemente, têm, no máximo, n
zeros distintos, alguns dos quais podem ser complexos. 
 Os zeros de são denominados de autovalores da matriz A.
 Se é um autovalor de A, então: 
 Conseqüentemente, se , então x é denominado 
um autovetor de A associado ao autovalor .
)( nnA 
)det()( IAp   )det()( IAp  
)(p
)(p

0)det(  IA  0)det(  IA  singular é IA  singular é IA 
0 e 0)(  xxIA 

18
Autovalores e Autovetores
 Interpretação geométrica
 Se x é um autovetor associado com o autovalor , então , assim 
a transformação A aumenta a magnitude do vetor x, mas não muda a 
sua direção, conforme ilustrado abaixo.
 xAx 
19
Autovalores e Autovetores
 Exemplo
 Determine os autovalores e autovetores de 
 Polinômio característico:
 Portanto:
 Autovetores:


 
32
10
A 

 
32
10
A
)det()( IAp   )det()( IAp   2)3(
32
10
det)( 



 
p 2)3(
32
10
det)( 



 
p
23)( 2  p 23)( 2  p 2 e 1 :sAutovalore 21   2 e 1 :sAutovalore 21  
 0)1(  xIA 0)1(  xIA 





 
0
0
22
11
2
1
x
x






 
0
0
22
11
2
1
x
x
 11  11 
12 xx  12 xx 
tAV )1,1(1  tAV )1,1(1 
 22  22  0)2(  xIA 0)2(  xIA 





 
0
0
12
12
2
1
x
x






 
0
0
12
12
2
1
x
x 12 2xx  12 2xx 
tAV )2,1(2  tAV )2,1(2 
Qualquer múltiplo não-nulo de um autovetor é também um autovetor.
20
Autovalores e Autovetores
 Exemplo 2 – Aplicação do Matlab
 Determine os autovalores e autovetores de 










111
110
201
A










111
110
201
A
sAutovaloresAutovalore sAutovetoresAutovetore
21
Autovalores e Autovetores
 Raio espectral de uma matriz
 O raio espectral de uma matriz é definido por
, onde é um autovalor de . 
 Para o exemplo do slide anterior, tem-se: 
 Caracterização da norma Euclidiana de matriz
 Se é uma matriz , então:
 ;
 para qualquer norma.
)(A A
 max)( A  max)( A A
 iiA 31,31,1max)(   iiA 31,31,1max)(   2,2,1max)( A  2,2,1max)( A 2 2
A )( nn
   2/1
2
AAA t
AA )(
22
Autovalores e Autovetores
 Exemplo – Norma Euclidiana de matriz
 Determine para:
 Então:










211
121
011
A










211
121
011
A


























 

541
462
123
211
121
011
210
121
111
AAt


























 

541
462
123
211
121
011
210
121
111
AAt
   2/1
2
AAA t
















541
462
123
det)det(0 IAAt
















541
462
123
det)det(0 IAAt
)4214(0 2  
77 ,77 ,0  
 AAA t
2
 AAA t
2  77 ,77 ,0max2 A  77 ,77 ,0max2 A 106.377  106.377 
23
Métodos de Jacobi e Gauss-Seidel
 Aspectos gerais
 São métodos iterativos desenvolvidos no século 18 e aplicáveis para 
sistemas com matrizes esparsas e de grande dimensão.
 Sistemas com essas característica são encontrados, por exemplo, em 
estudos de circuitos integrados em grande escala e na solução numérica 
de problemas de valores de contorno e equações diferenciais parciais.
 Elementos básicos do método de Jacobi
 A resolução de , , por métodos iterativos, parte de uma 
aproximação inicial , para , e gera uma seqüência de vetores 
que converge para . 
 Este processo envolve a conversão de 
 A seqüência de aproximações é gerada, a partir de , calculando-se:
bAx  )( nnA 
)0(x x  1kkx
x
bAx  bAx 
,3,2,1 para ;1)(   kcTxx kk ,3,2,1 para ;1)(   kcTxx kk
)0(x
cTxx  cTxx 
24
O Método de Jacobi
 Convergência e raio espectral
 A seqüência converge para a solução única de , 
para qualquer , se e somente se 
 Exemplo
 Considere o sistema linear , onde
 A conversão para a forma é feita isolando-se na i-ésima 
linha, para , ou seja: 
cTxx kk  1)(
nx )0(
cTxx 
.1)( T









61032 
8 5 
71210
321
321
321
xxx
xxx
xxx









61032 
8 5 
71210
321
321
321
xxx
xxx
xxx









1
2
1
x









1
2
1
x
ix
3,2,1i









)10/6( )10/3( )10/2(
)5/8( )5/1( )5/1( 
)10/7( )10/1( )10/2( 
213
312
321
xxx
xxx
xxx









)10/6( )10/3( )10/2(
)5/8( )5/1( )5/1( 
)10/7( )10/1( )10/2( 
213
312
321
xxx
xxx
xxx
cTxx 
25
O Método de Jacobi
 Exemplo (cont.)
 Assim, tem a forma apresentada abaixo
 onde:
 Autovalores de T:









)10/6( )10/3( )10/2(
)5/8( )5/1( )5/1( 
)10/7( )10/1( )10/2( 
213
312
321
xxx
xxx
xxx









)10/6( )10/3( )10/2(
)5/8( )5/1( )5/1( 
)10/7( )10/1( )10/2( 
213
312
321
xxx
xxx
xxx
cTxx bAx 














0
10
3
10
2
5
1
0
5
1
10
1
10
2
0
T














0
10
3
10
2
5
1
0
5
1
10
1
10
2
0
T
e











10
6
5
8
10
7
c











10
6
5
8
10
7
c
2552.0 ,1391.0 ,3943.0 321   2552.0 ,1391.0 ,3943.0 321   .13943.0)( T .13943.0)( T
26
O Método de Jacobi
 Exemplo (cont.)
 O processo iterativo é executado como segue:
 Os resultados de cada iteração, para são:
 Critério de parada:
,
)10/6( )10/3( )10/2(
)5/8( )5/1( )5/1( 
)10/7( )10/1( )10/2( 
)1(
2
)1(
1
)(
3
)1(
3
)1(
1
)(
2
)1(
3
)1(
2
)(
1












kkk
kkk
kkk
xxx
xxx
xxx,
)10/6( )10/3( )10/2(
)5/8( )5/1( )5/1( 
)10/7( )10/1( )10/2( 
)1(
2
)1(
1
)(
3
)1(
3
)1(
1
)(
2
)1(
3
)1(
2
)(
1












kkk
kkk
kkk
xxx
xxx
xxx
cTxx kk   )1()(
,2,1k ,2,1k
0001.19997.09854.00270.1892.012.110.00.1
9999.10003.20092.29640.1042.270.100.20.1
0001.19998.09901.00192.1928.009.140.00.1
109543210
)(
3
)(
2
)(
1




k
k
k
x
x
x
k

0001.19997.09854.00270.1892.012.110.00.1
9999.10003.20092.29640.1042.270.100.20.1
0001.19998.09901.00192.1928.009.140.00.1
109543210
)(
3
)(
2
)(
1




k
k
k
x
x
x
k

tx )1,1,1()0( 
3)9()10( 10  xx 3)9()10( 10  xx



 


























4456.0
3710.0
3059.0
100.1
9997.0
0003.2
9998.0
0001.1
9999.1
0001.1
3)9()10( xx



 


























4456.0
3710.0
3059.0
100.1
9997.0
0003.2
9998.0
0001.1
9999.1
0001.1
3)9()10( xx
27
O Método de Jacobi
 Equação geral e formulação matricial
 O método iterativo de Jacobi para 
consiste em obter:
 A matriz A pode ser dividida em , como segue:
n,1,2,i ;0 com ;  iiabAx
ni
a
b
a
xa
x
ii
i
n
ij
j ii
k
jijk
i ,,2,1p/ ,
1
)1(
)( 





ni
a
b
a
xa
x
ii
i
n
ij
j ii
k
jijk
i ,,2,1p/ ,
1
)1(
)( 














nnnn
n
n
aaa
aaa
aaa
A
21
22221
11211

































000
00
0
0
00
000
00
00
00
2
112
21
2122
11












n
n
nnnn
a
aa
aa
a
a
a
a
A

ULDA 
 D  L  U
28
O Método de Jacobi
 Equação geral e formulação matricial (cont.)
 A equação ou é então transformada em:
 Se , existe e, então, pode-se escrever: :n,1,2,i ;0 iia
bxULD  )(bAx 
bxULDx  )( bxULDx  )(
1D
bDxULDx 11 )(   bDxULDx 11 )(   cTxx kk   )1()( cTxx kk   )1()(
bDc
ULDT
1
1 e )(
:onde




bDc
ULDT
1
1 e )(
:onde




29
O Método de Gauss-Seidel
 Elementos básicos
 Representa a busca de melhor eficiência e desempenho, em relação ao 
método de Jacobi, na resolução de sistemas lineares do tipo .
 Utiliza, no momento do cálculo de cada componente , todas as 
componentes , já determinadas , as quais, na maioria das 
vezes, representam melhores aproximações do que .
 A técnica assim definida é denominada de método iterativo de Gauss-
Seidel e descrita genericamente pela equação abaixo. 
   
ni
a
bxaxa
x
ii
i
j
n
ij
i
k
jij
k
jij
k
i ,,2,1p/ ,
1
1 1
)1()(
)( 


 
 
   
ni
a
bxaxa
x
ii
i
j
n
ij
i
k
jij
k
jij
k
i ,,2,1p/ ,
1
1 1
)1()(
)( 


 
 

)(k
ix
)(
1
)(
1 ,,
k
i
k xx 
)1(
1
)1(
1 ,,


 k
i
k xx 
bAx 
30
O Método de Gauss-Seidel
 Exemplo
 Considere o sistema linear:
 Aplicando-se a equação geral do método de Gauss-Seidel, obtém-se:
,
61032 
8 5 
71210
321
321
321









xxx
xxx
xxx
,
61032 
8 5 
71210
321
321
321









xxx
xxx
xxx









1
2
1
x









1
2
1
x











)10/6( )10/3( )10/2(
)5/8( )5/1( )5/1( 
)10/7( )10/1( )10/2( 
)(
2
)(
1
)(
3
)1(
3
)(
1
)(
2
)1(
3
)1(
2
)(
1
kkk
kkk
kkk
xxx
xxx
xxx











)10/6( )10/3( )10/2(
)5/8( )5/1( )5/1( 
)10/7( )10/1( )10/2( 
)(
2
)(
1
)(
3
)1(
3
)(
1
)(
2
)1(
3
)1(
2
)(
1
kkk
kkk
kkk
xxx
xxx
xxx
:é solucão cuja
31
O Método de Gauss-Seidel
 Exemplo (cont.)
 Realizando o processo iterativo para , obtém-se: 
 O critério de parada utilizado é dado por:
0000.10000.1004.10096.1084.10.1
0000.20002.20021.20021.288.10.1
0000.10004.10011.19676.0400.00.1
543210
)(
3
)(
2
)(
1
k
k
k
x
x
x
k

0000.10000.1004.10096.1084.10.1
0000.20002.20021.20021.288.10.1
0000.10004.10011.19676.0400.00.1
543210
)(
3
)(
2
)(
1
k
k
k
x
x
x
k




 


























0221.0
1597.0
3503.0
100.1
0000.1
0002.2
0004.1
0000.1
0000.2
0000.1
3)4()5( xx



 


























0221.0
1597.0
3503.0
100.1
0000.1
0002.2
0004.1
0000.1
0000.2
0000.1
3)4()5( xx
3)4()5( 10  xx 3)4()5( 10  xx











)10/6( )10/3( )10/2(
)5/8( )5/1( )5/1( 
)10/7( )10/1( )10/2( 
)(
2
)(
1
)(
3
)1(
3
)(
1
)(
2
)1(
3
)1(
2
)(
1
kkk
kkk
kkk
xxx
xxx
xxx











)10/6( )10/3( )10/2(
)5/8( )5/1( )5/1( 
)10/7( )10/1( )10/2( 
)(
2
)(
1
)(
3
)1(
3
)(
1
)(
2
)1(
3
)1(
2
)(
1
kkk
kkk
kkk
xxx
xxx
xxx
tx )1,1,1()0( 
32
O Método de Gauss-Seidel
 Formulação matricial
 Na forma matricial, a equação geral do método de G-S é descrita por:
 Portanto, na forma compacta, tem-se:
 Se existe , então:





































































n
k
n
k
k
n
n
k
n
k
k
nnnn b
b
b
x
x
x
a
aa
x
x
x
aa
a
a
a
a














2
1
)1(
)1(
2
)1(
1
2
112
)(
)(
2
)(
1
21
2122
11
000
00
0
0
00
000
00
00
00
 D  L  U  b  )1( kx  )(kx
  bUxxLD kk   )1()(  bUxxLD kk   )1()(
cTxx kk   )1()( cTxx kk   )1()(
  1 LD
bLDc
ULDT
1
1
)(
 e )( :onde




bLDc
ULDT
1
1
)(
 e )( :onde



 nnaaaLD  2211)det(:que Note
nnaaaLD  2211)det(
:que Note    bLDUxLDx kk 1)1(1)(       bLDUxLDx kk 1)1(1)(  
33
O Método de Gauss-Seidel
 Formulação matricial (Exemplo)
 Considere o sistema linear:
 Aplicando-se a equação geral , obtém-se:
 Autovalores de T:
,
61032 
8 5 
71210
321
321
321









xxx
xxx
xxx
,
61032 
8 5 
71210
321
321
321









xxx
xxx
xxx









1
2
1
x









1
2
1
x:é solucão cuja
cTxx 







































000
100
120
03-2-
001-
000
1000
050
0010
 )(
1
1ULDT







































000
100
120
03-2-
001-
000
1000
050
0010
 )(
1
1ULDT











074.0028.00
18.004.00
10.02.00











074.0028.00
18.004.00
10.02.00
ii 0689.0057.0 ,0689.0057.0 ,0.0 321   ii 0689.0057.0 ,0689.0057.0 ,0.0 321   .10894.0)( T .10894.0)( T
Note a redução do raio espectral em relação ao método de Jacobi
34
Método de Jacobi e Gauss-Seidel
 Comentários
 Se a matriz de coeficientes do sistema for de diagonal 
estritamente dominante, então, para qualquer vetor de coeficientes 
e para qualquer aproximação inicial , ambos os métodos, Jacobi 
e Gauss-Seidel, convergem para a solução única de . 
 Em geral, o método de Gauss-Seidel apresenta desempenho 
superior ao método de Jacobi, porém, há sistemas lineares em que 
o método de Jacobi converge e o método de Gauss-Seidel não 
converge.
 A formulação matricial é comum aos dois 
métodos, porém a matriz T e o vetor c são distintos para cada 
método.
bAx 
b
)0(x
bAx 
cTxx kk   )1()(
35
O método SOR
 Aspectos gerais
 O método SOR é uma técnica mais recente que os métodos Jacobi e 
Gauss-Seidel.
 Utiliza o conceito de relaxação no método de Gauss-Seidel, através 
do uso de um fator de escala em cada iteração, para alterar a 
velocidade de convergência do processo de resolução.

36
O método SOR
 Formulação matemática
 O método SOR é uma técnica iterativa para o cálculo de aproximações 
. , em um processo descrito por , obtido a 
partir de um sistema do tipo : 
 A equação geral do método SOR é dado por:
 Usando-se os coeficientes do sistema , resulta: 
,2,1 ;)( kx k
     
ni
xaxab
a
xx
i
j
n
ij
k
jij
k
jiji
ii
kk
i
,,2,1p/ 
,1
1
1 1
)1()()1()(



   
 
      
ni
xaxab
a
xx
i
j
n
ij
k
jij
k
jiji
ii
kk
i
,,2,1p/ 
,1
1
1 1
)1()()1()(



   
 
 
)( )1()(  kk xgx
bAx 
 )1()1()1()( )(   kkkk xxgxx   )1()1()1()( )(   kkkk xxgxx  SeidelGaus de método1  relaxação-sub de método:10 
relaxação-sobre de método:1 
bAx 
37
O método SOR
 Formulação matricial
 A equação geral anterior pode ser re-escrita na seguinte forma: 
 Assim, na forma matricial compacta, tem-se:
 Se existe , então:
     
ni
bxaxaxaxa i
n
ij
k
jij
k
ii
i
j
k
jij
k
iii
,,2,1p/ 
1
1
)1()1(
1
1
)()(

 



      
ni
bxaxaxaxa i
n
ij
k
jij
k
ii
i
j
k
jij
k
iii
,,2,1p/ 
1
1
)1()1(
1
1
)()(

 




     bxUDxLD kk    )1()( 1     bxUDxLD kk    )1()( 1
  1 LD 
       bLDxUDLDx kk 1)1(1)( 1          bLDxUDLDx kk 1)1(1)( 1   
cTxx kk   )1()( cTxx kk   )1()(
38
O método SOR
 Condições de convergência
 Se a matriz A for positiva-definida e , então o método SOR 
converge para qualquer escolha de condição inicial . 
 Exemplo
 Considere o sistema:
 Resolva para usando GS e SOR com . 
20 
)0(x
:é solucão cuja










5
4
3
x










5
4
3
x





























24
30
24
410
143
034
3
2
1
x
x
x





























24
30
24
410
143
034
3
2
1
x
x
x
25.1tx )1,1,1()0( 
    bLDUxLDx kk 1)1(1)(       bLDUxLDx kk 1)1(1)(  :GS
:SOR        bLDxUDLDx kk 1)1(1)( 1          bLDxUDLDx kk 1)1(1)( 1   
39
O método SOR
 Matrizes do sistema:
 Portanto:
;
010
003
000









L ;
010
003
000









L
  ULDTg 1   ULDTg 1
:GS
:SOR
    UDLDT    11    UDLDT    11
;
400
040
004








D ;
400
040
004








D





























24
30
24
410
143
034
3
2
1
x
x
x





























24
30
24
410
143
034
3
2
1
x
x
x







 

000
100
030
U







 

000
100
030
U







 

0625.01406.00
25.05625.00
075.00
T







 

0625.01406.00
25.05625.00
075.00
T 625.0)( gT 625.0)( gT











1523.01965.00732.0
3125.06289.02344.0
09375.025.0
T











1523.01965.00732.0
3125.06289.02344.0
09375.025.0
T
25.0)(  T 25.0)(  T
40
O método SOR
 Resultados:
 Usando Gauss-Seidel:
 Usando SOR:
0003.50967.56004.46501.60.1
00026.40103.49585.35195.30.1
00005.31333.36223.23125.60.1
73210
)(
3
)(
2
)(
1
 



k
k
k
x
x
x
k
0003.50967.56004.46501.60.1
00026.40103.49585.35195.30.1
00005.31333.36223.23125.60.1
73210
)(
3
)(
2
)(
1
 



k
k
k
x
x
x
k
0028.50183.50293.50487.50.1
9888.39267.38828.38125.30.1
0134.30879.31406.32500.50.1
73210
)(
3
)(
2
)(
1
 



k
k
k
x
x
x
k
0028.50183.50293.50487.50.1
9888.39267.38828.38125.30.1
0134.30879.31406.32500.50.1
73210
)(
3
)(
2
)(
1
 



k
k
k
x
x
x
k
    bLDUxLDx kk 1)1(1)(       bLDUxLDx kk 1)1(1)(  
iterações 34p/ 10
:precisão de Ordem
 6
iterações 14p/ 10
:precisão de Ordem
 6
       bLDxUDLDx kk 1)1(1)( 1          bLDxUDLDx kk 1)1(1)( 1   
41
O método SOR
 Aplicação para matrizes tri-diagonais Se A for uma matriz tri-diagonal, então , e a 
escolha ótima de para o método SOR é: 
 Comentários
 Métodos de sub-relaxação :
Usados para se obter convergência em alguns sistemas que não são 
convergentes pelo método de Gauss-Seidel.
 Métodos de sobre-relaxação :
Usados para acelerar a convergência em sistemas que são convergentes 
pelo método de Gauss-Seidel.
  1)()( 2  jg TT 

 2)(11
2
jT


  2)(11
2
jT


 1)(  T
10 
1
42
Limites de Erro e Refinamentos Iterativos
 Erro limitado pelo vetor de resíduos
 Se é uma aproximação para a solução de e é uma matriz 
não-singular, então, para qualquer norma natural, tem-se:
e, , supondo .
 Estes resultados implicam que fornecem uma 
indicação da correlação entre o vetor resíduo e a precisão da 
aproximação, para qualquer norma.
 Em geral, o erro relativo é de maior interesse, sendo este erro limitado 
pelo produto de com o erro relativo residual para esta 
aproximação, .
1~~  AxAbxx 1~~  AxAbxx
x~ bAx  A
b
xAb
AA
x
xx ~~ 1  
b
xAb
AA
x
xx ~~ 1   0 e 0  bx
 e 11  AAA
 1AA
 b/~xAb 
43
Limites de Erro e Refinamentos Iterativos
 Número de condição de uma matriz
 O número de condição, , de uma matriz não-singular relativo 
a uma norma é:
 Com esta notação, pode-se escrever as condições anteriores de 
limitação do erro como segue: 
 Para qualquer matriz A não-singular e norma natural , tem-se: 
)(A A

1)(  AAA 1)(  AAA
A
xAb
Axx
~
)(~
 
A
xAb
Axx
~
)(~
 
b
xAb
A
x
xx ~
)(
~  
b
xAb
A
x
xx ~
)(
~  e

)(1 11 AAAAAI   )(1 11 AAAAAI  
44
Limites de Erro e Refinamentos Iterativos
 Número de condição de uma matriz (cont.)
 Matriz bem-condicionada:
Uma matriz é bem-condicionada se estiver próximo a 1.
 Matriz mal-condicionada: 
Uma matriz é mal-condicionada se
 Exemplo
 Considere a matriz:
)(AA
A 1)( A



20001.1
21
A 


20001.1
21
A





50005.5000
10000100001A 




50005.5000
10000100001A
0001.3A 0001.3A
200001 A 200001 A
60002)( 1  AAA 60002)( 1  AAA
45
Limites de Erro e Refinamentos Iterativos
 Exemplo (cont.)
 O sistema linear abaixo tem solução única :
 O vetor resíduo para a aproximação é: 
 Análise: 
 Embora a norma do vetor resíduo seja muito pequena, a 
aproximação é considerada muito pobre (insuficiente);
 Esse tipo de dificuldade surge em sistemas lineares com matriz de 
coeficientes mal-condicionadas e exige uma análise cuidadosa do 
processo de convergência para solução.







0001.3
3
20001.1
21
2
1
x
x







0001.3
3
20001.1
21
2
1
x
x
tx )1,1(
0002.0~  xAb 0002.0~  xAb
e
tx )0,3(~ 










0002.0
0
0
3
20001.1
21
0001.3
3~xAb 









0002.0
0
0
3
20001.1
21
0001.3
3~xAb
2~  xx 2~  xx
tx )0,3(~ 
46
Limites de Erro e Refinamentos Iterativos
 Exemplo (cont.)
 Visualização gráfica da aproximação e da solução 
única para o sistema linear :







0001.3
3
20001.1
21
2
1
x
x







0001.3
3
20001.1
21
2
1
x
x
tx )1,1(
tx )0,3(~ 
32: 211  xxl
0001.320001.1: 212  xxl



1
1
:Solução *x 


1
1
:Solução *x
47
Esta aproximação , situa-se, em geral, mais próxima da 
solução única do sistema linear que a aproximação .
Limites de Erro e Refinamentos Iterativos
 Refinamentos Iterativos
 O resíduo de uma aproximação também pode ser utilizado para 
melhorar a aproximação.
 Suponha que é uma aproximação para a solução do sistema 
e que é o resíduo.
 Considere ser a solução aproximada para o sistema .
 Então: 
x~ bAx 
xAbr ~
y~ rAy 
rAy 1~  rAy 1~  )~(1 xAbA   )~(1 xAbA   xAAbA ~11   xAAbA ~11   xxy ~~  xxy ~~  yxx
~~  yxx ~~ 
yxx ~~ 
x~
Recomenda-se analisar o exemplo 3, página 375, do livro Faires e Burden.
48
O método Gradiente Conjugado
 Aspectos gerais
 O método gradiente conjugado (GC) foi originalmente desenvolvido, 
em 1952, por Hestenes e Stiefel, como um método direto, mas 
apresentou desempenho inferior ao método da eliminação gaussiana 
com pivoteamento.
 Posteriormente, verificou-se que o método GC é muito útil para a 
resolução de sistemas lineares de grande porte e esparsos, que 
surgem na resolução de problemas de valores de contorno descritos 
por equações diferenciais ordinárias e que surgem na resolução de 
equações diferenciais parciais.
 O método é aplicável para sistemas com matriz de coeficientes 
simétrica e positiva definida.
49
O método Gradiente Conjugado
 Representação de produto interno
 Utilizar-se-á a seguinte representação para produto interno de 
vetores:
 Propriedades do produto interno
 Para quaisquer vetores e qualquer número real , tem-se:
(i)
(ii)
(iii) 
(iv) 
(v) 
yxyx t, yxyx t,
zyx e, 
xyyx ,, 
yxyxyx ,,,  
yzyxyzx ,,, 
0, xx
0 se somente e se 0,  xxx
50
O método Gradiente Conjugado
 Outras propriedades envolvendo o produto interno
 Para positiva definida, tem-se:
 Para positiva definida e simétrica, tem-se:
A
0 se ,0,  xAxxAxx t 0 se ,0,  xAxxAxx t
A
  yAxyAxAyx tttt    yAxyAxAyx tttt  yAxAyx ,,  yAxAyx ,, 
51
O método Gradiente Conjugado
 Formulação básica
 Para simétrica e positiva definida, tem-se:
 Ilustração para 
 Função : 
)( nnA 
bxAxxxgbAx ,2,)(min  bxAxxxgbAx ,2,)(min  bxAxxxg tt 2)(min  bxAxxxg tt 2)(min 
)22( A
)(xg

    






2
1
21
2
1
2221
1211
21 2)( b
b
xx
x
x
aa
aa
xxxg     






2
1
21
2
1
2221
1211
21 2)( b
b
xx
x
x
aa
aa
xxxg
2211
2
22221212112
2
111 22)( bxbxxaxxaxxaxaxg  22112222212121122111 22)( bxbxxaxxaxxaxaxg 
),()( 21 xxgxg 
52
O método Gradiente Conjugado
 Ilustração para (cont.)
 Cálculo do gradiente de : 
 Portanto, para A simétrica, , tem-se:
2211
2
22221212112
2
111 22)( bxbxxaxxaxxaxaxg  22112222212121122111 22)( bxbxxaxxaxxaxaxg 


















222212112
122112111
2
1
22)(
2)(2
)(
)(
)(
bxaxaa
bxaaxa
x
xg
x
xg
xg 

















222212112
122112111
2
1
22)(
2)(2
)(
)(
)(
bxaxaa
bxaaxa
x
xg
x
xg
xg
)22( A
)(),( xgxg 







2
1
2
1
2221
1211 22)(
b
b
x
x
aa
aa
xg 





2
1
2
1
2221
1211 22)(
b
b
x
x
aa
aa
xg
  rbAxxg 22)( 
resíduo vetor o é
:onde Axbr 
Note que é a solução do sistema , sendo 
o resultado válido também para . 
2112 aa 
0)(),( *2
*
1  xgxx t bAx 
)( nnA 
0)()(min  xgxg
 Princípio geral de funcionamento
 Escolher uma aproximação inicial .
 Escolher uma direção em que diminui.
 Escolher um passo t tal que .
 Equação geral:
 Note que é um escalar que define a distância do deslocamento na 
direção .
 A direção é a direção de maior decréscimo de , neste 
caso equivalente a direção do vetor de resíduos r.
 No método GC toma-se como primeira direção de busca a direção do 
vetor de resíduos, calculado a partir de uma aproximação inicial . 
 Todas as direções subseqüentes do processo iterativo devem ser 
ortogonais em relação a matriz A.
53
O método Gradiente Conjugado
)0(x
)(xg
)()( )0(xgxg 
,2,1 ;)()1()(   kvtxx kkkk ,2,1 ;)()1()(   kvtxx kkkk
kt
)(kv
)(xg )(xg
)0(x
)0()0()1( Axbrv  )0()0()1( Axbrv 
 jiAvv ji  se ,0, )()( jiAvv ji  se ,0, )()(
54
O método Gradiente Conjugado
 Condição de minimização
 O vetor é uma solução para o sistema linear 
. , A positiva definida, se e somente se 
minimiza:
 Para a função 
. tem seu mínimo quando:
 Note que define um mínimo na direção , 
sendo o mínimo de obtido com a repetição do 
processo em novas direções,ortogonais em relação 
a matriz A.
*x
bAx  *x
bxAxxxg ,2,)(  bxAxxxg ,2,)( 
,2,1 ;0 e )()1(  kvx kk
)( )()1( kk
k vtxg 
)()()1()( ,/, kkkkk AvvAxbvt
 )()()1()( ,/, kkkkk AvvAxbvt 
)(xg
)( )()1( kk tvxg 
kt
)(xg
)(kv
55
O método Gradiente Conjugado
 Sumário de Fórmulas
 Resíduo e direção inicial:
 Fórmulas do processo iterativo
)0()1( rv e
( para 1, 2, , )k n 
)1()1(
)()(
,
,
 kk
kk
k rr
rr
s
)1()1(
)()(
,
,
 kk
kk
k rr
rr
s
( ) ( 1) ( )k k k
kx x t v
 ( ) ( 1) ( )k k kkx x t v 
)()1()( k
k
kk Avtrr   )()1()( kkkk Avtrr  
)()()1( k
k
kk vsrv  )()()1( kkkk vsrv 
( )mínimo na direção kv
)((*)
)(
 Faça
pare. , Se .atualizado resíduo
k
k
xx
r

 
( 1) ( )direção conjuga: , 0k kv Av 
*nova aproximação para x
( 1) ( 1)
( ) ( )
,
,
k k
k k k
r r
t
v Av
 

( 1) ( 1)
( ) ( )
,
,
k k
k k k
r r
t
v Av
 

(0) (0)r b Ax 
56
O método GC pré-condicionado
 Aspectos gerais
 Se a matriz A for mal-condicionada, o método gradiente conjugado 
(GC) torna-se altamente suscetível aos erros de arredondamento.
 O método GC é geralmente aplicado como um método iterativo para 
sistemas bem condicionados e, nestes casos, obtém-se uma 
aproximação aceitável para a solução em cerca de passos.
 A aplicação do método GC a um sistema melhor condicionado é feita 
usando uma matriz não-singular, de pré-condicionamento, tal que:
 Assim, aplica-se o método GC ao sistema: 
 A solução é obtida por:
n
C
tCACA )(~ 11  tCACA )(~ 11 
Ax b  Ax b   bCbxCx t 1~ e ~ :onde  bCbxCx t 1~ e ~ :onde 
tx C x tx C x 
,
57
O método GC pré-condicionado
 Sumário de Fórmulas nas variáveis originais
 Resíduo e direção inicial:
 Fórmulas do processo iterativo
)0()0( Axbr  )0()1( wCv t,
)()(
)1()1(
,
,~
kk
kk
k Avv
ww
t


)()(
)1()1(
,
,~
kk
kk
k Avv
ww
t


),,2,1 para ( nk 
)1()1(
)()(
,
,~
 kk
kk
k ww
ww
s
)1()1(
)()(
,
,~
 kk
kk
k ww
ww
s
)()1()( ~ k
k
kk vtxx   )()1()( ~ kkkk vtxx  
)()1()( ~ k
k
kk Avtrr   )()1()( ~ kkkk Avtrr  
)()()1( ~ k
k
ktk vswCv   )()()1( ~ kkktk vswCv  
)0(1)0( rCw ,
)(1)( kk rCw  )(1)( kk rCw 
)( direção na mínimo kv
* para oaproximaçã nova x
)((*)
)(
 Faça
pare. , Se .atualizado resíduo
k
k
xx
r

 
0, :conjuga direção )()1(  kk Avv
58
O método GC pré-condicionado
 Exemplo
 Considere o sistema:
 Considere ainda e . 
 Então, obteve-se o seguinte resultado:





























24
30
24
410
143
034
3
2
1
x
x
x





























24
30
24
410
143
034
3
2
1
x
x
x :é solucão cuja










5
4
3
x










5
4
3
x
ICC  1 tx )0,0,0()0( 
9999.49542.45258.30
0000.41490.44072.40
9999.28580.25258.30
3210
)(
3
)(
2
)(
1
k
k
k
x
x
x
k
9999.49542.45258.30
0000.41490.44072.40
9999.28580.25258.30
3210
)(
3
)(
2
)(
1
k
k
k
x
x
x
k
8)(
3
8)(
2
8)(
1
1014.00341.04897.524
1039.01241.07320.130
1036.01210.03247.324
3210






k
k
k
r
r
r
k
8)(
3
8)(
2
8)(
1
1014.00341.04897.524
1039.01241.07320.130
1036.01210.03247.324
3210






k
k
k
r
r
r
k
Lembre-se que foram necessárias 34 e 14 iterações para resolver o 
mesmo sistema por G-S e SOR, respectivamente. . 
59
O método GC pré-condicionado
 Comentários
 O método GC pré-condicionado é freqüentemente usado na resolução 
de sistemas lineares de grande porte e matrizes esparsas.
 Esses sistemas são comuns em problemas de valores de contorno 
descritos por equações diferenciais ordinárias.
 Quanto maior a dimensão do sistema maiores são os benefícios, em 
geral, da opção pelo método GC, visto ser significativamente reduzido o 
número de interações necessárias, comparando-se a outros métodos.
 É comum o uso da matriz de pré-condicionamento C aproximadamente 
igual a matriz L da fatoração de Choleski .
 Geralmente, os elementos numericamente pequenos de A são 
ignorados no cálculo da matriz de pré-condicionamento e, assim, 
denominada de fatoração incompleta de Choleski.
ALLt 
ALLt  ALLt  11   ACC t 11   ACC t
LC 
60
O método GC pré-condicionado
 Exemplo de aplicação
 Considere o sistema linear:
 Características da matriz A:
 simétrica;
 positiva definida;
mal-condicionada 



































5
4
3
2
1
5
4
3
2
1
7004210
48011
206011
11141.0
0111.02.0
b
b
b
b
b
x
x
x
x
x



































5
4
3
2
1
5
4
3
2
1
7004210
48011
206011
11141.0
0111.02.0
b
b
b
b
b
x
x
x
x
x
:é solucão cuja












60106261628.0
5406430164.0
60735922390.0
4229264082.0
859713071.7
*x












60106261628.0
5406430164.0
60735922390.0
4229264082.0
859713071.7
*x
 71.1396)(  A61
O método GC pré-condicionado
 Exemplo de aplicação (cont.)
 Comparação do desempenho de métodos
2/1DC  Maior precisão e menor número de iterações
62
Resolução de SL por métodos iterativos
 Comentários Finais
 Os métodos de Jacobi e Gauss-Seidel exigem a especificação de uma 
aproximação inicial e geram uma seqüência de vetores 
usando a equação da forma .
 A condição suficiente para a convergência desses métodos é que o 
raio espectral da matriz de iteração , e quanto menor for o raio 
espectral mais rápida será a convergência. 
 O método SOR é uma alternativa para acelerar a convergência do 
método de Gauss-Seidel usando-se um fator de escala .
 O método gradiente conjugado é aplicável a sistemas com matrizes 
simétricas, positivas definidas, esparsas e de grande porte, que 
surgem normalmente em problemas de valores de contorno e 
equações diferenciais parciais.
 Na maioria das aplicações do método GC deve ser utilizada uma 
matriz de pré-condicionamento.
cTxx kk   )1()(
)0(x )(kx
1)( T
21 