aula12 sistemas

Prévia do material em texto

Ca´lculo Nume´rico
Resoluc¸a˜o de Sistemas de Equac¸o˜es Lineares
Heder S. Bernardino
Heder S. Bernardino Ca´lculo Nume´rico
Suma´rio
1 Aula Anterior
2 Me´todos Iterativos
3 Me´todo de Jacobi
4 Me´todo de Gauss-Seidel
5 Convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel
6 Me´todos de Relaxac¸a˜o
7 Revisa˜o
Heder S. Bernardino Ca´lculo Nume´rico
Aula Anterior
Aula Anterior
Heder S. Bernardino Ca´lculo Nume´rico
Aula Anterior
Aula Anterior
◮ Decomposic¸a˜o LU com Pivotamento Parcial
◮ Vetor com as permutac¸o˜es das linhas
◮ Decomposic¸a˜o de Cholesky
◮ Sistemas em que a matriz de coeficientes e´ sime´trica e positiva definida
◮ Requer menos operac¸o˜es aritme´ticas do que a decomposic¸a˜o LU
◮ Decomposic¸a˜o LDLT
◮ Na˜o necessita de ca´lculos de raiz quadrada
◮ Requer a resoluc¸a˜o de um sistema linear com uma matriz de
coeficientes diagonal, ale´m de dois sistemas triangulares
Heder S. Bernardino Ca´lculo Nume´rico
Me´todos Iterativos
Me´todos Iterativos
Heder S. Bernardino Ca´lculo Nume´rico
Me´todos Iterativos
Me´todos Iterativos
◮ O sistema de equac¸o˜es lineares Ax = b pode ser resolvido por um
processo que gera, a partir de um vetor inicial x(0), uma sequeˆncia de
vetores x(1),x(2),x(3), . . . que deve convergir para a soluc¸a˜o
◮ Os chamados me´todos iterativos estaciona´rios sera˜o estudados aqui
◮ Um me´todo iterativo escrito na forma
x(k) = Bx(k−1) + c,
e´ dito estaciona´rio quando a matriz B for fixa durante o processo
iterativo
Heder S. Bernardino Ca´lculo Nume´rico
Me´todos Iterativos
Me´todos Iterativos
◮ Sera˜o vistos aqui
◮ Me´todo de Jacobi
◮ Me´todo de Gauss-Seidel
◮ Me´todos de Relaxac¸a˜o
Heder S. Bernardino Ca´lculo Nume´rico
Me´todos Iterativos
Normas de Vetores e Matrizes
◮ Para discutir o erro envolvido nas aproximac¸o˜es e´ preciso associar a
cada vetor e matriz um valor escalar na˜o negativo que, de alguma
forma, mede sua magnitude
◮ As normas para vetores mais comuns sa˜o:
◮ Norma euclideana (ou norma L2)
‖x‖2 =
(
x21 + x
2
2 + · · ·+ x
2
n
)1/2
◮ Norma infinito (ou norma do ma´ximo)
‖x‖∞ = max1≤i≤n
|xi|
◮ Normas vetoriais devem satisfazer a`s seguintes propriedades:
1. ‖x‖ > 0 se x 6= 0, ‖x‖ = 0 se x = 0
2. ‖αx‖ = α ‖x‖, onde α e´ um escalar
3. ‖x+ y‖ ≤ ‖x‖+ ‖y‖
Heder S. Bernardino Ca´lculo Nume´rico
Me´todos Iterativos
Normas de Vetores e Matrizes
◮ A norma que segue sera´ utilizada aqui
‖A‖∞ = max1≤i≤n
n∑
j=1
|aij |
◮ Normas de matrizes tem que satisfazer a`s seguintes propriedades
1. ‖A‖ > 0 se A 6= 0, ‖A‖ = 0 se A = 0
2. ‖αA‖ = α ‖A‖, onde α e´ um escalar
3. ‖A+B‖ ≤ ‖A‖+ ‖B‖
4. ‖AB‖ ≤ ‖A‖ ‖B‖
5. ‖Ax‖ ≤ ‖A‖ ‖x‖
Heder S. Bernardino Ca´lculo Nume´rico
Me´todos Iterativos
Exemplo
◮ Exemplo 1
Calcule ‖x‖∞ para
x =


