JUAN CAMILO MUÑOZ CASTELBLANCO
257120
Resumen
La factorización de Cholesky es una manera de resolver sistemas de ecuaciones matriciales, tenemos la matriz de coeficientes de un sistema de ecuaciones, llamada A. Una condición necesaria y suficiente para que una matriz A admita factorización de Cholesky es que sea simétrica y definida positiva. Si cumple podemos tratar de factorizarla la forma A = L*LT, cuando la tenemos factorizada ya podemos resolver el sistema de ecuaciones.
Desarrollo
Sea el
sistema de ecuaciones lineales A x = b, donde A es simétrica y definida positiva, entonces el
método de Cholesky para la resolución del sistema A x = b está
basado en la descomposición de la matriz A como sigue:
donde L es una
matriz triangular inferior de orden n, es decir, L tiene la
siguiente forma:
Descompuesta
de esta forma la matriz A, la resolución del sistema A x = b queda dada por la
resolución de dos sistemas triangulares. En efecto,
Si
hacemos,
entonces
:
el cual
resulta un sistema triangular inferior en y, con:
de fácil
resolución con:
En
forma general, tenemos:
Una
vez que se resuelve (1.9), procedemos a resolver el sistema (1.8), que es un
sistema triangular superior
Es
decir, los valores de 
quedan dados por:
De
(1.6) se obtienen las siguientes ecuaciones para el cálculo de los elementos de
la matriz L
( 
):
Se
mencionó anteriormente que para la aplicación de este método la matriz A debe ser
simétrica y definida positiva. A continuación se enuncian ciertos teoremas al
respecto.
Observación: Es necesario verificar que ningún elemento de la
diagonal principal sea cero.
Pruebas
Para las pruebas, se utilizó el siguiente código
del algoritmo, implementado en Matlab, el cual trata
de resolver un sistema de ecuaciones con el método de Cholesky.
Se debe ingresar A y b, de los cuales, la matriz A debe ser simétrica y
positiva.
matriz=input ('Ingrese la matriz aumentada
del sistema, A|b, A tiene que ser simétrica y
positiva, por ejemplo: [5 -4 2 20;-4 5 14 19;2 14 3 10]\n');
tam=size(matriz);%sacar el tamaño de la matriz para determinar
A(matris de coeficientes)
% y
b(vector de terminos
independientes)
n=tam(1);%saca
el numero de filas de la matriz
for i=1:n
b(i)=matriz(i,n+1);%determinar "b"
for j=1:n
A(i,j)=matriz(i,j);%determinar
"A"
end
end
b1=b';% "b" es un vector columna
for k=1:n %Algoritmo
de cholesky
for i=1:k-1
sum=0;
for j=1:i-1
sum=sum+A(i,j)*A(k,j);
end
A(k,i)=(A(k,i)-sum)/A(i,i);
end
sum=0;
for j=1:k-1
sum=sum+A(k,j)*A(k,j);
end
A(k,k)=sqrt(A(k,k)-sum);
end
for i=1:n-1 %Añade los ceros de
for j=1:n %''(puesto
que el algoritmo solo '''
if j>i %'''altera
los elementos de
A(i,j)=0; %la diagonal principal de A
end %y por debajo de esta)
end
end
L=A;%cambio
de variable
Lt=L';%Lt sera
c=b1;%se inicializa el vector "c", que tiene el mismo
tamaño de "b"
c(1)=b1(1)/L(1,1);%se determina el primer elemento de c
for i=2:n %procedimiento para
hallar "c"(progresivamente)
s=0;
for j=1:n-1
if i~=j & i>j
s=s+L(i,j)*c(j) ;
end
end
c(i)=(b1(i)-s)/L(i,i);
end
x=c;%se inicializa el vector "x", que tiene el mismo
tamaño de "c"
x(n)=c(n)/Lt(n,n);%se
determina x(n)(ultima solucion del sistema)
for i=n-1:-1:1 %procedimiento para
hallar "x"(regresivamente)
z=0;
for j=n:-1:2 %''''''Lt*x=c
if i~=j & i<j
z=z+Lt(i,j)*x(j);
end
end
x(i)=(c(i)-z)/Lt(i,i);
end
L%muestra la matriz triangular inferior de cholesky
Lt%muestra la matriz superior de cholesky
LLt=L*Lt%muestra la factorizacion de cholesky
x%vector solución del sistema
clear all%elimina
las variables del espacio de trabajo(evita que el programa se cargue de basura)
Referencias
http://es.wikipedia.org/wiki/Factorizaci%C3%B3n_de_Cholesky
Descripción del método en Wikipedia.
http://www.monografias.com/trabajos18/sistemas-ecuaciones/sistemas-ecuaciones.shtml#cooigcholes
Explicación y código MatLab
para la factorización de cholesky.
http://rkb.home.cern.ch/rkb/AN16pp/node33.html
Descripción de la descomposición de Cholesky.
http://www.gnu.org/software/gsl/manual/html_node/Cholesky-Decomposition.html
Otra forma de implementar la factorización de Cholesky.
http://sepwww.stanford.edu/sep/prof/gem/hlx/paper_html/node11.html
Descripción de la descomposición de Cholesky.