Método numérico: Cholesky
1
Índice
Introducción………………………………………………………………………3
Algoritmo del método…………………………………………………………….4
Ejercicios resueltos………………………………………………………………5
Conclusión, Bibliografía………………………………………………………..12
2
Introducción:
La factorización o descomposición de Cholesky toma su nombre del matemático
André-Louis Cholesky, quien encontró que una matriz simétrica definida positiva
puede ser descompuesta como el producto de una matriz triangular inferior y la
traspuesta de la matriz triangular inferior. La matriz triangular inferior es el
triángulo de Cholesky de la matriz original positiva definida. El resultado de
Cholesky ha sido extendido a matrices con entradas complejas. Es una manera de
resolver sistemas de ecuaciones matriciales y se deriva de la factorización LU con
una pequeña variación.
La descomposición de Cholesky es única: dada una matriz Hermitiana positiva
definida A, hay una única matriz triangular inferior L con entradas diagonales
estrictamente positivas tales que A = LL*. El recíproco se tiene trivialmente: si A se
puede escribir como LL* para alguna matriz invertible L, triangular inferior o no,
entonces A es Hermitiana y definida positiva.
El requisito de que L tenga entradas diagonales estrictamente positivas puede
extenderse para el caso de la descomposición en el caso de ser semi-definida
positiva. La proposición se lee ahora: una matriz cuadrada A tiene una
descomposición de Cholesky si y sólo si A es Hermitiana y semi-definida positiva.
Las factorizaciones de Cholesky para matrices semi-definidas positivas no son
únicas en general.
En el caso especial que A es una matriz simétrica definida positiva con entradas
reales, L se puede asumir también con entradas reales. Una Matriz D diagonal con
entradas positivas en la diagonal (valores propios de A), es factorizable como
, donde es matriz cuya diagonal consiste en la raíz cuadrada
de cada elemento de D, que tomamos como positivos.
La factorización puede ser calculada directamente a través de las siguientes
fórmulas (en este caso realizamos la factorización superior ):
3
Para los elementos de la diagonal principal, y:
Para el resto de los elementos. Donde son los elementos de la matriz U.
Algoritmo:
1. Si se tiene un sistema de la forma AX=b donde la matriz A es simétrica y si
determinante es mayor que cero.
2. Se aplica el método Cholesky que es la factorización de A en la forma LU
que toma la forma LLT.
3. Para poder factorizar la matriz L debe ser triangular superior.
4. Una vez hallado la matriz L.
5. Se resolver el sistema Lc=b donde se encontrara la matriz columna C.
6. Luego con la matriz transpuesta LT se resuelve el sistema LTx=c de donde
nos dará el resultado de las x.
4
Ejercicios resueltos:
1.- Dada la matriz
a. Hallar la descomposición de Cholesky
b. Utilizar dicha descomposición para calcular det(A).
c. Calcular la segunda columna de la inversa utilizando la descomposición
anterior.
Solución:
Se puede calcular la descomposición de Cholesky por ser la matriz A simétrica y
definida positiva:
Sabemos que:
Y
Por lo que obtenemos:
5
Con lo que obtenemos:
b) Sabemos que:
det(A) = det(G.GT) = det(G).det(GT) = 2*2 = 4.
c) Para calcular la segunda columna de la inversa:
Luego resolveremos los dos sistemas triangulares:
6
2.- Resolver el siguiente sistema de ecuaciones lineales usando el método de
Cholesky
6 15 55 100
A=
[ 15 55 225
55 225 979 ] y C=
[] 150
100
Solución:
En el método de Cholesky el primer paso es encontrar la matriz L usando las
fórmulas
i−1
a ki−∑ l ij l kj k−1
l ki= j=1
l ii Y
√
l kk= akk− ∑ l 2kj
j=1
La primera ecuación se usa para elementos fuera de la diagonal y la segunda para
elementos en la diagonal principal.
Entonces.
a21 15
l 21= =
l 11= √a 11=√ 6 = 2.4495 l 11 2 . 4495 = 6.1237
a31 55
l 21= =
l 11 2 . 4495 = 22.454 Ya sabemos que l12 = 0
l 22=√ a22−l 221=√ 55−6. 12372 = 4.1833
a32−l 21 l 31 55−(6 . 1237 )(22. 454 )
l 32= =
l 22 4 .1833 = 20.916
De igual forma l13 = l23 = 0 y
7
2
l 33=√ a33−(l31 +l 232 )= √979−(22 . 4542 +20 .916 2 ) = 6.1106
La matriz L es igual a
2.4495 0 0
[
L= 6.1237 4 .1833 0
22. 454 20.916 6.1106 ]
En el método de Cholesky U = LT
2.4495 6.1237 22.454
U= 0
0 [ 4.1833 20.916
0 6.1106 ]
El siguiente paso es encontrar el vector D de la misma manera que en el método
de descomposición de LU
i−1
c i −∑ lij d j
j =1
d i=
l ii
c 1 100 c2 −l 21 d1 150−(6 .1237 )(40 . 8246 )
d 1= = d 2= =
l11 2 . 4495 =40.8246 l 22 4 . 1833 =-
23.9045
c3 −(l 31 d 1 +l 32 d2 ) 100−((22 . 454 )(40 . 8246 )+(20 .916 )(−23 .9045 )
d 3= =
l33 6. 1106 =-51.826
Finalmente se calcula el vector de incógnitas comenzando por la última x.
n
d i− ∑ uij x j
j=i+1
x i=
uii
8
d3 d 2 −u23 x3
x 3= x 2=
u33 =-8.481 u22 = [-23.9045-(20.916)(-8.481)]/4.1833 =
36.690
d 1 −( u12 x 2 + u13 x 3 )
x 1=
u11 = [40.8246 – ((6.1237)(36.69)+(22.454)(-8.481))]/2.4495 =
2.685
El resultado se puede comprobar multiplicando A por X y el resultado debe ser
igual a C.
3.- Dado el sistema de ecuaciones lineales:
a. Calcular la descomposición LU de la matriz de coeficientes, utilizando el
método de pivotación parcial.
b. Calcula el determinante de la matriz de coeficientes.
c. Resuelve el sistema de ecuaciones utilizando la descomposición del
apartado a).
Solución:
a. Inicializamos el vector de permutaciones y formamos la matriz de
coeficientes ampliada con la columna de los términos independientes:
(1, 2, 3)
Calculamos el pivote, permutamos el vector y calculamos multiplicadores de
Gauss de la primera columna:
9
(2, 1, 3)
Calculamos el pivote, permutamos el vector y calculamos multiplicadores de
Gauss de la segunda columna:
(2, 1, 3)
Con lo que obtenemos la descomposición LU con pivotación parcial:
PA=LU
Siendo:
L = U = P =
b. Para el cálculo del determinante de A:
det(P A) = det (L U) det(P) det(A)= det (L) det(U) det(A) = -det (U) = 40
c. Para resolver el sistema solamente nos falta resolver un sistema triangular
superior:
10
Luego
11
Conclusión:
En conclusión se puede decir que este método es uno más para realizar
ecuaciones lineales Ax=b donde A es simétrica y positiva definida. En mi opinión
este método comparado con otros métodos numéricos, este se me hace algo más
complicado por el número de determinantes realizadas y operaciones entre ellas,
pero algo más sistemático que algunos otros.
Bibliografía:
http://users.dsic.upv.es/asignaturas/eui/cnu/libro/tema5/tema59.htm
http://www.frsn.utn.edu.ar/gie/an/sel/Directos_Cholesky.html
http://es.wikipedia.org/wiki/Factorizaci%C3%B3n_de_Cholesky
12