−1
10
3
4
−20


◮ Soluc¸a˜o: ‖x‖∞ = 20
Heder S. Bernardino Ca´lculo Nume´rico
Me´todos Iterativos
Exemplo
◮ Exemplo 2
Calcule ‖A‖∞ para
A =
[
4 6
−3 4
]
◮ Soluc¸a˜o: ‖A‖∞ = 10
Heder S. Bernardino Ca´lculo Nume´rico
Me´todos Iterativos
Crite´rio de Parada
◮ A distaˆncia entre dois vetores x e y pode ser calculada como
‖x− y‖2 ou ‖x− y‖∞
◮ A norma infinito sera´ adotada aqui
◮ Sejam x(k) e x(k−1) duas aproximac¸o˜es para o vetor soluc¸a˜o x∗ de
um sistema de equac¸o˜es lineares, enta˜o o seguinte crite´rio de parada
pode ser utilizado
∥∥x(k) − x(k−1)∥∥
∞∥∥x(k)∥∥
∞
=
max
1≤i≤n
∣∣∣x(k)i − x(k−1)i
∣∣∣
max
1≤i≤n
∣∣∣x(k)i
∣∣∣ < ǫ
onde ǫ e´ a precisa˜o desejada
Heder S. Bernardino Ca´lculo Nume´rico
Me´todos Iterativos
Crite´rio de Parada
◮ Na pra´tica tambe´m adotamos um nu´mero ma´ximo de iterac¸o˜es para
evitar que o programa execute indefinidamente, caso o me´todo na˜o
convirja para um determinado problema
k < kmax
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Jacobi
Me´todo de Jacobi
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Jacobi
Me´todo de Jacobi
◮ Dado o sistema de equac¸o˜es lineares

a11x1 + a12x2 + · · ·+ a1nxn = b1
a21x1 + a22x2 + · · ·+ a2nxn = b2
...
an1x1 + an2x2 + · · ·+ annxn = bn
◮ Assumindo que os elementos da diagonal principal de A sa˜o
diferentes de zero, enta˜o o sistema pode ser re-escrito isolando-se as
varia´veis, de modo que

x1 =
b1−(a12x2+a13x3+···+a1nxn)
a11
x2 =
b2−(a21x1+a23x3+···+a2nxn)
a22
...
xn =
bn−(an1x1+an2x2+···+an,n−1xn−1)
ann
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Jacobi
Me´todo de Jacobi
◮ A partir de uma aproximac¸a˜o inicial
x(0) =


x
(0)
1
x
(0)
2
...
x
(0)
n


◮ As aproximac¸o˜es x(k) podem enta˜o ser calculadas fazendo

x
(k)
1 =
b1−
(
a12x
(k−1)
2 +a13x
(k−1)
3 +···+a1nx
(k−1)
n
)
a11
x
(k)
2 =
b2−
(
a21x
(k−1)
1 +a23x
(k−1)
3 +···+a2nx
(k−1)
n
)
a22
...
x
(k)
n =
bn−
(
an1x
(k−1)
1 +an2x
(k−1)
2 +···+an,n−1x
(k−1)
n−1
)
ann
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Jacobi
Me´todo de Jacobi
◮ Assim, para um sistema com n equac¸o˜es e n inco´gnitas, tem-se que
x
(k)
i =
bi −
i−1∑
j=1
aijx
(k−1)
j −
n∑
j=i+1
aijx
(k−1)
j
aii
para i = 1, 2, . . . , n
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Jacobi
Me´todo de Jacobi
Entrada: A, b, x(0), kmax, ǫ
1 inicio
2 k ←− 1;
3 enquanto crite´rio de parada na˜o e´ satisfeito fac¸a
4 para i = 1, . . . , n hacer
5 x
(k)
i ←−
bi −
i−1∑
j=1
aijx
(k−1)
j −
n∑
j=i+1
aijx
(k−1)
j
aii
6 k ←− k + 1;
7 retorna x(k)
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Jacobi
Exemplo
◮ Exemplo 3
Resolva o seguinte sistema linear utilizando o Me´todo de Jacobi.
Adote x(0) = 0 como valor inicial e
‖x(k)−x(k−1)‖
∞∥∥∥x(k)∞
∥∥∥
≤ ǫ = 0,01 como
crite´rio de parada.


