Factorització de Cholesky

Per veure si és possible fer aquesta descomposició procedirem per hipòtesi d'inducció sobre l'ordre dels menors principals, és a dir, veurem que és possible fer aquesta factorització per un menor de la matriu A d'ordre qualsevol. Considerem primer el menor d'ordre 1:

${\displaystyle A_{[1]}=(a_{1,1})}$

Podem factoritzar-lo fàcilment, definint L com:

${\displaystyle L_{[1]}=({\sqrt {(a_{1,1})}})}$

És evident que es compleix, doncs:

${\displaystyle A_{[1]}=L_{[1]}\cdot L_{[1]}^{T}=({\sqrt {(a_{1,1})}})\cdot ({\sqrt {(a_{1,1})}})=(a_{1,1})}$

Suposem, per hipòtesi d'inducció, que és possible factoritzar el menor d'ordre n d'aquesta manera:

${\displaystyle A_{[n]}=L_{[n]}\cdot L_{[n]}^{T}}$

Estudiem, aleshores, si és possible factoritzar així el menor d'ordre n+1; per començar, podem escriure:

${\displaystyle A_{[n+1]}={\begin{pmatrix}A_{[n]}&c_{[n+1]}\\c_{[n+1]}^{T}&a_{n+1,n+1}\\\end{pmatrix}}}$

On ${\displaystyle A_{[n]}}$ és el menor d'ordre n de la matriu A, ${\displaystyle c_{[n+1]}}$ és el vector que conté el n primers termes del vector columna (n+1)-èsim de la matriu A i ${\displaystyle a_{n+1,n+1}}$ és, lògicament, el terme ${\displaystyle a_{n+1,n+1}}$ de la matriu A. I també podem escriure:

${\displaystyle L_{[n+1]}={\begin{pmatrix}L_{[n]}&0_{[n+1]}\\f_{[n+1]}&l_{n+1,n+1}\\\end{pmatrix}}}$

On ${\displaystyle L_{[n]}}$ és el menor d'ordre n de la matriu L, ${\displaystyle 0_{[n+1]}}$ és un vector columna amb n components nul·les (doncs la matriu L és triangular inferior), ${\displaystyle f_{[n+1]}}$ és un vector fila amb n components i ${\displaystyle l_{n+1,n+1}}$ és, lògicament, el terme ${\displaystyle l_{n+1,n+1}}$ de la matriu L.

Estudiem ara si podem conèixer tots els elements de la factorització que desitgem i si no arribem a cap contradicció:

${\displaystyle A_{[n+1]}={\begin{pmatrix}A_{[n]}&c_{[n+1]}\\c_{[n+1]}^{T}&a_{n+1,n+1}\\\end{pmatrix}}=L_{[n+1]}\cdot L_{[n+1]}^{T}={\begin{pmatrix}L_{[n]}&0_{[n+1]}\\f_{[n+1]}&l_{n+1,n+1}\\\end{pmatrix}}\cdot {\begin{pmatrix}L_{[n]}^{T}&f_{[n+1]}^{T}\\0_{[n+1]}^{T}&l_{n+1,n+1}\\\end{pmatrix}}}$

Així doncs, obtenim els sistemes d'equacions:

${\displaystyle 1)A_{[n]}=L_{[n]}\cdot L_{[n]}^{T}}$

${\displaystyle 2)c_{[n+1]}=L_{[n]}\cdot f_{[n+1]}^{T}}$

${\displaystyle 3)c_{[n+1]}^{T}=f_{[n+1]}\cdot L_{[n]}^{T}}$

${\displaystyle 4)a_{n+1,n+1}=f_{[n+1]}\cdot f_{[n+1]}^{T}+l_{n+1,n+1}\cdot l_{[n+1,n+1]}}$

Si ens hi fixem, aplicant la hipòtesi d'inducció, l'expressió 1) és certa. 2) i 3) són equivalents; quedem-nos amb l'expressió 2). L'única incògnita d'aquesta expressió és el vector ${\displaystyle f_{[n+1]}^{T}}$ . Podem girar la volta a la truita i considerar aquesta igualtat com un sistema d'equacions lineals amb la matriu del sistema triangular inferior (que es pot resoldre mitjançant una substitució endavant) on les incògnites són les components del vector ${\displaystyle f_{[n+1]}^{T}}$ . Per tant, sempre podrem trobar un vector de longitud n que pugui satisfer les expressions 2) i 3). Finalment, queda l'expressió 4), on l'única incògnita que queda és el terme ${\displaystyle l_{n+1,n+1}}$ ; però això es redueix a trobar la solució d'una equació de 2n grau sense terme de primer grau, és a dir:

${\displaystyle l_{n+1,n+1}={\sqrt {a_{n+1,n+1}-f_{[n+1]}\cdot f_{[n+1]}^{T}}}}$

