Práctica 2 (Métodos Numéricos)

Ejercicio 9

Probar que si $A\in R^{nxn}$ tiene todas sus submatrices principales no singulares entonces A tiene factorizacion LU sin pivoteo. Ademas esa factorizacion es unica.

Por induccion en n.
Casos base:
n=1, $A_{1}={\begin{bmatrix}a_{11}\end{bmatrix}}=1\ a_{11}$
n=2, $A_{2}={\begin{bmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{bmatrix}}$ como $det(A_{1})\neq 0\iff a_{11}\neq 0$ entonces puedo hacer gauss sin intercambio de filas en $A_{2}$ entonces se que existen unicos $U_{2},L_{2}$ tal que $A_{2}=U_{2}L_{2}$

Paso inductivo:
Supongo que vale $A_{n}={\begin{bmatrix}A_{n-1}&c_{n}\\\ &\ \\\ &\ \\f_{n}&a_{n,n}\end{bmatrix}}=L_{n}U_{n}={\begin{bmatrix}L_{n-1}&\ &0\\\ &\ &0\\\ &\ &\vdots \\l_{n}&\ &1\end{bmatrix}}{\begin{bmatrix}U_{n-1}&u_{n}\\\ &\ \\\ &\ \\0\ldots 0&u_{n,n}\end{bmatrix}}$
donde $A_{n-1},L_{n-1}yU_{n-1}$ son matrices de n-1 x n-1, $c_{n}yu_{n}$ columnas de n-1 elementos asi como $f_{n}yl_{n}$ son filas de n-1 elementos.
Quiero ver que vale $A_{n+1}={\begin{bmatrix}A_{n}&c_{n+1}\\\ &\ \\\ &\ \\f_{n+1}&a_{n+1,n+1}\end{bmatrix}}=L_{n+1}U_{n+1}={\begin{bmatrix}L_{n}&\ &0\\\ &\ &0\\\ &\ &\vdots \\l_{n+1}&\ &1\end{bmatrix}}{\begin{bmatrix}U_{n}&u_{n+1}\\\ &\ \\\ &\ \\0\ldots 0&u_{n+1,n+1}\end{bmatrix}}$
Es decir que mis incognitas son $l_{n+1},u_{n+1}\ y\ u_{n+1,n+1}$
Como los bloques son del mismo tama~no puedo multiplicar por bloques y queda
i) Despejo $l_{n+1}$ haciendo: $l_{n+1}U_{n}=f_{n+1}$.
ii) Despejo $u_{n+1}$ haciendo: $c_{n+1}=L_{n}U_{n+1}$.
iii) Despejo $u_{n+1,n+1}$ haciendo:$l_{n+1}u_{n+1}+u_{n+1,n+1}=a_{n+1,n+1}$.
i) y ii) tiene soluciones unicas porque $U_{n}$y $L_{n}$ son inversibles.

Ejercicio 10

Supongamos que una matriz $A\in R^{nxn}$ tiene factorizacion A = LU y que L y U son conocidas. Dar una algoritmo que calcule el elemento (i,j) de $A^{-1}$ en aproximadamente $(n-j)^{2}+(n-i)^{2}$ flops. (Un flop es una operacion de punto flotante)

Si A = LU entonces $A^{-1}=U^{-1}L^{-1}$ y por lo tanto $A_{i,j}^{-1}=fila_{i}U^{-1}\times col_{j}L^{-1}$.
Calcular $col_{j}L^{-1}$ nos lleva O($n^{2}$) porque se puede plantear directamente el sistema $Lx=e_{j}$ donde $e_{j}$ es el canonico con 1 en la posicion j y $x$ nos daria la columna j de $L^{-1}$. Se puede llevar a O($(n-j)^{2}$) ya que se sabe de antemano que la columna j de $L^{-1}$ tiene j ceros, es decir no es necesario calcularlos. Idem con $fila_{i}U^{-1}$.

Ejercicio 11

Sea $A\in R^{nxn}$ y sea $A^{k}$ la matriz que se obtiene a partir de A por el metodo de eliminacion Gaussiana cuando las primeras k columnas ya han sido trianguladas. Usando propiedades de determinantes, probar que A es no singular si y solo si $A^{k}$ es no singular.

