Descomposición de Cholesky

Método de descomposición matricial

En álgebra lineal , la descomposición de Cholesky o factorización de Cholesky ( pronunciada / ʃəˈlɛs k i / shə- LES - kee ) es una descomposición de una matriz hermítica , definida positiva, en el producto de una matriz triangular inferior y su transpuesta conjugada , que es útil para soluciones numéricas eficientes, por ejemplo, simulaciones de Monte Carlo . Fue descubierta por André-Louis Cholesky para matrices reales y publicada póstumamente en 1924. ^[1] Cuando es aplicable, la descomposición de Cholesky es aproximadamente el doble de eficiente que la descomposición LU para resolver sistemas de ecuaciones lineales . ^[2]

Declaración

La descomposición de Cholesky de una matriz hermítica positiva definida A , es una descomposición de la forma

$${\displaystyle \mathbf {A} =\mathbf {LL} ^{*},}$$

donde L es una matriz triangular inferior con entradas diagonales reales y positivas, y L * denota la transpuesta conjugada de L . Toda matriz hermítica definida positiva (y, por lo tanto, también toda matriz simétrica definida positiva de valor real) tiene una descomposición de Cholesky única. ^[3]

Lo inverso es trivialmente válido: si A puede escribirse como LL * para alguna L invertible , triangular inferior o de otro tipo, entonces A es hermítica y definida positiva.

Cuando A es una matriz real (por lo tanto, simétrica positiva definida), la factorización puede escribirse donde L es una matriz triangular inferior real con entradas diagonales positivas. ^{[4] [5] [6]} $${\displaystyle \mathbf {A} =\mathbf {LL} ^{\mathsf {T}},}$$

Matrices semidefinidas positivas

Si una matriz hermítica A es sólo semidefinida positiva, en lugar de definida positiva, entonces todavía tiene una descomposición de la forma A = LL * donde se permite que las entradas diagonales de L ^{sean cero. [7]} La ​​descomposición no necesita ser única, por ejemplo: para cualquier θ . Sin embargo, si el rango de A es r , entonces hay una única L triangular inferior con exactamente r elementos diagonales positivos y n − r columnas que contienen todos ceros. ^[8] $${\displaystyle {\begin{bmatrix}0&0\\0&1\end{bmatrix}}=\mathbf {L} \mathbf {L} ^{*},\quad \quad \mathbf {L} ={\begin{bmatrix}0&0\\\cos \theta &\sin \theta \end{bmatrix}},}$$

Alternativamente, la descomposición puede hacerse única cuando se fija una elección pivote. Formalmente, si A es una matriz semidefinida positiva n × n de rango r , entonces hay al menos una matriz de permutación P tal que PAP ^T tiene una descomposición única de la forma PAP ^T = LL ^* con , donde L ₁ es una matriz triangular inferior r × r con diagonal positiva. ^[9] ${\textstyle \mathbf {L} ={\begin{bmatrix}\mathbf {L} _{1}&0\\\mathbf {L} _{2}&0\end{bmatrix}}}$

Descomposición de LDL

Una variante estrechamente relacionada de la descomposición clásica de Cholesky es la descomposición de LDL,

$${\displaystyle \mathbf {A} =\mathbf {LDL} ^{*},}$$

donde L es una matriz triangular unitaria inferior (unitriangulo) y D es una matriz diagonal . Es decir, se requiere que los elementos diagonales de L sean 1 a costa de introducir una matriz diagonal adicional D en la descomposición. La principal ventaja es que la descomposición LDL se puede calcular y utilizar con esencialmente los mismos algoritmos, pero evita la extracción de raíces cuadradas. ^[10]

Por esta razón, la descomposición LDL se denomina a menudo descomposición de Cholesky sin raíz cuadrada . Para matrices reales, la factorización tiene la forma A = LDL ^T y a menudo se denomina descomposición LDLT (o descomposición LDL ^T , o LDL′ ). Recuerda a la descomposición propia de matrices simétricas reales , A = QΛQ ^T , pero es bastante diferente en la práctica porque Λ y D no son matrices similares .

La descomposición de LDL está relacionada con la descomposición clásica de Cholesky de la forma LL * de la siguiente manera:

$${\displaystyle \mathbf {A} =\mathbf {LDL} ^{*}=\mathbf {L} \mathbf {D} ^{1/2}\left(\mathbf {D} ^{1/2}\right)^{*}\mathbf {L} ^{*}=\mathbf {L} \mathbf {D} ^{1/2}\left(\mathbf {L} \mathbf {D} ^{1/2}\right)^{*}.}$$

Por el contrario, dada la descomposición clásica de Cholesky de una matriz definida positiva, si S es una matriz diagonal que contiene la diagonal principal de , entonces A se puede descomponer como donde (esto reescala cada columna para hacer que los elementos diagonales sean 1), ${\textstyle \mathbf {A} =\mathbf {C} \mathbf {C} ^{*}}$ ${\textstyle \mathbf {C} }$ ${\textstyle \mathbf {L} \mathbf {D} \mathbf {L} ^{*}}$ $${\displaystyle \mathbf {L} =\mathbf {C} \mathbf {S} ^{-1}}$$ $${\displaystyle \mathbf {D} =\mathbf {S} ^{2}.}$$

Si A es definida positiva, entonces los elementos diagonales de D son todos positivos. Para A semidefinida positiva, existe una descomposición donde el número de elementos distintos de cero en la diagonal D es exactamente el rango de A. ^[11] Algunas matrices indefinidas para las que no existe una descomposición de Cholesky tienen una descomposición LDL con entradas negativas en D : basta con que los primeros n − 1 menores principales de A no sean singulares. ^[12] ${\textstyle \mathbf {L} \mathbf {D} \mathbf {L} ^{*}}$

Ejemplo

Aquí está la descomposición de Cholesky de una matriz real simétrica:

$${\displaystyle {\begin{aligned}{\begin{pmatrix}4&12&-16\\12&37&-43\\-16&-43&98\\\end{pmatrix}}={\begin{pmatrix}2&0&0\\6&1&0\\-8&5&3\\\end{pmatrix}}{\begin{pmatrix}2&6&-8\\0&1&5\\0&0&3\\\end{pmatrix}}.\end{aligned}}}$$

Y aquí está su descomposición en LDL ^{T :}

$${\displaystyle {\begin{aligned}{\begin{pmatrix}4&12&-16\\12&37&-43\\-16&-43&98\\\end{pmatrix}}&={\begin{pmatrix}1&0&0\\3&1&0\\-4&5&1\\\end{pmatrix}}{\begin{pmatrix}4&0&0\\0&1&0\\0&0&9\\\end{pmatrix}}{\begin{pmatrix}1&3&-4\\0&1&5\\0&0&1\\\end{pmatrix}}.\end{aligned}}}$$

Interpretación geométrica

La elipse es una imagen lineal del círculo unitario. Los dos vectores son ejes conjugados de la elipse, elegidos de forma que sean paralelos al primer eje y se encuentren dentro del plano abarcado por los dos primeros ejes. ${\textstyle v_{1},v_{2}}$ ${\textstyle v_{1}}$ ${\textstyle v_{2}}$

