Diferencia entre revisiones de «Práctica 2 (Métodos Numéricos)»

De Cuba-Wiki
(algunos ej interesantes)
 
(Actualizo numeración de los ejs en la guía actual)
Línea 1: Línea 1:
{{Back|Métodos Numéricos}}
{{Back|Métodos Numéricos}}


==Ejercicio 9==
==Ejercicio 6==
'''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>
'''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 \leftrightarrrow det(A^{k}) \neq 0 \leftrightarrrow det(L_k * L_{k-1} * \ldots * L_1 * A) \neq 0 </math>
<math> \leftrightarrrow det(L_k) * det(L_{k-1}) * \ldots * det(L_1) * det(A) \neq 0 \leftrightarrrow det(A) \neq 0 \leftrightarrrow 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 \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>
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>
Paso inductivo:<br>
Supongo que vale <math>A_n =  
Supongo que vale <math>A_n =  
Línea 36: Línea 53:
\ & \ \\
\ & \ \\
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 incognitas son <math>l_{n+1}, u_{n+1}\ y\ u_{n+1,n+1}</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~no puedo multiplicar por bloques y queda<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>
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 unicas porque <math>U_n</math>y <math> L_n</math> son inversibles.
i) y ii) tiene soluciones únicas porque <math>U_n</math>y <math> L_n</math> son inversibles.


==Ejercicio 10==
==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>
'''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 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>.
<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 11==
'''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>
 
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 \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>
 


==Ejercicio 24==
==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>
a) Probar que <math>||(I+R)^{-1}|| \leq \frac{1}{1-||R||}</math>.<br>
b) Probar que <math>||(I+R)^{-1}|| \leq \frac{1}{1-||R||}</math>.<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>
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>


a) No se si el enunciado supone que (I+R) es inversible o hay que demostrarlo, por las dudas es asi:<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>
<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 \iff x+Rx = 0 \iff Rx = -x \Longrightarrow ||Rx|| = ||x|| = 1</math>.<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>
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 84: Línea 86:
<br><br><br>
<br><br><br>


b)<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 a). 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 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>
<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}))|| = ||  (I+(\delta A (A^{-1}))^{-1} A^{-1}|| \underbrace{\leq}_{por\ a)}</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  
<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 ultimo paso use que <math>||\delta A|| ||A^{-1}|| < 1</math> (por enunciado) y asi aseguro que no divide por 0.
en el último paso usé que <math>||\delta A|| ||A^{-1}|| < 1</math> (por enunciado) y asi aseguro que no divide por 0.

Revisión del 22:26 10 sep 2014

Plantilla:Back

Ejercicio 6

Sea y sea 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 es no singular.

Nota: es la matriz identidad con los coeficientes que se usaron en la eliminacion gaussiana para poner un 0 en la posicion i,j.
Por ejemplo para una matriz de 4x4.
Asi,

Volviendo al ejercicio Error al representar (función desconocida «\leftrightarrrow»): {\displaystyle A^{k}\ inversible \leftrightarrrow det(A^{k}) \neq 0 \leftrightarrrow det(L_k * L_{k-1} * \ldots * L_1 * A) \neq 0 } Error al representar (función desconocida «\leftrightarrrow»): {\displaystyle \leftrightarrrow det(L_k) * det(L_{k-1}) * \ldots * det(L_1) * det(A) \neq 0 \leftrightarrrow det(A) \neq 0 \leftrightarrrow A \ inversible}

Ejercicio 7

Probar que si tiene todas sus submatrices principales no singulares entonces A tiene factorizacion LU sin pivoteo. Ademas esa factorización es única.

Por induccion en n.
Casos base:
n=1,
n=2, como entonces puedo hacer gauss sin intercambio de filas en entonces se que existen unicos tal que

Paso inductivo:
Supongo que vale
donde son matrices de n-1 x n-1, columnas de n-1 elementos asi como son filas de n-1 elementos.
Quiero ver que vale
Es decir que mis incógnitas son
Como los bloques son del mismo tamaño puedo multiplicar por bloques y queda
i) Despejo haciendo: .
ii) Despejo haciendo: .
iii) Despejo haciendo:.
i) y ii) tiene soluciones únicas porque y son inversibles.

Ejercicio 8

Supongamos que una matriz tiene factorizacion A = LU y que L y U son conocidas. Dar una algoritmo que calcule el elemento (i,j) de en aproximadamente flops. (Un flop es una operacion de punto flotante)

Si A = LU entonces y por lo tanto .
Calcular nos lleva O() porque se puede plantear directamente el sistema donde es el canonico con 1 en la posicion j y nos daría la columna j de . Se puede llevar a O() ya que se sabe de antemano que la columna j de tiene j ceros, es decir no es necesario calcularlos. Idem con .

Ejercicio 21

Sea tal que , siendo cualquier norma consistente.
b) Probar que .
c) Sea una matriz inversible y tal que . Probar que es inversible y vale


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

entonces . Si I+R es inversible entonces Nu(I+R) = {0}
Sea .
Da que para que exista un x tal que y entonces 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 es inversible.

Volviendo al ejercicio, por inspiracion divina se me ocurre que

Meto norma en los 2 lados


porque ya que es consistente. El unico numero que cumple esto es 1.

Entonces,

asi que no se puede pasar dividiendo.


c)
i) es inversible. Primero pruebo que es inversible por lo hecho en b). Para eso veo que :
inversible.
Pero entonces porque A es inversible, entonces es inversible.

ii)

en el último paso usé que (por enunciado) y asi aseguro que no divide por 0.