Factorización de Cholesky

A factorización ou descomposición de Cholesky é un método alxebraico de descomposición de matrices descuberto polo oficial militar francés e matemático André-Louis Cholesky. Cholesky faleceu polas feridas recibidas no campo de batalla o 31 de agosto de 1918 no norte de Francia. Despois da súa morte, un dos seus compañeiros oficiais, o comandante Benoit, publicou o método de Cholesky para calcular solucións ás ecuacións normais para algúns problemas de axuste de datos de mínimos cadrados en Note sur une méthode de résolution des équations normales provenant de l'application de la méthode des moindres carrés. à un système d'équations lineaires en nombre inferior à aquel des inconnues. Aplicación do método á resolución dun sistema definido de ecuacións lineais (Procede du Commandant Cholesky) Ⓣ, publicado no Bulletin Géodesique en 1924.

Para introducir a factorización de Cholesky é preciso contextualizar que ao resolver un sistema de ecuacións lineais, que defina procesos físicos ou de enxeñaría, é necesario seleccionar o método de resolución, ben sexa directo ou iterativo. A principal desvantaxe dos métodos directos, como o método de eliminación de Gauss,é a súa complexidade computacional. Para unha matriz de tamaño N × N, o método de eliminación gaussiano é de orde $O(n^{3})$ O(n3) que para matrices moi grandes é un custo computacional caro. Unha solución a este problema é proporcionada polos métodos iterativo como : Jacobi, Gauss-Seidel, SOR ou gradiente conxugado. Estes métodos teñen menor complexidade, o que os fai máis eficientes. Ademais, os erros de redondeo, que poden ocorrer ao traballar con precisión finita na aplicación de métodos directos, fai os métodos iterativos máis apropiados. Na práctica tamén se pode considerar non necesario ter varios díxitos na solución, polo que os métodos das probas iterativas son máis que suficientes para ter unha boa aproximación. No caso específico das matrices simétricas definidas positivas, a factorización de Cholesky demostrou ser un dos condicionadores máis comúns, xa que só require almacenar unha matriz triangular inferior na memoria. Na práctica, moitos servizos de enxeñaría só están interesados en resolver unha matriz de coeficientes simétrica definida positiva, como por exemplo as matrices que xorden da discretización de problemas de dispersión electromagnética.

Definición

Nunha definición xeral cando nunha factorización LU é certo que L=U a factorización chámase factorización de Cholesky. Conceptualmente, obsérvase que esta factorización realiza unha función análoga á raíz cadrada dentro do corpo dos reais escalares positivos. Do mesmo xeito que a raíz cadrada ten limitacións para a súa aplicación dentro dos números reais (o número a tratar debe ser non negativo) a factorización de Cholesky tamén ten certas limitacións en canto á súa aplicación. Diremos que unha matriz A de orde n, definida positiva simétrica (spd), ten factorización de Cholesky se existe unha matriz triangular inferior L con elementos positivos na diagonal, tal que $A=LL^{t}$ . Diremos que A é definida positiva se A é simétrica e $x^{t}Ax>0$ para todo x diferente de 0. Doutra maneira podemos dicir que a matriz A é definida positiva se todos os elementos da diagonal son positivos. Entón, a factorización de Cholesky existe e é única.

Para comprender o algoritmo que realiza a factorización de Cholesky, a continuación mostraremos o caso específico da devandita factorización para unha matriz 2x2 spd. Teña en conta que o primeiro elemento da matriz (a11, l11). Este elemento é o único de toda a matriz que non ten ningún tipo de requisito previo no seu cálculo:

${\begin{pmatrix}a_{11}&A_{21}^{t}\\A_{21}&A_{22}\end{pmatrix}}$ = ${\begin{pmatrix}l_{11}&0\\L_{21}&L_{22}\end{pmatrix}}$ ${\begin{pmatrix}l_{11}&L_{21}^{t}\\0&L_{22}^{t}\end{pmatrix}}$ = ${\begin{pmatrix}l_{11}^{2}&l_{11}L_{21}^{t}\\l_{11}L_{21}&L_{21}L_{21}^{t}+L_{22}L_{22}^{t}\end{pmatrix}}$

  $l_{11}={\sqrt {a_{11}}}$       
  
   $L_{21}=(1/l_{11})A_{21}^{t}$ 
   
       $A_{22}-L_{21}L_{21}^{t}=L_{22}L_{22}^{t}$ 
       