La descomposición de Cholesky es equivalente a una elección particular de ejes conjugados de un elipsoide . ^[13] En detalle, dejemos que el elipsoide se defina como , entonces, por definición, un conjunto de vectores son ejes conjugados del elipsoide si y solo si . Entonces, el elipsoide es precisamente donde mapea el vector base , y es la esfera unitaria en n dimensiones. Es decir, el elipsoide es una imagen lineal de la esfera unitaria. ${\textstyle y^{T}Ay=1}$ ${\textstyle v_{1},...,v_{n}}$ ${\textstyle v_{i}^{T}Av_{j}=\delta _{ij}}$ $${\displaystyle \left\{\sum _{i}x_{i}v_{i}:x^{T}x=1\right\}=f(\mathbb {S} ^{n})}$$ ${\textstyle f}$ ${\textstyle e_{i}\mapsto v_{i}}$ ${\textstyle \mathbb {S} ^{n}}$

Defina la matriz , entonces es equivalente a . Diferentes opciones de los ejes conjugados corresponden a diferentes descomposiciones. ${\textstyle V:=[v_{1}|v_{2}|\cdots |v_{n}]}$ ${\textstyle v_{i}^{T}Av_{j}=\delta _{ij}}$ ${\textstyle V^{T}AV=I}$

La descomposición de Cholesky corresponde a elegir ser paralelo al primer eje, estar dentro del plano abarcado por los dos primeros ejes, y así sucesivamente. Esto produce una matriz triangular superior. Luego, hay , donde es triangular inferior. ${\textstyle v_{1}}$ ${\textstyle v_{2}}$ ${\textstyle V}$ ${\textstyle A=LL^{T}}$ ${\textstyle L=(V^{-1})^{T}}$

De manera similar, el análisis de componentes principales corresponde a elegir que sean perpendiculares. Entonces, sea y , y hay donde es una matriz ortogonal. Esto entonces da como resultado . ${\textstyle v_{1},...,v_{n}}$ ${\textstyle \lambda =1/\|v_{i}\|^{2}}$ ${\textstyle \Sigma =\mathrm {diag} (\lambda _{1},...,\lambda _{n})}$ ${\textstyle V=U\Sigma ^{-1/2}}$ ${\textstyle U}$ ${\textstyle A=U\Sigma U^{T}}$

Aplicaciones

Solución numérica de un sistema de ecuaciones lineales

La descomposición de Cholesky se utiliza principalmente para la solución numérica de ecuaciones lineales . Si A es simétrica y definida positiva, entonces se puede resolver calculando primero la descomposición de Cholesky , luego resolviendo y mediante sustitución hacia adelante y, finalmente, resolviendo x mediante sustitución hacia atrás . ${\textstyle \mathbf {Ax} =\mathbf {b} }$ ${\textstyle \mathbf {Ax} =\mathbf {b} }$ ${\textstyle \mathbf {A} =\mathbf {LL} ^{\mathrm {*} }}$ ${\textstyle \mathbf {Ly} =\mathbf {b} }$ ${\textstyle \mathbf {L^{*}x} =\mathbf {y} }$

Una forma alternativa de eliminar la extracción de raíces cuadradas en la descomposición es calcular la descomposición LDL , luego resolver para y y finalmente resolver . ${\textstyle \mathbf {LL} ^{\mathrm {*} }}$ ${\textstyle \mathbf {A} =\mathbf {LDL} ^{\mathrm {*} }}$ ${\textstyle \mathbf {Ly} =\mathbf {b} }$ ${\textstyle \mathbf {DL} ^{\mathrm {*} }\mathbf {x} =\mathbf {y} }$

Para los sistemas lineales que se pueden poner en forma simétrica, la descomposición de Cholesky (o su variante LDL) es el método de elección, por su mayor eficiencia y estabilidad numérica. En comparación con la descomposición LU , es aproximadamente el doble de eficiente. ^[2]

Mínimos cuadrados lineales

Los sistemas de la forma Ax = b con A simétricos y definidos positivos surgen con bastante frecuencia en las aplicaciones. Por ejemplo, las ecuaciones normales en problemas de mínimos cuadrados lineales tienen esta forma. También puede suceder que la matriz A provenga de un funcional de energía, que debe ser positivo desde el punto de vista físico; esto sucede con frecuencia en la solución numérica de ecuaciones diferenciales parciales .

Optimización no lineal

Las funciones multivariables no lineales pueden minimizarse sobre sus parámetros utilizando variantes del método de Newton llamadas métodos cuasi-Newton . En la iteración k, la búsqueda avanza en una dirección definida al resolver para , donde es la dirección del paso, es el gradiente y es una aproximación a la matriz hessiana formada al repetir actualizaciones de rango 1 en cada iteración. Dos fórmulas de actualización bien conocidas se denominan Davidon-Fletcher-Powell (DFP) y Broyden-Fletcher-Goldfarb-Shanno (BFGS). La pérdida de la condición de definida positiva a través del error de redondeo se evita si en lugar de actualizar una aproximación a la inversa de la hessiana, se actualiza la descomposición de Cholesky de una aproximación de la propia matriz hessiana. ^[14] ${\textstyle p_{k}}$ ${\textstyle B_{k}p_{k}=-g_{k}}$ ${\textstyle p_{k}}$ ${\textstyle p_{k}}$ ${\textstyle g_{k}}$ ${\textstyle B_{k}}$

Simulación de Monte Carlo

La descomposición de Cholesky se utiliza comúnmente en el método de Monte Carlo para simular sistemas con múltiples variables correlacionadas. La matriz de covarianza se descompone para dar la L triangular inferior . Al aplicar esto a un vector de observaciones no correlacionadas en una muestra u se produce un vector de muestra Lu con las propiedades de covarianza del sistema que se está modelando. ^[15]

El siguiente ejemplo simplificado muestra la economía que se obtiene con la descomposición de Cholesky: supongamos que el objetivo es generar dos variables normales correlacionadas y con un coeficiente de correlación dado . Para lograrlo, es necesario generar primero dos variables aleatorias gaussianas no correlacionadas y (por ejemplo, mediante una transformada de Box-Muller ). Dado el coeficiente de correlación requerido , las variables normales correlacionadas se pueden obtener mediante las transformaciones y . ${\textstyle x_{1}}$ ${\textstyle x_{2}}$ ${\textstyle \rho }$ ${\textstyle z_{1}}$ ${\textstyle z_{2}}$ ${\textstyle \rho }$ ${\textstyle x_{1}=z_{1}}$ ${\textstyle x_{2}=\rho z_{1}+{\sqrt {1-\rho ^{2}}}z_{2}}$

Filtros de Kalman

Los filtros de Kalman sin aroma suelen utilizar la descomposición de Cholesky para elegir un conjunto de los denominados puntos sigma. El filtro de Kalman rastrea el estado promedio de un sistema como un vector x de longitud N y la covarianza como una matriz N × N P . La matriz P siempre es semidefinida positiva y se puede descomponer en LL ^T . Las columnas de L se pueden sumar y restar de la media x para formar un conjunto de 2 N vectores denominados puntos sigma . Estos puntos sigma capturan por completo la media y la covarianza del estado del sistema.

