factorizacion cholesky

Factorizaci´n de Cholesky de matrices singulares
o
´
A.M. Urbano, R. Canto, B. Ricarte
Institut de Matem`tica Multidisciplinar, Universitat Polit`cnica de Val`ncia,
a
e
e
E-46022 Valencia
amurbano@mat.upv.es,rcanto@mat.upv.es,bearibe@mat.upv.es,
Resumen
Es conocido que toda matriz sim´trica definida positiva admite una unica face
´
torizaci´n de Cholesky, mientras que si la matriz essemidefinida positiva dicha
o
factorizaci´n no es, por regla general, unica. En este trabajo vamos a demostrar
o
´
que existe una unica factorizaci´n de Cholesky de rango completo en forma
´
o
escalonada para las matrices sim´tricas semidefinidas positivas. Los resultados
e
obtenidos pueden extenderse a matrices rectangulares A sin rango completo para
obtener la factorizaci´n de Choleskyde rango completo de la matriz sim´trica
o
e
semidefinida positiva AT A. Adem´s presentamos dos algoritmos que permiten
a
obtener la factorizaci´n de Cholesky de AT A sin necesidad de hacer el producto
o
de ambas matrices.
Secci´n en el CEDYA 2011: ALAMA
o

1.

Introducci´n
o

Dada una matriz A ∈ Rn×n con rank(A) = r < n, una factorizaci´n de la
o
forma A = F U , donde F ∈ Rn×r ,U ∈ Rr×n y rank(F ) = rank(U ) = r recibe
el nombre de factorizaci´n de rango completo de A. Dicha factorizaci´n no es
o
o
unica, pero s´ que lo es la factorizaci´n de rango completo en la que la matriz
´
ı
o
U est´ en forma escalona reducida superior unitaria.
a
Cuando la matriz A es sim´trica definida positiva es conocido que existe una
e
unica factorizaci´n de Cholesky A = LLT ,donde L es triangular inferior con
´
o
diagonal positiva, pero si A es sim´trica semidefinida positiva esta factorizaci´n
e
o
no es unica en general. Uno de los objetivos del trabajo es demostrar que existe
´
una unica factorizaci´n de Cholesky de rango completo (factorizaci´n CRC) de
´
o
o
la matriz A, de la forma A = LLT , donde L ∈ Rn×r es escalonada inferior y con
la entrada principalde cada columna positiva. Dicha factorizaci´n la obtenemos
o
aplicando a la matriz A el algoritmo de quasi-Gauss sin intercambio de filas [2].
Este resultado puede aplicarse para obtener la factorizaci´n CRC de la mao
triz semidefinida positiva AT A, donde A es una matriz rectangular sin rango
completo. Adem´s, presentamos dos algoritmos que permiten obtener dicha faca
torizaci´n sin realizarel producto de matrices AT A.
o

2.

Factorizaci´n CRC de matrices sim´tricas
o
e
semidefinidas positivas

Dada una matriz A ∈ Rn×n sim´trica semidefinida positiva y con rank(A) =
e
r < n, en la siguiente proposici´n se obtiene la factorizaci´n CRC de A sin
o
o
realizar intercambio de filas aplicando el algoritmo de quasi-Gauss [2]. Para ello
supondremos, sin p´rdida de generalidad,que A no tiene filas ni, por la simetr´
e
ıa,
columnas nulas. En caso contrario, si las filas de ´
ındices i1 , i2 , . . . , is fuesen
nulas premultiplicando y postmultiplicando A por las matrices I {i1 ,i2 ,...,is } y
( {i ,i ,...,i } )T
s
I 1 2
, respectivamente, obtenidas a partir de la matriz identidad de
¯
orden n sin las filas de ´
ındices i1 , i2 , . . . , is , obtenemos una matrizA sin filas ni
columnas nulas,
(
)T
¯
A = I {i1 ,i2 ,...,is } A I {i1 ,i2 ,...,is }
¯
A partir de la factorizaci´n CRC de A obtenemos la correspondiente factorizao
ci´n de la matriz A, es decir
o
((
)(
)T
)
¯
A = LA LT =⇒ A =
I {i1 ,i2 ,...,is } LA
LT I {i1 ,i2 ,...,is } = LLT
¯ A
¯
¯
¯
A
e
Proposici´n 1. Consideremos la matriz A ∈ Rn×n sim´trica semidefinida poo
sitiva conrank(A) = r y sin filas ni columnas nulas. Existe la factorizaci´n
o
CRC de A, A = LLT , donde L ∈ Rn×r es escalonada inferior y con la entrada
principal de cada columna positiva.
Demostraci´n: Como A es semidefinida positiva y no tiene filas ni columnas
o
nulas, todos los elementos de la diagonal principal son positivos. Supongamos
que podemos aplicar el algoritmo de Gauss sin intercambio...