elimicacao de gaus

Prévia do material em texto

UNIVERSIDADE FEDERAL RURAL DO SEMI-A´RIDO
CENTRO MULTIDISCIPLINAR PAU DOS FERROS
DISCIPLINA: CA´LCULO NUME´RICO
Resoluc¸a˜o de Sistemas Lineares: Me´todos Exatos
Pau dos Ferros - RN
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 1 / 33
Suma´rio
1 Sistemas Lineares
2 Me´todos Exatos
Me´todo LU
Algoritmo
Eliminac¸a˜o de Gauss
Algoritmo
3 Considerac¸o˜es Finais
4 Refereˆncias
Sistemas Lineares
Introduc¸a˜o
Uma variedade de problemas de engenharia pode ser resolvido
atrave´s da ana´lise linear de sistemas.
Exemplo: Sistema Linear
x + y + z = 1
x − y − z = 1
2x + 3y − 4z = 9
(1)
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 3 / 33
Me´todos Exatos Me´todo LU
Me´todo LU
Consiste em decompor uma matriz quadrada A(ai j) no produto
de uma matriz triangular superior e inferior.
LU = A

1
l21 1
l31 l32 1
.
.
.
.
.
.
.
.
.
. . .
.
.
.
ln1 ln2 ln3 · · · 1


u11 u12 u13 · · · u1n
u22 u23 · · · u2n
u33 · · · u3n
. . .
.
.
.
unn
=

a11 a12 a13 · · · a1n
a21 a22 a23 · · · a2n
a31 a32 a33 · · · a3n
.
.
.
.
.
.
.
.
.
. . .
.
.
.
an1 an2 an3
. . . ann

(2)
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 4 / 33
Me´todos Exatos Me´todo LU
Me´todo LU
Teorema LU: Seja A = (ai j) uma matriz quadrada de ordem n, e
Ak o menor principal, constituı´do das k primeiras linhas e k
primeiras colunas de A. Assumimos que det(Ak) 6= 0 para k =1, 2,
...m n-1. Enta˜o existe uma u´nica matriz trinagular inferior L = (li j),
com l11 = l22 = ...lnn = 1, e uma matriz triangular superior U = ui j
tal que LU =A. Ale´m disso det(A) = u11u22...unn.
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 5 / 33
Me´todos Exatos Me´todo LU
Me´todo LU
Etapa 1 (1a linha de U): Faz o produto da 1a linha de L por todas as
colunas de U e igualando com os elementos da 1a linha de A, obtemos:
u1 j = a1 j, j = 1,2, ...,n.
Etapa 2 (1a Coluna de L): Faz o produto de todas as linhas de L (da 2a
ate´ a na) pela primeira coluna de U.
u11li1 = ai1 ∴ li1 = ai1/u11
Etapa 3 (2a Coluna de U): Faz o produto da 2a linha de L por todas as
colunas de U:
l21u12+u22 = a22 ⇒ u22 = a22− l21u12
l21u13+u23 = a23 ⇒ u23 = a23− l21u13
l21u1n+u2n = a2n ⇒ u2n = a2n− l21u1n, n= 1,2, ...k.
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 6 / 33
Me´todos Exatos Me´todo LU
Me´todo LU
Etapa 4 (2a Coluna de L): Faz o produto de todas as linhas de L
(da 3a ate´ a na) pela 2a coluna de U e igualando com os
elementos da 2a coluna de A (abaixo da diagonal principal).
l31u12+ l32u22 = a32 ⇒ l32 = a32− l31u12u22
l41u12+ l42u22 = a42 ⇒ l42 = a42− l41u12u22
ln1u12+ ln2u22 = an2 ⇒ ln2 = an2− ln1u12u22 , n= 1,2, ...,k.
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 7 / 33
Me´todos Exatos Me´todo LU
Me´todo LU
Se continuarmos calculando a 3a linha de U, 3a coluna de L, 4a
linha de U, 4a coluna de L, etc..., teremos as fo´rmulas gerais:
ui j = ai j−
i−1
∑
k=1
likuk j, i≤ j.
li j =
ai j−∑ j−1k=1 likuk j
u j j
, i> j.
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 8 / 33
Me´todos Exatos Me´todo LU
Soluc¸a˜o de sistema com o me´todo LU
Seja Ax=b de ordem n determinado, onde A satisfaz as condic¸o˜es
da decomposic¸a˜o LU. Enta˜o
LUx= b.
Fazendo Ux = y, a equac¸a˜o acima reduz-se a Ly=b.
Dessa forma resolvendo o sistema triangular inferior Ly = b
obtemos o vetor y.
Substituindo o valor y no sistema Ux= y obtemos um sistema
triangular superior, cuja soluc¸a˜o e´ o vetor x que procuramos.
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 9 / 33
Me´todos Exatos Me´todo LU
Me´todo LU - Exemplo:
Obtenha a soluc¸a˜o do sistema abaixo utilizando o me´todo LU.
5x1 + 2x2 + x3 = 0
3x1 + x2 + 4x3 = −7
x1 + x2 + 3x3 = −5
(3)
Matricialmente temos,
 5 2 13 1 4