Inversión de matriz

La inversa explícita de una matriz hermítica se puede calcular mediante la descomposición de Cholesky, de manera similar a la resolución de sistemas lineales, utilizando operaciones ( multiplicaciones). ^[10] La inversión completa incluso se puede realizar de manera eficiente en el lugar. ${\textstyle n^{3}}$ ${\textstyle {\tfrac {1}{2}}n^{3}}$

Una matriz no hermítica B también se puede invertir utilizando la siguiente identidad, donde BB * siempre será hermítica:

$${\displaystyle \mathbf {B} ^{-1}=\mathbf {B} ^{*}(\mathbf {BB} ^{*})^{-1}.}$$

Cálculo

Existen varios métodos para calcular la descomposición de Cholesky. La complejidad computacional de los algoritmos comúnmente utilizados es O ( n ³ ) en general. ^{[ cita requerida ]} Los algoritmos descritos a continuación implican todos aproximadamente (1/3) n ³ FLOP ( n ³ /6 multiplicaciones y el mismo número de adiciones) para sabores reales y (4/3) n ³ FLOP para sabores complejos, ^[16] donde n es el tamaño de la matriz A . Por lo tanto, tienen la mitad del costo de la descomposición LU , que utiliza 2 n ³ /3 FLOP (ver Trefethen y Bau 1997).

Cuál de los algoritmos siguientes es más rápido depende de los detalles de la implementación. Por lo general, el primer algoritmo será un poco más lento porque accede a los datos de una manera menos regular.

El algoritmo de Cholesky

El algoritmo de Cholesky , utilizado para calcular la matriz de descomposición L , es una versión modificada de la eliminación gaussiana .

El algoritmo recursivo comienza con i  := 1 y

A ⁽¹⁾  := A .

En el paso i , la matriz A ^{( i )} tiene la siguiente forma: donde I _{i −1} denota la matriz identidad de dimensión i − 1 . $${\displaystyle \mathbf {A} ^{(i)}={\begin{pmatrix}\mathbf {I} _{i-1}&0&0\\0&a_{i,i}&\mathbf {b} _{i}^{*}\\0&\mathbf {b} _{i}&\mathbf {B} ^{(i)}\end{pmatrix}},}$$

Si la matriz L _i está definida por (nótese que a _i,i > 0 ya que A ^{( i )} es definida positiva), entonces A ^{( i )} puede escribirse como donde Nótese que b _i b * _i es un producto externo , por lo tanto, este algoritmo se llama la versión de producto externo en (Golub y Van Loan). $${\displaystyle \mathbf {L} _{i}:={\begin{pmatrix}\mathbf {I} _{i-1}&0&0\\0&{\sqrt {a_{i,i}}}&0\\0&{\frac {1}{\sqrt {a_{i,i}}}}\mathbf {b} _{i}&\mathbf {I} _{n-i}\end{pmatrix}},}$$ $${\displaystyle \mathbf {A} ^{(i)}=\mathbf {L} _{i}\mathbf {A} ^{(i+1)}\mathbf {L} _{i}^{*}}$$ $${\displaystyle \mathbf {A} ^{(i+1)}={\begin{pmatrix}\mathbf {I} _{i-1}&0&0\\0&1&0\\0&0&\mathbf {B} ^{(i)}-{\frac {1}{a_{i,i}}}\mathbf {b} _{i}\mathbf {b} _{i}^{*}\end{pmatrix}}.}$$

Esto se repite para i desde 1 hasta n . Después de n pasos, se obtiene A ^{( n + 1)} = I y, por lo tanto, la matriz triangular inferior L buscada se calcula como

$${\displaystyle \mathbf {L} :=\mathbf {L} _{1}\mathbf {L} _{2}\dots \mathbf {L} _{n}.}$$

Los algoritmos de Cholesky-Banachiewicz y Cholesky-Crout

Patrón de acceso (blanco) y patrón de escritura (amarillo) para el algoritmo de Cholesky-Banachiewicz en una matriz de 5×5

Si la ecuación $${\displaystyle {\begin{aligned}\mathbf {A} =\mathbf {LL} ^{T}&={\begin{pmatrix}L_{11}&0&0\\L_{21}&L_{22}&0\\L_{31}&L_{32}&L_{33}\\\end{pmatrix}}{\begin{pmatrix}L_{11}&L_{21}&L_{31}\\0&L_{22}&L_{32}\\0&0&L_{33}\end{pmatrix}}\\[8pt]&={\begin{pmatrix}L_{11}^{2}&&({\text{symmetric}})\\L_{21}L_{11}&L_{21}^{2}+L_{22}^{2}&\\L_{31}L_{11}&L_{31}L_{21}+L_{32}L_{22}&L_{31}^{2}+L_{32}^{2}+L_{33}^{2}\end{pmatrix}},\end{aligned}}}$$

se escribe lo siguiente:

$${\displaystyle {\begin{aligned}\mathbf {L} ={\begin{pmatrix}{\sqrt {A_{11}}}&0&0\\A_{21}/L_{11}&{\sqrt {A_{22}-L_{21}^{2}}}&0\\A_{31}/L_{11}&\left(A_{32}-L_{31}L_{21}\right)/L_{22}&{\sqrt {A_{33}-L_{31}^{2}-L_{32}^{2}}}\end{pmatrix}}\end{aligned}}}$$

y por lo tanto las siguientes fórmulas para las entradas de L :

$${\displaystyle L_{j,j}=(\pm ){\sqrt {A_{j,j}-\sum _{k=1}^{j-1}L_{j,k}^{2}}},}$$ $${\displaystyle L_{i,j}={\frac {1}{L_{j,j}}}\left(A_{i,j}-\sum _{k=1}^{j-1}L_{i,k}L_{j,k}\right)\quad {\text{for }}i>j.}$$

En el caso de matrices complejas y reales, se permiten cambios arbitrarios de signo sin importancia de los elementos diagonales y no diagonales asociados. La expresión debajo de la raíz cuadrada siempre es positiva si A es real y definida positiva.

Para una matriz hermítica compleja, se aplica la siguiente fórmula:

$${\displaystyle L_{j,j}={\sqrt {A_{j,j}-\sum _{k=1}^{j-1}L_{j,k}^{*}L_{j,k}}},}$$ $${\displaystyle L_{i,j}={\frac {1}{L_{j,j}}}\left(A_{i,j}-\sum _{k=1}^{j-1}L_{j,k}^{*}L_{i,k}\right)\quad {\text{for }}i>j.}$$

Ahora es posible calcular la entrada ( i , j ) si se conocen las entradas de la izquierda y de arriba. El cálculo suele organizarse en uno de los siguientes órdenes:

• El algoritmo de Cholesky-Banachiewicz comienza desde la esquina superior izquierda de la matriz L y procede a calcular la matriz fila por fila.