4x1 + 0,24x2 − 0,08x3 = 8
0,09x1 + 3x2 − 0,15x3 = 9
0,04x1 − 0,08x2 + 4x3 = 20
◮ Soluc¸a˜o:
k 0 1 2 3
x1 0 2 1,92 1,91
x2 0 3 3,19 3,1944
x3 0 5 5,04 5,0446
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Jacobi
Me´todo de Jacobi – Exemplo em Python
1 from pylab import *
2
3 def jacobi(A, b, x0, epsilon, kmax):
4 n = A.shape[ 0 ]
5 x = zeros( n )
6 x[:] = x0[:]
7 for k in range(kmax):
8 print "Iteracao " + str( k )
9 print x
10 x0[:] = x[:]
11 for i in range(n):
12 soma = 0
13 for j in range(i):
14 soma += A[i,j] * x0[j]
15 for j in range(i+1, n):
16 soma += A[i,j] * x0[j]
17 x[i] = ( b[i] - soma ) / A[ i, i ]
18 if max( abs( x - x0 ) ) / max( abs( x ) ) < epsilon:
19 break
20 return np.matrix(x).transpose()
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Jacobi
Me´todo de Jacobi – Exemplo em Python – cont.
1 # inicializa a matriz A
2 A = np.matrix([[ 4.0, 0.24, -0.08 ],
3 [ 0.09, 3.0, -0.15 ],
4 [ 0.04, -0.08, 4.0 ]])
5
6 # inicializa o vetor b
7 b = np.matrix( [ [8.0], [9.0], [20.0] ] )
8
9 # aproximacao inicial
10 x0 = zeros( A.shape[ 0 ] )
11
12 # resolve o sistema e exibe o resultado
13 x = jacobi(A, b, x0, 0.01, 10)
14 print( x )
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Gauss-Seidel
Me´todo de Gauss-Seidel
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Gauss-Seidel
Me´todo de Gauss-Seidel
◮ Observa-se que o Me´todo de Jacobi utiliza apenas os valores obtidos
no passo anterior x(k−1) para calcular x(k)
◮ Entretanto, e´ poss´ıvel aproveitar os ca´lculos ja´ realizados para x(k) na
atualizac¸a˜o das componentes seguintes
◮ x
(k)
1 e´ utilizado para calcular x
(k)
2
◮ x
(k)
1 e x
(k)
2 sa˜o utilizados para calcularx
(k)
3
◮
...
◮ Esse procedimento e´ chamado de Me´todo de Gauss-Seidel e pode ser
visto como uma modificac¸a˜o do Me´todo de Jacobi
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Gauss-Seidel
Me´todo de Gauss-Seidel
◮ Assim, no Me´todo de Gauss-Seidel tem-se que
x
(k)
i =
bi −
i−1∑
j=1
aijx
(k)
j −
n∑
j=i+1
aijx
(k−1)
j
aii
para i = 1, 2, . . . , n
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Gauss-Seidel
Me´todo de Gauss-Seidel
Entrada: A, b, x(0), kmax, ǫ
1 inicio
2 k ←− 1;
3 enquanto crite´rio de parada na˜o e´ satisfeito fac¸a
4 para i = 1, . . . , n hacer
5 x
(k)
i ←−
bi −
i−1∑
j=1
aijx
(k)
j −
n∑
j=i+1
aijx
(k−1)
j
aii
6 k ←− k + 1;
7 retorna x(k)
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Gauss-Seidel
Exemplo
◮ Exemplo 4
Execute 3 passos do Me´todo de Gauss-Seidel no sistema linear que
segue com x(0) = 0.