1 1 3
 x1x2
x3
=
 0−7
−5

Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 10 / 33
Me´todos Exatos Me´todo LU
Soluc¸a˜o:
Primeiramente verificamos se A satisfaz as condic¸o˜es de
decomposic¸a˜o LU, isto e´, det(Ak) 6= 0.
Se satisfaz, enta˜o vamos obter as matrizes L e U, tal que LU=A. 1l21 1
l31 l32 1
 u11 u12 u13u22 u23
u33
=
 5 2 13 1 4
1 1 1
 (4)
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 11 / 33
Me´todos Exatos Me´todo LU
Me´todo LU
Etapa 1 (1a linha de U):
u11 = 5, u12 = 2, u13 = 1.
Etapa 2 (1a Coluna de L):
u11l21 = 3 ∴ l21 = 3/5
u11l31 = 1 ∴ l31 = 1/5
Etapa 3 (2a Coluna de U):
u22 = a22− l21u12 = 1− 352=−
1
5
u23 = a23− l21u12 = 4− 35 =
17
5
.
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 12 / 33
Me´todos Exatos Me´todo LU
Me´todo LU
Etapa 4 (2a Coluna de L):
l31u12+ l32u22 = a32 ⇒ l32 = a32− l31u12u22
l32 =
1− 152
−15
=−3.
Etapa 5: (3a linha de U)
ui j = ai j−
i−1
∑
k=1
likuk j, i≤ j.
u33 = a33−
2
∑
k=1
l3kuk3 = a33− l31u13− l32u23
u33 = 13.
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 13 / 33
Me´todos Exatos Me´todo LU
Me´todo LU
L=
 13/5 1
1/5 −3 1
 U =
 5 2 1−1/5 17/5
13
 (5)
Assim Ly =b e´, 13/5 1
1/5 −3 1
 y1y2
y3
=
 0−7
−5

Dessa forma, y1 = 0, y2 =−7 e y3 =−26.
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 14 / 33
Me´todos Exatos Me´todo LU
Me´todo LU
E o sistema Ux=y e´, 5 2 1−1/5 17/5
13
 x1x2
x3
=
 0−7
−26

Portanto, x3 =−2, x2 = 1 e x1 = 0. Dessa forma o vetor de soluc¸a˜o do
sistema e´ x= (0,1,−2)t .
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 15 / 33
Me´todos Exatos Me´todo LU
Algoritmo
<link>
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 16 / 33
Me´todos Exatos Me´todo LU
Exercı´cios
1. Resolver o sistema abaixo, utilizando o Me´todo LU.
6x1 + 2x2 − x3 = 7
2x1 + 4x2 + x3 = 7
3x1 + 2x2 + 8x3 = 13
(6)
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 17 / 33
Me´todos Exatos Eliminac¸a˜o de Gauss
Eliminac¸a˜o de Gauss
Consiste em transformar o sistema dado em um sistema
triangular.
a111 + a
1
12 · · · + a11n = b11
a121 + a
1
22 · · · + a12n = b12
...
...
...
. . .
...
... =
...
a1n1 + a
1
n2 · · · + a1nn = b1n
(7)
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 18 / 33
Me´todos Exatos Eliminac¸a˜o de Gauss
Eliminac¸a˜o de Gauss
Em primeiro montamos a matriz aumentada:
a111 a
1
12 · · · a11n | b11
a121 a
1
22 · · · a12n | b12
...
...
. . .
... | ...
a1n1 a
1
n2 · · · a1nn | b1n

Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 19 / 33
Me´todos Exatos Eliminac¸a˜o de Gauss
Etapas: Me´todo Eliminac¸a˜o de Gauss
1. Passo: Eliminar a inco´gnita x1 da 2a, 3a, ..., na equac¸a˜o. Para
isso, substituı´mos a 2a, 3a, ..., na, respectivamente,
pela diferenc¸a entre a 2a equac¸a˜o e a 1a multiplicado por a
1
21
a111
pela diferenc¸a entre a 3a equac¸a˜o e a 1a multiplicado por a
1
31
a111
pela diferenc¸a entre a na equac¸a˜o e a 1a multiplicado por a
1
n1
a111
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 20 / 33
Me´todos Exatos Eliminac¸a˜o de Gauss
Eliminac¸a˜o de Gauss