para ( i = 0 ; i < dimensionSize ; i ++ ) { para ( j = 0 ; j <= i ; j ++ ) { suma flotante = 0 ; para ( k = 0 ; k < j ; k ++ ) suma += L [ i ][ k ] * L [ j ][ k ];                                   si ( i == j ) L [ i ][ j ] = sqrt ( A [ i ][ i ] - suma ); de lo contrario L [ i ][ j ] = ( 1.0 / L [ j ][ j ] * ( A [ i ][ j ] - suma )); } }                   

El algoritmo anterior se puede expresar sucintamente como una combinación de un producto escalar y una multiplicación de matrices en lenguajes de programación vectorizados como Fortran de la siguiente manera:

hacer i = 1 , tamaño ( A , 1 ) L ( i , i ) = sqrt ( A ( i , i ) - producto_punto ( L ( i , 1 : i - 1 ), L ( i , 1 : i - 1 ))) L ( i + 1 :, i ) = ( A ( i + 1 :, i ) - matmul ( conjg ( L ( i , 1 : i - 1 )), L ( i + 1 :, 1 : i - 1 ))) / L ( i , i ) fin hacer                 

donde conjgse refiere al conjugado complejo de los elementos.

• El algoritmo de Cholesky-Crout comienza desde la esquina superior izquierda de la matriz L y procede a calcular la matriz columna por columna.

  para ( j = 0 ; j < dimensionSize ; j ++ ) { suma flotante = 0 ; para ( k = 0 ; k < j ; k ++ ) { suma += L [ j ][ k ] * L [ j ][ k ]; } L [ j ][ j ] = sqrt ( A [ j ][ j ] - suma );                                 para ( i = j + 1 ; i < tamañoDeDimensión ; i ++ ) { suma = 0 ; para ( k = 0 ; k < j ; k ++ ) { suma += L [ i ][ k ] * L [ j ][ k ]; } L [ i ][ j ] = ( 1.0 / L [ j ][ j ] * ( A [ i ][ j ] - suma )); } }                                      

El algoritmo anterior se puede expresar sucintamente como una combinación de un producto escalar y una multiplicación de matrices en lenguajes de programación vectorizados como Fortran de la siguiente manera:

hacer i = 1 , tamaño ( A , 1 ) L ( i , i ) = sqrt ( A ( i , i ) - producto_punto ( L ( 1 : i - 1 , i ), L ( 1 : i - 1 , i ))) L ( i , i + 1 :) = ( A ( i , i + 1 :) - matmul ( conjg ( L ( 1 : i - 1 , i )), L ( 1 : i - 1 , i + 1 :))) / L ( i , i ) fin hacer                 

donde conjgse refiere al conjugado complejo de los elementos.

Cualquiera de los patrones de acceso permite realizar todo el cálculo en el lugar si así se desea.

Estabilidad del cálculo

Supongamos que se desea resolver un sistema bien condicionado de ecuaciones lineales. Si se utiliza la descomposición LU, el algoritmo es inestable a menos que se utilice algún tipo de estrategia de pivoteo. En este último caso, el error depende del denominado factor de crecimiento de la matriz, que suele ser pequeño (aunque no siempre).

Ahora, supongamos que se puede aplicar la descomposición de Cholesky. Como se mencionó anteriormente, el algoritmo será el doble de rápido. Además, no es necesario pivotar y el error siempre será pequeño. Específicamente, si Ax = b , e y denota la solución calculada, entonces y resuelve el sistema perturbado ( A + E ) y = b , donde Aquí ||·|| ₂ es la matriz 2-norma , c _n es una pequeña constante que depende de n , y ε denota el redondeo unitario . $${\displaystyle \|\mathbf {E} \|_{2}\leq c_{n}\varepsilon \|\mathbf {A} \|_{2}.}$$

Una preocupación con la descomposición de Cholesky que se debe tener en cuenta es el uso de raíces cuadradas. Si la matriz que se está factorizando es definida positiva como se requiere, los números bajo las raíces cuadradas siempre son positivos en aritmética exacta . Desafortunadamente, los números pueden volverse negativos debido a errores de redondeo , en cuyo caso el algoritmo no puede continuar. Sin embargo, esto solo puede suceder si la matriz está muy mal acondicionada. Una forma de abordar esto es agregar una matriz de corrección diagonal a la matriz que se está descomponiendo en un intento de promover la definición positiva. ^[17] Si bien esto puede disminuir la precisión de la descomposición, puede ser muy favorable por otras razones; por ejemplo, al realizar el método de Newton en optimización , agregar una matriz diagonal puede mejorar la estabilidad cuando está lejos del óptimo.

Descomposición de LDL

Una forma alternativa, que elimina la necesidad de tomar raíces cuadradas cuando A es simétrica, es la factorización indefinida simétrica ^[18]. $${\displaystyle {\begin{aligned}\mathbf {A} =\mathbf {LDL} ^{\mathrm {T} }&={\begin{pmatrix}1&0&0\\L_{21}&1&0\\L_{31}&L_{32}&1\\\end{pmatrix}}{\begin{pmatrix}D_{1}&0&0\\0&D_{2}&0\\0&0&D_{3}\\\end{pmatrix}}{\begin{pmatrix}1&L_{21}&L_{31}\\0&1&L_{32}\\0&0&1\\\end{pmatrix}}\\[8pt]&={\begin{pmatrix}D_{1}&&(\mathrm {symmetric} )\\L_{21}D_{1}&L_{21}^{2}D_{1}+D_{2}&\\L_{31}D_{1}&L_{31}L_{21}D_{1}+L_{32}D_{2}&L_{31}^{2}D_{1}+L_{32}^{2}D_{2}+D_{3}.\end{pmatrix}}.\end{aligned}}}$$

Las siguientes relaciones recursivas se aplican para las entradas de D y L : $${\displaystyle D_{j}=A_{jj}-\sum _{k=1}^{j-1}L_{jk}^{2}D_{k},}$$ $${\displaystyle L_{ij}={\frac {1}{D_{j}}}\left(A_{ij}-\sum _{k=1}^{j-1}L_{ik}L_{jk}D_{k}\right)\quad {\text{for }}i>j.}$$

Esto funciona siempre que los elementos diagonales generados en D sean distintos de cero. La descomposición es entonces única. D y L son reales si A es real.

Para la matriz hermítica compleja A , se aplica la siguiente fórmula:

$${\displaystyle D_{j}=A_{jj}-\sum _{k=1}^{j-1}L_{jk}L_{jk}^{*}D_{k},}$$ $${\displaystyle L_{ij}={\frac {1}{D_{j}}}\left(A_{ij}-\sum _{k=1}^{j-1}L_{ik}L_{jk}^{*}D_{k}\right)\quad {\text{for }}i>j.}$$

Nuevamente, el patrón de acceso permite que todo el cálculo se realice en el lugar si así se desea.

Variante de bloque

Cuando se utiliza en matrices indefinidas, se sabe que la factorización LDL * es inestable sin un pivoteo cuidadoso; ^[19] específicamente, los elementos de la factorización pueden crecer arbitrariamente. Una posible mejora es realizar la factorización en submatrices de bloques, comúnmente 2 × 2: ^[20]

