Aula 07 e 08 Decomposicao LU

Prévia do material em texto

Resolvendo Sistemas Lineares por 
Decomposição LU
• Consideremos os seguintes abordagens:
1) Mostrar como um sistema linear Ax = b pode ser resolvido, 
fatorando a matriz A em duas matrizes triangulares (superior e 
inferior), e
2) Como construir tal fatoração
2
Decomposição em LU
• O objetivo é fatorar a matriz dos 
coeficientes A em um produto de duas 
matrizes L e U.
– Seja:
nn
n
n
n
nnn u
uu
uuu
uuuu
mmm
mm
m
LU










000
00
0
1
0
01
001
0001
333
22322
1131211
321
3231
21
• Definição
Uma fatoração de uma matriz quadrada A com A = LU, onde L 
é triangular inferior e U é triangular superior, é chamada uma 
fatoração ou decomposição LU ou, ainda, decomposição 
triangular da matriz A.
• Teorema 1
Se A é uma matriz quadrada que pode ser reduzida à forma
escalonada por linhas U por eliminação gaussiana sem troca
de linhas, então A pode ser fatorada como
A = LU,
onde L é uma matriz triangular inferior.
• Se uma matriz A de tamanho n x n puder ser fatorada num
produto de matrizes n x n como
A = LU
onde L é triangular inferior e U é triangular superior, então o
sistema linear A x = b pode ser resolvido como segue:
Passo1. reescrever o sistema A x = b como LU x = b (1)
Passo2. definir uma nova matriz y de tamanho n x 1 por U x = y (2)
Passo3. usar (2) para escrever (1) como L y = b e resolver esse sistema 
em y.
Passo4. substituir y em (2) e resolver em x.
• Observação: embora esse procedimento substitua o problema
de resolver um único sistema A x = b, pelo problema de
resolver dois sistemas Ly = b e U x = y, esses dois sistemas
são fáceis de resolver, pois usam matrizes triangulares.
Exemplo: resolvendo um sistema por fatoração
100
310
131
734
013
002
294
083
262
3
2
2
294
083
262
3
2
1
x
x
x
Considerando-se válida a fatoração
usar o método descrito para resolver o sistema
Soluçao: Passo1. reescrever o sistema A x = b como LU x = b
3
2
2
100
310
131
734
013
002
3
2
1
x
x
x
(continua)
(1)
Exemplo: resolvendo um sistema 
por fatoração (continuação)
3
2
1
3
2
1
100
310
131
y
y
y
x
x
x
(continua)
Passo2. definir uma nova matriz y de tamanho n x 1 por
U x = y
Passo3. usar (2) para escrever (1) como L y = b e resolver esse sistema em y.
3
2
2
734
013
002
3
2
1
y
y
y
3734
23
22
321
21
1
yyy
yy
y
ou 
Para resolver esse sistema o procedimento é similar à retro-substituição,
exceto que as equações são resolvidas de cima para baixo. 
Esses procedimento é chamado substituição direta.
O resultado é
25,1 321 yeyy
(2)
Resolvendo um Sistema por 
Fatoração (continuação)
O resultado, usando retro-substituição é
21,2 321 xexx
Passo4. substituir y em (2) e resolver em x.
3
2
1
3
2
1
100
310
131
y
y
y
x
x
x
2
5
1
100
310
131
3
2
1
x
x
x
(2)
portanto
2
53
13
3
32
321
x
xx
xxxou
8
Decomposição em LU
• Para se obter os elementos da matriz L e 
da matriz U, deve-se calcular os 
elementos das linhas de U e os 
elementos da colunas de L como segue.
9
Decomposição em LU
• E a matriz coeficiente A:
– Têm-se:
nn3n2n1n
n22221
n11211
aaaa
aaa
aaa
A