Nota: $L_{i}$ es la matriz identidad con los coeficientes $m_{i,j}={\frac {a_{i,j}}{a_{j,j}}}$ que se usaron en la eliminacion gaussiana para poner un 0 en la posicion i,j.
Por ejemplo $L_{1}={\begin{bmatrix}1&0&0&0\\-m_{21}&1&0&0\\-m_{31}&0&1&0\\-m_{41}&0&0&1\end{bmatrix}}$ para una matriz de 4x4.
Asi, $A^{k}=L_{k}*L_{k-1}*\ldots *L_{1}*A$

Volviendo al ejercicio $A^{k}\ inversible\iff det(A^{k})\neq 0\iff det(L_{k}*L_{k-1}*\ldots *L_{1}*A)\neq 0$ $\iff det(L_{k})*det(L_{k-1})*\ldots *det(L_{1})*det(A)\neq 0\iff det(A)\neq 0\iff A\ inversible$

Ejercicio 24

Sea $R\in R^{nxn}$ tal que $||R||<1$, siendo $||\bullet ||$ cualquier norma consistente.
a) Probar que $||(I+R)^{-1}||\leq {\frac {1}{1-||R||}}$.
b) Sea $A\in R^{nxn}$ una matriz inversible y $\delta A\in R^{nxn}$ tal que $||\delta A||<{\frac {1}{||A^{-1}||}}$. Probar que $A+\delta A$ es inversible y vale $||(A+\delta A)^{-1}||\leq {\frac {||A^{-1}||}{1-||A^{-1}||||\delta A||}}$

a) No se si el enunciado supone que (I+R) es inversible o hay que demostrarlo, por las dudas es asi:

$||R||<1$ entonces $\sup _{||x||=1}||Rx||<1$. Si I+R es inversible entonces Nu(I+R) = {0}
Sea $||x||=1,(I+R)x=0\iff x+Rx=0\iff Rx=-x\Longrightarrow ||Rx||=||x||=1$.
Da que para que exista un x tal que $||x||=1$ y $(I+R)x=0$ entonces $||Rx||=1$ lo cual ya sabemos que no pasa. Como cualquier vector se puede llevar a vector de norma 1 el unico x que cumple es 0 entonces $(I+R)$ es inversible.

Volviendo al ejercicio, por inspiracion divina se me ocurre que
$I=(I+R)^{-1}(I+R)=(I+R)^{-1}+(I+R)^{-1}R\Longrightarrow (I+R)^{-1}=I-(I+R)^{-1}R.$
Meto norma en los 2 lados
$||(I+R)^{-1}||=||I-(I+R)^{-1}R||\leq ||I||+||(I+R)^{-1}R||\leq 1+||(I+R)^{-1}||||R||$

$||I||\leq 1$ porque $||I||=||II||\leq ||I||^{2}$ ya que es consistente. El unico numero que cumple esto es 1.

Entonces, $||(I+R)^{-1}||\leq 1+||(I+R)^{-1}||||R||\Longrightarrow$
$||(I+R)^{-1}||(1-||R||)\leq 1\Longrightarrow ||(I+R)^{-1}||\leq {\frac {1}{1-||R||}}$
$||R||<1$ asi que no se puede pasar dividiendo.

b)
i) $A+\delta A$ es inversible. Primero pruebo que $I+\delta A(A^{-1})$ es inversible por lo hecho en a). Para eso veo que $||\delta A(A^{-1})||<1$:
$||\delta A(A^{-1})||\leq ||\delta A||||A^{-1}||<{\frac {||A^{-1}||}{||A^{-1}||}}=1\Longrightarrow (I+\delta A(A^{-1}))$ inversible.
Pero entonces $det(A+\delta A)=det(A(I+(\delta A(A^{-1})))=det(A)*det(blah)=0$ porque A es inversible, entonces $A+\delta A$ es inversible.

ii) $||(A+\delta A)^{-1}||=||A(I+(\delta A(A^{-1}))||=||(I+(\delta A(A^{-1}))^{-1}A^{-1}||\underbrace {\leq } _{por\ a)}$
${\frac {||A^{-1}||}{1-||\delta A(A)^{-1}||}}\leq {\frac {||A^{-1}||}{1-||\delta A||||A^{-1}||}}$
en el ultimo paso use que $||\delta A||||A^{-1}||<1$ (por enunciado) y asi aseguro que no divide por 0.