$${\displaystyle {\begin{aligned}\mathbf {A} =\mathbf {LDL} ^{\mathrm {T} }&={\begin{pmatrix}\mathbf {I} &0&0\\\mathbf {L} _{21}&\mathbf {I} &0\\\mathbf {L} _{31}&\mathbf {L} _{32}&\mathbf {I} \\\end{pmatrix}}{\begin{pmatrix}\mathbf {D} _{1}&0&0\\0&\mathbf {D} _{2}&0\\0&0&\mathbf {D} _{3}\\\end{pmatrix}}{\begin{pmatrix}\mathbf {I} &\mathbf {L} _{21}^{\mathrm {T} }&\mathbf {L} _{31}^{\mathrm {T} }\\0&\mathbf {I} &\mathbf {L} _{32}^{\mathrm {T} }\\0&0&\mathbf {I} \\\end{pmatrix}}\\[8pt]&={\begin{pmatrix}\mathbf {D} _{1}&&(\mathrm {symmetric} )\\\mathbf {L} _{21}\mathbf {D} _{1}&\mathbf {L} _{21}\mathbf {D} _{1}\mathbf {L} _{21}^{\mathrm {T} }+\mathbf {D} _{2}&\\\mathbf {L} _{31}\mathbf {D} _{1}&\mathbf {L} _{31}\mathbf {D} _{1}\mathbf {L} _{21}^{\mathrm {T} }+\mathbf {L} _{32}\mathbf {D} _{2}&\mathbf {L} _{31}\mathbf {D} _{1}\mathbf {L} _{31}^{\mathrm {T} }+\mathbf {L} _{32}\mathbf {D} _{2}\mathbf {L} _{32}^{\mathrm {T} }+\mathbf {D} _{3}\end{pmatrix}},\end{aligned}}}$$

donde cada elemento de las matrices anteriores es una submatriz cuadrada. De esto se deducen las siguientes relaciones recursivas análogas:

$${\displaystyle \mathbf {D} _{j}=\mathbf {A} _{jj}-\sum _{k=1}^{j-1}\mathbf {L} _{jk}\mathbf {D} _{k}\mathbf {L} _{jk}^{\mathrm {T} },}$$ $${\displaystyle \mathbf {L} _{ij}=\left(\mathbf {A} _{ij}-\sum _{k=1}^{j-1}\mathbf {L} _{ik}\mathbf {D} _{k}\mathbf {L} _{jk}^{\mathrm {T} }\right)\mathbf {D} _{j}^{-1}.}$$

Esto implica productos matriciales e inversión explícita, lo que limita el tamaño de bloque práctico.

Actualizando la descomposición

Una tarea que surge a menudo en la práctica es la necesidad de actualizar una descomposición de Cholesky. En más detalle, ya se ha calculado la descomposición de Cholesky de alguna matriz , luego se cambia la matriz de alguna manera por otra matriz, digamos , y se desea calcular la descomposición de Cholesky de la matriz actualizada: . La pregunta ahora es si se puede utilizar la descomposición de Cholesky de que se calculó antes para calcular la descomposición de Cholesky de . ${\textstyle \mathbf {A} =\mathbf {L} \mathbf {L} ^{*}}$ ${\textstyle \mathbf {A} }$ ${\textstyle \mathbf {A} }$ ${\textstyle {\tilde {\mathbf {A} }}}$ ${\textstyle {\tilde {\mathbf {A} }}={\tilde {\mathbf {L} }}{\tilde {\mathbf {L} }}^{*}}$ ${\textstyle \mathbf {A} }$ ${\textstyle {\tilde {\mathbf {A} }}}$

Actualización de rango uno

El caso específico, donde la matriz actualizada está relacionada con la matriz por , se conoce como actualización de rango uno . ${\textstyle {\tilde {\mathbf {A} }}}$ ${\textstyle \mathbf {A} }$ ${\textstyle {\tilde {\mathbf {A} }}=\mathbf {A} +\mathbf {x} \mathbf {x} ^{*}}$

Aquí hay una función ^[21] escrita en sintaxis de Matlab que realiza una actualización de rango uno:

función  [L] = cholupdate ( L, x ) n = length ( x ); para k = 1 : n r = sqrt ( L ( k , k ) ^ 2 + x ( k ) ^ 2 ); c = r / L ( k , k ); s = x ( k ) / L ( k , k ); L ( k , k ) = r ; si k < n L (( k + 1 ): n , k ) = ( L (( k + 1 ): n , k ) + s * x (( k + 1 ): n )) / c ; x (( k + 1 ): n ) = c * x (( k + 1 ): n ) - s * L (( k + 1 ): n , k ); fin fin fin                                                          

Una actualización de rango n es aquella en la que, para una matriz, se actualiza la descomposición de modo que . Esto se puede lograr realizando actualizaciones de rango uno sucesivamente para cada una de las columnas de . ${\textstyle \mathbf {M} }$ ${\textstyle {\tilde {\mathbf {A} }}=\mathbf {A} +\mathbf {M} \mathbf {M} ^{*}}$ ${\textstyle \mathbf {M} }$

Actualización de rango uno

Una actualización de rango uno es similar a una actualización de rango uno, excepto que la suma se reemplaza por una resta: . Esto solo funciona si la nueva matriz sigue siendo definida positiva. ${\textstyle {\tilde {\mathbf {A} }}=\mathbf {A} -\mathbf {x} \mathbf {x} ^{*}}$ ${\textstyle {\tilde {\mathbf {A} }}}$

El código para la actualización de rango uno que se muestra arriba se puede adaptar fácilmente para realizar una actualización de rango uno: uno simplemente necesita reemplazar las dos adiciones en la asignación por ry L((k+1):n, k)por sustracciones.

Agregar y eliminar filas y columnas

Si una matriz simétrica y definida positiva se representa en forma de bloque como ${\textstyle \mathbf {A} }$

$${\displaystyle \mathbf {A} ={\begin{pmatrix}\mathbf {A} _{11}&\mathbf {A} _{13}\\\mathbf {A} _{13}^{\mathrm {T} }&\mathbf {A} _{33}\\\end{pmatrix}}}$$

y su factor de Cholesky superior $${\displaystyle \mathbf {L} ={\begin{pmatrix}\mathbf {L} _{11}&\mathbf {L} _{13}\\0&\mathbf {L} _{33}\\\end{pmatrix}},}$$

luego para una nueva matriz , que es la misma que pero con la inserción de nuevas filas y columnas, ${\textstyle {\tilde {\mathbf {A} }}}$ ${\textstyle \mathbf {A} }$ $${\displaystyle {\begin{aligned}{\tilde {\mathbf {A} }}&={\begin{pmatrix}\mathbf {A} _{11}&\mathbf {A} _{12}&\mathbf {A} _{13}\\\mathbf {A} _{12}^{\mathrm {T} }&\mathbf {A} _{22}&\mathbf {A} _{23}\\\mathbf {A} _{13}^{\mathrm {T} }&\mathbf {A} _{23}^{\mathrm {T} }&\mathbf {A} _{33}\\\end{pmatrix}}\end{aligned}}}$$

