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

De Cuba-Wiki
Advertencia: no has iniciado sesión. Tu dirección IP se hará pública si haces cualquier edición. Si inicias sesión o creas una cuenta, tus ediciones se atribuirán a tu nombre de usuario, además de otros beneficios.

Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.

Revisión actual Tu texto
Línea 1: Línea 1:
{{Back|Métodos Numéricos}}
{{Back|Métodos Numéricos}}


==Ejercicio 6==
==Ejercicio 9==
'''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.
'''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 factorizacion es unica.'''<br><br>
 
 
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>
Por induccion en n.<br>
Casos base:<br>
Casos base:<br>
n=1, <math>A_1 = \begin{bmatrix} a_{11} \end{bmatrix} = 1\  a_{11}</math><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} \\
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>
a_{21} & a_{22} \end{bmatrix} </math> como <math>det(A_1) \neq 0 \iff 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>
Paso inductivo:<br>
Supongo que vale <math>A_n =  
Supongo que vale <math>A_n =  
Línea 53: Línea 36:
\ & \ \\
\ & \ \\
0 \ldots 0 & u_{n+1,n+1} \end{bmatrix}</math><br>
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>
Es decir que mis incognitas 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>
Como los bloques son del mismo tama~no 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>
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>
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>
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.
i) y ii) tiene soluciones unicas porque <math>U_n</math>y <math> L_n</math> son inversibles.


==Ejercicio 8==
==Ejercicio 10==
'''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>
'''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>
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
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>.
<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 daria 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==
==Ejercicio 11==
<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:
'''Sea <math>A \in R^{nxn}</math> y sea <math>A^{k}</math> 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 <math>A^{k}</math> es no singular.'''<br><br>


a) T y S son inversibles, usando propiedades de determinantes.
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>


b) A tiene factorización LU (con unos en la diagonal de L).</b>
Volviendo al ejercicio <math>A^{k}\ inversible \iff det(A^{k}) \neq 0 \iff det(L_k * L_{k-1} * \ldots * L_1 * A) \neq 0 </math>
<math>\iff det(L_k) * det(L_{k-1}) * \ldots * det(L_1) * det(A) \neq 0 \iff det(A) \neq 0 \iff A \ inversible</math>


<b>a)</b>


A es inversible sii det(A) != 0
==Ejercicio 24==
 
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==
'''Sea <math> R \in R^{nxn}</math> tal que <math>||R|| < 1 </math>, siendo <math>|| \bullet ||</math> cualquier norma consistente.<br>
'''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>
a) 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) 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>
a) 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>
<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>
Sea <math>||x||=1, (I+R)x = 0 \iff x+Rx = 0 \iff 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>
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>
Volviendo al ejercicio, por inspiracion divina se me ocurre que<br>
Línea 107: Línea 84:
<br><br><br>
<br><br><br>


c)<br>
b)<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>
i) <math>A + \delta A</math> es inversible. Primero pruebo que  <math>I+\delta A (A^{-1})</math> es inversible por lo hecho en a). 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>
<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>
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\ a)}</math><br>
<math> \frac{||A^{-1}||}{1-||\delta A (A)^{-1}||} \leq  
<math> \frac{||A^{-1}||}{1-||\delta A (A)^{-1}||} \leq  
\frac{||A^{-1}||}{1-||\delta A|| ||A^{-1}||}</math><br>
\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.
en el ultimo paso use 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 !!
Ten en cuenta que todas las contribuciones a Cuba-Wiki pueden ser editadas, modificadas o eliminadas por otros colaboradores. Si no deseas que las modifiquen sin limitaciones, no las publiques aquí.
Al mismo tiempo, asumimos que eres el autor de lo que escribiste, o lo copiaste de una fuente en el dominio público o con licencia libre (véase Cuba-Wiki:Derechos de autor para más detalles). ¡No uses textos con copyright sin permiso!

Para editar esta página, responde la pregunta que aparece abajo (más información):

Cancelar Ayuda de edición (se abre en una ventana nueva)

Plantilla usada en esta página:

Obtenido de «https://www.cubawiki.com.ar/index.php/Práctica_2_(Métodos_Numéricos)»