4x1 + 0,24x2 − 0,08x3 = 8
0,09x1 + 3x2 − 0,15x3 = 9
0,04x1 − 0,08x2 + 4x3 = 20
◮ Soluc¸a˜o:
k 0 1 2 3
x1 0 2 1,924376 1,909240
x2 0 2,94 3,194209 3,194955
x3 0 5,0388 5,044640 5,044807
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Gauss-Seidel
Me´todo de Gauss-Seidel – Exemplo em Python
1 from pylab import *
2
3 def gaussSeidel(A, b, x0, epsilon, kmax):
4 n = A.shape[ 0 ]
5 x = zeros( n )
6 x[:] = x0[:]
7 for k in range(kmax):
8 print "Iteracao " + str( k )
9 print x
10 x0[:] = x[:]
11 for i in range(n):
12 soma = 0
13 for j in range(i):
14 soma += A[i,j] * x[j] # <- alteracao
15 for j in range(i+1, n):
16 soma += A[i,j] * x0[j]
17 x[i] = ( b[i] - soma ) / A[ i, i ]
18 if max( abs( x - x0 ) ) / max( abs( x ) ) < epsilon:
19 break
20 return np.matrix(x).transpose()
Heder S. Bernardino Ca´lculo Nume´rico
Me´todo de Gauss-Seidel
Me´todo de Gauss-Seidel – Exemplo em Python – cont.
1 # inicializa a matriz A
2 A = np.matrix([[ 4.0, 0.24, -0.08 ],
3 [ 0.09, 3.0, -0.15 ],
4 [ 0.04, -0.08, 4.0 ]])
5
6 # inicializa o vetor b
7 b = np.matrix( [ [8.0], [9.0], [20.0] ] )
8
9 # aproximacao inicial
10 x0 = zeros( A.shape[ 0 ] )
11
12 # resolve o sistema e exibe o resultado
13 x = gaussSeidel(A, b, x0, 0.01, 10)
14 print( x )
Heder S. Bernardino Ca´lculo Nume´rico
Convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel
Convergeˆncia dos Me´todos de Jacobi e
Gauss-Seidel
Heder S. Bernardino Ca´lculo Nume´rico
Convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel
Convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel
◮ Para estudar a convergeˆncia dos me´todos, primeiramente ambos sera˜o
escritos na forma
x(k) = Bx(k−1) + c
◮ Nota-se que a matriz A pode ser representada como
A = L︸︷︷︸
triangular inferior
+ D︸︷︷︸
diagonal
+ U︸︷︷︸
triangular superior
◮ Por exemplo, para uma matriz 3× 3 tem-se que
a11 a12 a13a21 a22 a23
a31 a32 a33

 =

 0 0 0a21 0 0
a31 a32 0

+

a11 0 00 a22 0
0 0 a33

+

0 a12 a130 0 a23
0 0 0