De forma análoga á factorización LU, para resolver un SEL por factorización Cholesky, non hai máis nada que resolver por substitución directa (Lz = b), e substitución cara atrás ( $L^{t}x=z$.).

Unha das formas máis sinxelas de implementar o código de factorización de Cholesky é a seguinte (implementación en pseudocódigo tendo en conta que A é a matriz asociada ao SEL e n é a dimensión de dita matriz) :

Cholesky(MATRIZ A,enteiro N) { desde i = 0 ata n { } desde j = 0 ata i-1 { suma = 0.0; desde k = 0 ata j – 1 suma += A[i][k] * A[j][k]; A[i][j] = (A[i][j] - suma) / A[j][j]; } suma = 0.0; desde k = 0 ata i – 1 suma += A[i][k] * A[i][k]; A[i][i] = raiz2(A[i][i] - suma); }

Observando o pseudocódigo é relativamente sinxelo calcular o custo computacional factorización de Cholesky. Dado que A é unha matriz de orde n, tendo en conta. Teña en conta que os métodos de substitución cara adiante e cara atrás teñen un custo $n^{2}$, o custo de resolver o SEL mediante a factorización de Cholesky é do tipo:

$(1/3)n^{3}+2n^{2}$

Aplicacións

Se se buscan aplicacións concretas para todo o explicado ata agora, a aplicación máis obvia para a factorización de Cholesky é a resolución de SEL simétrico definido positivo, pero ten varias aplicacións concretas adicionais no mundo da ciencia, a estatística, as comunicacións e a informática:

A. Mínimos cadrados lineais. Este método é unha ferramenta estatística que se encarga de axustar as curvas a un determinado conxunto de datos, optimizando o mínimo do erro cadrado medio total. A factorización de Cholesky pódese usar para calcular os parámetros deste algoritmo. Neste caso é certo que para axustar as curvas hai que resolver o seguinte sistema

$A^{t}Ax=A^{t}b$ sendo  $A^{t}A$ spd

B. Simulación Montecarlo. A simulación de Monte Carlo é unha técnica cuantitativa que fai uso da estatística e ordenadores para imitar, mediante modelos matemáticos, o comportamento aleatorio de sistemas reais non dinámicos. Mediante a factorización de Cholesky é posíbel xerar ruído de cores segundo o modelado dun sistema determinado a partir de ruído non correlacionado, permitindo adaptar a simulación de Monte Carlo a calquera problema específico

C. Xeración de vectores aleatorios. Relacionado coa simulación de Monte Carlo, obsérvase que a factorización de Cholesky pódese usar para xerar vectores aleatorios.

D. Filtro D. Kalman. Este tipo de filtro caracterízase por controlar o estado medio e a covarianza do sistema. Trátase dun tipo de filtro adaptativo que emprega a factorización de Cholesky para extraer datos estatísticos da matriz de covarianza (que sempre reúne as condicións para factorizar) para que os parámetros estatísticos do filtro se poidan axustar en todo momento.

E. Núcleo para o cálculo de factorizacións en matrices dispersas. As matrices escasas son aquelas nas que un gran número dos seus elementos son nulos. Estas matrices adoitan seguir certos patróns de distribución de elementos distintos de cero e hai varios deles nos que a factorización de Cholesky pode ser útil. O máis claro destes patróns é o daquelas matrices escasas nas que os elementos non nulos se concentran en bloques e arredor da diagonal principal. A factorización densa de Cholesky úsase nestes casos nos bloques que residen preto da diagonal que son spd.

F. Precondicionamento de métodos iterativos. Ás veces pódese usar a factorización de Cholesky para precondicionar métodos iterativos e mellorar a súa converxencia. O obxectivo final do precondicionamento é aproximar a matriz de precondicionamento o máis preto posible da matriz SEL orixinal para mellorar as súas propiedades numéricas e a converxencia do método numérico.

Véxase tamén

Ligazóns externas

• Implementación e evaluación da Factorización de Cholesky mediante TBB