aula12

Prévia do material em texto

GEX114 - Ca´lculo Nume´rico
Profa. Dra. Amanda Castro Oliveira
Departamento de Cieˆncias Exatas - DEX/UFLA
amanda@dex.ufla.br
Cap.3 - Resoluc¸o˜es de Sistemas Lineares
3.1 Introduc¸a˜o
Te´cnicas para a resoluc¸a˜o de sistemas lineares atrave´s de me´todos:
diretos de decomposic¸a˜o e eliminac¸a˜o;
iterativos.
A necessidade de se resolver sistemas de equac¸o˜es lineares aparece
numa grande variedade de problemas cient´ıficos.
Estimativas sugerem que a cada 4 problemas de simulac¸a˜o nume´rica 3
convertem-se na resoluc¸a˜o de sistemas.
3.2 Sistemas de Equac¸o˜es Lineares
Seja o Sistema Linear Ax = b , onde A = (aij) i , j = 1, 2, ..., n
A = matriz nxn, matriz dos coeficientes,
x = (xj)
t , j = 1, ..., n
vetor da inco´gnitas,
b = (bi )
t , i = 1, ..., n
vetor dos coeficientes independentes,
det(A) 6= 0
Garantia de soluc¸a˜o u´nica.
3.2 Sistemas de Equac¸o˜es Lineares
O sistema linear (s.l.) pode ser representado da seguinte forma:
a11x1+ a12x2+ · · · +a1nxn =
a21x1+ a22x2+ · · · +a2nxn =
...
an1x1+ an2x2+ · · · +annxn =
b1
b2
...
bn
ou na forma matricial
a11 a12 · · · a1n
a21 a22 · · · a2n
...
...
. . .
...
an1 an2 · · · ann


x1
x2
...
xn
 =

b1
b2
...
bn

ou ainda na forma compacta:
n∑
j=1
aijxj = bi i = 1, ...n
3.2 Sistemas de Equac¸o˜es Lineares
O sistema linear (s.l.) pode ser representado da seguinte forma:
a11x1+ a12x2+ · · · +a1nxn =
a21x1+ a22x2+ · · · +a2nxn =
...
an1x1+ an2x2+ · · · +annxn =
b1
b2
...
bn
ou na forma matricial
a11 a12 · · · a1n
a21 a22 · · · a2n
...
...
. . .
...
an1 an2 · · · ann


x1
x2
...
xn
 =

b1
b2
...
bn

ou ainda na forma compacta:
n∑
j=1
aijxj = bi i = 1, ...n
3.2 Sistemas de Equac¸o˜es Lineares
O sistema linear (s.l.) pode ser representado da seguinte forma:
a11x1+ a12x2+ · · · +a1nxn =
a21x1+ a22x2+ · · · +a2nxn =
...
an1x1+ an2x2+ · · · +annxn =
b1
b2
...
bn
ou na forma matricial
a11 a12 · · · a1n
a21 a22 · · · a2n
...
...
. . .
...
an1 an2 · · · ann


x1
x2
...
xn
 =

b1
b2
...
bn