Així doncs, queda demostrat que aquesta factorització és possible per a qualsevol matriu A simètrica definida positiva (cal que sigui definida positiva, perquè contràriament l'arrel quadrada de ${\displaystyle l_{n+1,n+1}}$ no estaria ben definida per a certs termes) i, a més, la demostració és constructiva, ens proporciona un mètode per calcular aquesta factorització.

De nou, procedirem per hipòtesi d'inducció sobre l'ordre dels menors principals, és a dir, veurem que és possible fer aquesta factorització per un menor de la matriu A d'ordre qualsevol. Considerem primer el menor d'ordre 1:

${\displaystyle A_{[1]}=(a_{1,1})}$

Podem factoritzar-lo fàcilment, definint L com la matriu triangular amb uns a la diagonal:

${\displaystyle L_{[1]}=(1)}$

i D com la matriu diagonal:

${\displaystyle D_{[1]}=(a_{1,1})}$

És evident que es compleix, doncs:

${\displaystyle A_{[1]}=L_{[1]}\cdot D_{[1]}\cdot L_{[1]}^{T}=(1)\cdot (a_{1,1})\cdot (1)=(a_{1,1})}$

Suposem, per hipòtesi d'inducció, que és possible factoritzar el menor d'ordre n d'aquesta manera:

${\displaystyle A_{[n]}=L_{[n]}\cdot D_{[n]}\cdot L_{[n]}^{T}}$

Estudiem, aleshores, si és possible factoritzar així el menor d'ordre n+1; per començar, podem escriure el menor d'ordre n+1 de la matriu simètrica A com:

${\displaystyle A_{[n+1]}={\begin{pmatrix}A_{[n]}&c_{[n+1]}\\c_{[n+1]}^{T}&a_{n+1,n+1}\\\end{pmatrix}}}$

On ${\displaystyle A_{[n]}}$ és el menor d'ordre n de la matriu A, ${\displaystyle c_{[n+1]}}$ és el vector que conté els n primers termes del vector columna (n+1)-èsim de la matriu A i ${\displaystyle a_{n+1,n+1}}$ és, lògicament, el terme ${\displaystyle a_{n+1,n+1}}$ de la matriu A. I podem construir els menors d'ordre n+1:

${\displaystyle L_{[n+1]}={\begin{pmatrix}L_{[n]}&0_{[n+1]}\\f_{[n+1]}&1\\\end{pmatrix}}}$

${\displaystyle D_{[n+1]}={\begin{pmatrix}D_{[n]}&0_{[n+1]}\\0_{[n+1]}^{T}&d_{n+1,n+1}\\\end{pmatrix}}}$

On ${\displaystyle L_{[n]}}$ és el menor d'ordre n de la matriu L, ${\displaystyle D_{[n]}}$ és el menor d'ordre n de la matriu D, ${\displaystyle 0_{[n+1]}}$ és un vector columna amb n components nul·les, ${\displaystyle f_{[n+1]}}$ és un vector fila amb n components i ${\displaystyle d_{n+1,n+1}}$ és, lògicament, el terme ${\displaystyle d_{n+1,n+1}}$ de la matriu D.

Estudiem si podem conèixer tots els elements de la factorització que desitgem sense arribar a cap contradicció:

${\displaystyle A_{[n+1]}={\begin{pmatrix}A_{[n]}&c_{[n+1]}\\c_{[n+1]}^{T}&a_{n+1,n+1}\\\end{pmatrix}}=L_{[n+1]}\cdot D_{[n+1]}\cdot L_{[n+1]}^{T}={\begin{pmatrix}L_{[n]}&0_{[n+1]}\\f_{[n+1]}&1\\\end{pmatrix}}\cdot {\begin{pmatrix}D_{[n]}&0_{[n+1]}\\0_{[n+1]}^{T}&d_{n+1,n+1}\\\end{pmatrix}}\cdot {\begin{pmatrix}L_{[n]}^{T}&f_{[n+1]}^{T}\\0_{[n+1]}^{T}&1\\\end{pmatrix}}}$

Així doncs, obtenim els sistemes d'equacions:

${\displaystyle 1)A_{[n]}=L_{[n]}\cdot D_{[n]}\cdot L_{[n]}^{T}}$

${\displaystyle 2)c_{[n+1]}=L_{[n]}\cdot D_{[n]}\cdot f_{[n+1]}^{T}}$

${\displaystyle 3)c_{[n+1]}^{T}=f_{[n+1]}\cdot D_{[n]}\cdot L_{[n]}^{T}}$

${\displaystyle 4)a_{n+1,n+1}=f_{[n+1]}\cdot D_{[n]}\cdot f_{[n+1]}^{T}+d_{n+1,n+1}}$

Si ens hi fixem, aplicant la hipòtesi d'inducció, l'expressió 1) és certa. 2) i 3) són equivalents; quedem-nos amb l'expressió 2). L'única incògnita d'aquesta expressió és el vector ${\displaystyle f_{[n+1]}}$ . Tanmateix, podem girar la volta a la truita i pensar que estem resolent un sistema d'equacions de terme independent ${\displaystyle c_{[n+1]}}$ i matriu ${\displaystyle L_{[n]}\cdot D_{[n]}}$ , que és una matriu triangular inferior (i, per tant, resoldre aquest sistema d'equacions és directe, per substitució endavant). Finalment, queda l'expressió 4), on l'única incògnita que roman oculta és el terme ${\displaystyle d_{n+1,n+1}}$ ; però trobar aquest terme es redueix a calcular:

${\displaystyle d_{n+1,n+1}=a_{n+1,n+1}-f_{[n+1]}\cdot D_{[n]}\cdot f_{[n+1]}^{T}}$

Així doncs, és possible factoritzar A de la manera desitjada.

Nota: La condició de ser semidefinida o no singular és necessària per poder resoldre el sistema d'equacions per substitució enrere.