ayuayu

Factorizaci´n PA=LU
o
Prof. I. Huerta
Facultad de Matem´ticas
a
UC
ihuerta@mat.puc.cl
Septiembre 2008

Factorizaci´n PA=LU
o

Aplicaciones

Factorizaciones
(Dividir para Conquistar)
• La estrategia consiste en expresar una operaci´n complicada como la
o
composici´n de varias sencillas.
o
• Esto permite revertir una operaci´n complicada revirtiendo una sucesi´n
o
o
deoperaciones sencillas
• En matrices, la estrategia consiste en expresar una matriz A como el
producto de matrices sencillas.
• Por ejemplo, para la composici´n A = BC tenemos
o

1

Factorizaci´n PA=LU
o

Aplicaciones

Ax = b ⇔ B

Cx

=b⇔

By = b
Cx = y

y
Entonces, para resolver Ax = b, donde A = BC, se hace lo siguiente
• Resuelva By = b
• Resuelva Cx = y
En general, sitenemos la factorizaci´n
o
A = A1 A 2 · · · A k
entonces para resolver Ax = b, se resuelven sucesivos sistemas de ecuaciones
• x0 = b
2

Factorizaci´n PA=LU
o

Aplicaciones

• Para i = 1, 2, . . . , k, resuelva Aixi = xi−1
• x = xk
Si A es invertible, entonces resolver Ax = b es equivalente a calcular
x = A−1b SIN TENER LA INVERSA de A.

3

Factorizaci´n A=LU
o

Tabulaci´n deDatos
o

Al final del semestre habremos visto las factorizaciones
•
•
•
•
•
•
•
•

A es el producto de matrices elementales para A invertible.
P A = LU ( Factorizaci´n PALU para matrices generales)
o
A = LDLT (Cholesky sin ra´ cuadrada para sim´tricas)
ız
e
A = RT R (Cholesky con ra´ cuadrada para A sim´trica positiva definida)
ız
e
A = QR (Factorizaci´n QR para matricesgenerales)
o
A = V DV −1 (Diagonalizaci´n)
o
A = V DV T (diagonalizaci´n ortogonal para A sim´trica)
o
e
A = V ΣU (descomposici´n de valores singulares para A matriz general
o
de m × n)

4

Factorizaci´n A=LU
o

Tabulaci´n de Datos
o

Factorizaci´n A=LU
o
Sea A de m × n. La factorizaci´n A = LU
o
• se obtiene al llevar la matriz A a la forma escalonada U

usando exclusivamentela operaci´n elemental fila: sumar un m´ltiplo
o
u
de una fila a otra.
• la matriz escalonada U de m × n obtenida no tiene los pivotes iguales a
1 en general.
• La factorizaci´n A = LU expresa a cada fila de A como combinaci´n
o
o
lineal de las filas de U .
5

Factorizaci´n A=LU
o

Tabulaci´n de Datos
o

• la matriz L de m × m es triangular inferior con 1’s en la diagonal


10
1

0
0
1

 l2,1

L =  l3,1 l3,2
 .
 .
lm,1 lm,2 lm,3

···
···
···
...
···

0
0
0








1

• A = LU no siempre puede realizarse pues en ciertos casos hay
intercambios de filas forzados, en cuyo caso se obtiene la factorizaci´n
o
P A = LU .
• La ecuaci´n A = LU expresa a la fila i de A como combinaci´n lineal de
o
o
las filas de U con coeficientesen la fila i de L.

6

Factorizaci´n A=LU
o

Tabulaci´n de Datos
o

Hay dos maneras de ver la factorizaci´n P A = LU .
o
i) Matricial: interpretando a la eliminaci´n de gauss como multiplicaciones
o
por matrices elementales
ii) Vectorial: interpretando las filas de A como combinaciones lineales de las
filas de U .

7

Factorizaci´n A=LU
o

Tabulaci´n de Datos
o

Ejemplo 1.A

=

· · · E (−l )
2,1
2,1 
· · ·  −→ 
···




E3,1 (−l3,1 )

−→












0




· · · E (−l ) 
 3,2 3,2 
· · ·  −→ 
···

0
0

···

··· 
···
···


···  = U

···

0
0



0

Matricialmente
E3,2(−l3,2) E3,1(−l3,1) E2,1(−l2,1) A = U








1
0
0
1
0 0
1
0 0
 0
1
0  0
1 0   −l2,1 1 0 A = U
0 −l3,2 1
−l3,1 0 1
0
0 1
8

Factorizaci´n A=LU
o

Tabulaci´n de Datos
o

Entonces
A = (E2,1(−l2,1))−1 (E3,1(−l3,1))−1(E3,2(−l3,2))−1 U
1
0 0
A =  −l2,1 1 0 
0
0 1

−1

−1 

−1 



1
0 0
 0
1 0 
−l3,1 0 1

1
0
0
 0
1
0 
0 −l3,2 1

U

Por lo tanto
A = E2,1(l2,1) E3,1(l3,1) E3,2(l3,2) U

= LU

L


1

A =  l2,1
0

...