Edición de «Práctica 2 (Métodos Numéricos)»

{{Back|Métodos Numéricos}}

==Ejercicio 6==
'''Sea <math>A \in R^{nxn}</math> y sea <math>A^{k}</math> la matriz que se obtiene a partir de A por el método de eliminación Gaussiana cuando las primeras k columnas ya han sido trianguladas. 


b) Usando propiedades de determinantes, probar que A es no singular si y solo si <math>A^{k}</math> es no singular.'''<br><br>

Nota: <math>L_i</math> es la matriz identidad con los coeficientes <math>m_{i,j}=\frac{a_{i,j}}{a_{j,j}}</math> que se usaron en la eliminacion gaussiana para poner un 0 en la posicion i,j.<br> Por ejemplo
<math>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}</math> para una matriz de 4x4.<br>
Asi, <math>A^{k} = L_k * L_{k-1} * \ldots * L_1 * A </math><br><br>

Volviendo al ejercicio <math>A^{k}\ inversible \leftrightarrow det(A^{k}) \neq 0 \leftrightarrow det(L_k * L_{k-1} * \ldots * L_1 * A) \neq 0 </math>
<math> \leftrightarrow det(L_k) * det(L_{k-1}) * \ldots * det(L_1) * det(A) \neq 0 \leftrightarrow det(A) \neq 0 \leftrightarrow A \ inversible</math>

==Ejercicio 7==
'''Probar que si <math>A \in R^{nxn}</math> tiene todas sus submatrices principales no singulares entonces A tiene factorizacion LU sin pivoteo. Ademas esa factorización es única.'''<br><br>
Por induccion en n.<br>
Casos base:<br>
n=1, <math>A_1 = \begin{bmatrix} a_{11} \end{bmatrix} = 1\  a_{11}</math><br>
n=2, <math>A_2 = \begin{bmatrix} a_{11} & a_{12} \\
a_{21} & a_{22} \end{bmatrix} </math> como <math>det(A_1) \neq 0 \leftrightarrow a_{11} \neq 0</math> entonces puedo hacer gauss sin intercambio de filas en <math>A_2</math> entonces se que existen unicos <math> U_2, L_2 </math> tal que <math>A_2 = U_2 L_2</math><br><br>
Paso inductivo:<br>
Supongo que vale <math>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}</math><br>
donde <math>A_{n-1}, L_{n-1} y U_{n-1}</math> son matrices de n-1 x n-1, <math>c_n y u_n</math> columnas de n-1 elementos asi como <math>f_n y l_n</math> son filas de n-1 elementos.<br>
Quiero ver que vale <math>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}</math><br>
Es decir que mis incógnitas son <math>l_{n+1}, u_{n+1}\ y\ u_{n+1,n+1}</math><br>
Como los bloques son del mismo tamaño puedo multiplicar por bloques y queda<br>
i) Despejo <math>l_{n+1}</math> haciendo: <math>l_{n+1} U_n = f_{n+1}</math>.<br>
ii) Despejo <math>u_{n+1}</math> haciendo: <math>c_{n+1} = L_n U_{n+1}</math>.<br>
iii) Despejo <math>u_{n+1,n+1}</math> haciendo:<math> l_{n+1} u_{n+1} + u_{n+1,n+1} = a_{n+1,n+1}</math>.<br>
i) y ii) tiene soluciones únicas porque <math>U_n</math>y <math> L_n</math> son inversibles.

==Ejercicio 8==
'''Supongamos que una matriz <math>A \in R^{nxn}</math> tiene factorizacion A = LU y que L y U son conocidas. Dar una algoritmo que calcule el elemento (i,j) de <math>A^{-1}</math> en aproximadamente <math>(n-j)^2 + (n-i)^2</math> flops. (Un flop es una operacion de punto flotante)'''<br><br>
Si A = LU entonces <math>A^{-1} = U^{-1} L^{-1}</math> y por lo tanto <math>A^{-1}_{i,j} = fila_i U^{-1} \times col_j L^{-1}</math>.<br>
Calcular <math>col_j L^{-1}</math> nos lleva O(<math>n^2</math>) porque se puede plantear directamente el sistema
<math>L x = e_j</math> donde <math>e_j</math> es el canonico con 1 en la posicion j y <math>x</math> nos daría la columna j de <math>L^{-1}</math>. Se puede llevar a O(<math>(n-j)^2</math>) ya que se sabe de antemano que la columna j de <math>L^{-1}</math> tiene j ceros, es decir no es necesario calcularlos. Idem con <math>fila_i U^{-1}</math>.

