Factorisació de Cholesky

En matemàtiques, la factorisació o descomposició de Cholesky pren el seu nom del matemàtic André-Louis Cholesky, qui va trobar que una matriu simètrica definida positiva pot ser descomposta com el producte d'una matriu triangular inferior i la trasponer de la matriu triangular inferior. La matriu triangular inferior és el triàngul de Cholesky de la matriu original positiva definida. El resultat de Cholesky ha segut estés a matrius en entrades complexes. És una manera de resoldre sistemes d'equacions matriciales i es deriva de la factorisació LU en una chicoteta variació.

Qualsevol matriu quadrada A en pivots no nuls pot ser escrita com el producte d'una matriu triangular inferior L i una matriu triangular superior O; açò rep el nom de factorisació LU. No obstant, si A és simètrica i definida positiva, es poden triar els factors tals que O és la transpuesta de L, i açò es diu la descomposició o factorisació de Cholesky. Tant la descomposició LU com la descomposició de Cholesky són usades per a resoldre sistemes d'equacions llineals. Quan és aplicable, la descomposició de Cholesky és dos voltes més eficient que la descomposició LU.

Definició

En general, si A és Hermitiana i definida positiva, llavors A pot ser descomposta com

$𝐀=𝐋{𝐋}^{*},$

a on L és una matriu triangular inferior en entrades diagonals estrictament positives i L^* representa la conjugada trasponer de L. Esta és la descomposició de Cholesky.

La descomposició de Cholesky és única: donada una matriu Hermitiana positiva definida A, hi ha una única matriu triangular inferior L en entrades diagonals estrictament positives tals que A = LL^*. El recíproc es té trivialmente: si A es pot escriure com LL^* per a alguna matriu inversible L, triangular inferior o no, llavors A és Hermitiana i definida positiva.

El requisit de que L tinga entrades diagonals estrictament positives pot estendre's per al cas de la descomposició en el cas de ser semidefinida positiva. La proposició es llig ara: una matriu quadrada A té una descomposició de Cholesky si i només si A és Hermitiana i semidefinida positiva. Les factorisació de Cholesky per a matrius semidefinidas positives no són úniques en general.

En el cas especial que A és una matriu simètrica definida positiva en entrades reals, L es pot assumir també en entrades reals. Una Matriu D diagonal en entrades positives en la diagonal (valors propis de A), és factorisable com $D=\sqrt{D}\sqrt{D}$, a on $\sqrt{D}$ és matriu que la seua diagonal consistix en la raïl quadrada de cada element de D, que prenem com a positius. Aixina:

$A=LU=LD{U}_0=LD{L}^t=L(\sqrt{D}\sqrt{D})L^t=(L\sqrt{D})(\sqrt{D}{L}^t)=(L\sqrt{D})(L\sqrt{D}{)}^t=K{K}^t$

La factorisació pot ser calculada directament a través de les següents fòrmules (en este cas realisem la factorisació superior $A=U^T*U$):
$u_{ii}^2=a_{ii}-\sum _{k=1}^{i-1}{u}_{ki}^2$ per als elements de la diagonal principal, i:

$u_{ij}=\frac{a_{ij}-\sum _{k=1}^{i-1}{u}_{ki}{u}_{kj}}{u_{ii}}$ per al restant dels elements. A on $u_{ij}$ són els elements de la matriu U.

Aplicacions

La descomposició de Cholesky s'usa principalment per a trobar la solució numèrica d'equacions llineals Ax = b. Si A és simètrica i positiva definida, llavors es pot solucionar Ax = b calculant primer la descomposició de Cholesky A = LL^T, després resolent Ly = b per a i, i finalment resolent L^Tx = i per a x.

Mínims quadrats llineals

Sistemes de la forma Ax = b en A simètrica i definida positiva apareixen a sovint en la pràctica. Per eixemple, les equacions normals en problemes de mínims quadrats llineals són problemes d'esta forma. Podria ocórrer que la matriu A prové d'un funcional d'energia el qual deu ser positiu baix consideracions físiques; açò ocorre freqüentment en la solució numèrica d'equacions diferencials parcials.

Simulació de Montecarlo

La descomposició de Cholesky s'usa comunament en el método de Montecarlo per a simular sistemes en variables múltiples correlacionadas: la matriu de correlació entre variables és descomposta, per a obtindre la triangular inferior L. Aplicant esta a un vector de sorolls simulats incorrelacionados o, produïx un vector Lu en les propietats de covarianza del sistema a ser modelat.

Filtre de Kalman

Els filtres de Kalman usen freqüentment la descomposició de Cholesky per a triar un conjunt de punts sigma. El filtre de Kalman seguix l'estat promig d'un sistema com un vector x de llongitut n i covarianza donada per una matriu P de tamany nxn. La matriu P és sempre semidefinida positiva i pot descompondre's com LL^T. Les columnes de L pot ser adicionadas i restades de la mija x per a formar un conjunt de 2N vectores cridats els punts sigma. Estos punts sigma capturen la mija i la covarianza de l'estat del sistema.