ayuayu
Páginas: 28 (6948 palabras)
Publicado: 4 de junio de 2014
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
...
Leer documento completo
Regístrate para leer el documento completo.