42) Factorizacion Cholesky

Clase 42: Factorización de Cholesky

📚 Introducción

La factorización de Cholesky es una factorización especial de matrices simétricas y positivas definidas que tiene importantes aplicaciones en álgebra lineal computacional, estadística, optimización y análisis numérico. Es significativamente más eficiente que la factorización LU estándar para matrices con estas propiedades especiales.

Esta factorización es fundamental en muchos algoritmos numéricos modernos, incluyendo métodos de mínimos cuadrados, simulación de variables aleatorias correlacionadas, optimización con restricciones, y resolución de sistemas de ecuaciones lineales con matrices simétricas positivas definidas.

Objetivos de la Clase

• Comprender la definición de factorización de Cholesky
• Entender cuándo una matriz admite factorización de Cholesky
• Dominar el algoritmo de construcción de la factorización
• Aplicar la factorización a problemas prácticos
• Relacionar con matrices positivas definidas y formas cuadráticas
• Comparar con otras factorizaciones (LU, QR)

---

1. Definición de Factorización de Cholesky

1.1 Definición Básica

Definición - Factorización de Cholesky

Una factorización de Cholesky de una matriz simétrica A es una factorización de la forma:

$A=R^{T}R$

donde R es una matriz triangular superior con entradas diagonales positivas.

Equivalentemente, se puede escribir como:

$A=L{L}^T$

donde L = Rᵀ es una matriz triangular inferior con entradas diagonales positivas.

Observación Importante

La factorización de Cholesky solo existe para matrices simétricas y positivas definidas. Si A es simétrica pero no positiva definida, la factorización puede fallar o requerir pivoteo.

1.2 Conexión con Matrices Positivas Definidas

Teorema - Existencia de Factorización de Cholesky

Una matriz simétrica A de n × n admite una factorización de Cholesky A = RᵀR si y solo si A es positiva definida.

Cuando A es positiva definida, la factorización de Cholesky es única (con la convención de diagonales positivas en R).

Criterio Práctico

Una matriz A admite factorización de Cholesky si y solo si:

1. A es simétrica (Aᵀ = A)
2. Todos los valores propios de A son positivos
3. Equivalentemente, la forma cuadrática xᵀAx > 0 para toda x ≠ 0

---

2. Algoritmo de Factorización de Cholesky

2.1 Algoritmo para Matrices 2×2

Ejemplo 1: Factorización de Cholesky para matriz 2×2

Sea A = $\left[\begin{array}{cc}4& 2\\ 2& 5\end{array}\right]$. Encuentre la factorización de Cholesky A = RᵀR.

Verificación previa: ¿Es A positiva definida?

• A es simétrica ✓
• det(A) = 4(5) - 2(2) = 20 - 4 = 16 > 0 ✓
• Valores propios: λ₁ = 6, λ₂ = 3 (ambos positivos) ✓

Construcción de R:

Sea R = $\left[\begin{array}{cc}{r}_{11}& r_{12}\\ 0& r_{22}\end{array}\right]$ con r₁₁, r₂₂ > 0.

Entonces:

$R^{T}R=\left[\begin{array}{cc}{r}_{11}& 0\\ r_{12}& r_{22}\end{array}\right]\left[\begin{array}{cc}{r}_{11}& r_{12}\\ 0& r_{22}\end{array}\right]=\left[\begin{array}{cc}{r}_{11}^2& r_{11}{r}_{12}\\ r_{11}{r}_{12}& r_{12}^2+r_{22}^2\end{array}\right]$

Igualando con A:

$\left[\begin{array}{cc}{r}_{11}^2& r_{11}{r}_{12}\\ r_{11}{r}_{12}& r_{12}^2+r_{22}^2\end{array}\right]=\left[\begin{array}{cc}4& 2\\ 2& 5\end{array}\right]$

Paso 1: De r₁₁² = 4, obtenemos r₁₁ = 2 (tomamos raíz positiva)

Paso 2: De r₁₁r₁₂ = 2, obtenemos r₁₂ = 2/r₁₁ = 2/2 = 1

Paso 3: De r₁₂² + r₂₂² = 5, obtenemos r₂₂² = 5 - 1² = 4, luego r₂₂ = 2

Resultado:

$R=\left[\begin{array}{cc}2& 1\\ 0& 2\end{array}\right]$

Verificación:

$R^{T}R=\left[\begin{array}{cc}2& 0\\ 1& 2\end{array}\right]\left[\begin{array}{cc}2& 1\\ 0& 2\end{array}\right]=\left[\begin{array}{cc}4& 2\\ 2& 5\end{array}\right]=A✓$

2.2 Algoritmo General

Algoritmo de Cholesky (Forma Triangular Superior)

Para factorizar A = RᵀR donde R es triangular superior:

Para j = 1 hasta n:

1. Calcular el elemento diagonal: $r_{jj}=\sqrt{a_{jj}-{\sum }_{k=1}^{j-1}{r}_{kj}^2}$

2. Calcular los elementos sobre la diagonal en la fila j: $r_{ji}=\frac{1}{r_{jj}}\left(a_{ji}-{\sum }_{k=1}^{j-1}{r}_{kj}{r}_{ki}\right)\text{para }i>j$

Complejidad computacional: O(n³/3), aproximadamente la mitad del costo de factorización LU.

Condición de Falla

Si en algún paso encontramos que el término bajo la raíz cuadrada es negativo o cero:

$a_{jj}-{\sum }_{k=1}^{j-1}{r}_{kj}^2\le 0$

entonces la matriz no es positiva definida y la factorización de Cholesky no existe.

---

3. Ejemplos Completos

3.1 Matriz 3×3

Ejemplo 2: Factorización de Cholesky 3×3

Sea A = $\left[\begin{array}{ccc}4& 2& 2\\ 2& 5& 3\\ 2& 3& 6\end{array}\right]$. Encuentre R tal que A = RᵀR.

Paso 1: Calcular r₁₁

$r_{11}=\sqrt{a_{11}}=\sqrt{4}=2$

Paso 2: Calcular r₁₂ y r₁₃

$r_{12}=\frac{a_{12}}{r_{11}}=\frac{2}{2}=1$

$r_{13}=\frac{a_{13}}{r_{11}}=\frac{2}{2}=1$

Paso 3: Calcular r₂₂

$r_{22}=\sqrt{a_{22}-r_{12}^2}=\sqrt{5-1^2}=\sqrt{4}=2$

Paso 4: Calcular r₂₃

$r_{23}=\frac{a_{23}-r_{12}{r}_{13}}{r_{22}}=\frac{3-1\cdot 1}{2}=\frac{2}{2}=1$

Paso 5: Calcular r₃₃

$r_{33}=\sqrt{a_{33}-r_{13}^2-r_{23}^2}=\sqrt{6-1^2-1^2}=\sqrt{4}=2$

Resultado:

$R=\left[\begin{array}{ccc}2& 1& 1\\ 0& 2& 1\\ 0& 0& 2\end{array}\right]$

Verificación:

$R^{T}R=\left[\begin{array}{ccc}2& 0& 0\\ 1& 2& 0\\ 1& 1& 2\end{array}\right]\left[\begin{array}{ccc}2& 1& 1\\ 0& 2& 1\\ 0& 0& 2\end{array}\right]=\left[\begin{array}{ccc}4& 2& 2\\ 2& 5& 3\\ 2& 3& 6\end{array}\right]=A✓$

3.2 Matriz que No Admite Factorización

Ejemplo 3: Matriz que falla la factorización de Cholesky

Sea A = $\left[\begin{array}{cc}1& 2\\ 2& 3\end{array}\right]$. Intente factorizar como A = RᵀR.

Verificación: ¿Es A positiva definida?

• A es simétrica ✓
• det(A) = 1(3) - 2(2) = 3 - 4 = -1 < 0 ✗

La matriz no es positiva definida (tiene determinante negativo).

Intentando el algoritmo:

Paso 1: r₁₁ = √1 = 1 ✓

Paso 2: r₁₂ = 2/1 = 2 ✓

Paso 3: r₂₂ = √(3 - 2²) = √(3 - 4) = √(-1) ✗

Conclusión: La factorización falla porque encontramos una raíz cuadrada de un número negativo. Esto confirma que A no es positiva definida.

---

🎯 Conceptos Clave

Resumen

1. Factorización de Cholesky: A = RᵀR con R triangular superior
2. Existencia: Solo para matrices simétricas y positivas definidas
3. Eficiencia: ~n³/3 operaciones (mitad del costo de LU)
4. Aplicaciones: Sistemas lineales, mínimos cuadrados, simulación

---

🏷️ Tags

algebra-lineal factorizacion-cholesky matrices-positivas-definidas clase-42 capitulo-7