Buscar

Metodos_Iterativos_1

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 9 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 9 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 9 páginas

Prévia do material em texto

Sistemas de Equac¸o˜es Lineares
Introduc¸a˜o
Me´todos Iterativos
Introduc¸a˜o
I Os me´todos diretos na˜o sa˜o os mais indicados para resolver
sistemas esparsos e os sistemas de grande porte.
I O refinamento do algoritmo de Gauss e´ uma forma de me´todo
iterativo.
I Os algoritmos iterativos partem de uma soluc¸a˜o inicial e
sistematicamente geram uma sequeˆncia de iterandos.
I Dada uma aproximac¸a˜o inicial x0 da soluc¸a˜o de Ax = b, o
processo iterativo pode ser descrito como:
xk+1 = G (xk), k = 1, 2, . . . ,
I Aqui vamos estudar os me´todos de Jacobi e de Gauss-Seidel.
4 / 61
Sistemas de Equac¸o˜es Lineares
Me´todo de Jacobi
Me´todo de Jacobi
Seja Ax = b um sistema de equac¸o˜es lineares quadrado, expresso
na forma: 

a11 a12 . . . a1n
a21 a22 . . . a2n
...
...
...
...
an1 an2 . . . ann




x1
x2
...
xn

 =


b1
b2
...
bn

 (1)
6 / 61
Sistemas de Equac¸o˜es Lineares
Me´todo de Jacobi
Me´todo de Jacobi
Assumindo que ajj 6= 0 para j = 1, . . . , n, podemos expressar (1)
na forma:{
xj =
1
ajj
(bj − aj1x1 − aj2x2 − . . .
−aj ,(j−1)xj−1 − aj ,(j+1)xj+1 − . . .− aj ,nxn
) (2)
para j = 1, . . . , n, onde sa˜o conhecidos os valores de
x1, x2, . . . , xj−1, xj+1, . . . , xn a serem utilizados no lado direito da
expressa˜o acima.
7 / 61
Sistemas de Equac¸o˜es Lineares
Me´todo de Jacobi
Me´todo de Jacobi
O Me´todo de Jacobi consiste no processo iterativo dado por:
xk+1j =
1
ajj
(
bj − aj1x
k
1 − aj2x
k
2 − . . .
−aj ,(j−1)x
k
j−1 − aj ,(j+1)x
k
j+1 − . . .− aj ,nx
k
n
)
(3)
para j = 1, . . . , n.
8 / 61
Sistemas de Equac¸o˜es Lineares
Me´todo de Jacobi
Me´todo de Jacobi
Observac¸o˜es
I Se o sistema Ax = y e´ na˜o singular, sempre sera´ poss´ıvel
obter ajj 6= 0 se trocarmos as equac¸o˜es adequadamente.
I Em sistemas esparsos, o me´todo de Jacobi evita multiplicac¸o˜es
desnecessa´rias, simplificando a expressa˜o acima.
9 / 61
Sistemas de Equac¸o˜es Lineares
Me´todo de Jacobi
Me´todo de Jacobi
Algoritmo (x1, . . . , xn, aij , bj , lim)
1) k ← 1
2) Enquanto k < lim
Para j = 1, . . . , n
zj =
1
ajj
(bj − aj1x1 − aj2x2 − . . .
−aj ,(j−1)xj−1 − aj ,(j+1)xj+1 − . . .− aj ,nxn
)
Se teste de convergeˆncia e´ satisfeito
Sa´ıda(zj : j = 1, . . . , n)
Caso contra´rio
xj ← zj , j = 1, . . . , n
k ← k + 1
3) Sa´ıda“Algoritmo na˜o convergente”.
10 / 61
Sistemas de Equac¸o˜es Lineares
Me´todo de Jacobi
Exemplo do Me´todo de Jacobi
Vamos tomar como exemplo o sistema de equac¸o˜es lineares dado
por:

5x1 + − 3x4 − x5 = 2
−x1 + 4x2 − x5 = 3
+ 2x3 − x4 = −1
−x1 + 4x4 − 2x5 = 0
− x4 + 2x5 = −1
(4)
11 / 61
Sistemas de Equac¸o˜es Lineares
Me´todo de Jacobi
Exemplo do Me´todo de Jacobi
Primeiramente, obtemos o operador iterativo que corresponde a`s
equac¸o˜es: 

xk+11 =
1
5(2 + 3x
k
4 + x
k
5 )
xk+12 =
1
4(3 + x
k
1 + x
k
5 )
xk+13 =
1
2(−1 + x
k
4 )
xk+14 =
1
4(x
k
1 + 2x
k
5 )
xk+15 =
1
2(−1 + x
k
4 )
(5)
O processo iterativo acima ao ser aplicado na resoluc¸a˜o de (4)
produz a sequ¨eˆncia de iterandos dada na Tabela 1.
12 / 61
Sistemas de Equac¸o˜es Lineares
Me´todo de Jacobi
Exemplo do Me´todo de Jacobi
Tabela: iterandos obtidos pelo processo iterativo de Jacobi
Iterac¸a˜o 1 2 . . . 35 36
x1 1 1.20 . . . 0.0869574059 0.086957108
x2 1 1.25 . . . 0.6086962107 0.608696020
x3 1 0.00 . . . -0.6521793252 -0.652173522
x4 1 0.75 . . . -0.3043470441 -0.304347311
x5 1 0.00 . . . -0.6521733252 -0.652173522
13 / 61

Outros materiais