Ahora existe un interés en encontrar la factorización de Cholesky de , que puede llamarse , sin calcular directamente toda la descomposición. ${\textstyle {\tilde {\mathbf {A} }}}$ ${\textstyle {\tilde {\mathbf {S} }}}$ $${\displaystyle {\begin{aligned}{\tilde {\mathbf {S} }}&={\begin{pmatrix}\mathbf {S} _{11}&\mathbf {S} _{12}&\mathbf {S} _{13}\\0&\mathbf {S} _{22}&\mathbf {S} _{23}\\0&0&\mathbf {S} _{33}\\\end{pmatrix}}.\end{aligned}}}$$

Escribiendo para la solución de , que se puede encontrar fácilmente para matrices triangulares, y para la descomposición de Cholesky de , se pueden encontrar las siguientes relaciones: ${\textstyle \mathbf {A} \setminus \mathbf {b} }$ ${\textstyle \mathbf {A} \mathbf {x} =\mathbf {b} }$ ${\textstyle {\text{chol}}(\mathbf {M} )}$ ${\textstyle \mathbf {M} }$ $${\displaystyle {\begin{aligned}\mathbf {S} _{11}&=\mathbf {L} _{11},\\\mathbf {S} _{12}&=\mathbf {L} _{11}^{\mathrm {T} }\setminus \mathbf {A} _{12},\\\mathbf {S} _{13}&=\mathbf {L} _{13},\\\mathbf {S} _{22}&=\mathrm {chol} \left(\mathbf {A} _{22}-\mathbf {S} _{12}^{\mathrm {T} }\mathbf {S} _{12}\right),\\\mathbf {S} _{23}&=\mathbf {S} _{22}^{\mathrm {T} }\setminus \left(\mathbf {A} _{23}-\mathbf {S} _{12}^{\mathrm {T} }\mathbf {S} _{13}\right),\\\mathbf {S} _{33}&=\mathrm {chol} \left(\mathbf {L} _{33}^{\mathrm {T} }\mathbf {L} _{33}-\mathbf {S} _{23}^{\mathrm {T} }\mathbf {S} _{23}\right).\end{aligned}}}$$

Estas fórmulas se pueden utilizar para determinar el factor de Cholesky después de la inserción de filas o columnas en cualquier posición, si las dimensiones de las filas y columnas están configuradas adecuadamente (incluso a cero). El problema inverso,

$${\displaystyle {\begin{aligned}{\tilde {\mathbf {A} }}&={\begin{pmatrix}\mathbf {A} _{11}&\mathbf {A} _{12}&\mathbf {A} _{13}\\\mathbf {A} _{12}^{\mathrm {T} }&\mathbf {A} _{22}&\mathbf {A} _{23}\\\mathbf {A} _{13}^{\mathrm {T} }&\mathbf {A} _{23}^{\mathrm {T} }&\mathbf {A} _{33}\\\end{pmatrix}}\end{aligned}}}$$con descomposición de Cholesky conocida $${\displaystyle {\begin{aligned}{\tilde {\mathbf {S} }}&={\begin{pmatrix}\mathbf {S} _{11}&\mathbf {S} _{12}&\mathbf {S} _{13}\\0&\mathbf {S} _{22}&\mathbf {S} _{23}\\0&0&\mathbf {S} _{33}\\\end{pmatrix}}\end{aligned}}}$$

y el deseo de determinar el factor Cholesky $${\displaystyle {\begin{aligned}\mathbf {L} &={\begin{pmatrix}\mathbf {L} _{11}&\mathbf {L} _{13}\\0&\mathbf {L} _{33}\\\end{pmatrix}}\end{aligned}}}$$

de la matriz con filas y columnas eliminadas, ${\textstyle \mathbf {A} }$ $${\displaystyle {\begin{aligned}\mathbf {A} &={\begin{pmatrix}\mathbf {A} _{11}&\mathbf {A} _{13}\\\mathbf {A} _{13}^{\mathrm {T} }&\mathbf {A} _{33}\\\end{pmatrix}},\end{aligned}}}$$

produce las siguientes reglas: $${\displaystyle {\begin{aligned}\mathbf {L} _{11}&=\mathbf {S} _{11},\\\mathbf {L} _{13}&=\mathbf {S} _{13},\\\mathbf {L} _{33}&=\mathrm {chol} \left(\mathbf {S} _{33}^{\mathrm {T} }\mathbf {S} _{33}+\mathbf {S} _{23}^{\mathrm {T} }\mathbf {S} _{23}\right).\end{aligned}}}$$

Tenga en cuenta que las ecuaciones anteriores que implican encontrar la descomposición de Cholesky de una nueva matriz tienen todas la forma , lo que permite calcularlas de manera eficiente utilizando los procedimientos de actualización y desactualización detallados en la sección anterior. ^[22] ${\textstyle {\tilde {\mathbf {A} }}=\mathbf {A} \pm \mathbf {x} \mathbf {x} ^{*}}$

Demostración de matrices semidefinidas positivas

Prueba mediante argumento limitante

Los algoritmos anteriores muestran que toda matriz definida positiva tiene una descomposición de Cholesky. Este resultado se puede extender al caso semidefinido positivo mediante un argumento limitante. El argumento no es totalmente constructivo, es decir, no proporciona algoritmos numéricos explícitos para calcular los factores de Cholesky. ${\textstyle \mathbf {A} }$

Si es una matriz semidefinida positiva , entonces la secuencia consta de matrices definidas positivas . (Esta es una consecuencia inmediata, por ejemplo, del teorema de aplicación espectral para el cálculo funcional polinomial). Además, en la norma del operador . Del caso definido positivo, cada uno tiene descomposición de Cholesky . Por propiedad de la norma del operador, ${\textstyle \mathbf {A} }$ ${\textstyle n\times n}$ ${\textstyle \left(\mathbf {A} _{k}\right)_{k}:=\left(\mathbf {A} +{\frac {1}{k}}\mathbf {I} _{n}\right)_{k}}$ $${\displaystyle \mathbf {A} _{k}\rightarrow \mathbf {A} \quad {\text{for}}\quad k\rightarrow \infty }$$ ${\textstyle \mathbf {A} _{k}}$ ${\textstyle \mathbf {A} _{k}=\mathbf {L} _{k}\mathbf {L} _{k}^{*}}$

$${\displaystyle \|\mathbf {L} _{k}\|^{2}\leq \|\mathbf {L} _{k}\mathbf {L} _{k}^{*}\|=\|\mathbf {A} _{k}\|\,.}$$