ou ainda na forma compacta:
n∑
j=1
aijxj = bi i = 1, ...n
3.2 Sistemas de Equac¸o˜es Lineares
Resolver um sistema linear consiste em determinar um vetor
x∗ = (x1, x2, ...xn)t que satisfac¸a simultaneamente a todas as equac¸o˜es
do sistema.
Graficamente, no <2, podemos representar a soluc¸a˜o de um sistema linear
considerando os seguintes exemplos:{ −x1 + 2x2 = 3
x1 + x2 = 3
, det(A) = −1− 2 = −1.
3.2 Sistemas de Equac¸o˜es Lineares
Resolver um sistema linear consiste em determinar um vetor
x∗ = (x1, x2, ...xn)t que satisfac¸a simultaneamente a todas as equac¸o˜es
do sistema.
Graficamente, no <2, podemos representar a soluc¸a˜o de um sistema linear
considerando os seguintes exemplos:{ −x1 + 2x2 = 3
x1 + x2 = 3
, det(A) = −1− 2 = −1.
3.2 Sistemas de Equac¸o˜es Lineares
Resolver um sistema linear consiste em determinar um vetor
x∗ = (x1, x2, ...xn)t que satisfac¸a simultaneamente a todas as equac¸o˜es
do sistema.
Graficamente, no <2, podemos representar a soluc¸a˜o de um sistema linear
considerando os seguintes exemplos:{ −x1 + 2x2 = 3
x1 + x2 = 3
, det(A) = −1− 2 = −1.
3.2 Sistemas de Equac¸o˜es Lineares
{
x1 + x2 = 3
2x1 + 2x2 = 6
, det(A) = 2− 2 = 0.
3.2 Sistemas de Equac¸o˜es Lineares
{
x1 + x2 = 3
2x1 + 2x2 = 6
, det(A) = 2− 2 = 0.
3.2 Sistemas de Equac¸o˜es Lineares
{
x1 + x2 = 3
x1 + x2 = 6
, det(A) = 1− 1 = 0.
3.2 Sistemas de Equac¸o˜es Lineares
{
x1 + x2 = 3
x1 + x2 = 6
, det(A) = 1− 1 = 0.
3.2 Sistemas de Equac¸o˜es Lineares
Definic¸a˜o 3.1: Dizemos que o sistema Ax = b, onde A = (aij) ,
x = (xj)
t , b = (bi )
t ; i , j = 1, ..., n e´ consistente se apresenta pelo
menos uma soluc¸a˜o, caso contra´rio ele e´ dito inconsistente.
Definic¸a˜o 3.2: O Sistema Ax = b e´ dito homogeˆneo se o vetor dos
coeficientes independentes, b = (bi )
t = 0 ∀i
Todo sistema homogeˆneo e´ consistente, pois o vetor nulo sempre e´
soluc¸a˜o.
Vamos procurar resolver sistemas consistentes atrave´s de me´todos
diretos e iterativos cuja soluc¸a˜o seja na˜o nula.
Consideraremos sempre o vetor dos termos independentes
b = (bi )
t 6= 0 ∀i
3.2 Sistemas de Equac¸o˜es Lineares
Definic¸a˜o 3.1: Dizemos que o sistema Ax = b, onde A = (aij) ,
x = (xj)
t , b = (bi )
t ; i , j = 1, ..., n e´ consistente se apresenta pelo
menos uma soluc¸a˜o, caso contra´rio ele e´ dito inconsistente.
Definic¸a˜o 3.2: O Sistema Ax = b e´ dito homogeˆneo se o vetor dos
coeficientes independentes, b = (bi )
t = 0 ∀i
Todo sistema homogeˆneo e´ consistente, pois o vetor nulo sempre e´
soluc¸a˜o.
Vamos procurar resolver sistemas consistentes atrave´s de me´todos
diretos e iterativos cuja soluc¸a˜o seja na˜o nula.
Consideraremos sempre o vetor dos termos independentes
b = (bi )
t 6= 0 ∀i
3.2 Sistemas de Equac¸o˜es Lineares
Definic¸a˜o 3.1: Dizemos que o sistema Ax = b, onde A = (aij) ,
x = (xj)
t , b = (bi )
t ; i , j = 1, ..., n e´ consistente se apresenta pelo
menos uma soluc¸a˜o, caso contra´rio ele e´ dito inconsistente.
Definic¸a˜o 3.2: O Sistema Ax = b e´ dito homogeˆneo se o vetor dos
coeficientes independentes, b = (bi )
t = 0 ∀i
Todo sistema homogeˆneo e´ consistente, pois o vetor nulo sempre e´
soluc¸a˜o.
Vamos procurar resolver sistemas consistentes atrave´s de me´todos
diretos e iterativos cuja soluc¸a˜o seja na˜o nula.
Consideraremos sempre o vetor dos termos independentes
b = (bi )
t 6= 0 ∀i
3.3 Me´todos Diretos
Me´todos diretos sa˜o aqueles que, a menos de erros de
arredondamento, fornecem a soluc¸a˜o exata do sistema linear, caso ela
exista, apo´s um nu´mero finito de operac¸o˜es.
Todos os me´todos estudados no ensino me´dio, Regra de Cramer,
Escalonamento, etc.
No caso de sistemas lineares nxn, com soluc¸a˜o u´nica, o vetor x∗ e´
dado por: x∗ = A−1b, pois se Ax = b com det(A) 6= 0 ∃A−1 tal que
AA−1 = In
e A−1Ax = A−1b enta˜o Inx = A−1b
Calcular explicitamente A−1 e em seguida efetuar o produto A−1b e´
desaconselha´vel, uma vez que o nu´mero de operac¸o˜es envolvidas e´
grande, o que faz com que este processo na˜o seja ta˜o competitivo
face aos demais me´todos estudados.
3.3 Me´todos Diretos
Me´todos diretos sa˜o aqueles que, a menos de erros de
arredondamento, fornecem a soluc¸a˜o exata do sistema linear, caso ela
exista, apo´s um nu´mero finito de operac¸o˜es.
Todos os me´todos estudados no ensino me´dio, Regra de Cramer,
Escalonamento, etc.
No caso de sistemas lineares nxn, com soluc¸a˜o u´nica, o vetor x∗ e´
dado por: x∗ = A−1b, pois se Ax = b com det(A) 6= 0 ∃A−1 tal que
AA−1 = In
e A−1Ax = A−1b enta˜o Inx = A−1b
Calcular explicitamente A−1 e em seguida efetuar o produto A−1b e´
desaconselha´vel, uma vez que o nu´mero de operac¸o˜es envolvidas e´
grande, o que faz com que este processo na˜o seja ta˜o competitivo
face aos demais me´todos estudados.
3.3.1 Me´todos de Eliminac¸a˜o de Gauss
Os me´todos de eliminac¸a˜o evitam o ca´lculo direto da matriz inversa
de A, ale´m disto, na˜o apresentam problemas com o tempo de
execuc¸a˜o como na regra de Cramer.
Consiste em transformar o sistema linear original em um sistema
linear equivalente com matriz dos coeficientes triangular superior.
Sistemas triangulares tem soluc¸a˜o imediata.
Definic¸a˜o 3.3: Dois sistemas lineares sa˜o ditos equivalentes se
possuem a mesma soluc¸a˜o.
3.3.1 Me´todos de Eliminac¸a˜o de Gauss - Sistemas
Triangulares
Considere o sistema linear Ux = b com U = (uij) , x = (xj)
t ,
b = (bi )
t ; i , j = 1, ..., n onde a matriz dos coeficientes e´ triangularsuperior, isto e´, seus coeficientes (uij = 0) sempre que i > j e com
(uii 6= 0), i = 1, ..., n, enta˜o podemos escrever:
u11x1+ u12x2+ · · · +u1nxn =
u22x2+ · · · +u2nxn =
.. .
unnxn =
b1
b2
...
bn
Este sistema pode ser facilmente resolvido por substituic¸a˜o, sendo xn
a primeira inco´gnita a ser determinada e x1 a u´ltima.
3.3.1 Me´todos de Eliminac¸a˜o de Gauss - Sistemas
Triangulares
Ex. Calcule a soluc¸a˜o do seguinte sistema de equac¸o˜es lineares:
3x1 +x2 =
+2x2 −x3 =
+3x3 =
4
2
0
x3 =
0
3
= 0
x2 =
2 + (x3)
2
=
2 + (0)
2
= 1
x1 =
4− x2
3
=
4− 1
3
= 1
Enta˜o x =
 11
0
 e´ o vetor soluc¸a˜o do sistema.
3.3.1 Me´todos de Eliminac¸a˜o de Gauss - Sistemas
Triangulares
Ex. Calcule a soluc¸a˜o do seguinte sistema de equac¸o˜es lineares:
3x1 +x2 =
+2x2 −x3 =
+3x3 =
4
2
0
x3 =
0
3
= 0
x2 =
2 + (x3)
2
=
2 + (0)
2
= 1
x1 =
4− x2
3
=
4− 1
3
= 1
Enta˜o x =
 11
0
 e´ o vetor soluc¸a˜o do sistema.
3.3.1 Me´todos de Eliminac¸a˜o de Gauss - Sistemas
Triangulares
Ex. Calcule a soluc¸a˜o do seguinte sistema de equac¸o˜es lineares:
3x1 +x2 =
+2x2 −x3 =
+3x3 =
4
2
0
x3 =
0
3
= 0
x2 =
2 + (x3)
2
=
2 + (0)
2
= 1
x1 =
4− x2
3
=
4− 1
3
= 1
Enta˜o x =
 11
0
 e´ o vetor soluc¸a˜o do sistema.
3.3.1 Me´todos de Eliminac¸a˜o de Gauss - Sistemas
Triangulares
Consideremos a matriz U, triangular superior, cuja linha gene´rica (i) e´
dada por:
uiixi + uii+1xi+1 + uii+2xi+2 + · · ·+ uinxn = bi ,
enta˜o:
xi =
(bi −
n∑
j=i+1
uijxj)
uii
Algoritmo 3.1: Resoluc¸a˜o de um sistema triangular superior
1 xn =
bn
unn
2 Para i = (n − 1), (n − 2), · · · , 1 fac¸a:
xi =
(bi −
n∑
j=i+1
uijxj)
uii
.
3.3.1 Me´todos de Eliminac¸a˜o de Gauss - Sistemas
Triangulares
Consideremos a matriz U, triangular superior, cuja linha gene´rica (i) e´
dada por:
uiixi + uii+1xi+1 + uii+2xi+2 + · · ·+ uinxn = bi ,
enta˜o:
xi =
(bi −
n∑
j=i+1
uijxj)
uii
Algoritmo 3.1: Resoluc¸a˜o de um sistema triangular superior
1 xn =
bn
unn
2 Para i = (n − 1), (n − 2), · · · , 1 fac¸a:
xi =
(bi −
n∑
j=i+1
uijxj)
uii
.
3.3.1 Me´todos de Eliminac¸a˜o de Gauss - Descric¸a˜o
Este me´todo consiste em transformar convenientemente o sistema
linear original para obter um sistema linear equivalente com a matriz
dos coeficientes triangular superior.
Teorema 3.1
Seja Ax = b um sistema linear. Aplicando sobre as equac¸o˜es deste sistema
uma sequeˆncia de operac¸o˜es elementares escolhidas entre:
(i) trocar duas equac¸o˜es;
(ii) multiplicar uma equac¸a˜o por uma constante na˜o nula;
(iii) adicionar um mu´ltiplo de uma equac¸a˜o a uma outra equac¸a˜o;
obtemos um novo sistema A˜x = b˜ e os sistemas sa˜o
equivalentes.
3.3.1 Me´todos de Eliminac¸a˜o de Gauss - Descric¸a˜o
Este me´todo consiste em transformar convenientemente o sistema
linear original para obter um sistema linear equivalente com a matriz
dos coeficientes triangular superior.
Teorema 3.1
Seja Ax = b um sistema linear. Aplicando sobre as equac¸o˜es deste sistema
uma sequeˆncia de operac¸o˜es elementares escolhidas entre:
(i) trocar duas equac¸o˜es;
(ii) multiplicar uma equac¸a˜o por uma constante na˜o nula;
(iii) adicionar um mu´ltiplo de uma equac¸a˜o a uma outra equac¸a˜o;
obtemos um novo sistema A˜x = b˜ e os sistemas sa˜o
equivalentes.
3.3.1 Me´todos de Eliminac¸a˜o de Gauss
Ex. Seja o seguinte sistema linear use a eliminac¸a˜o gaussiana para
encontrar a sua soluc¸a˜o:
3x1 +2x2 +4x3 =
x1 +x2 +2x3 =
4x1 +3x2 −2x3 =
1
2
3
Neste sistema aii 6= 0 ∀i
Ale´m disto, det(A) = −8 6= 0, garantia de soluc¸a˜o u´nica para o
sistema.
3.3.1 Me´todos de Eliminac¸a˜o de Gauss
Vamos trabalhar com a representac¸a˜o matricial e vamos considerar a
matriz A na forma aumentada.
A(0) = A|b
 3 2 4 11 1 2 2
4 3 −2 3

Seja L
(t)
i a linha i da matriz aumentada na etapa t.
Aqui L
(0)
2 = [1 1 2 2].
3.3.1 Me´todos de Eliminac¸a˜o de Gauss
1aEtapa: Eliminar x1 das equac¸o˜es i = 2, · · · , n, da seguinte forma:
da equac¸a˜o i subtra´ımos a 1a equac¸a˜o multiplicada por mi1.
mi1 =
a
(0)
i1
a
(0)
ii
, i = 2, · · · , n
Os elementos mi1 sa˜o chamados de multiplicadores e o elemento
a
(0)
ii e´ denominado pivoˆ da 1
a etapa.
O pivoˆ desta etapa e´ a
(0)
11 = 3
m21 =
1
3 e m31 =
4
3
L
(1)
1 ← L(0)1
L
(1)
2 ← L(0)2 −m21L(0)1
L
(1)
3 ← L(0)3 −m31L(0)1
3.3.1 Me´todos de Eliminac¸a˜o de Gauss
1aEtapa: Eliminar x1 das equac¸o˜es i = 2, · · · , n, da seguinte forma:
da equac¸a˜o i subtra´ımos a 1a equac¸a˜o multiplicada por mi1.
mi1 =
a
(0)
i1
a
(0)
ii
, i = 2, · · · , n
Os elementos mi1 sa˜o chamados de multiplicadores e o elemento
a
(0)
ii e´ denominado pivoˆ da 1
a etapa.
O pivoˆ desta etapa e´ a
(0)
11 = 3
m21 =
1
3 e m31 =
4
3
L
(1)
1 ← L(0)1
L
(1)
2 ← L(0)2 −m21L(0)1
L
(1)
3 ← L(0)3 −m31L(0)1
3.3.1 Me´todos de Eliminac¸a˜o de Gauss
A(1) =
 3 2 4 10 1/3 2/3 5/3
0 1/3 −22/3 5/3

2aEtapa: Deve-se ter pelo menos um elemento a
(1)
i2 6= 0, para
i = 2, · · · , n, caso contra´rio, det(A(1)) = 0 o que implica que
det(A) = 0, mas por hipo´tese det(A) 6= 0.
Enta˜o, sempre e´ poss´ıvel reescrever a matriz A(1), sem alterar a
posic¸a˜o da linha 1, de forma que o pivoˆ a
(1)
22 6= 0.
Eliminar x2 das equac¸o˜es i = 3, · · · , n, da seguinte forma: da equac¸a˜o
i subtra´ımos a 2a equac¸a˜o multiplicada por mi2.
mi2 =
a
(1)
i2
a
(1)
22
, i = 2, · · · , n
3.3.1 Me´todos de Eliminac¸a˜o de Gauss
O pivoˆ desta etapa e´ a
(1)
22 = 1/3
m32 =
a
(1)
32
a
(1)
22
= 13 ∗ 3 = 1
L
(2)
1 ← L(1)1
L
(2)
2 ← L(1)2
L
(2)
3 ← L(1)3 −m32L(2)2
A(2) =
 3 2 4 10 1/3 2/3 5/3
0 0 −8 0

Seguindo racioc´ınio ana´logo, procede-se ate´ a etapa (n − 1) para que
a matriz aumentada se torne triangular superior e equivalente ao
sistema original.
3.3.1 Me´todos de Eliminac¸a˜o de Gauss
Assim resolver o sistema A(2)x = b(2) e´ equivalente a resolver o
sistema Ax = b

3x1 +2x2 +4x3 =
+x2
2
3x3 =
−8x3 =
1
5/3
0
cujo vetor soluc¸a˜o e´ dado por x =
 − 35
0
 Podemos ver que este vetor
tambe´m e´ a soluc¸a˜o do sistema original.
3x1 +2x2 +4x3 =
x1 +x2 +2x3 =
4x1 +3x2 −2x3 =
1
2
3
3.3.1 Me´todos de Eliminac¸a˜o de Gauss
Assim resolver o sistema A(2)x = b(2) e´ equivalente a resolver o
sistema Ax = b

3x1 +2x2 +4x3 =
+x2
2
3x3 =
−8x3 =
1
5/3
0
cujo vetor soluc¸a˜o e´ dado por x =
 − 35
0
 Podemos ver que este vetor
tambe´m e´ a soluc¸a˜o do sistema original.

3x1 +2x2 +4x3 =
x1 +x2 +2x3 =
4x1 +3x2 −2x3 =
1
2
3
3.3.1 Me´todos de Eliminac¸a˜o de Gauss
Assim resolver o sistema A(2)x = b(2) e´ equivalente a resolver o
sistema Ax = b

3x1 +2x2 +4x3 =
+x2
2
3x3 =
−8x3 =
1
5/3
0
cujo vetor soluc¸a˜o e´ dado por x =
 − 35
0
 Podemos ver que este vetor
tambe´m e´ a soluc¸a˜o do sistema original.
3x1 +2x2 +4x3 =
x1 +x2 +2x3 =
4x1 +3x2 −2x3 =
1
2
3
3.3.1 Me´todos de Eliminac¸a˜o de Gauss
O nu´mero total de operac¸o˜es para se resolver um sistema linear pelo
me´todo de eliminac¸a˜o de Gauss e´ da ordem de n3, onde n e´ a
dimensa˜o do sistema linear.
Use a eliminac¸a˜o gaussiana para encontrar a soluc¸a˜o do seguinte
sistema linear:
x1 −x2 +2x3 −x4 =
2x1 −2x2 +3x3 −3x4 =
x1 +x2 +x3 =
x1 −x2 +4x3 +3x4 =
− 8
− 20
− 2
4
cujo vetor soluc¸a˜o e´ dado por x =

− 7
3
2
2

3.3.1 Me´todos de Eliminac¸a˜o de Gauss
O nu´mero total de operac¸o˜es para seresolver um sistema linear pelo
me´todo de eliminac¸a˜o de Gauss e´ da ordem de n3, onde n e´ a
dimensa˜o do sistema linear.
Use a eliminac¸a˜o gaussiana para encontrar a soluc¸a˜o do seguinte
sistema linear:
x1 −x2 +2x3 −x4 =
2x1 −2x2 +3x3 −3x4 =
x1 +x2 +x3 =
x1 −x2 +4x3 +3x4 =
− 8
− 20
− 2
4
cujo vetor soluc¸a˜o e´ dado por x =

− 7
3
2
2

Pro´xima aula
Estrate´gias de pivoteamento
Por hoje e´ so´ pessoal!!
Este material e´ inteiramente baseado na bibliografia do curso,
principalmente no livro texto :RUGIERO, M. A.G; LOPES,V Ca´lculo
Nume´rico: Aspectos teo´ricos e computacionais, Editora McGraw-Hill.1997.
Sites consultados acessados em 24/03/2011: CASTILHO, J. E., Apostila
de Ca´lculo Nume´rico, http://www.castilho.prof.ufu.br, UFU, 2002
http://www.alunos.eel.usp.br/numerico/notas.html
Colli, E., Asano, H. C,Ca´lculo Nume´rico — Fundamentos e
Aplicac¸o˜es-Departamento de Matema´tica Aplicada – IME-USP, 2009
Este material na˜o substitui a bibliografia.