a111 a
1
12 · · · a11n | b11
a222 · · · a22n | b22
...
. . .
... | ...
a2n2 · · · a2nn | b1n

a2i j = a
1
i j−a11 j
a1i1
a111
; i= 2,3, ...,n.
b2i= b
1
i −b11
a1i1
a111
; j = 1,2, ...,n.
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 21 / 33
Me´todos Exatos Eliminac¸a˜o de Gauss
Etapas: Me´todo Eliminac¸a˜o de Gauss
2. Passo: Eliminar a inco´gnita x2 da 3a, 4a, ..., na equac¸a˜o. Para
isso, substituı´mos a 3a, 4a, ..., na, respectivamente,
pela diferenc¸a entre a 3a equac¸a˜o e a 2a multiplicado por a
2
32
a222
pela diferenc¸a entre a 4a equac¸a˜o e a 2a multiplicado por a
2
32
a222
pela diferenc¸a entre a na equac¸a˜o e a 2a multiplicado por a
2
n2
a222
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 22 / 33
Me´todos Exatos Eliminac¸a˜o de Gauss
Eliminac¸a˜o de Gauss

a111 a
1
12 a
1
13 · · · a11n | b11
a222 a
1
23 · · · a22n | b22
a333 · · · a33n | b33
...
. . .
... | ...
a3n3 · · · a3nn | b3n

a3i j = a
2
i j−a22 j
a2i2
a222
; i= 3,4, ...,n.
b3i = b
2
i −b22
a2i2
a222
; j = 2,3, ...,n.
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 23 / 33
Me´todos Exatos Eliminac¸a˜o de Gauss
Etapas: Me´todo Eliminac¸a˜o de Gauss
n-1. Passo: Eliminar a inco´gnita xn−1 na equac¸a˜o. Para isso,
substituı´mos a na,
pela diferenc¸a entre a na equac¸a˜o e a (n-1)a multiplicado por
an−1n,n−1
an−1n−1,n−1
De forma geral,
ani j = a
n−1
i j −an−1n−1, j
an−1i,n−1
an−1n−1,n−1
bni = b
n−1
i −bn−1n−1
an−1i,n−1
an−1n−1,n−1
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 24 / 33
Me´todos Exatos Eliminac¸a˜o de Gauss
Exemplo: Me´todo de Gauss
6x1 + 2x2 − x3 = 7
2x1 + 4x2 + x3 = 7
3x1 + 2x2 + 8x3 = 13
(8)
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 25 / 33
Me´todos Exatos Eliminac¸a˜o de Gauss
Para solucionar, montamos o sistema na forma matricial
ampliada. Desse modo teremos: 6 2 −1 | 72 4 1 | 7
3 2 8 | 13

Para zerar os demais elementos x1, recalculamos as linhas 2 e 3 da
matriz. Desse modo teremos:
L2← L2−L1m2
L3← L3−L1m3
em que m2 = a21a11 =
2
6 =
1
3
m3 =
a31
a11
= 36 =
1
2
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 26 / 33
Me´todos Exatos Eliminac¸a˜o de Gauss
Para solucionar, montamos o sistema na forma matricial
ampliada. Desse modo teremos: 6 2 −1 | 72 4 1 | 7
3 2 8 | 13

