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

Ejercicio 6

Sea Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \in R^{nxn}} y sea Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A^{k}} 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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A^{k}} es no singular.

Nota: Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle L_i} es la matriz identidad con los coeficientes Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 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, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A^{k} = L_k * L_{k-1} * \ldots * L_1 * A }

Volviendo al ejercicio Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A^{k}\ inversible \leftrightarrow det(A^{k}) \neq 0 \leftrightarrow det(L_k * L_{k-1} * \ldots * L_1 * A) \neq 0 } Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \leftrightarrow det(L_k) * det(L_{k-1}) * \ldots * det(L_1) * det(A) \neq 0 \leftrightarrow det(A) \neq 0 \leftrightarrow A \ inversible}

Ejercicio 7

Probar que si Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \in R^{nxn}} 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, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A_1 = \begin{bmatrix} a_{11} \end{bmatrix} = 1\ a_{11}}
n=2, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A_2 = \begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{bmatrix} } como Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle det(A_1) \neq 0 \leftrightarrow a_{11} \neq 0} entonces puedo hacer gauss sin intercambio de filas en Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A_2} entonces se que existen unicos Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle U_2, L_2 } tal que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A_2 = U_2 L_2}

Paso inductivo:
Supongo que vale Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A_{n-1}, L_{n-1} y U_{n-1}} son matrices de n-1 x n-1, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle c_n y u_n} columnas de n-1 elementos asi como Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f_n y l_n} son filas de n-1 elementos.
Quiero ver que vale Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 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 incógnitas son Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle l_{n+1}, u_{n+1}\ y\ u_{n+1,n+1}}
Como los bloques son del mismo tamaño puedo multiplicar por bloques y queda
i) Despejo Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle l_{n+1}} haciendo: Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle l_{n+1} U_n = f_{n+1}} .
ii) Despejo Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle u_{n+1}} haciendo: Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle c_{n+1} = L_n U_{n+1}} .
iii) Despejo Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle u_{n+1,n+1}} haciendo:Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle l_{n+1} u_{n+1} + u_{n+1,n+1} = a_{n+1,n+1}} .
i) y ii) tiene soluciones únicas porque Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle U_n} y Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle L_n} son inversibles.

Ejercicio 8

Supongamos que una matriz Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A^{-1}} en aproximadamente Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle (n-j)^2 + (n-i)^2} flops. (Un flop es una operacion de punto flotante)

Si A = LU entonces Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A^{-1} = U^{-1} L^{-1}} y por lo tanto Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A^{-1}_{i,j} = fila_i U^{-1} \times col_j L^{-1}} .
Calcular Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle col_j L^{-1}} nos lleva O(Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle n^2} ) porque se puede plantear directamente el sistema Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle L x = e_j} donde Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle e_j} es el canonico con 1 en la posicion j y Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle x} nos daría la columna j de Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle L^{-1}} . Se puede llevar a O(Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle (n-j)^2} ) ya que se sabe de antemano que la columna j de Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle L^{-1}} tiene j ceros, es decir no es necesario calcularlos. Idem con Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle fila_i U^{-1}} .

Ejercicio 9

Sea Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \in R^{nxn}} inversible tal que A = TS donde Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle T \in R^{nxn}} es triangular inferior y Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle S \in R^{nxn}} 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).

a)

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)

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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle R \in R^{nxn}} tal que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle ||R|| < 1 } , siendo Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle || \bullet ||} cualquier norma consistente.
b) Probar que $||(I+R)^{-1}||\leq {\frac {1}{1-||R||}}$.
c) 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||}}$

b) 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\leftrightarrow x+Rx=0\leftrightarrow 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.

c)
i) $A+\delta A$ es inversible. Primero pruebo que $I+\delta A(A^{-1})$ es inversible por lo hecho en b). 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\ b)}$
${\frac {||A^{-1}||}{1-||\delta A(A)^{-1}||}}\leq {\frac {||A^{-1}||}{1-||\delta A||||A^{-1}||}}$
en el último paso usé que $||\delta A||||A^{-1}||<1$ (por enunciado) y asi aseguro que no divide por 0.