Fatoração LU para Resolução de Sistemas Lineares

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
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.3.2 Fatorac¸a˜o LU
Ja´ vimos como e´ “fa´cil” resolver sistemas triangulares.
Tal fato nos motiva a investigar formas de que um sistema de
equac¸o˜es lineares Ax = b possa ser resolvido atrave´s da soluc¸a˜o de
sistemas triangulares.
O processo de fatorac¸a˜o para resoluc¸a˜o do sistema consiste em
decompor a matriz A dos coeficientes em um produto de dois ou mais
fatores e, em seguida, resolver uma sequeˆncia de sistemas lineares que
nos conduzira´ a` soluc¸a˜o do sistema.
Toda matriz na˜o singular admite uma decomposic¸a˜o em duas
matrizes triangulares, uma superior e outra inferior.
3.3.2 Fatorac¸a˜o LU
Ja´ vimos como e´ “fa´cil” resolver sistemas triangulares.
Tal fato nos motiva a investigar formas de que um sistema de
equac¸o˜es lineares Ax = b possa ser resolvido atrave´s da soluc¸a˜o de
sistemas triangulares.
O processo de fatorac¸a˜o para resoluc¸a˜o do sistema consiste em
decompor a matriz A dos coeficientes em um produto de dois ou mais
fatores e, em seguida, resolver uma sequeˆncia de sistemas lineares que
nos conduzira´ a` soluc¸a˜o do sistema.
Toda matriz na˜o singular admite uma decomposic¸a˜o em duas
matrizes triangulares, uma superior e outra inferior.
3.3.2 Fatorac¸a˜o LU
Ja´ vimos como e´ “fa´cil” resolver sistemas triangulares.
Tal fato nos motiva a investigar formas de que um sistema de
equac¸o˜es lineares Ax = b possa ser resolvido atrave´s da soluc¸a˜o de
sistemas triangulares.
O processo de fatorac¸a˜o para resoluc¸a˜o do sistema consiste em
decompor a matriz A dos coeficientes em um produto de dois ou mais
fatores e, em seguida, resolver uma sequeˆncia de sistemas lineares que
nos conduzira´ a` soluc¸a˜o do sistema.
Toda matriz na˜o singular admite uma decomposic¸a˜o em duas
matrizes triangulares, uma superior e outra inferior.
3.3.2 Fatorac¸a˜o LU
Ja´ vimos como e´ “fa´cil” resolver sistemas triangulares.
Tal fato nos motiva a investigar formas de que um sistema de
equac¸o˜es lineares Ax = b possa ser resolvido atrave´s da soluc¸a˜o de
sistemas triangulares.
O processo de fatorac¸a˜o para resoluc¸a˜o do sistema consiste em
decompor a matriz A dos coeficientes em um produto de dois ou mais
fatores e, em seguida, resolver uma sequeˆncia de sistemas lineares que
nos conduzira´ a` soluc¸a˜o do sistema.
Toda matriz na˜o singular admite uma decomposic¸a˜o em duas
matrizes triangulares, uma superior e outra inferior.
3.3.2 Fatorac¸a˜o LU
Teorema 3.2 - Teorema de Gauss
Seja A uma matriz quadrada de ordem n tal que detA 6= 0. Seja Ak a
matriz constitu´ıda das primeiras k linhas e colunas de A. Suponha que
det(Ak) 6= 0 para k = 1, 2, , (n − 1). Sejam U uma matriz triangular
superior,
U =
{
uij , se i ≤ 0
0, se i > j ,
e L uma matriz triangular inferior unita´ria,
L =

0, se i < j
1, se i = j
lij , se i > j .
Enta˜o existe e e´ u´nica a decomposic¸a˜o A = LU, onde U e´ a matriz
resultante do processo de eliminac¸a˜o gaussiana e lij = mij (multiplicadores
de linha).
3.3.2 Fatorac¸a˜o LU
Se pudermos realizar a fatorac¸a˜o A = LU o sistema linear Ax = b
pode ser escrito como:
(LU)x = b
Se fizermos
Ux = y ,
enta˜o resolver o sistema linear Ax = b e´ equivalente a resolver o
sistema linear
Ly = b
e, em seguida, o sistema linear
Ux = y
3.3.2 Fatorac¸a˜o LU
Se pudermos realizar a fatorac¸a˜o A = LU o sistema linear Ax = b
pode ser escrito como:
(LU)x = b
Se fizermos
Ux = y ,
enta˜o resolver o sistema linear Ax = b e´ equivalente a resolver o
sistema linear
Ly = b
e, em seguida, o sistema linear
Ux = y
3.3.2 Fatorac¸a˜o LU
A maior vantagem dos processos de fatorac¸a˜o e´ que podemos resolver
qualquer sistema linear que tenha a matriz A como matriz dos
coeficientes.
Se o vetor b for alterado, a resoluc¸a˜o do novo sistema linear sera´
praticamente imediata.
Nesta fatorac¸a˜o a matriz L e´ triangular inferior com diagonal unita´ria.
E a matriz U e´ triangular superior.
Existem diversos me´todos para se determinar as matrizes L e U tais
que A = LU.
A fatorac¸a˜o LU e´ um dos processos de fatorac¸a˜o mais empregados.
3.3.2 Fatorac¸a˜o LU
Regra pra´tica: Usar a eliminac¸a˜o gaussiana para determinar a matriz
U e a matriz L sera´ formada pelos multiplicadores.
Resolver o sistema abaixo atrave´s da fatorac¸a˜o LU
3x1 + 2x2 + 4x3 =
x1 + x2 + 2x3 =
4x1 + 3x2 + 2x3 =
1
2
3
3.3.2 Fatorac¸a˜o LU
Regra pra´tica: Usar a eliminac¸a˜o gaussiana para determinar a matriz
U e a matriz L sera´ formada pelos multiplicadores.
Resolver o sistema abaixo atrave´s da fatorac¸a˜o LU
3x1 + 2x2 + 4x3 =
x1 + x2 + 2x3 =
4x1 + 3x2 + 2x3 =
1
2
3
3.3.2 Fatorac¸a˜o LU
A(0) =
 3 2 41 1 2
4 3 2

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.2 Fatorac¸a˜o LU
A(1) =
 3 2 40 1/3 2/3
0 1/3 −10/3

m32 =
1/3
1/3
L
(2)
1 ← L(1)1
L
(2)
2 ← L(1)2
L
(2)
3 ← L(1)3 −m32L(1)2
A(2) =
 3 2 40 1/3 2/3
0 0 −4

3.3.2 Fatorac¸a˜o LU
Assim:
U =
 3 2 40 1/3 2/3
0 0 −4

e
L =
 1 0 01/3 1 0
4/3 1 1

Podemos verificar que A = LU.
3.3.2 Fatorac¸a˜o LU
Resta-nos agora resolver o sistema LUx = b
Fazendo Ux = y
Resolvemos inicialmente Ly = b 1 0 01/3 1 0
4/3 1 1
 y1y2
y3
 =
 12
3

Que resolvemos por substituic¸a˜o direta, encontrando:
y1 = 1, y2 = 5/3 e y3 = 0
3.3.2 Fatorac¸a˜o LU
Resta-nos agora resolver o sistema LUx = b
Fazendo Ux = y
Resolvemos inicialmente Ly = b 1 0 01/3 1 0
4/3 1 1
 y1y2
y3
 =
 12
3

Que resolvemos por substituic¸a˜o direta, encontrando:
y1 = 1, y2 = 5/3 e y3 = 0
3.3.2 Fatorac¸a˜o LU
E finalmente resolvemos Ux = y
U =
 3 2 40 1/3 2/3
0 0 −4
 x1x2
x3
 =
 15/3
0

Que leva a:
x1 = −3, x2 = 5 e x3 = 0
3.3.2 Fatorac¸a˜o LU
E finalmente resolvemos Ux = y
U =
 3 2 40 1/3 2/3
0 0 −4
 x1x2
x3
 =
 15/3
0

Que leva a:
x1 = −3, x2 = 5 e x3 = 0
3.3.2 Fatorac¸a˜o LU
Resolver o sistema abaixo atrave´s da fatorac¸a˜o LU
2x1 + x2 + x3 =
4x1 + 4x2 + 3x3 =
6x1 + 7x2 + 4x3 =
7
21
32
x1 = 1, x2 = 2 e x3 = 3
3.3.2 Fatorac¸a˜o LU
Resolver o sistema abaixo atrave´s da fatorac¸a˜o LU
2x1 + x2 + x3 =
4x1 + 4x2 + 3x3 =
6x1 + 7x2 + 4x3 =
7
21
32
x1 = 1, x2 = 2 e x3 = 3
3.3.2 Fatorac¸a˜o LU com pivoteamento parcial
Como a fatorac¸a˜o LU so´ transforma os elementos da matriz A, se
precisarmos aplicar as estrate´gias de pivoteamento parcial e´ preciso
“guardar” esta informac¸a˜o e atualiza´-la na matriz dos coeficientes.
Esta atualizac¸a˜o se da´ atrave´s de produtos da matriz de permutac¸a˜o.
Uma matriz quadrada de ordem n e´ uma matriz de permutac¸a˜o se
puder ser obtida da matriz identidade de ordem n permutando-se suas
linhas ou colunas.
Ao se pre´-multiplicar uma matriz A por uma matriz de permutac¸a˜o P
obtem-se uma matriz PA com as linhas permutadas.
Esta permutac¸a˜o de linhas e´ a mesma efetuada na matriz identidade
para se obter P.
3.3.2 Fatorac¸a˜o LU com pivoteamento parcial
Como a fatorac¸a˜o LU so´ transforma os elementos da matriz A, se
precisarmos aplicar as estrate´gias de pivoteamento parcial e´ preciso
“guardar” esta informac¸a˜o e atualiza´-lana matriz dos coeficientes.
Esta atualizac¸a˜o se da´ atrave´s de produtos da matriz de permutac¸a˜o.
Uma matriz quadrada de ordem n e´ uma matriz de permutac¸a˜o se
puder ser obtida da matriz identidade de ordem n permutando-se suas
linhas ou colunas.
Ao se pre´-multiplicar uma matriz A por uma matriz de permutac¸a˜o P
obtem-se uma matriz PA com as linhas permutadas.
Esta permutac¸a˜o de linhas e´ a mesma efetuada na matriz identidade
para se obter P.
3.3.2 Fatorac¸a˜o LU com pivoteamento parcial
Seja I3 a matriz identidade de ordem 3
I3 =
 1 0 00 1 0
0 0 1

Se permutarmos inicialmente as linhas 1 e 2 e logo apo´s as linhas 2 e
3 obtemos a seguinte matriz de permutac¸a˜o
P =
 0 1 00 0 1
1 0 0

3.3.2 Fatorac¸a˜o LU com pivoteamento parcial
Se quisermos que a matriz A sofra as mesmas permutac¸o˜es devemos
fazer A′ = PA
A =
 3 2 41 1 2
4 3 2

A’=PA =
 0 1 00 0 1
1 0 0
 3 2 41 1 2
4 3 2
 =
 1 1 24 3 2
3 2 4

3.3.2 Fatorac¸a˜o LU com pivoteamento parcial
Na fatorac¸a˜o LU, Ax = b com A = LU, se as matrizes L e U sa˜o
obtidas com estrate´gia de pivoteamento parcial enta˜o devemos
resolver:
A′ = PA
Encontramos a fatorac¸a˜o da matriz A′
As mesmas permutac¸o˜es efetuadas nas linhas de A devem ser
efetuadas sobre o vetor dos coeficientes independentes b uma vez que
permutar as linhas de A implica em permutar as equac¸o˜es do sistema
Ax = b.
Fac¸amos enta˜o
b′ = Pb
O sistema linear A′x = b′ e´ equivalente ao original, enta˜o resolvemos
os seguintes sistemas triangulares:
Ly = Pb e
Ux = y , onde
A′ = LU
3.3.2 Fatorac¸a˜o LU com pivoteamento parcial
Na fatorac¸a˜o LU, Ax = b com A = LU, se as matrizes L e U sa˜o
obtidas com estrate´gia de pivoteamento parcial enta˜o devemos
resolver:
A′ = PA
Encontramos a fatorac¸a˜o da matriz A′
As mesmas permutac¸o˜es efetuadas nas linhas de A devem ser
efetuadas sobre o vetor dos coeficientes independentes b uma vez que
permutar as linhas de A implica em permutar as equac¸o˜es do sistema
Ax = b.
Fac¸amos enta˜o
b′ = Pb
O sistema linear A′x = b′ e´ equivalente ao original, enta˜o resolvemos
os seguintes sistemas triangulares:
Ly = Pb e
Ux = y , onde
A′ = LU
3.3.2 Fatorac¸a˜o LU com pivoteamento parcial
Resolver o sistema abaixo atrave´s da fatorac¸a˜o LU com estrate´gia de
pivoteamento parcial
3x1 − 4x2 + x3 =
1x1 + 2x2 + 2x3 =
4x1 − 3x3 =
9
3
−2
x1 = 1, x2 = −1 e x3 = 2
3.3.2 Fatorac¸a˜o LU com pivoteamento parcial
Resolver o sistema abaixo atrave´s da fatorac¸a˜o LU com estrate´gia de
pivoteamento parcial
3x1 − 4x2 + x3 =
1x1 + 2x2 + 2x3 =
4x1 − 3x3 =
9
3
−2
x1 = 1, x2 = −1 e x3 = 2
3.3.2 Fatorac¸a˜o LU com pivoteamento parcial
Pro´xima aula
Me´todos Iterativos
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.