nn
n333
n22322
n1131211
nn3n2n1n
3231
21
nn3n2n1n
n22221
n11211
u000
uu00
uuu0
uuuu
mmmm
0
01mm
001m
0001
]LU[
aaaa
aaa
aaa
A













10
Decomposição em LU
• 1ª linha de U: Faze-se o produto da 1ª
linha de L por todas as colunas de U e a 
iguala com todos os elementos da 1ª linha 
de A, assim:
.n,...,2,1j,au
,auau1
,auau1
,auau1
j1j1
n1n1n1n1
12121212
11111111

11
Decomposição em LU
• 1ª coluna de L: Faz-se o produto de todas 
as linhas de L, (da 2ª a até a nª), pela 1ª
coluna de U e a iguala com os elementos 
da 1ª coluna de A, (abaixo da diagonal 
principal), obtendo ,
.n,...,2,1l,
u
a
m
,
u
a
maum
,
u
a
maum
,
u
a
maum
11
1l
1l
11
1l
1l1l111l
11
31
31311131
11
21
21211121

12
Decomposição em LU
• 2ª linha de U: Faz-se o produto da 2ª
linha de L por todas as colunas de U, (da
2ª até a nª), e igualando com os 
elementos da 2ª linha de A, (da diagonal 
principal em diante), obtêm-se ,
.n,...,3j,umau
,umauauum
,umauauum
,umauauum
j121j2j2
n121n2n2n2n2n121
1321232323231321
1221222222221221

13
Decomposição em LU
• 2ª coluna de L: Faz-se o produto de todas 
as linhas de L (da 3ª até a nª) pela 2ª
coluna de U e a iguala com os elementos 
da 2ª coluna de A, (abaixo da diagonal 
principal), obtendo ,
.n,...,3l,
u
uma
m
,
u
uma
maumum
,
u
uma
maumum
,
u
uma
maumum
22
121l2l
2l
22
121l2l
2l2l222l121l
22
124142
424222421241
22
123132
323222321231

14
Decomposição em LU
• Temos a seguinte fórmula geral:
.jl,u/)uma(m
,jl,umau
jjkjlkljlj
1l
1k
kjlkljlj
Método para se encontrar uma decomposição LU
• Passo 1. reduzir A à forma escalonada por linhas U por eliminação
gaussiana sem troca de linhas, mantendo armazenados os
multiplicadores usados para introduzir os pivôs (líderes) e os
multiplicadores utilizados para introduzir os zeros abaixo dos pivôs.
• Passo 2. em cada posição ao longo da diagonal principal de L,
colocar o recíproco do multiplicador que introduziu o pivô naquela
posição em U.
• Passo 3. em cada posição abaixo da diagonal principal de L,
colocar o negativo do multiplicador utilizado para introduzir o zero
naquela posição em U.
• Passo 4. formar a decomposição A = LU.
A decomposição LU tem como variantes os elementos da 
matriz diagonal 
•Método de Doolittle :
• Método de Crout : 
• Método de Cholesky : 
1iiU
1iiL
iiii UL
Método de Doolittle
Decomposição LU com lii = 1
Faz a geração de ambas as linhas de L e U
Fortemente adaptável a eliminação gaussiana e armazenada
Vantagens quando a matriz é armazenada por linhas
Os elementos de L são dados 
jiparauulal jj
j
k
kjikijij /)(
1
1
jiparaulau
i
k
kjikijij )(
1
1
Enquanto os elementos de U são dados por
3234
22
1423
321
321
321
xxx
xxx
xxx
234
211
423
A
3
2
1
b
333231
232221
131211
33
2322
131211
3231
21
00
0
1
01
001
aaa
aaa
aaa
u
uu
uuu
ll
l
u11 = a11 = 3; u12 = a12 = 2; u13 = a13 = 4;
jiparaulau
i
k
kjikijij )(
1
1
u22= a22 - l21u12; u23 = a23 - l21u13; 
*00
**0
423
U
u33 = a33 - l31u13 - l32u23
jiparauulal jj
j
k
kjikijij /)(
1
1
Os elementos de L são dados
l21 = a12/ u11 = 1/3; 
l31 = a31/u11 = 4/3; 
113/4
013/1
001
L
l32 = [3 - (4/3).2]/1/3 = 1 
400
3/23/10
423
U
u22 = 1 - (1/3).2 = 1/3 
u23 = 2 - (1/3).4 = 2/3 
u33 = 2 - (4/3).4 – 1.(2/3) = - 4;
Logo a solução do sistema é x1= -3; x2 = 5; x3 = 0
Propriedades da decomposição LU
P1: O det (A) é a multiplicação dos elementos da diagonal
principal da matriz U
P2: Dado que A = LU, então A-1=U-1.L-1
P3: Uma dada matriz A pode não ser decomponível na forma
LU se existir submatrizes com det = 0
 
123
111
122
A1
363
742
321
A 2
Método de Crout
• Decomposição LU com 
• Faz a geração das colunas deL e linhas de U.
• Possui como estrutura:
niAL ii ..1,11 njLAU ij ..2,/ 1111
1iiU
1
1
..2,
j
k
kjikijij niijULAL
njji
L
ULA
U
ii
i
k
kjikij
ij ..3,
1
1
Teorema 1: Dada uma matriz quadrada A de ordem n, seja Ak a
matriz constituída das primeiras k linhas e colunas de A. Suponha
que det(Ak) 0 para k = 1, 2, …, (n-1).
Então, existe uma única matriz triangular inferior
L = (lii), com lii = 1, 1 i n e uma única matriz triangular superior
U = (uij) tais que A = LU.
Ainda mais, det(A) = u11u22…unn.
Complexidade da Decomposição LU
bZL
Quão mais rápida e melhor a Decomposição 
LU em relação a Eliminação Gaussiana.
Complexidade
n = número de equações
Para decompor [A], a complexidade será
Para resolver:
Com complexidade
3
3n
bXU
2
2n
Complexidade da Decomposição LU
Portanto a complexidade será proporcional a:
2
3
3
n
n
)
2
(2
3
23 nn
or
Enquanto que a eliminação gaussiana será:
23
23 nn
Qual será o melhor?
Complexidade da Decomposição LU
)
2
n
3
n
(m
23
)n(m
3
n 2
3
51033.8
Complexidade do Vetor Independente
Na decomposição LU da [A] é independente do vetor [b], portanto 
somente uma vez:
Seja m = o número de vezes que o vetor [b] é trocado
The computational times are proportional to
Eliminação Gaussiana = Decomposição LU=
Considere um conjunto de 100 variaveis com 50 elementos dos 
lados direito do vetor. Então:
LU Decomposition = Gauss Elimination = 71069.1
Complexidade da Decomposição LU
Outra vantagem
Encontrar a inversa da matriz
LU Decomposition Gauss Elimination
3
4
)(
3
3
2
3 n
nn
n
2323
3423 nnnn
n
Para valores grandes de n
3
4
23
334 nnn
27
• Exemplo:
– O resíduo calculado é:
– Vê-se pelo resíduo que a precisão alcançada 
não foi satisfatória.
– O vetor x(0) é chamado de vetor solução.
594,0
594,0
214,0
042,0
Axbr )0()0(
Erros – Resíduo
28
• Exemplo:
– Com o intuito de melhorar a solução, considera-
se um novo vetor x(1) chamado de vetor solução 
melhorado.
Erros – Resíduo
29
• Exemplo:
– De forma que : x(1) = x(1) + δ(0), onde δ(0) é o vetor 
de correção. Assim:
)0()0(
)0()0(
)0()0(
)0()0(
)1(
rA
AxbA
bAAx
b)x(A
bAx
Erros – Resíduo
30
• Exemplo:
– Calcular o vetor de correção:
594,0
594,0
214,0
042,0
5,212,130,810,21
4,115,238,83,53
1,455,118,85,24
0,113,90,37,8
4
3
2
1
Erros – Resíduo
31
• Exemplo:
– A solução é:
0000,0
0294,0
0195,0
0295,0
)0(
Erros – Resíduo
32
• Exemplo:
– Desta forma, a solução melhorada será:
0000,1
9999,0
0000,2
0000,1
xx )0()0()1(
Erros – Resíduo
33
• Exemplo:
– Cujo novo resíduo é:
013,0
024,0
011,0
009,0
Axbr )1()1(
Erros – Resíduo
34
• Exemplo:
– Utilizando o mesmo procedimento, têm-se que:
x(2)=x(1)+δ(1)
– Assim, o vetor correção, calculado por A 
δ(1)=r(1), é:
0000,0
0007,0
0002,0
0002,0
)1(
Erros – Resíduo
35
• Exemplo:
– Acha-se assim uma solução melhorada:
0000,1
0000,1
0000,2
0000,1
x )2(
Erros – Resíduo
36
• Exemplo:
– Que possui resíduo:
0
0
0
0
r )2(
Erros – Resíduo
37
Sistemas Lineares - Bibliografia
– Ruggiero, M. A. Gomes & Lopes, V. L. da R. Cálculo 
Numérico: Aspectos teóricos e computacionais. MAKRON 
Books, 1996, 2ª ed.
– Asano, C. H. & Colli, E. Cálculo Numérico: Fundamentos e 
Aplicações. Departamento de Matemática Aplicada 
– IME/USP, 2007.
– Sanches, I. J. & Furlan, D. C. Métodos Numéricos. 
DI/UFPR, 2006.
– Paulino, C. D. & Soares, C. Erros e Propagação de Erros, 
Notas de aula, SE/ DM/ IST [Online] 
http://www.math.ist.utl.pt/stat/pe/qeb/semestre_1_2004-
2005/PE_erros.pdf [Último acesso 07 de Junho de 2007].