El hecho de que esté equipado con la norma del operador es un álgebra C*. Por lo tanto, es un conjunto acotado en el espacio de Banach de operadores, por lo tanto relativamente compacto (porque el espacio vectorial subyacente es de dimensión finita). En consecuencia, tiene una subsecuencia convergente, también denotada por , con límite . Se puede comprobar fácilmente que esto tiene las propiedades deseadas, es decir , y es triangular inferior con entradas diagonales no negativas: para todos y , ${\textstyle \leq }$ ${\textstyle M_{n}(\mathbb {C} )}$ ${\textstyle \left(\mathbf {L} _{k}\right)_{k}}$ ${\textstyle \left(\mathbf {L} _{k}\right)_{k}}$ ${\textstyle \mathbf {L} }$ ${\textstyle \mathbf {L} }$ ${\textstyle \mathbf {A} =\mathbf {L} \mathbf {L} ^{*}}$ ${\textstyle \mathbf {L} }$ ${\textstyle x}$ ${\textstyle y}$

$${\displaystyle \langle \mathbf {A} x,y\rangle =\left\langle \lim \mathbf {A} _{k}x,y\right\rangle =\langle \lim \mathbf {L} _{k}\mathbf {L} _{k}^{*}x,y\rangle =\langle \mathbf {L} \mathbf {L} ^{*}x,y\rangle \,.}$$

Por lo tanto, . Debido a que el espacio vectorial subyacente es de dimensión finita, todas las topologías en el espacio de operadores son equivalentes. Por lo tanto, tiende a en la norma significa que tiende a por entrada. Esto a su vez implica que, dado que cada uno es triangular inferior con entradas diagonales no negativas, también es. ${\textstyle \mathbf {A} =\mathbf {L} \mathbf {L} ^{*}}$ ${\textstyle \left(\mathbf {L} _{k}\right)_{k}}$ ${\textstyle \mathbf {L} }$ ${\textstyle \left(\mathbf {L} _{k}\right)_{k}}$ ${\textstyle \mathbf {L} }$ ${\textstyle \mathbf {L} _{k}}$ ${\textstyle \mathbf {L} }$

Demostración por descomposición QR

Sea una matriz hermítica semidefinida positiva . Entonces puede escribirse como un producto de su matriz de raíz cuadrada , . Ahora se puede aplicar la descomposición QR a , lo que da como resultado , donde es unitaria y es triangular superior. Insertando la descomposición en la igualdad original se obtiene . El ajuste completa la prueba. ${\textstyle \mathbf {A} }$ ${\textstyle \mathbf {A} =\mathbf {B} \mathbf {B} ^{*}}$ ${\textstyle \mathbf {B} ^{*}}$ ${\textstyle \mathbf {B} ^{*}=\mathbf {Q} \mathbf {R} }$ ${\textstyle \mathbf {Q} }$ ${\textstyle \mathbf {R} }$ ${\textstyle A=\mathbf {B} \mathbf {B} ^{*}=(\mathbf {QR} )^{*}\mathbf {QR} =\mathbf {R} ^{*}\mathbf {Q} ^{*}\mathbf {QR} =\mathbf {R} ^{*}\mathbf {R} }$ ${\textstyle \mathbf {L} =\mathbf {R} ^{*}}$

Generalización

La factorización de Cholesky se puede generalizar ^{[ cita requerida ]} a matrices (no necesariamente finitas) con entradas de operadores. Sea una secuencia de espacios de Hilbert . Considere la matriz de operadores ${\textstyle \{{\mathcal {H}}_{n}\}}$

$${\displaystyle \mathbf {A} ={\begin{bmatrix}\mathbf {A} _{11}&\mathbf {A} _{12}&\mathbf {A} _{13}&\;\\\mathbf {A} _{12}^{*}&\mathbf {A} _{22}&\mathbf {A} _{23}&\;\\\mathbf {A} _{13}^{*}&\mathbf {A} _{23}^{*}&\mathbf {A} _{33}&\;\\\;&\;&\;&\ddots \end{bmatrix}}}$$

actuando sobre la suma directa

$${\displaystyle {\mathcal {H}}=\bigoplus _{n}{\mathcal {H}}_{n},}$$

donde cada uno

$${\displaystyle \mathbf {A} _{ij}:{\mathcal {H}}_{j}\rightarrow {\mathcal {H}}_{i}}$$

es un operador acotado . Si A es positivo (semidefinido) en el sentido de que para todo k finito y para cualquier

$${\displaystyle h\in \bigoplus _{n=1}^{k}{\mathcal {H}}_{k},}$$

hay , entonces existe una matriz de operadores triangulares inferiores L tal que A = LL * . También se pueden tomar las entradas diagonales de L como positivas. ${\textstyle \langle h,\mathbf {A} h\rangle \geq 0}$

Implementaciones en librerías de programación

• Lenguaje de programación C : la biblioteca científica GNU proporciona varias implementaciones de la descomposición de Cholesky.
• Sistema de álgebra computacional Maximacholesky : la función calcula la descomposición de Cholesky.
• El sistema de cálculos numéricos GNU Octave proporciona varias funciones para calcular, actualizar y aplicar una descomposición de Cholesky.
• La biblioteca LAPACK proporciona una implementación de alto rendimiento de la descomposición de Cholesky a la que se puede acceder desde Fortran , C y la mayoría de los lenguajes.
• En Python , la función choleskydel numpy.linalgmódulo realiza la descomposición de Cholesky.
• En Matlab , la cholfunción proporciona la descomposición de Cholesky. Tenga en cuenta que cholutiliza el factor triangular superior de la matriz de entrada de forma predeterminada, es decir, calcula donde es triangular superior. Se puede pasar un indicador para utilizar el factor triangular inferior en su lugar. ${\textstyle A=R^{*}R}$ ${\textstyle R}$
• En R , la cholfunción proporciona la descomposición de Cholesky.
• En Julia , la choleskyfunción de la LinearAlgebrabiblioteca estándar proporciona la descomposición de Cholesky.
• En Mathematica , la función " CholeskyDecomposition" se puede aplicar a una matriz.
• En C++ , varias bibliotecas de álgebra lineal admiten esta descomposición:
  • La biblioteca Armadillo (C++) proporciona el comando cholpara realizar la descomposición de Cholesky.
  • La biblioteca Eigen proporciona factorizaciones de Cholesky para matrices densas y dispersas.
  • En el paquete ROOT , la TDecompCholclase está disponible.

• En Analytica , la función Decomposeproporciona la descomposición de Cholesky.
• La biblioteca Apache Commons Math tiene una implementación que se puede utilizar en Java, Scala y cualquier otro lenguaje JVM.

Véase también

• Rango de ciclo
• Factorización de Cholesky incompleta
• Descomposición matricial
• Algoritmo de grado mínimo
• Raíz cuadrada de una matriz
• Ley de inercia de Sylvester
• Descomposición simbólica de Cholesky

Notas

