Factorizacion De Choleski

Factorizaciones de Cholesky, matrices definidas
y semidefinidas positivas
H´ector Manuel Mora Escobar
Universidad Central, Bogot´a
hectormora@yahoo.com
Junio de 2011

1

Introducci´
on

Este documento presenta, con ejemplos, varios algoritmos ampliamente conocidos para la factorizaci´on de Cholesky incluyendo la adaptaci´on para matrices semidefinidas positivas.
La factorizaci´on usual deCholesky se puede usar u
´nicamente para matrices
definidas positivas. En optimizaci´on o en econom´ıa, se necesita saber frecuentemente si una matriz es semidefinida positiva, para aplicar condiciones
de segundo orden o para averiguar si una funci´on es convexa. Te´oricamente
esto se puede hacer mediante el c´alculo de los valores propios, pero, num´ericamente, este proceso es mucho m´as demorado que lafactorizaci´on de Cholesky.

2

Definiciones y notaci´
on

Existen muchos art´ıculos y textos que tratan la factorizaci´on de Cholesky,
en este documento se usaron [AlK02], [Dem97], [GoV96], [Hig90], [Hig08],
[Mor01], [Ste98], [TrB97].

1

Sea A ∈ Rn×n una matriz sim´etrica. Se dice que A es definida positiva si
xT Ax > 0 para todo x no nulo en Rn×1 .

(1)

Se dice que A es semidefinida positivasi
xT Ax ≥ 0 para todo x en Rn×1 .

(2)

Son usuales las notaciones A 0 y A 0 para las matrices definidas positivas
y semidefinidas postivas, respectivamente. Obviamente toda matriz definida
positiva es semidefinida positiva. En este documento, mientras no se diga lo
contrario, todas las matrices son reales y cuadradas de tama˜
no n × n. Todos
los vectores son vectores columna y se puedenescribir como una n-upla o
expl´ıcitamente como un vector columna:
 
x1
 x2 
 
x = (x1 , x2 , ..., xn ) =  .. 
.
xn
xT = x1 x2 ... xn .
Uma matriz sim´etrica tiene factorizaci´on de Cholesky si existe U triangular
superior invertible tal que
A = U T U.

(3)

Si los elementos diagonales de U son positivos, la factorizaci´on es u
´nica.
Por esto, se puede hablar de la factorizaci´on de Cholesky.Algunas veces
se presenta la factorizaci´on de Cholesky como A = L LT con L triangular
inferior. Otras veces se presenta la factorizaci´on de Cholesky
A = V TD V
con D matriz diagonal invertible y V triangular superior con unos en la
diagonal.
En este documento se utiliza algunas veces la siguiente notaci´on de Matlab
y Scilab, mezclada con la notaci´on usual de matem´aticas. La i-´esima fila
de Ase puede denotar por Ai· o por A(i, :). De manera an´aloga para las
2

columnas: A·j o A(:, j) . A(i : j, k : l) es la submatriz de A obtenida con
las filas i, i + 1, ..., j y con las columnas k, k + 1, ..., l. Si p es un vector
con enteros entre 1 y n, entonces A(:, p) es la submatriz de A obtenida con
las columnas cuyo ´ındice est´a en p. El elemento (entrada) de A en la fila i
y columna j sedenotar´a indiferentemente por aij o por A(i, j). La funci´on
triu(A) construye una matriz triangular superior con la parte triangular
superior de A.
Sean λ1 , λ2 , ..., λn los valores propios de A. Si A es sim´etrica, todos son
reales. Sea
δi = det( A(1 : i, 1 : i) ), i = 1, ..., n.
En particular, δ1 = a11 , δn = det(A). Sea A sim´etrica. Una permutaci´on
sim´etrica de A se obtiene permutandofilas de A y permutatndo de la misma
manera las columnas. De manera matricial, B es una permutaci´on sim´etrica
de A si existe P , matriz de permutaci´on, tal que
B = P AP T .

(4)

Aunque son conceptos completamente diferentes, aqu´ı, un conjunto num´erico
finito es lo mismo que un vector cuyas entradas son justamente los elementos
del conjunto.
Una matriz A es de diagonal dominante por filas sipara cada fila i
|aii | ≥

|aij |.

(5)

j=i

La matriz es de diagonal estrictamente dominante por filas si todas las desigualdades son estrictas. Definiciones an´alogas se tienen por columnas. Para
matrices sim´etricas se habla simplemente de matrices de diagonal dominante
o de diagonal estrictamente dominante.

3

Algunos resultados

Existen varias caracterizaciones para las matrices definidas...