Cholesky

Definición

Una matriz \(A\) es definida positiva si \(x^TAx > 0\) para todo \(x \neq 0\).

Propiedades

  • Una matriz definida positiva es simétrica.
  • Una matriz definida positiva tiene todos sus valores propios positivos.
  • Una matriz definida positiva tiene todos sus menores principales positivos.

Ejemplo

La matriz \(A = \begin{bmatrix} 1 & 2 \\ 2 & 5 \end{bmatrix}\) es definida positiva.

Algoritmo

El algoritmo de Cholesky es un método para calcular la factorización de Cholesky de una matriz definida positiva.

Sea \(A\) una matriz simetrica definida positiva de orden \(n\). Entonces, existe una matriz triangular inferior \(G\) con elementos reales positivos en la diagonal tal que \(A = GG^T\). Para encontrar \(G\), se procede de la siguiente manera:

Sea la matriz \[G=\begin{bmatrix} g_{11} & 0 & \cdots & 0 \\ g_{21} & g_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ g_{n1} & g_{n2} & \cdots & g_{nn} \end{bmatrix}\]

Entonces, \(A = GG^T\) implica que

\[\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{bmatrix} = \begin{bmatrix} g_{11}^2 & g_{11}g_{21} & \cdots & g_{11}g_{n1} \\ g_{11}g_{21} & g_{21}^2 + g_{22}^2 & \cdots & g_{21}g_{n1} + g_{22}g_{n2} \\ \vdots & \vdots & \ddots & \vdots \\ g_{11}g_{n1} & g_{21}g_{n1} + g_{22}g_{n2} & \cdots & g_{n1}^2 + g_{n2}^2 + \cdots + g_{nn}^2 \end{bmatrix}\]

de esta forma tenemos que

\[g_{11}^2 = a_{11} \Rightarrow g_{11} = \sqrt{a_{11}}\] \[g_{11}g_{21} = a_{12} \Rightarrow g_{21} = \frac{a_{12}}{g_{11}}\]

\[\vdots\]

\[g_{11}g_{n1} = a_{1n} \Rightarrow g_{n1} = \frac{a_{1n}}{g_{11}}\]

Ahora debemos calcular los elementos de la segunda fila de \(G\).

\[g_{21}^2 + g_{22}^2 = a_{22} \Rightarrow g_{22} = \sqrt{a_{22} - g_{21}^2}\]

\[g_{21}g_{n1} + g_{22}g_{n2} = a_{2n} \Rightarrow g_{n2} = \frac{a_{2n} - g_{21}g_{n1}}{g_{22}}\]

Ventajas dela algoritmod e Cholesky

  • El algoritmo de Cholesky es una técnica importante en álgebra lineal numérica.
  • Se utiliza para factorizar una matriz simétrica definida positiva en el producto de una matriz triangular inferior y su traspuesta.
  • Esta factorización tiene aplicaciones en la resolución de sistemas de ecuaciones lineales y la estimación de covarianzas en estadísticas.
  • El algoritmo de Cholesky es aproximadamente el doble de eficiente que la eliminación gaussiana para resolver sistemas de ecuaciones lineales.
  • También es más estable numéricamente.

Algoritmo de Cholesky

import numpy as np

def cholesky_decomposition(A): n = len(A) L = np.zeros_like(A)

for i in range(n):
    for j in range(i + 1):
        if i == j:
            temp = A[i, i] - np.sum(L[i, :i] ** 2)
            L[i, i] = np.sqrt(temp) if temp > 0 else 0.0
        else:
            L[i, j] = (A[i, j] - np.sum(L[i, :j] * L[j, :j])) / L[j, j]

return L

A = np.array([[4, 2, 2], [2, 5, 5], [2, 5, 9]]) L = cholesky_decomposition(A)

Ejercicios

  1. Implementar el algoritmo de Cholesky en Python.
  2. Resulva el siguiente sistema de ecuaciones usando Cholesky

\[\begin{bmatrix} 4 & 2 & 2 \\ 2 & 5 & 5 \\ 2 & 5 & 9 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 2 \\ 3 \\ 5 \end{bmatrix}\]

  • Halle el numero de condición de la matriz asociado al sistema de ecuaciones anterior.

  1. Halle la inversa de la matriz \(A\) usando Cholesky.

  2. Sea el sistema

\[A=\begin{bmatrix} 1&1&1&1 \\1&1&1&2 \\ 1&1&2&3 \\1&2&3&4\end{bmatrix}\begin{bmatrix} x_1 \\ x_2 \\ x_3\\x_4 \end{bmatrix} = \begin{bmatrix}1\\ 2 \\ 3 \\ 4 \end{bmatrix}\] * Encuentre el número de condición de la matriz \(A\). * Encuentre la solución el sistema usando Cholesky y LU, Compare las respuestas