Heder S. Bernardino Ca´lculo Nume´rico
Convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel
Convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel
◮ Assim, para o Me´todo de Jacobi
Ax = b
(L+D+U)x = b
Dx = − (L+U)x+ b
◮ e enta˜o
Dx(k) = − (L+U)x(k−1) + b
x(k) = −D−1 (L+U)︸ ︷︷ ︸
BJ
x(k−1) +D−1b︸ ︷︷ ︸
cJ
Heder S. Bernardino Ca´lculo Nume´rico
Convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel
Convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel
◮ Para o Me´todo de Gauss-Seidel
Ax = b
(L+D+U)x = b
(L+D)x = −Ux+ b
◮ e enta˜o
(L+D)x(k) = −Ux(k−1) + b
x(k) = − (L+D)−1U︸ ︷︷ ︸
BGS
x(k−1) + (L+D)−1 b︸ ︷︷ ︸
cGS
Heder S. Bernardino Ca´lculo Nume´rico
Convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel
Convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel
◮ Portanto, ambos me´todos podem ser expressos como
x(k) = Bx(k−1) + c
◮ com matrizes de iterac¸a˜o B dadas por
BJ = −D
−1 (L+U)
BGS = − (L+D)
−1
U
Heder S. Bernardino Ca´lculo Nume´rico
Convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel
Convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel
◮ A convergeˆncia dos me´todos de Jacobi ou Gauss-Seidel depende dos
autovalores da matriz de iterac¸a˜o B
◮ Definic¸a˜o (Autovalor):
λi, i = 1, . . . , n, sa˜o autovalores de uma matriz B se Bu = λiu, para
algum vetor u 6= 0.
◮ Teorema:
A condic¸a˜o necessa´ria e suficiente para que um me´todo iterativo
descrito por x(k) = Bx(k−1) + c convirja usando um vetor x(0)
qualquer e´
ρ(B) = max
1≤i≤n
|λi(B)| < 1
◮ Na pra´tica, encontrar os autovalores de uma matriz e´ ta˜o custoso
computacionalmente quanto resolver o sistema linear
◮ Logo, o teorema acima e´ dificilmente utilizado
Heder S. Bernardino Ca´lculo Nume´rico
Convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel
Convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel
◮ Sendo x∗ a soluc¸a˜o do sistema linear, sabe-se que{
x(k) = Bx(k−1) + c
x∗ = Bx∗ + c
◮ Subtraindo as equac¸o˜es obte´m-se
x(k) − x∗ = Bx(k−1) + c−Bx∗ − c
= B
(
x(k−1) − x∗
)
◮ Analogamente,
x(k−1) − x∗ = B
(
x(k−2) − x∗
)
...
x(1) − x∗ = B
(
x(0) − x∗
)
Heder S. Bernardino Ca´lculo Nume´rico
Convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel
Convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel
◮ Assim,
x(k) − x∗ = B
(
x(k−1) − x∗
)
= B2
(
x(k−2) − x∗
)
...
= Bk
(
x(0) − x∗
)
◮ Logo
x(k) − x∗ = Bk
(
x(0) − x∗
)
◮ Aplicando norma infinito∥∥∥x(k) − x∗∥∥∥
∞
=
∥∥∥Bk (x(0) − x∗)∥∥∥
∞
Heder S. Bernardino Ca´lculo Nume´rico
Convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel
Convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel
◮ Assim, ∥∥∥x(k) − x∗∥∥∥
∞
=
∥∥∥Bk (x(0) − x∗)∥∥∥
∞
≤
∥∥∥Bk∥∥∥
∞
∥∥∥x(0) − x∗∥∥∥
∞
≤ ‖B‖k∞
∥∥∥x(0) − x∗∥∥∥
∞
◮ Logo, ha´ convergeˆncia quando
‖B‖∞ < 1
Heder S. Bernardino Ca´lculo Nume´rico
Convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel
Convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel
◮ Para o Me´todo de Jacobi, a matriz de iterac¸a˜o e´ da forma
BJ = −D
−1 (L+U)
◮ Como
D =


a11 0 . . . 0
0 a22 . . . 0
0 0
. . .
...
0 0 . . . ann

⇒ D−1 =


1/a11 0 . . . 0
0 1/a22 . . . 0
...
...
. . .
...
0 0 . . . 1/ann


◮ Portanto,
BJ = −


0 a12
a11
. . . a1n
a11
a21
a22
0 . . . a2n
a22
...
...
. . .
...
an1
ann
an2
ann
. . . 0


Heder S. Bernardino Ca´lculo Nume´rico
Convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel
Convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel
◮ Portanto,
BJ = −


0 a12
a11
. . . a1n
a11
a21
a22
0 . . . a2n
a22
...
...
. . .
...
an1
ann
an2
ann
. . . 0


◮ Ou seja, bij = −
aij
aii
, quando i 6= j, e bij = 0, caso contra´rio
◮ Como ha´ garantia de convergeˆncia quando ‖B‖∞ < 1, enta˜o
‖B‖∞ = max1≤i≤n
n∑
j=1
|bij | = max
1≤i≤n
n∑
j=1,j 6=i
∣∣∣∣aijaii
∣∣∣∣ < 1
Heder S. Bernardino Ca´lculo Nume´rico
Convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel
Convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel
◮ Teorema (Crite´rio das Linhas):
Seja Ax = b e seja αi =
n∑
j=1,j 6=i
|aij |
|aii|
, i = 1, . . . , n.
Se α = maxαi < 1, enta˜o o Me´todo de Jacobi converge
independentemente da aproximac¸a˜o inicial x(0).
◮ Definic¸a˜o (Matriz Estritamente Diagonalmente Dominante):
Uma Matriz A e´ estritamente diagonalmente dominante se
n∑
j=1,j 6=i
|aij | < |aii|, i = 1, . . . , n
◮ Nota-se que o Crite´rio das Linhas e´ sempre satisfeito para matrizes
estritamente diagonalmente dominantes
Heder S. Bernardino Ca´lculo Nume´rico
Convergeˆncia dos Me´todos deJacobi e Gauss-Seidel
Exemplo
◮ Exemplo 5
Verifique se ha´ garantia de convergeˆncia para o Me´todo de Jacobi
quando aplicado a um sistema linear com a matriz de coeficientes
como segue.
A =

1 3 15 2 2
0 6 8


◮ Soluc¸a˜o:
◮ Na˜o ha´ garantia de convergeˆncia, pois α1 = 4 > 1
◮ Entretanto, trocando as linhas 1 e 2, enta˜o verifica-se que o me´todo
convergira´, pois
α1 = 4/5 < 1, α2 = 2/3 < 1, α3 = 6/8 < 1
Heder S. Bernardino Ca´lculo Nume´rico
Convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel
Convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel
◮ Para que haja garantia de convergeˆncia do Me´todo de Gauss-Seidel,
um dos crite´rios seguintes devem ser satisfeitos:
◮ Crite´rio das Linhas
max
1≤i≤n
n∑
j=1,j 6=i
|aij |
|aii|
< 1
◮ Crite´rio de Sassenfeld
max
1≤i≤n
βi < 1
onde
βi =
i−1∑
j=1
|aij |βj +
n∑
j=i+1
|aij |
|aii|
< 1
Heder S. Bernardino Ca´lculo Nume´rico
Convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel
Convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel
◮ Observac¸o˜es
◮ Mais informac¸o˜es sobre a convergeˆncia do Me´todo de Gauss-Seidel
podem ser encontradas no livro Ca´lculo Nume´rico da Neide Franco,
Pearson, 2006
◮ O Crite´rio de Sassenfeld pode ser satisfeito e o Crite´rio das Linhas na˜o
◮ Quanto menor o valor de ‖B‖∞, mais ra´pida e´ a convergeˆncia do
me´todo
◮ Permutac¸o˜es em linhas ou colunas podem reduzir ‖B‖∞
◮ A convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel na˜o depende do
vetor inicial x(0)
Heder S. Bernardino Ca´lculo Nume´rico
Convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel
Exemplo
◮ Exemplo 6
Verifique se ha´ garantia de convergeˆncia para os Me´todos de Jacobi e
Gauss-Seidel quando aplicados a um sistema linear com a matriz de
coeficientes como segue.
A =

5 1 13 4 1
3 3 6


◮ Soluc¸a˜o:
◮ Na˜o ha´ garantia de convergeˆncia pelo Crite´rio das Linhas:
α1 = 2/5 < 1
α2 = 1
α3 = 1
Heder S. Bernardino Ca´lculo Nume´rico
Convergeˆncia dos Me´todos de Jacobi e Gauss-Seidel
Exemplo
◮ Exemplo 6
Verifique se ha´ garantia de convergeˆncia para os Me´todos de Jacobi e
Gauss-Seidel quando aplicados a um sistema linear com a matriz de
coeficientes como segue.
A =

5 1 13 4 1
3 3 6


◮ Soluc¸a˜o:
◮ Todavia, o Me´todo de Gauss-Seidel convergira´, pois o Crite´rio de
Sassenfeld e´ satisfeito, ja´ que
β1 = 0,4 < 1
β2 = 0,55 < 1
β3 = 0,475 < 1
Heder S. Bernardino Ca´lculo Nume´rico
Me´todos de Relaxac¸a˜o
Me´todos de Relaxac¸a˜o
Heder S. Bernardino Ca´lculo Nume´rico
Me´todos de Relaxac¸a˜o
Me´todos de Relaxac¸a˜o
◮ Um me´todo pode ser definido de modo a gerar uma aproximac¸a˜o x(k)
como uma me´dia ponderada entre o valor de x(k−1) e o valor que e´
obtido pelo Me´todo de Gauss-Seidel
◮ Assim,
x
(k)
R = (1− ω)x
(k−1)
R + ωx
(k)
GS
onde
◮ x
(k)
R e´ a aproximac¸a˜o obtida pelo Me´todo de Relaxac¸a˜o no passo k
◮ x
(k)
GS e´ a aproximac¸a˜o obtida pelo Me´todo de Gauss-Seidel no passo k
Heder S. Bernardino Ca´lculo Nume´rico
Me´todos de Relaxac¸a˜o
Me´todos de Relaxac¸a˜o
◮ Quando ω = 1 enta˜o tem-se o Me´todo de Gauss-Seidel
◮ O me´todo converge apenas quando 0 < ω < 2
◮ Se 0 < ω < 1, o procedimento e´ chamado de Sub-relaxac¸a˜o e pode
servir para obter convergeˆncia em alguns sistemas que na˜o sa˜o
convergentes com o Me´todo de Gauss-Seidel
◮ Se 1 < ω < 2, o procedimento e´ conhecido como Sobre-relaxac¸a˜o e
serve para acelerar a convergeˆncia
Heder S. Bernardino Ca´lculo Nume´rico
Revisa˜o
Revisa˜o
Heder S. Bernardino Ca´lculo Nume´rico
Revisa˜o
Revisa˜o
◮ Me´todos Iterativos
◮ Me´todo de Jacobi
x
(k)
i =
bi −
i−1∑
j=1
aijx
(k−1)
j −
n∑
j=i+1
aijx
(k−1)
j
aii
◮ Me´todo de Gauss-Seidel
x
(k)
i =
bi −
i−1∑
j=1
aijx
(k)
j −
n∑
j=i+1
aijx
(k−1)
j
aii
◮ Convergeˆncia dos Me´todos
◮ Crite´rio das Linhas e Crite´rio de Sassenfeld
◮ Me´todos de Relaxac¸a˜o
Heder S. Bernardino Ca´lculo Nume´rico
Revisa˜o
Du´vidas?
Heder S. Bernardino Ca´lculo Nume´rico
	Aula Anterior
	Métodos Iterativos
	Método de Jacobi
	Método de Gauss-Seidel
	Convergência dos Métodos de Jacobi e Gauss-Seidel
	Métodos de Relaxação
	Revisão