Embed Size (px)
Citation preview
SOLUÇÃO DE SISTEMA DE EQUAÇÕESSOLUÇÃO DE SISTEMA DE EQUAÇÕES
A solução de um sistema de equações é necessária na grande maioriados problemas de engenharia
Problemas de interpolação e ajuste de curvas
Solução de equações diferenciais - simulação de problemas de engenharia
Maior parte do tempo de uma simulação por elementos finitos,diferenças finitas ou outro método numérico é gasto na
resolução do sistema de equações obtido com a discretização
Necessidade de métodos robustos e rápidos
SISTEMA DE n EQUAÇÕES E n INCÓNITAS
=+++
=+++=+++
nnnnnn
nnnn
bxaxaxa
bxaxaxabxaxaxa
KMKK
2211
2222212111212111
Se os coeficientes aij são constantes, o sistema é dito linear
O sistema acima pode ser representado na forma de matriz:
=
−
−
−
−
nnnnannnn
nn
nn
nn
b
bbb
x
xxx
aaaa
aaaaaaaaaaaa
MML
MMMMLLL
3
2
1
3
2
1
21
3133231
2122221
1111211
bAx =
MÉTODOS DE SOLUÇÃO
MÉTODOS DIRETOS
A solução exata (a menos de erros de truncamento do computador)é determinada após um número finito de operações
Requer mais memória de armazenamentoMais robustoMais rápido
MÉTODOS ITERATIVOS
Fornece uma sequência de soluções aproximadas que convergemquando o número de passos tende a infinito
Menor necessidade de memória de armazenamentoProblemas de convergência
MÉTODOS DIRETOSSISTEMAS TRIANGULARES
=
−
−
−
nnnn
nn
nn
nn
b
bbb
x
xxx
u
uuuuuuuuu
MML
MMMMLLL
3
2
1
3
2
1
313
21222
1111211
000
000
Se niuii ,,2,1,0 K=≠
ii
n
ikkkii
i
nn
nnnnnnnnnnnn
nn
nn
u
xubx
uxub
xbxuxu
ubx
∑+=
−−
−−−−−−−−
−=
−=→=+
=
1,
1,1
,1111,111,1
:i linha
; :1-n linha
; :n linha
M
RETROSUBSTITUIÇÃO
as incógnitas podem ser facilmente calculadas
Se a matriz for triangular inferior:
=
− nnnnannnn b
bbb
x
xxx
llll
llll
l
MML
MMMMLLL
3
2
1
3
2
1
21
3231
2221
11
0000000
A solução é calculada da seguinte forma:
ii
i
ikkkii
i l
xlbx
uxub
xbxuxu
lbx
∑−
=
−=
−=→=+
=
1
,
22
11,222222,211,2
11
11
:i linha
; :2 linha
; :1 linha
M
SUBSTITUIÇÃO A FRENTE
∑=
≈−+=−+n
i
nnnnin1
2
21)1(
21)1(NÚMERO DE OPERAÇÕES:
ELIMINAÇÃO GAUSSIANA
Eliminar as variáveis de uma maneira sistemática até obter um sistema triangular, de fácil solução
=+++
=+++=+++
nnnnnn
nnnn
bxaxaxa
bxaxaxabxaxaxa
KMKK
2211
2222212111212111
Eliminar x1 das (n-1) úlimas equações
Se a 011 ≠
−=
−++
−+
−=
−++
−+
−
=+++
111
11
11
1212
11
121
111
2121
11
212212
11
21221
0
1111
2121
11212111
0 baabxa
aaaxa
aaax
baabxa
aaaxa
aaaxa
aaa
bxaxaxa
nnnn
nnn
nn
nnn
nn
K
M
K
44 344 21
K
Após o primeiro passo, o sistema fica sendo:
nibmbbniamaa
niaam
iii
jiijij
ii
,,3,2;,,3,2;
,,3,2;
11)2(
11)2(
11
11
K
K
K
=−==−=
==
=++
=++=+++
)2()2(2
)2(2
)2(2
)2(22
)2(22
11212111
nnnnn
nn
nn
bxaxa
bxaxabxaxaxa
K
MK
K Onde
Eliminar x2 das (n-2) últimas equações
Se 0)2(22 ≠a
=++
=++=+++
=++++
)3()3(3
)3(3
)3(3
)3(33
)3(33
)2(2
)2(23
)2(232
)2(22
11313212111
nnnnn
nn
nn
nn
bxaxa
bxaxabxaxaxa
bxaxaxaxa
K
MK
K
K
nibmbbniamaa
niaam
iii
jiijij
ii
,,4,3;,,4,3;
,,4,3;
)2(22
)2()3(
)2(22
)2()3(
)2(22
)2(2
2
K
K
K
=−==−=
==
E assim por diante, até obter um sistema da forma
=
=++=+++
=++++
)()(
)3(3
)3(33
)3(33
)2(2
)2(23
)2(232
)2(22
)1(1
)1(13
)1(132
)1(121
)1(11
nnn
nnn
nn
nn
nn
bxa
bxaxabxaxaxa
bxaxaxaxa
MK
K
K
O SISTEMA TRIANGULAR PODE SER FACILMENTE RESOLVIDOATRAVÉS DE UMA RETROSUBSTITUIÇÃO
Os elementos são denominados de Pivots)1(1,1
)2(22
)1(11 ,,, −
−−n
nnaaa K
O lado direito do sistema de equações é modificado da mesma formaque os coeficientes das equações
Melhor tratar o sistema na forma matricial, com o lado direito do sistemasendo a coluna n+1 da matriz, conforme mostrado a seguir
−
−
−
−
nnnannnn
nn
nn
nn
b
bbb
aaaa
aaaaaaaaaaaa
ML
MMMMLLL
3
2
1
21
3133231
2122221
1111211niba ki
kni ,,2,1,)()(
1, K==+
ALGORÍTMO
RETROSUBSTITUIÇÃOELIMINAÇÃO
end
end*
,1For 0
1,1,For
)(
)(1,
)(
iii
ini
i
ki
ik
asuma
x
xasumsumnik
sumni
−=
+=+=
=−=
+
endend
end
1,1For
,1For 1,1For
)()()1(
)(
)(
kkjik
kij
kij
kkk
kik
ik
amaankj
aam
nkink
−=++=
=
+=−=
+
NÚMERO DE OPERAÇÕES:
RETROSUBSTITUIÇÃOELIMINAÇÃO
∑−
=
≈+−−1
1
331)1)((
n
k
nknkn ∑=
≈−=−n
i
nnni1
221
21 )1()1(
O maior custo computacional ocorre no processo de eliminação
Supor que o tempo de cada operação seja de 1 microsegundo t
O tempo em segundos de cada parte do algoritmo é mostrado abaixo
s610−=
n Eliminação Retrosubstituição10 0.0050 s 0.0008 s
100 5 s 0.075 s1000 5000 s 7.5 s
PIVOTAMENTO
RESOLVER O SISTEMA POR ELMINAÇÃO GAUSSIANA
⇒
=++=++
=++
122122111111
12222
1
321
321
321
xxxxxx
xxx
1321 ==−= xxxSistema não singular, e a solução é:
Após o primeiro passo na eliminação, a matriz fica sendo:
0011011001111
)2(22 =→
a
A eliminação não pode continuar pelo procedimento normal.
Uma solução seria trocar a posição das linhas 2 e 3, o que já fornece a matriz triangular
OUTRO EXEMPLO: RESOLVER O SISTEMA POR ELMINAÇÃO GAUSSIANA
⇒
=++=++
=++
1221220001.111111
122220001.1
1
321
321
321
xxxxxx
xxx
0001.1 e 1 321 ==−= xxxSistema não singular, e a solução é:
O sistema triangular obtido após a eliminação sem troca de linhas é:
10000999900110001.001111
O processo de retrosubstituição usando uma precisão de 3 casas decimais fornece:
Resultado incorreto000.1,0 ,0 321 === xxx
Se as linhas 2 e 3 fossem trocadas durante o processo de eliminação, a solução também usando uma precisão de 3 casas decimais seria
000.1,000.1 ,000.1 321 =−== xxx Resultado correto usando uma precisão de 3 casas decimais
Para evitar falha catastrófica (divisão por zero) ou resultados erradosé necessário fazer uma escolha criteriosa dos PIVOTS usados na eliminação
PIVOTAMENTO PARCIALPIVOTAMENTO COMPLETO
k s
kPIVOTAMENTO PARCIAL
No passo k do processo de eliminação
rknikaa
rk
ikk
rk
e linhasTrocar ,max
que talinteiromenor o como Escolher )()(
•≤≤=
• k
r
PIVOTAMENTO COMPLETONo passo k do processo de eliminação
skrknjikaa
srk
ijk
rs
e colunas e , e linhasTrocar ,,max
que talinteiros menores os como e Escolher )()(
•≤≤=
• k
r
A Eliminação Gaussiana deve ser feita sempre com PIVOTAMENTOpara garantir estabilidade do método
Na grande maioria dos casos, PIVOTAMENTO PARCIAL é suficientee deve ser usada no lugar de PIVOTAMENTO COMPLETO
PIVOTAMENTO COMPLETO não é muito usado devido ao grandetempo computacional gasto no processo de busca do pivot.
PIVOTAMENTO não é necessário em dois casos particulares
MATRIZ DIAGONAL DOMINANTE
MATRIZ SIMÉTRICA E POSITIVA-DEFINIDA
∑≠=
=≥n
ijj
ijii niaa1
.,,2,1, K
0xAxxAA ≠∀>== ,0 e)( Tjiij
T aa
%===========================================================================% MEC 1701 - METODOS NUMERICOS PARA ENGENHARIA MECANICA% MEC 2951 - METODOS NUMERICOS E COMPUTACIONAIS%% Departamento de Engenharia Mecânica% PUC-Rio%% Prof. : Marcio Carvalho% Monitor: Oscar Coronado%===========================================================================
% PROGRAMA PARA O RESOLUÇÃO DE UM SISTEMA DE EQUAÇÕES POR ELIMINAÇÃO GAUSSIANA
% SETEMBRO 2001
%===========================================================================
% Comandos de inicialização: Limpeza da memoria do ambiente MatLab
clcclear all
% Mostrar na tela titulo do programadisp(' ' );disp(' ' );disp(' ELIMINAÇÃO GAUSSIANA ' );disp(' ---------- --------- ' );
% Definição do tamanho do sistemadisp(' ' );disp(' ' );n=input('Entre com o numero de equações : ');disp(' ' );disp(' ' );% Definiçao da Matriz a ser resolvida
A=input('Entre a matriz dos coeficientes A(n*n): ');disp(' ' );disp(' ' );
% Definição do termo independente (lado direito do sistema)
b=input('Entre o vetor dos valores do lado direito do sistema b(n,1) : ');disp(' ' );disp(' ' );
%--------------------------------------------------------------------------
% ELIMINAÇÃO GAUSSIANA
success=1;
for i=1:n
% Procura um Pivot (Pivotamento Parcial)
pivot=abs(A(i,i));irow = i;
for k=i+1:n
if (abs(A(k,i))>pivot) pivot=abs(A(k,i));irow=k;
end
end
% Checar se a matriz e singular
if (pivot < 1e-10) success=0;stop;
end
% Trocar as linhas i e k
for j=i:naaux=A(irow,j);A(irow,j)=A(i,j);A(i,j)=aaux;
end
baux = b(irow);b(irow)=b(i);b(i)=baux;
% Proceder com a eliminação dos elementos abaixo da linha i
for k=i+1:nm=A(k,i)/A(i,i);for j=i:n
A(k,j)=A(k,j)-A(i,j)*m;endb(k)=b(k)-b(i)*m;
end
end
% retrosubstituição
for i=n:-1:1
sum=0;for j=i+1:n
sum=sum+A(i,j)*x(j,1);end
x(i,1)=(b(i)-sum)/A(i,i);
end
disp(' A solução do sistema é : ' );
disp(' ' );disp(' ' );
x
DECOMPOSIÇÃO LUMuitas vezes o mesmo sistema é resolvido com
diferentes termos independente (lado direito do sistema)
Pode-se evitar o processo repetido de eliminação gaussiana atravésde uma decomposição da matriz A
Todo matriz não singular pode ser decomposta como o produto de uma matriztriangular inferior L e uma matriz triangular superior U
Uma vez feita a decomposição, a solução do sistema fica reduzida a soluçãode dois sistemas triangulares:
L;; 2211 bAxbAx ==
=
==
− nn
n
n
n
nnnn u
uuuuuuuuu
lll
lll
000
000
;
1
010010001
; 333
22322
1131211
1,21
3231
21
LM
LLL
LM
LLL
ULLUA
{
yUxbLy
bUxLy
==
⇒=
depois e Resolver
Sistema triangular inferiorSistema triangular superior
EQUIVALÊNCIA ENTRE DECOMPOSIÇÃO LU E ELIMINAÇÃO GAUSSIANA
A eliminação gaussiana pode ser vista como a determinaçãode uma sequência de matrizes )()3()2()1( ,,,, nAAAAA K=
=
)()(
)()(
)2(2
)2(2
)2(22
)1(1
)1(1
)1(12
)1(11
)(
0 que tal
knn
knk
kkn
kkk
nk
nk
k
aa
aa
aaaaaaa
L
LL
LLL
LL
A
jiaaaji iij
iij
nij ≤===≤• + , :principal) diagonal da acima (elemento Se )()1()( L
jiaaji jij
nij >===>• + ,0 :principal) diagonal da abaixo (elemento Se )1()( L
),1min(,,3,2,1;)()()1( jirkamaa kkjik
kij
kij −==−=+ K
),1min(,,3,2,1;)()()1( jirkamaa kkjik
kij
kij −==−=+ K
Calculando o somatório para k=1, …, r, obtém-se:
>+
≤+=⇒
⇒+=
⇒−=−=−=−
⇒−=
∑
∑
∑
∑∑∑
∑∑∑
=
−
=
=
+
=
++
==
+
===
+
j
k
kkjik
i
k
kkjik
iij
ij
r
k
kkjik
rijij
r
k
kkjikij
rijij
rij
r
k
kij
r
k
kij
r
k
kkjik
r
k
kij
r
k
kij
jiam
jiamaa
amaa
amaaaaaa
amaa
1
)(
1
1
)()(
1
)()1(
1
)()1()1()1(
1
)(
1
)1(
1
)(
1
)(
1
)1(
;0
;
∑=
==
==p
k
kkjikij
ii
jipama
nim
1
)( ),min(,
,,2,1;1 KDefinindo
Observe que a expressão anterior representa o produto de duas matrizes
., e ),1( )( jkaUkimmL kkjkjiiikik ≤=≥==
= LUA
nn
n
n
n
u
uuuuuuuuu
000
000
333
22322
1131211
LM
LLL
− 1
010010001
1,21
3231
21
nnnn mmm
mmm
LM
LLL
∑==
=
=+=2),min(
12232123132
jip
kkjikumumuma
A matriz L corresponde aos coeficientes mik da eliminação gaussiana e a matriz U corresponde a matriz triangular superior obtida na eliminação gaussiana
ESQUEMA COMPACTO PARA DECOMPOSIÇÃO LU E ELIMINAÇÃO GAUSSIANA
No algorítmo para decomposição LU apresentado anteriormente, diversosresultados parciais devem ser armazenados temporariamente antesdo cálculo final de cada elemento da matriz L e U.
Para matrizes muito grandes, isto pode acarretar erros de truncamentoque comprometem o resultado final do cálculo.
Método de Doolittle: O cálculo dos termos são reagrupados, de formaque resultados parciais não precisem ser armazenados temporariamente.
Em cada passo k da eliminação, os elementos são calculados por:
nkiu
umam
nkkjumau
m
kk
k
ppkipik
ik
k
ppjkpkjkj
kk
,,1,
,,1,,
1
1
1
1
1
K
K
+=
−
=
+=−=
=
∑
∑−
=
−
=
MÉTODO DE CHOLESKI
Matriz simétrica, positiva-definida
Escolher L e U de forma que TLU =
nkim
mmam
mam
mumu
kk
k
pkpipik
ik
k
pkpkkkk
kppkkkkk
,,1,
e
1
1
2/11
1
2
K+=
−
=
−=
==
∑
∑−
=
−
=
MATRIZES DE BANDA
Matrizes onde os elementos diferentes de zero estão localizados emuma banda centrada na diagonal principal da matriz
As matrizes obtidas em resolução de um problema de valor de contornosão geralmente de banda, daí a importância do estudo deste tipo de matriz
0
0
pq qjipijaij +>+>= ou se 0
1 :Matriz da Banda ++= qpw
A estrutura de banda não é perdida, se não forem realizadas nenhumatroca de linhas ou coluna (pivotamento parcial ou completo)
As matrizes L e U serão matrizes de banda.jipijuqjiijm
ij
ij
>+>=+>>=
ou se 0ou se 0
EXEMPLO
⇒⇒
aaaaaaa
aaaaaaam
aamuu
aaaaaaa
aaaaaaaa
aaaaa
'''''
passo 1Sem pivotamento
A estrutura de banda não é perdida
⇒⇒
aaaaaaa
aaaaaaamaaamuuuu
aaaaaaa
aaaaaa
aaaaaaa
''''''
passo 1
Com pivotamento (troca linha 1 e 3)A estrutura de banda é perdida
Os algoritmos devem ser escritos levando em conta a estrutura da matriz
Grande economia de tempo computacional
MATRIZ TRIDIAGONAL
−−−
nn
nnnab
cab
cabca
L
MLL
000
000
111
222
11
Matriz de banda com p = q = 1
Decomposição LU da matriz triagonal:
444 3444 21L
MLL
444 3444 21L
MLL
L
MLL
UL
=
−−−−−−
n
nn
n
n
nn
nnn c
cc
abcab
cabca
αα
αα
ββ
β
00000
0000
100010
0010001
000
000
11
22
11
1
2
111
222
11
nkcaba kkkkk
kk ,,3,2;,, 1
111 K=−=== −
−
βαα
βα
A solução do sistema é feita através de uma resolução de sistemas triangulares
1,2,,1,1;,
,,3,2;,1
111
K
K
−−=−
==
=−==+
−
nnixcgxgx
nigfgfg
i
iiii
n
nn
iiii
αα
β
ANÁLISE DE ERRO DA DECOMPOSIÇÃO LU
Considere o sistema bAx =
Asolução do sistema sempre apresenta algum erro devido a erros de truncamento que ocorrem durante o processo
Denominar solução obtida como
Definir vetor resíduo como
x
R xAb −=
xx0R =⇒= Solução calculada é a solução exata
Espera-se que quando o vetor resíduo seja próximo a zero, a solução calculada seja próxima da solução exata
Isto nem sempre é verdade !
=
= 1440.0
8642.0 e 1441.02161.08648.02969.1 bAConsidere o exemplo
−= 0000.20000.2xSolução exata:
Solução obtida:
−=
−
−
=−=
⇒
−=
−
−
8
8
1010
4870.09911.0
1441.02161.08648.02969.1
1440.08642.0
4870.09911.0
xAbR
x
Apesar do vetor resíduo ser muito pequeno, a solução obtidanão é muito distante da solução exata
Este problema pode ser explicado analisando-se o processode eliminação gaussiana
Processo de eliminação gaussiana
4870.0
101440000154.01440.08642.02969.12161.01440.0
101440999923.01441.08648.02969.12161.01441.0
)2(22
)2(2
2
81
11
212
)2(2
812
11
2122
)2(22
−==⇒
≈−=×−=−=
≈−=×−=−=
−
−
abx
baabb
aaaaa
Uma pequena variação no elemento 0.1441 causa uma grande variação no elemento e consequentemente em )2(
22a 2x
Para uma análise da precisão da eliminação gaussianda,é necessário usar o conceito de norma de vetores e matrizes
NORMA DE VETOR E MATRIZ
Escalar não negativo que em algum sentido mede a magnitude de um vetor ou matriz
Norma p de um vetor
( ) ∞<≤+++= pxxxpp
npp
p 1,/1
21 Lx
Norma Euclideana: p=2
Norma do máximo: p=infinito
( ) 2/1222
212 nxxx +++= Lx
inix
≤≤∞=
1maxx
Propriedades de uma Norma
yxyxxx
0xx0xx
+≤+=
==≠>escalar ,
se ,0 e se ,0ααα
xAx
A0x≠
= maxNorma de uma Matriz
Para Norma do máximo, pode-se mostrar que
Relação entre a norma de um vetor e de uma matriz:
∑=
≤≤∞=
n
jijni
a11
maxA
xAAx ≤
ANÁLISE DE PERTURBAÇÃO
Analisar o efeito de pequenas perturbações na matriz A e vetor b na solução x
( )
AA
AAxx
xxxAAx
xxAAxxxAxAbxxAA
bAxbAxbbxxAbAxbAx
A
11
11
1
δδ
δδδδ
δδδδδδδδ
δδδδδδ
43421)(
1 )(0)()(
)()(
K
−−
−
−−
−
≤+
⇒+≤
+−=⇒=++⇒=++
≤⇒=⇒+=+=⇒=
bb
Axx
xAbAxbδδ
)( Como K≤⇒≤⇒=
Condicionamento da matriz
Se o condicionamento da matriz for alto, pequenas perturbaçõesna matriz A e no vetor b provacam grandes perturbações na solução
A Matriz é dita mal-condicionada e a solução do problema torna-se imprecisa
Para determinar o condionamento de uma matriz é necessário calculara norma da matriz inversa, que normalmente não é conhecida
No exemplo anterior:
dacondiciona-mal Matriz 103.3)(1671.2)8648.02969.1(
10513.110)2161.02969.1(2969.12161.08648.01441.010
8
881
81
→×≈⇒=+=
×=×+=⇒
−−×=
−
−
AAA
A
K
MÉTODOS ITERATIVOS
Fornece uma sequência de soluções aproximadas que convergemquando o número de passos tende a infinito
xx
xxxx
=
⇒⇒⇒⇒
∞→
)(
)()2()1()0(
lim k
k
kL
Chute inicial
Usado para matrizes esparsas e grandes Menor necessidade de memória de armazenamentoEliminação Gaussiana “enche” a matrizProblemas de convergência
MÉTODO DE JACOBI
O sistema de equações pode ser escrito como
nia
bxa
xbxaxa
nibxa
ii
i
n
ijj
jij
i
n
ijj
ijijiii
i
n
jjij
,,2,1 para,
,,2,1 para,
1
1
1
K
K
=
+−
=⇒=+
==
∑∑
∑
≠=
≠=
=
No Método de Jacobi, a sequência de aproximações é obtida por:
nia
bxa
xii
i
n
ijj
kjij
ki ,,2,1 para,
1
)(
)1( K=
+−
=
∑≠=
+
MÉTODO DE GAUSS-SEIDEL
No método de Jacobi, os novos valores de x só são usados no próximo passo
No método de Gauss-Seidel, os novos valores de x são usados a medida que eles são obtidos
nia
bxaxaxbxaxaxa
nibxa
ii
i
n
ijjij
i
jjij
ii
n
ijjijiii
i
jjij
i
n
jjij
,,2,1 para,
,,2,1 para,
1
1
1
1
1
1
1
K
K
=
+−−
=⇒=++
==
∑∑∑∑
∑
+=
−
=
+=
−
=
=
Para j<1, os novos valores de xj já foram calculados
No Método de Gauss-Seidel, a sequência de aproximações é obtida por:
nia
bxaxax
ii
i
n
ij
kjij
i
j
kjij
ki ,,2,1 para,1
)(1
1
)1(
)1( K=
+−−
=∑∑
+=
−
=
+
+
=
−−−−−−
−−=
1021
;411014011041
0114bAEXEMPLO: Resolver Ax = b
=
0000
:inicial Chute )0(x
MÉTODO DE JACOBI
L==+×+×−−×−−
=
========
)2(2
)2(1
)1(4
)1(3
)1(2
)1(1
;375.04
125.0)0.0(0.0)1(5.0)1(
25.041;0.0
40;5.0
42;25.0
41
xx
xxxx
k X1(k) X2
(k) X3(k) X4
(k)
0 0.0 0.0 0.0 0.01 0.25 0.5 0.0 0.252 0.375 0.625 0.125 0.3753 0.4375 0.6875 0.1875 0.4375
8 0.49805 0.74793 0.24793 0.49805
MÉTODO DE GAUSS-SEIDEL
40625.04
10625.0)1(5625.0)1(;0625.04
025.0)1(
;5625.04
225.0)1(;25.041
)1(4
)1(3
)1(2
)1(1
=+×−−×−−
==+×−−
=
=+×−−
===
xx
xx
k X1(k) X2
(k) X3(k) X4
(k)
0 0.0 0.0 0.0 0.01 0.25 0.5625 0.0625 0.406252 0.40625 0.70312 0.20312 0.476563 0.47656 0.73828 0.23828 0.49854
5 0.49854 0.74927 0.24927 0.49963
De um modo geral, os dois métodos podem ser escritos como
Os diferentes métodos possuem diferentes formas para matriz B e o vetor c.
cxBx +=+ )()1( kk
Uma matriz A pode ser decomposta na soma de três matrizes:
Diagonal + Triangular Superior + Triangular Inferior
)( UILDA ++=
O Método de Jacobi pode ser escrito como:
( ) bDxULx 1)()1(1
)(
)1( ,,2,1 para, −+≠=
+ ++−=⇒=
+−
=
∑kk
ii
i
n
ijj
kjij
ki ni
a
bxa
x K
( )ULB +−=J
O Método de Gauss-Seidel pode ser escrito como:
bDUxLxx 1)()1()1(
1
)(1
1
)1(
)1( ,,2,1 para,
−++
+=
−
=
+
+
+−−=
⇒=
+−−
=∑∑
kkkii
i
n
ij
kjij
i
j
kjij
ki ni
a
bxaxax K
( ) ULIB 1−+−=GS
ANÁLISE DE CONVERGÊNCIA
cxBx +=+ )()1( kk
Se x é solução do sistema Ax = b : cxBx +=
O erro de cada aproximação x(k) é obtido pela subtração das equações
)()()( )0(1)1(2)()1( xxBxxBxxBxx −==−=−=− +−+ kkkk L
Vamos supor que B tenha n autovetores linearmente independentes. Essesn vetores formam uma base do espaço vetorial. Qualquer vetor podeser escrito como uma combinação linear dos autovetores.
n
n
uuu ,,, :sAutovetore,,, :sAutovalore
21
21
L
L λλλ
nknn
kkk
nnn
nn
nn
uuuxx
uuuxx
BuBuBuxxBxx
uuuxx
1
1
1
1
λαλαλα
λαλαλα
ααα
ααα
+++=−
+++=−⇒
⇒+++=−=−
+++=−
L
M
L
L
L
22211)(
22211)1(
221)0()1(
221)0(
)(
1)(max)(1
<=≤≤
BB iniλρRaio Espectral de B:
O processo iterativo converge somente se somente se 1B <)(ρ
( ))(log10 Bρ−=A taxa de convergência é dada por R
Os autovalores de B não são conhecidos e esta condição não é facilmenteaplicada. Uma condição suficiente que pode ser aplicada é quepara o processo iterativo convergir: 1<B
MÉTODO DE JACOBI
∑≠=
≤≤=
n
ijj ii
ij
niJ a
a
11maxB( )ULB +−=J 0, =≠=⇒ ii
ii
ijij bji
aa
b
Converge Processo1 →<JBSe B for diagonal-dominante
MÉTODO DE GAUSS-SEIDEL
xByxy
Bx GS
n
ijj
GS == ∑≠= ∞
∞
=,max
10( ) ULIB 1−+−=GS
dominante diagonalfor se converge Processo1
max
, onde,
1
1
11
1
1
11
AB
xyy
y
→−
≤
==+≤=
+==⇒=
≤≤∞
−
=+=∞∞∞
+=
−
==∞
∑∑
∑∑∑
i
i
niGS
i
j ii
iji
n
ij ii
ijikkk
n
ijjkj
i
jjkj
n
jjkjkk
sr
a
as
a
arrsy
xbybxbyy
MÉTODO SOR (SUCCESSIVE OVERRELAXATION)
Modificação do Método de Gauss-Seidel para melhorar a taxa de convergência
ii
i
n
ij
kjij
i
j
kjij
ki
ki
ki
ki
ii
kiii
ii
ik
iii
n
ij
kjij
i
j
kjij
ii
i
n
ij
kjij
i
j
kjij
ki
a
bxaxarrxx
axa
a
bxaxaxa
a
bxaxax
+−−
=+=
+
+−−−
=
+−−
=
∑∑
∑∑∑∑
=
−
=
+
+
+=
−
=
+
+=
−
=
+
+
)(1
1
)1(
)()()()1(
)()(
1
)(1
1
)1(
1
)(1
1
)1(
)1(
onde,
)()()1( SOR ki
ki
ki rxx ω+=⇒ + ω: Parâmetro de Relaxação
[ ]20
)1()( 1
<<−−+= −
ωωωωω UILIB