==Ejercicio 21==
'''Sea <math> R \in R^{nxn}</math> tal que <math>||R|| < 1 </math>, siendo <math>|| \bullet ||</math> cualquier norma consistente.<br>
b) Probar que <math>||(I+R)^{-1}|| \leq \frac{1}{1-||R||}</math>.<br>
c) Sea <math>A \in R^{nxn}</math> una matriz inversible y <math>\delta A \in R^{nxn}</math> tal que <math>||\delta A|| < \frac{1}{||A^{-1}||}</math>. Probar que <math>A + \delta A</math> es inversible y vale <math>|| (A+\delta A)^{-1}|| \leq \frac{||A^{-1}||}{1-||A^{-1}|| ||\delta A||}</math>'''<br><br><br>

b) No se si el enunciado supone que (I+R) es inversible o hay que demostrarlo, por las dudas es asi:<br><br>
<math>||R|| < 1</math> entonces <math>\sup_{||x||=1} ||Rx|| < 1</math>. Si I+R es inversible entonces Nu(I+R) = {0}<br>
Sea <math>||x||=1, (I+R)x = 0 \leftrightarrow x+Rx = 0 \leftrightarrow Rx = -x \Longrightarrow ||Rx|| = ||x|| = 1</math>.<br>
Da que para que exista un x tal que <math>||x||=1</math> y <math>(I+R)x = 0</math> entonces <math>||Rx|| = 1</math> 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 <math>(I+R)</math> es inversible.<br><br>
Volviendo al ejercicio, por inspiracion divina se me ocurre que<br>
<math>I = (I+R)^{-1} (I+R) = (I+R)^{-1} + (I+R)^{-1}R \Longrightarrow (I+R)^{-1} = I - (I+R)^{-1}R.</math><br>
Meto norma en los 2 lados<br>
<math> ||(I+R)^{-1}|| = || I - (I+R)^{-1}R|| \leq ||I|| + ||(I+R)^{-1}R|| \leq 1 + ||(I+R)^{-1}|| ||R|| </math><br><br>
<math>||I|| \leq 1</math> porque <math>||I|| = ||II|| \leq ||I||^2</math> ya que es consistente. El unico numero que cumple esto es 1.<br><br>

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