1. Benoit (1924). "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 linéaires en nombre inferior à celui des inconnues (Procédé du Commandant Cholesky)". Boletín Géodésique (en francés). 2 : 66–67. doi :10.1007/BF03031308.
2. Press, William H.; Saul A. Teukolsky; William T. Vetterling; Brian P. Flannery (1992). Recetas numéricas en C: el arte de la computación científica (segunda edición). Cambridge University England EPress. pág. 994. ISBN 0-521-43108-5. Consultado el 28 de enero de 2009 .
3. Golub y Van Loan (1996, pág. 143), Horn y Johnson (1985, pág. 407), Trefethen y Bau (1997, pág. 174).
4. Horn y Johnson (1985, pág. 407).
5. "matrices - Diagonalización de una matriz simétrica compleja". MathOverflow . Consultado el 25 de enero de 2020 .
6. Schabauer, Hannes; Pacher, Christoph; Sunderland, Andrew G.; Gansterer, Wilfried N. (1 de mayo de 2010). "Hacia un solucionador paralelo para problemas de valores propios simétricos complejos generalizados". Procedia Computer Science . ICCS 2010. 1 (1): 437–445. doi : 10.1016/j.procs.2010.04.047 . ISSN  1877-0509.
7. Golub y Van Loan (1996, pág. 147).
8. Gentle, James E. (1998). Álgebra lineal numérica para aplicaciones en estadística . Springer. pág. 94. ISBN 978-1-4612-0623-1.
9. Higham, Nicholas J. (1990). "Análisis de la descomposición de Cholesky de una matriz semidefinida". En Cox, MG; Hammarling, SJ (eds.). Cálculo numérico fiable . Oxford, Reino Unido: Oxford University Press. pp. 161–185. ISBN 978-0-19-853564-5.
10. Krishnamoorthy, Aravindh; Menon, Deepak (2011). "Inversión de matrices mediante descomposición de Cholesky". 1111 : 4144. arXiv : 1111.4144 . Código Bibliográfico :2011arXiv1111.4144K. {{cite journal}}: Requiere citar revista |journal=( ayuda )
11. Por tanto, Anthony Man-Cho (2007). Un enfoque de programación semidefinida para el problema de realización de grafos: teoría, aplicaciones y extensiones (PDF) (PhD). Teorema 2.2.6.
12. Golub y Van Loan (1996, Teorema 4.1.3)
13. Pope, Stephen B. "Algoritmos para elipsoides". Informe de la Universidad de Cornell n.º FDA (2008): 08-01.
14. Arora, Jasbir Singh (2 de junio de 2004). Introducción al diseño óptimo. Elsevier. ISBN 978-0-08-047025-2.
15. Documentación de Matlab randn. mathworks.com.
16. ?potrf Biblioteca de núcleo matemático Intel® [1]
17. Fang, Haw-ren; O'Leary, Dianne P. (8 de agosto de 2006). "Algoritmos de Cholesky modificados: un catálogo con nuevos enfoques" (PDF) . {{cite journal}}: Requiere citar revista |journal=( ayuda )
18. Watkins, D. (1991). Fundamentos de los cálculos matriciales . Nueva York: Wiley. pág. 84. ISBN. 0-471-61414-9.
19. Nocedal, Jorge (2000). Optimización numérica . Springer.
20. Fang, Haw-ren (24 de agosto de 2007). "Análisis de factorizaciones LDLT en bloques para matrices indefinidas simétricas". {{cite journal}}: Requiere citar revista |journal=( ayuda )
21. Basado en: Stewart, GW (1998). Descomposiciones básicas . Filadelfia: Sociedad de Matemáticas Industriales y Aplicadas. ISBN 0-89871-414-1.
22. Osborne, M. (2010), Apéndice B.

Referencias

• Dereniowski, Dariusz; Kubale, Marek (2004). "Factorización de Cholesky de matrices en paralelo y clasificación de grafos". 5.ª Conferencia internacional sobre procesamiento paralelo y matemáticas aplicadas (PDF) . Notas de clase sobre informática. Vol. 3019. Springer-Verlag. págs. 985–992. doi :10.1007/978-3-540-24669-5_127. ISBN . 978-3-540-21946-0. Archivado desde el original (PDF) el 16 de julio de 2011.
• Golub, Gene H. ; Van Loan, Charles F. (1996). Cálculos matriciales (3.ª ed.). Baltimore: Johns Hopkins. ISBN 978-0-8018-5414-9.
• Horn, Roger A.; Johnson, Charles R. (1985). Análisis de matrices . Cambridge University Press. ISBN 0-521-38632-2.
• SJ Julier y JK Uhlmann. "Un método general para aproximar transformaciones no lineales de distribuciones de probabilidad".
• SJ Julier y JK Uhlmann, "Una nueva extensión del filtro Kalman a sistemas no lineales", en Proc. AeroSense: 11th Int. Symp. Aerospace/Defence Sensing, Simulation and Controls, 1997, págs. 182-193.
• Trefethen, Lloyd N. ; Bau, David (1997). Álgebra lineal numérica . Filadelfia: Sociedad de Matemáticas Industriales y Aplicadas. ISBN 978-0-89871-361-9.
• Osborne, Michael (2010). Procesos gaussianos bayesianos para predicción secuencial, optimización y cuadratura (PDF) (tesis). Universidad de Oxford.
• Ruschel, João Paulo Tarasconi, Licenciatura "Implementaciones paralelas de la descomposición de Cholesky en CPU y GPU" Universidade Federal Do Rio Grande Do Sul, Instituto De Informatica, 2016, págs. 29-30.

Enlaces externos

Historia de la ciencia

• Sur la résolution numérique des systèmes d'équations linéaires , manuscrito de Cholesky de 1910, en línea y analizado en BibNum (en francés e inglés) [para inglés, haga clic en 'A télécharger']

Información

• "Factorización de Cholesky", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Descomposición de Cholesky, resumen del análisis de datos
• Descomposición de Cholesky en www.math-linux.com
• La descomposición de Cholesky simplificada en Science Meanderthal

Código de computadora

• LAPACK es una colección de subrutinas FORTRAN para resolver problemas de álgebra lineal densa (DPOTRF, DPOTRF2, detalles de rendimiento)
• ALGLIB incluye un puerto parcial de LAPACK a C++, C#, Delphi, Visual Basic, etc. (spdmatrixcholesky, hpdmatrixcholesky)
• libflame es una biblioteca C con funcionalidad LAPACK.
• Notas y vídeo sobre la implementación de alto rendimiento de la factorización de Cholesky en la Universidad de Texas en Austin.
• Cholesky: TBB + Threads + SSE es un libro que explica la implementación del CF con TBB, threads y SSE (en español).
• Biblioteca "Ceres Solver" de Google.
• Rutinas de descomposición de LDL en Matlab.
• Armadillo es un paquete de álgebra lineal de C++
• Rosetta Code es un sitio de crestomatía de programación. en el tema de la página.
• AlgoWiki es una enciclopedia abierta de propiedades de algoritmos y características de sus implementaciones en la página del tema.
• Biblioteca de núcleo matemático Intel® oneAPI Biblioteca matemática optimizada por Intel para computación numérica ?potrf, ?potrs

Uso de la matriz en simulación

• Generación de variables aleatorias correlacionadas y procesos estocásticos, Martin Haugh, Universidad de Columbia

Calculadoras en línea

• Calculadora de matrices en línea Realiza la descomposición de Cholesky de matrices en línea.