fatoracao_LU

Prévia do material em texto

16/04/2010
1
FATORAÇÃO LUFATORAÇÃO LU
Railei Garcia Leal
Raimundo Viana de Castro
Sistema de equações lineares
Um sistema linear com m equações e n
variáveis é escrito, usualmente, na forma:
a11x1 + a12x2 + ... + a1nxn = b111 1 12 2 1n n 1
a21x1 + a22x2 + ... + a2nxn = b2
. . . . (1)
. . . . 
. . . .
am1x1 + am2x2 + ... + amnxn= bm
aij : coeficientes 1 ≤ i ≤ m, 1 ≤ j ≤ n
xj : variáveis j = 1, 2, ..., n
bi : constantes i = 1, 2, ..., m
Sistemas de Equações Lineares
Resolver um sistema linear consiste em calcular
os valores de xj, (j = 1, ..., n), caso eles existam,
que satisfaçam as m equações
simultaneamente .
Uma outra forma de expressar o sistema (1) é
através da notação matricial, como:
Ax = b (2)
onde 
a11 a12 ... a1n 
a21 a22 ... a2n 
A = . . . é a matriz dos coeficientes , 
. . . 
. . . 
am1 am2 ... amn 
x1 b1
x2 b2
. .
X = é o vetor das variáveis e b = . É o vetorX . é o vetor das variáveis e b . É o vetor 
. 
xn bm 
constante.
16/04/2010
2
Problema da existência e 
unicidade
Num sistema linear apenas uma entre as
situações abaixo irá ocorrer:
1) o sistema linear tem solução única;
2) o sistema linear admite infinitas soluções;
3) i t li ã d it l ã3) o sistema linear não admite solução.
Métodos numéricos 
Os métodos numéricos para resolução de umOs métodos numéricos para resolução de um
sistema linear podem ser divididos em dois
grupos:
1) Métodos diretos: fornecem a solução exata do
sistema linear, caso ela exista, após um número
finito de operações;finito de operações;
2) métodos iterativos: geram uma sequência de
vetores x(k) , a partir de uma aproximação
inicial x(0). Sob certas condições esta sequência
converge para a solução caso ela exista.
Justificativa para este estudo
z A resolução de Sistemas de equações lineares podez A resolução de Sistemas de equações lineares pode
ser inviável ou ineficiente, para sistemas de ordem
muito grandes.
z Grande parte de sistemas lineares podem ser
resolvidos com métodos de resolução relativamente
simples, como o método da Eliminação de Gauss e
fatoração LUfatoração LU.
z O surgimento de novos métodos é decorrente da
necessidade de se obter algoritmos que sejam mais
eficientes e menos sensíveis a erros.
Fatoração LU
A base deste método, assim
como o método da eliminação
de Gauss, é o uso de uma
propriedade elementar de
sistemas de equações linearessistemas de equações lineares
que estabelece o seguinte:
16/04/2010
3
Fatoração LU
A solução de um sistema linear Ax = b não se 
lt b t üê i daltera se o submetermos a uma seqüência de 
operações tais como:
z multiplicação de uma equação (linha) por uma 
constante não nula;
z soma do múltiplo de uma equação a outra;
z troca de posição de duas ou mais equações. 
Fatoração LU
z Seja o sistema linear: 
Ax=bAx b
z O processo consiste em decompor a matriz A em 
duas outras matrizes L e U, isto é,
A=LU 
z O sistema anterior fica:z O sistema anterior fica:
(LU)x=b
Fatoração LU
z A partir de (LU)x=b, fazendo 
y=Uxy=Ux
z temos então dois sistemas:
i) Ly=b
ii) Ux=y
Idéi t i L U f t i lz Idéia: se as matrizes L e U forem triangulares, a 
solução desses sistemas é imediata. Encontrar tais 
matrizes é a estratégia de solução.
Fatoração LU
Procedimento:
9 Decompõe-se a matriz A em uma matriz L 
triangular inferior e uma matriz U triangular 
superior pelo método de Eliminação de Gauss:
A = LU
9 Resolvem-se os sistemas triangulares resultantes:
L bLy=b 
Ux=y
16/04/2010
4
Exemplo - Fatoração LU
z Seja, por exemplo, o sistema:
⎧ 1423
z 1º passo: aplica-se o método de Eliminação de 
⎪⎩
⎪⎨
⎧
=++
=++
=++
3234
22 
1423
321
321
321
xxx
xxx
xxx
Gauss na matriz A para se obter L e U
211
423
0A )( ⎟⎟
⎞
⎜⎜
⎛
Obtenção dos fatores LU
41 
234
2110 A )( ⎟⎟
⎟
⎠⎜
⎜⎜
⎝
=
3
4
3
1
3121 == ; mm
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
=⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
⋅⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
=
−
3
10
3
1
3
2
3
1
31
21
1
0
0
423
234
211
423
10
01
001
-m
-mA )( 132 =m
⎞⎛⎞⎛⎞⎛ 423423001
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
−
=⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
⋅⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
=
− 400
0
423
0
0
423
10
010
001
3
2
3
1
3
10
3
1
3
2
3
1
32
2
-m
A )(
Obtenção dos fatores LU
z Se chamarmos de M(k) as matrizes que contêm os
multiplicadores na k-ésima etapa da eliminação de Gauss,p p ç ,
então:
A = A(0)
A(1) = M(0)A(0) = M(0)A
A(2) = M(1)A(1) = M(1)M(0)A(0) =M(1)M(0)A
z Da última linha, temos:
1 1A=(M(1)M(0))-1A(2) = (M(0))-1 (M(1)) -1 A(2)
z donde, 
L = (M(0)) -1(M(1)) -1 e U = A(2)
Obtenção dos fatores LU
z Então, para a matriz A dada, temos
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
−
=⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
=
400
0
423
 e 
11
01
001
3
2
3
1
3
4
3
1 UL
16/04/2010
5
Solução dos subsistemas
z 2º passo: resolver os dois sistemas lineares 
i l t btid l b tit i ã A LUequivalentes, obtidos pela substituição A=LU
i) Ly = b
ii) Ux=y
⎪⎩
⎪⎨
⎧
=++
=+
=
3 4/3
2 1/3
1 
321
21
1
yyy
yy
y
⎪⎧ =++ 14 2 3 321 xxx ⎞⎛−3
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
=
0
 
