Fatoracao - LU

Prévia do material em texto

3.2.3. Fatoração L.U.
Seja o sistema linear .A x b=
rr . O processo de fatoração para a resolução deste 
sistema linear consiste em decompor a matriz A dos coeficientes em um produto de dois 
ou mais fatores, e, em seguida resolver uma seqüência de sistemas lineares que nos 
conduzirá à solução do sistema linear original.
Por exemplo, se pudermos fazer a fatoração: .A C D= , o sistema linear .A x b=
rr 
pode ser escrito como . .C D x b=
rr .
Se .y D x=
r r
, então resolver o sistema linear .A x b=
rr é equivalente a resolver o 
sistema linear .C y b=
rr
 e, em seguida, o sistema linear .y D x=
r r
.
Vantagem em resolver um sistema linear utilizando processos de fatoração:
Podemos resolver qualquer sistema linear que tenha A como matriz dos coeficientes. Se 
o vetor b
r
 for alterado, a resolução do sistema será quase imediata.
A fatoração L.U é um dos processos de fatoração mais empregados. Nesta fatoração a 
matriz L é triangular inferior com diagonal unitária e a matriz U é triangular superior.
Cálculo dos fatores L e U.
Os fatores L e U podem ser obtidos através de fórmulas para os elementos ijl e 
iju , ou então, podem ser construídos usando a idéia básica da Eliminação de Gauss.
Vamos utilizar um exemplo teórico de dimensão três.
11 1 12 2 13 3 1
21 1 22 2 23 3 2
31 1 32 2 33 3 3
a x a x a x b
a x a x a x b
a x a x a x b
+ =


+ =

 + =

Vamos trabalhar somente com a matriz dos coeficientes. 
Seja: 
(0) (0) (0)
11 12 13
(0) (0) (0) (0)
21 22 23
(0) (0) (0)
31 32 33
a a a
A A a a a
a a a
 
 
= =
 
 
 
Os multiplicadores da primeira etapa do processo de Eliminação de Gauss são:
(0)(0)
3121
21 31(0) (0)
11 11
e
aa
m m
a a
= = (supondo que (0)11 0a ≠ )
Para eliminar ix da linha i, i = 2,3 vamos multiplicar a linha um por 1im− e 
subtraímos o resultando da linha i.
Os coeficientes 
(0)
1 ja serão alterados para 
(1)
1 ja , onde:
(1) (0)
1 1j ja a= para j = 1, 2, 3 e
(1) (0) (0)
1 1ij j i ija a m a= − para i = 2,3 e j = 1, 2, 3
Estas operações correspondem a se pré-multiplicar a matriz (0)A pela matriz (0)M , onde 
(0)
21
31
1 0 0
1 0
0 1
M m
m
 
 
= −
 
 
−
 
, pois:
(0) (0) (0) (0) (0) (0)
11 12 13 11 12 13
(0) (0) (0) (0) (0) (0) (0) (0) (0) (0) (0)
21 21 22 23 21 21 11 22 21 12 23 21 13
(0) (0) (0) (0) (0) (0) (0)
31 31 32 33 31 31 11 32 31 12
1 0 0
. 1 0 .
0 1
a a a a a a
M A m a a a a m a a m a a m a
m a a a a m a a m a a
 
 
 
 
= − = − − −
 
 
 
 
− − −
 
 
(0) (0)
33 31 13m a
 
 
 
 
−
 
(1) (1) (1)
11 12 13
(0) (0) (1) (1) (1)
22 23
(1) (1)
32 33
. 0
0
a a a
M A a a A
a a
 
 
= =
 
 
 
Portanto, (0) (0) (1)M A A= onde (1)A é a mesma matriz obtida no final da etapa um do 
processo de Eliminação de Gauss.
Supondo agora que (1)22 0a ≠ , o multiplicador da etapa 2 será: 
(1)
32
32 (1)
22
a
m
a
= .
Para eliminar 2x da linha 3, multiplicamos a linha 2 por 32m e subtraímos o resultado da 
linha 3.
Os coeficientes 
(1)
1 ja serão alterados para:
(2) (1)
1 1j ja a= para j = 1, 2, 3 e
(2) (1)
2 2j ja a= para j = 2, 3
(2) (1) (1)
3 3 3 2j j j ja a m a= − para j = 2, 3
As operações efetuadas em (1)A são equivalentes a pré-multiplicar (1)A por (1)M , onde
(1)
32
1 0 0
0 1 0
0 1
M
m
 
 
=
 
 
−
 
, pois:
(1) (1) (1) (1) (1) (1)
11 12 13 11 12 13
(1) (1) (1) (1) (1) (1)
22 23 22 23
(1) (1) (1) (1) (1) (1)
32 32 33 32 32 22 33 32 23
1 0 0
0 1 0 . 0 0
0 1 0 0
a a a a a a
M A a a a a
m a a a m a a m a
   
 
   
 
= =
   
 
   
 
− − −
 
   
(2) (2) (2)
11 12 13
(1) (1) (2) (2)
22 23
(2)
33
0
0 0
a a a
M A a a
a
 
 
=
 
 
 
Portanto, (1) (1) (2)M A A= onde (2)A é a mesma matriz obtida no final da etapa dois do 
processo de Eliminação de Gauss.
Temos então que:
(0)A A=
(1) (0) (0) (0)
(2) (1) (1) (1) (0) (0) (1) (0)
A M A M A
A M A M M A M M A
= =
= = =
Onde (2)A é triangular superior.
É fácil verificar que:
( ) 1(0) 21
31
1 0 0
1 0
0 1
M m
m
−
 
 
=
 
 
 
 e ( ) 1(1)
31
1 0 0
0 1 0
0 1
M
m
−
 
 
=
 
 
 