c)<br>
i) <math>A + \delta A</math> es inversible. Primero pruebo que  <math>I+\delta A (A^{-1})</math> es inversible por lo hecho en b). Para eso veo que <math>||\delta A (A^{-1})|| < 1</math>:<br>
<math>||\delta A (A^{-1})|| \leq ||\delta A|| ||A^{-1}|| < \frac{||A^{-1}||}{||A^{-1}||} = 1 \Longrightarrow (I + \delta A (A^{-1}))</math> inversible.<br>
Pero entonces <math> det(A+\delta A) = det(A(I+(\delta A (A^{-1}))) = det(A) * det( blah ) = 0 </math> porque A es inversible, entonces <math>A+\delta A</math> es inversible.<br><br>
ii) <math>||(A+\delta A)^{-1}|| = ||A(I+(\delta A (A^{-1}))|| = ||  (I+(\delta A (A^{-1}))^{-1} A^{-1}|| \underbrace{\leq}_{por\ b)}</math><br>
<math> \frac{||A^{-1}||}{1-||\delta A (A)^{-1}||} \leq 
\frac{||A^{-1}||}{1-||\delta A|| ||A^{-1}||}</math><br>
en el último paso usé que <math>||\delta A|| ||A^{-1}|| < 1</math> (por enunciado) y asi aseguro que no divide por 0.
@@ Línea 65: / Línea 65: @@
 Calcular <math>col_j L^{-1}</math> nos lleva O(<math>n^2</math>) porque se puede plantear directamente el sistema
 <math>L x = e_j</math> donde <math>e_j</math> es el canonico con 1 en la posicion j y <math>x</math> nos daría la columna j de <math>L^{-1}</math>. Se puede llevar a O(<math>(n-j)^2</math>) ya que se sabe de antemano que la columna j de <math>L^{-1}</math> tiene j ceros, es decir no es necesario calcularlos. Idem con <math>fila_i U^{-1}</math>.
-==Ejercicio 9==
-<b>Sea <math>A \in R^{nxn}</math> inversible tal que A = TS donde <math>T \in R^{nxn}</math> es triangular inferior y <math>S \in R^{nxn}</math> es triangular superior. Probar:
-a) T y S son inversibles, usando propiedades de determinantes.
-b) A tiene factorización LU (con unos en la diagonal de L).</b>
-<b>a)</b>
-A es inversible sii det(A) != 0
- det(A) = det(TS) = det(T) * det(S) entonces det(T) != 0, det(S) != 0 sii T, S son inversibles.
-<b>b)</b>
-A se puede reducir por filas aplicando operaciones de eliminación (operaciones del tipo aFi + Fj) a una matriz triangular superior U.
- Ek*E(k-1)*...*E2*E1*A = U entonces A= E1(-1)*E2(-1)*...*Ek(-1)*U
-Por construcción, cada matriz elemental E1,...,Ek es triangular inferior y tiene unos en la diagonal principal, por consiguiente sus inversas E1(-1),...,Ek(-1) y la matriz L = E1(-1)*E2(-1)*...*Ek(-1) tienen las mismas características por lo que obtuvimos A = LU con unos en la diagonal.
 ==Ejercicio 21==
@@ Línea 111: / Línea 90: @@
 <math>||\delta A (A^{-1})|| \leq ||\delta A|| ||A^{-1}|| < \frac{||A^{-1}||}{||A^{-1}||} = 1 \Longrightarrow (I + \delta A (A^{-1}))</math> inversible.<br>
 Pero entonces <math> det(A+\delta A) = det(A(I+(\delta A (A^{-1}))) = det(A) * det( blah ) = 0 </math> porque A es inversible, entonces <math>A+\delta A</math> es inversible.<br><br>
-ii) <math>||(A+\delta A)^{-1}|| = ||(A(I+(\delta A (A^{-1})))^{-1}|| = ||  (I+(\delta A (A^{-1}))^{-1} A^{-1}|| \underbrace{\leq}_{por\ b)}</math><br>
+ii) <math>||(A+\delta A)^{-1}|| = ||A(I+(\delta A (A^{-1}))|| = ||  (I+(\delta A (A^{-1}))^{-1} A^{-1}|| \underbrace{\leq}_{por\ b)}</math><br>
 <math> \frac{||A^{-1}||}{1-||\delta A (A)^{-1}||} \leq
 \frac{||A^{-1}||}{1-||\delta A|| ||A^{-1}||}</math><br>
 en el último paso usé que <math>||\delta A|| ||A^{-1}|| < 1</math> (por enunciado) y asi aseguro que no divide por 0.
-== Ejercicio 22)a) ==
-Sea x la solucion del sistema  Ax = b.
-A)Sea <math>(x + \hat{x})</math> la solución del sistema Ax = b + <math>\hat{b}</math>. Acotar la norma de ||x||.
-<math> A (x + \hat{x}) = b + \hat{b} </math>
-<math> A.x + A.\hat{x} = b + \hat{b}</math> paso restando A.x
-<math>       A.\hat{x} = b + \hat{b} - A.x</math> luego com A.x = b
-<math>       A.\hat{x} = b + \hat{b} - b </math> se anula b
-<math>       A.\hat{x} = \hat{b}</math>  supongo q A es INVERSIBLE ==><math> \exists A^{-1}</math>
-<math>A^{-1}.A.\hat{x} = A^{-1}.\hat{b} </math>
-<math>         \hat{x} = A^{-1}.\hat{b}</math> tomo norma de ambos lados
-<math>     ||\hat{x}|| = ||A^{-1}.\hat{b}||</math> que por C-S-B  es...
-<math>     ||\hat{x}|| \leq ||A^{-1}||.||\hat{b}|| </math>
-Listo !!