Clase 01 (22/03) - Optimización 2019

Ejercicio

Sean: $$A = \left( \begin{array}{ccc} 1 & 0 & -1 \\ 2 & 1 & 3 \\ 0 & 1 & -1 \end{array} \right) \qquad B = \left( \begin{array}{ccc} 0 & -2 & 1 \\ 3 & -1 & 0 \\ 2 & 0 & -1 \end{array} \right) \qquad v = (-1, 4, -2)$$ Computar en Python la siguiente operación: $A^tA^2v^t+ BAv^t + <v, A_{1 \cdot}>v^t$ siendo $A_{1 \cdot}$ la primera fila de $A$

Respuesta: $(40, 17, 57)$

Descomposición de Cholesky

Lema: sea $A\in \mathbb{R}^{n\times n}$ simétrica definida positiva, existe una única $L\in \mathbb{R}^{n\times n}$ triangular inferior tal que $A = LL^t$ y $l_{ii}>0 \; \forall 1\leq i \leq n$

Veamos qué ocurre en el caso de una matriz $A\in \mathbb{R}^{3\times 3}$ simétrica definida positiva: $$ A = \left( \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array} \right) $$ Queremos escribirla como el producto $LL^t$ donde: $$ L = \left( \begin{array}{ccc} l_{11} & 0 & 0 \\ l_{21} & l_{22} & 0 \\ l_{31} & l_{32} & l_{33} \end{array} \right) $$

Luego: $$ \left( \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array} \right) = \left( \begin{array}{ccc} l_{11} & 0 & 0 \\ l_{21} & l_{22} & 0 \\ l_{31} & l_{32} & l_{33} \end{array} \right) \left( \begin{array}{ccc} l_{11} & l_{21} & l_{31} \\ 0 & l_{22} & l_{32} \\ 0 & 0 & l_{33} \end{array} \right) = \left( \begin{array}{ccc} l_{11}^2 & l_{21}l_{11} & l_{31}l_{11} \\ l_{21}l_{11} & l_{21}^2+l_{22}^2 & l_{31}l_{21}+l_{32}l_{22} \\ l_{31}l_{11} & l_{31}l_{21}+l_{32}l_{22} & l_{31}^2 + l_{32}^2 + l_{33}^2 \end{array} \right) $$ Entonces: $$L = \left( \begin{array}{ccc} \sqrt{a_{11}} & 0 & 0 \\ \dfrac{a_{21}}{l_{11}} & \sqrt{a_{22}-l_{21}^2} & 0 \\ \dfrac{a_{31}}{l_{11}} & \dfrac{a_{32}-l_{31}l_{21}}{l_{22}} & \sqrt{a_{33} - l_{31}^2-l_{32}^2} \end{array} \right) $$

Idea:

1. $l_{11} = \sqrt{a_{11}}$
2. $l_{j1} = \dfrac{a_{j1}}{l_{11}}$ para $j$ desde $2$ hasta $n$
   Para todo $i$ desde $2$ hasta $n:$
3. $l_{ii} = \sqrt{a_{ii} - \displaystyle \sum_{k=1}^{i-1}l_{ik}^2} $
4. Si $i \neq n$ : $l_{ji} = \dfrac{a_{ji} - \displaystyle\sum_{k=1}^{i-1} l_{ik}l_{jk}}{l_{ii}}$ para todo $j$ entre $i+1$ y $n$
5. Si $i < n$, luego $i = i+1$ y volver al paso 3

Para probar si funciona, se puede usar el siguiente ejemplo: pasando la siguiente matriz como input: $$A = \left({\begin{array}{*{3}{r}}4&12&-16\\12&37&-43\\-16&-43&98\\\end{array}}\right)$$ la función de Python debe devolver la siguiente matriz: $$ L = \left({\begin{array}{*{3}{r}}2&0&0\\6&1&0\\-8&5&3\\\end{array}}\right)$$