1
3
5y
⎪⎩
⎪⎨
=−
=+
04 
3/53/21/3
3
32
321
x
xx
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛−
=
0
5
3
*x
Estratégias de pivoteamento
z Considere o cálculo dos multiplicadores no método 
d Eli i ã d Gde Eliminação de Gauss:
z O que acontece se o pivô (akk) for zero ou se estiver 
ó i d ?
,...,nki,...,n-k
a
a m
kk
ik
ik 1 ,11 , +===
próximo de zero?
Pivoteamento Parcial
z Na etapa k, escolher para pivô o elemento de maior 
ód l tmódulo entre aik, i=k,k+1,...,n;
z Trocar as linhas k e i para determinar a posição do 
i ô á i
ki
ika
≥
||max
novo pivô, se necessário.
Exemplo: Pivoteamento 
Parcial
3 3||max temos2,k e 4 Para 32
2
2 −==⇒===
≥
apivôan
i
i
Logo, trocamos as linhas 2 e 3:
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
=
15
7
6
5
 
0 
7 
3 
1-
 
4 
5-
0 
1 
 
2 
3-
1 
2 
 
0
0
0
3
| )1()1( bA
g
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
=
15
6
7
5
 
0 
3 
7 
1-
 
4 
0 
5- 
1 
 
2 
1 
3- 
2 
 
0
0
0
3
| )1()1( bA
16/04/2010
6
Pivoteamento Completo*
z Na etapa k, escolher para pivô o elemento de maior 
ód l t t d l t i d tmódulo entre todos os elementos que ainda atuam 
no processo de eliminação:
z Trocar as linhas k e i e as colunas k e j, para 
determinar a posição do novo pivô se necessário
kji
ija
≥,
||max
determinar a posição do novo pivô, se necessário.
*Obs: esta estratégia não é muitoempregada, pois acarreta em maior 
esforço computacional
Ex.: Pivoteamento Completo
7 7||max temos2,k e 4 Para 34
2,
==⇒===
≥
apivôan
ji
ij
Logo, trocamos as linhas 2 e 3 e as colunas 2 e 4:
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
=
15
7
6
5
 
0 
7 
3 
1-
 
4 
5-
0 
1 
 
2 
3-
1 
2 
 
0
0
0
3
| )1()1( bA
g
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
=
15
6
7
5
 
2 
1 
3-
2 
 
4 
0 
5- 
1 
 
0 
3 
7 
1- 
 
0
0
0
3
| )1()1( bA
O primeiro exemplo conhecido do uso de uma matriz
aumentada para descrever sistemas lineares aparece no
livro chinês “Nove Capítulos de Arte Matemática” publicado
entre 200 a.C. e 100 a.C.durante a dinastia de Han.
z Problema proposto pelo manuscrito: Existem três tipos de milho,
dos quais dois montes do primeiro três do segundo e um dodos quais dois montes do primeiro, três do segundo e um do
terceiro totalizam 34 medidas. três montes do primeiro, dois do
segundo e um do terceiro totalizam 39 medidas. Finalmente, um
monte do primeiro, dois do segundo e três do terceiro totalizam
26 medidas. Quantas medidas de milho estão contidas em um
monte de cada um dos tipos?
z O Problema leva a um sistema linear de três equações e três
incógnitas.
z Resolva o problema utilizando o método do LU com
pivoteamento parcial.
Informações retiradas de [1]
Complexidade dos algoritmos
Gráfico da dimensão da matriz (n) × número de operações em ponto
flutuante necessárias para a inversão da matriz pelo método de
Eliminação de Gauss (vermelho) e pela Fatoração LU (preto).
16/04/2010
7
Observação
Para encontrarmos a inversa de uma matriz
de ordem 3, pelo método de Eliminação de
Gauss, efetuamos n × ( (4n3+9n2-7n)/6 ) = 84
operações .Utilizando a fatoração
LU,efetuamos (4n3+15n2-n)/6 ) = 40
operações.