Assim,
( ) ( )1 1(0) (1) 21
31 32
1 0 0
. 1 0
1
M M m
m m
− −
 
 
=
 
 
 
Então, ( ) ( ) ( )1 1 1(1) (0) (2) (0) (1) (2)A M M A M M A− − −= =
(2) (2) (2)
11 12 13
(2) (2)
21 22 23
(2)
31 32 33
1 0 0
1 0 . 0 .
1 0 0
a a a
A m a a LU
m m a
 
 
 
 
= =
 
 
 
 
 
 
Ou seja: ( ) ( )1 1(0) (1) (2)eL M M U A− −= =
Isto é, fatoramos a matriz A em duas matrizes triangulares inferior com diagonal 
unitária e seus elementos ijl para i j> são os multiplicadores ijm obtidos no processo 
da Eliminação de Gauss; o fator U é triangular superior e é a matriz triangular superior 
obtida na fase da triangularização do método de Eliminação de Gauss.
Perguntas:
.A LU= sempre existe para qualquer A?
Se .A LU= existe, ela é única?
Estas perguntas podem ser respondidas pelo teorema a seguir:
Teorema: nxnA R∈ admite fatoração L.U se det( (1: ,1: )) 0A k k ≠ , para k = 1:n-1. Se a 
fatoração L.U existe e A é uma matriz não singular (determinante diferente de zero) 
então a fatoração L.U. é única.
Resolução do Sistema Linear .A x b=
rr
 através da fatoração da matriz A em L.U.
Dados o sistema linear .A x b=
rr e a fatoração L.U. da matriz A, temos:
 .A x b=
rr
Como .A LU= , logo
. .LU x b=
rr
Seja .U x y=
r r
. A solução do sistema poderá ser obtida da resolução dos sistemas 
lineares triangulares .L y b=
rr
 e .U x y=
r r
.
Exemplo:
Uma fábrica produz três tipos de ração: A, B e C. Para a produção ela necessita de uma 
unidade de pacote para cada tipo de ração. Para fabricar a ração A são necessários 3 kg 
de carne e 10 quilos de cereal. Para a ração B, 5 quilos de carne e 20 de cereal e a ração 
C, 9 quilos de carne e 50 de cereal. A fábrica possui um contrato de compra de 100 
pacotes, 600 quilos de carne e 2800 quilos de cereal. Quanto produzir de cada tipo de 
ração utilizando todos os recursos disponíveis?
Primeiro organizamos os dados em uma tabela:
A B C
Pacote 1 1 1
Carne 3 5 9
Cereal 10 20 50
Variável de decisão do modelo:
ix : quantidade de cada ração do tipo i (1, 2 e 3) a ser produzida.
Com os dados da tabela e o contrato de compra temos o sistema linear a seguir:
1 2 3
1 2 3
1 2 3
100
3 5 9 600
10 20 50 2800
x x x
x x x
x x x
+ + =


+ + =

 + + =

Etapa 1: Fatoração L.U:
2 1 2
3 1 3
1 1 1
3 5 9 3
10 20 50 10
L L L
L L L
 
 
= − +
 
  = − +
 
3 2 3
1 1 1
0 2 6
0 10 40 5L L L
 
 
 
  = − +
 
1 1 1
0 2 6
0 0 10
 
 
 
 
 
Logo: 
1 1 1
0 2 6
0 0 10
U
 
 
=
 
 
 
e 
1 0 0
3 1 0
10 5 1
L
 
 
=
 
 
 
Etapa 2: Resolução do sistema .L y b=
rr
:
1
2
3
1 0 0 100
3 1 0 . 600
10 5 1 2800
y
y
y
     
     
=
     
     
     
100
300
300
y
 
 
=
 
 
 
Etapa 2: Resolução do sistema .U x y=
r r
:
1
2
3
1 1 1 100
0 2 6 . 300
0 0 10 300
x
x
x
     
    
=
     
     
     
10
60
30
x
 
 
=
 
 
 
Logo, a fábrica deve produzir 10 quilos da ração A, 60 quilos da ração B e 30 quilos da 
ração C.
E se o contrato de compra for alterado para 150 pacotes, 650 quilos de carne e 2750 
quilos de cereal. Quanto produzir de cada tipo de ração utilizando todos os recursos 
disponíveis?
Lista 11: Fatoração L.U.
1) Resolva os sistemas A bx = , utilizando a fatoração LU., 3 casas decimais. 
Encontre E e ||E ||.
a)










−
−
−−
=
132
320
211
A 










−
−
=
4
1
2
b

 










=
0
0
0
b

b)












−
=
3960
2222
1134
0511
A 












−
−
=
15
0
13
15
b

 












−
−
=
10
0
10
10
b

c)










−
−
−
=
112
344
132
A 










−
=
1
3
5
b

 










−
=
2
6
10
b

d)










−
=
121
126
226
A 










=
3
2
1
b

 










−
=
2
6
10
b

2) Um fabricante de objetos de cerâmica produz jarras e pratos decorativos. Cada jarra 
exige 16 minutos de modelagem, 12 minutos de polimento e 2 minutos de pintura. 
Cada prato decorativo necessita de 30 minutos de modelagem, 15 de polimento e 10 
de pintura. Cada xícara necessita 8 minutos de polimento, 6 minutos de modelagem 
e 3 minutos de pintura. Sabendo-se que são reservadas 8 horas para modelagem, 4 
horas para polimento e 13 horas para pintura, encontre a quantidade de cada tipo de 
objeto que deverá ser fabricada por semana a fim de utilizar todo o tempo 
disponível. 
Jarras Pratos 
decorativos
Xícaras Minutos por 
semana
Modelagem 16 12 2 480
Polimento 30 15 10 780
Pintura 8 6 3 240