a3

Prévia do material em texto

Fundamentos IV
Sistemas Lineares
Clarimar Coelho
Departamento de Computac¸a˜o
August 26, 2014
Clarimar, Departamento de Computac¸a˜o Aula 1, Sistemas Lineares 1/24
Me´todos iterativos para a
soluc¸a˜o de sistema lineares
Clarimar, Departamento de Computac¸a˜o Aula 1, Sistemas Lineares 2/24
Me´todos iterativos
Um sistem Ax = b pode ser resolvido por um processo que
gera a partir de um vetor inicial x0 uma sequeˆncia de vetores
{x1, x2, x3, . . . , xk , . . .}
Que deve convergir para a soluc¸a˜o x do sistema
Esse processo e´ chamado de iterativo
Clarimar, Departamento de Computac¸a˜o Aula 1, Sistemas Lineares 3/24
Me´todo de Jacobi
Clarimar, Departamento de Computac¸a˜o Aula 1, Sistemas Lineares 4/24
Carl Gustav Jakob Jacobi/Iacobi
Potsdam, 10 de dezembro de 1804
Berlim, 18 de fevereiro de 1851
Matema´tico alema˜o que contribuiu com fundamentos para
func¸o˜es el´ıpticas, dinaˆmica, equac¸o˜es diferenciais e teoria dos
nu´meros
Clarimar, Departamento de Computac¸a˜o Aula 1, Sistemas Lineares 5/24
Me´todo de Jacobi
Resolve um sistema linear de n inco´gnitas
Seja o sistema
a11x1+ a12x2+ . . .+ a1nxn = b1
a21x1+ a22x2+ . . .+ a2nxn = b2
...
...
...
...
an1x1+ an2x2+ . . .+ annxn = bn
Clarimar, Departamento de Computac¸a˜o Aula 1, Sistemas Lineares 6/24
Parte pra´tica do me´todo
Na primeira equac¸a˜o coloca-se em evideˆncia o x1, na segunda
o x2 e na n−e´sima o xn
Clarimar, Departamento de Computac¸a˜o Aula 1, Sistemas Lineares 7/24
x1
a11x1 + a12x2 + . . .+ a1nxn = b1
x1 =
1
a11
(b1 − a12x2 − a13x3 − . . .− a1xn)
Clarimar, Departamento de Computac¸a˜o Aula 1, Sistemas Lineares 8/24
x2
a21x1 + a22x2 + . . .+ a2nxn = b2
x2 =
1
a22
(b2 − a21x1 − a23x3 − . . . − a2nxn)
Clarimar, Departamento de Computac¸a˜o Aula 1, Sistemas Lineares 9/24
xn
an1x1 + an2x2 + . . .+ annxn = bn
xn =
1
ann
(bn − an1x1 − an2x2 − . . .− ann−1xn−1)
Clarimar, Departamento de Computac¸a˜o Aula 1, Sistemas Lineares 10/24
Gerac¸a˜o de novos valores
Um valor novo e´ gerado a partir de um valor antigo
xN1 =
1
a11
(b1 − a12x
A
2 − a13x
A
3 − . . .− a1x
A
n )
xN2 =
1
a22
(b2 − a21x
A
1 − a23x
A
3 − . . .− a2nx
A
n )
...
xAn =
1
ann
(bn − an1x
A
1 − an2x
A
2 − . . . − ann−1x
A
n−1)
Clarimar, Departamento de Computac¸a˜o Aula 1, Sistemas Lineares 11/24
Exemplo 1
Seja o sistema
5x1 − 2x2 + 3x3 = 1
−3x1 + 9x2 + x3 = 2
2x1 − x2 − 7x3 = 1
Clarimar, Departamento de Computac¸a˜o Aula 1, Sistemas Lineares 12/24
Colocando em evideˆncia
xN1 =
1
5
(
−1 + 2xA2 − 3x
A
3
)
xN2 =
1
9
(
2 + 3xA1 − x
A
3
)
xN3 = −
1
7
(
3− 2xA1 + x
A
2
)
Clarimar, Departamento de Computac¸a˜o Aula 1, Sistemas Lineares 13/24
Chute inicial
xA1 = 0, x
A
2 = 0, x
A
3 = 0
Clarimar, Departamento de Computac¸a˜o Aula 1, Sistemas Lineares 14/24
Primeira iterac¸a˜o
lcm calcula o mmc em Octave
xN1 =
1
5
(−1 + 2× 0− 3× 0) = −1
5
xN2 =
1
9
(2 + 3× 0− 0) = 2
9
xN3 = −
1
7
(3− 2× 0 + 0) = −3
7
Clarimar, Departamento de Computac¸a˜o Aula 1, Sistemas Lineares 15/24
Segunda iterac¸a˜o
Consideramos os valores antigos aqueles gerados na primeira
iterac¸a˜o
xN1 =
1
5
(
−1 + 2(2
9
)− 3(−3
7
)
)
= − 46
315
xN2 =
1
9
(
2 + 3(−1
5
) + 3
7
)
= 64
315
xN3 = −
1
7
(
3− 2(−1
5
) + 2
9
)
= −163
315
Clarimar, Departamento de Computac¸a˜o Aula 1, Sistemas Lineares 16/24
Terceira iterac¸a˜o
xN1 =
1
5
(
−1 + 2( 64
315
)− 3(−163
315
)
)
= − 302
1575
xN2 =
1
9
(
2 + 3( 46
315
) + 163
315
)
= 133
405
xN3 = −
1
7
(
3− 2( 46
315
) + 64
315
)
= −131
315
Clarimar, Departamento de Computac¸a˜o Aula 1, Sistemas Lineares 17/24
Quarta iterac¸a˜o
xN1 = −
1
5
+ 2
5
× 133
405
− 3
5
(−131
315
) = 2564
14175
xN2 =
2
9
+ 3
9
× 302
1575
− 1
9
(−131
315
) = 673
2025
xN3 = −
3
7
+ 2
7
× 302
1575
− 1
7
× 133
405
= −41744
99225
Clarimar, Departamento de Computac¸a˜o Aula 1, Sistemas Lineares 18/24
Fazemos a quinta, sexta, se´tima iterac¸o˜es ...
Ate´ atingir um crite´rio de parada
Geralmente o crite´rio de parada e´ o erro relativo
A porcentagem do conjunto de valores x1, x2, x3 novos
x1, x2, x3 e o conjunto de valores x1, x2, x3 antigos
Clarimar, Departamento de Computac¸a˜o Aula 1, Sistemas Lineares 19/24
Crete´rio de parada relaxado
A tabela mostra os resultados ate´ a iterac¸a˜o 7
Observa-se que entre a sexta e se´tima iterac¸a˜o na˜o houve
alterac¸a˜o relevante
Clarimar, Departamento de Computac¸a˜o Aula 1, Sistemas Lineares 20/24
Me´todo de Gauss-Seidel
Clarimar, Departamento de Computac¸a˜o Aula 1, Sistemas Lineares 21/24
Johann Carl Friedrich Gauss
Braunschweig, 30 de Abril de 1777
Go¨ttingen, 23 de Fevereiro de 1855
Matema´tico, astroˆnomo e f´ısico alema˜o que contribuiu muito
em diversas a´reas da cieˆncia, dentre elas a teoria dos nu´meros,
estat´ıstica, ana´lise matema´tica, geometria diferencial,
geode´sia, geof´ısica, eletroesta´tica, astronomia e o´ptica
Clarimar, Departamento de Computac¸a˜o Aula 1, Sistemas Lineares 22/24
Philipp Ludwig von Seidel
Zweibru¨cken, 23 de outubro de 1821
Munique, 13 de agosto de 1896 matema´tico alema˜o
Em 1857 von Seidel decompoˆs as aberrac¸o˜es monocroma´ticas
de primeira ordem em cinco aberrac¸o˜es constituintes
Estas sa˜o comumentemente referenciadas como as cinco
aberrac¸o˜es de Seidel
O me´todo de Gauss-Seidel e´ um me´todo nume´rico iterativo
usual para a soluc¸a˜o de sistemas de equac¸o˜es lineares
Clarimar, Departamento de Computac¸a˜o Aula 1, Sistemas Lineares 23/24
Me´todo de Gauss-Seidel
Resolve um sistema linear de n inco´gnitas
Seja o sistema
a11x1+ a12x2+ . . .+ a1nxn = b1
a21x1+ a22x2+ . . .+ a2nxn = b2
...
...
...
...
an1x1+ an2x2+ . . .+ annxn = bn
Clarimar, Departamento de Computac¸a˜o Aula 1, Sistemas Lineares 24/24