Para zerar os demais elementos x1, recalculamos as linhas 2 e 3 da
matriz. Desse modo teremos:
L2← L2−L1m2
L3← L3−L1m3
em que m2 = a21a11 =
2
6 =
1
3
m3 =
a31
a11
= 36 =
1
2
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 26 / 33
Me´todos Exatos Eliminac¸a˜o de Gauss
L2← L2−L1m2
2 4 1 | 7
6 2 −1 | 7 ×13
0 103
4
3 | 143
L3← L3−L1m3
3 2 8 | 13
6 2 −1 | 7 ×12
0 1 172 | 192
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 27 / 33
Me´todos Exatos Eliminac¸a˜o de Gauss
Portanto a nova matriz e´: 6 2 −1 | 70 103 43 | 143
0 1 172 | 192

Agora precisamos zera os demais elementos dependente de x2
abaixo da diagonal, para precisamos recaulcular a linha 3 da
matriz.
L3← L3−L2m3
m3 =
a31
a22
= 110/3 =
3
10
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 28 / 33
Me´todos Exatos Eliminac¸a˜o de Gauss
Portanto a nova matriz e´: 6 2 −1 | 70 103 43 | 143
0 1 172 | 192

Agora precisamos zera os demais elementos dependente de x2
abaixo da diagonal, para precisamos recaulcular a linha 3 da
matriz.
L3← L3−L2m3
m3 =
a31
a22
= 110/3 =
3
10
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 28 / 33
Me´todos Exatos Eliminac¸a˜o de Gauss
L3← L3−L2m3
0 1 172 | 192
0 103
4
3 | 143 × 310
0 0 8110 | 8110
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 29 / 33
Me´todos Exatos Eliminac¸a˜o de Gauss
Dessa forma a obtivemos uma matriz triangular superior dada por, 6 2 −1 70 10/3 4/3 14/3
0 81/10 81/10

6x1+2x2− x3 = 7
10/3x2+4/3x3 = 14/3
81/10x3 = 81/10
x1 = 1, x2 = 1, x3 = 1.
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 30 / 33
Me´todos Exatos Eliminac¸a˜o de Gauss
Algoritmo
<link>
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 31 / 33
Considerac¸o˜es Finais
Me´todo LU versus Eliminac¸a˜o de Gauss
Se o me´todo LU faz os mesmos procedimentos da te´cnica de
eliminac¸a˜o de Gauss, qual a diferenc¸a entre essas duas te´cnicas?
Imagine um sistema onde desejamos calcular diferentes situac¸o˜es
mudando apenas o vetor b.
Na primeira execuc¸a˜o ja´ encontrarı´amos as matrizes L e U.
Para os outros casos, diferentes b’s, era apenas necessa´rio realizar
substituic¸o˜es diretas (encontrar y) e regressivas (encontrar x).
Nesse exemplo apenas o b muda, L e U sempre sa˜o os mesmos.
Os me´todos baseados na decomposic¸a˜o LU tem um problema
serio que esta relacionado com a propagac¸a˜o dos erros de
truncamento do computador.
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 32 / 33
Refereˆncias
Refereˆncias
Franco, Neide Bertoldi. Ca´lculo nume´rico. Pearson, 2006.
BURDEN, R. L. Ana´lise nume´rica. Sa˜o Paulo: Cengage Learning,
2013.
SPERANDIO, D.; MENDES, J. T.; SILVA, L. H. M Ca´lculo
nume´rico: caracterı´sticas matema´ticas e computacionais dos
me´todos nume´ricos. Sa˜o Paulo: Pearson Education, 2003.
RUGGIERO, M. A. G.; LOPES, V. L. R. Ca´lculo nume´rico:
aspectos teo´ricos e computacionais . 2a ed. Sa˜o Paulo: Pearson
Education, 1996.
Rosana Cibely B. Rego (UFERSA) Me´todos Nume´ricos Pau dos Ferros -RN 33 / 33
	Sistemas Lineares
	Métodos Exatos
	Método LU
	Eliminação de Gauss
	Considerações Finais
	Referências