Primer Parcial 11/05/2007 (Métodos Numéricos)

Ejercicio 2

Para 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 = (a_{ij}) \in R^{mxn}} sean 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||_M} 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 || A ||_2} normas matriciales definidas por 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||_M = max_{ij} |a_{ij}|} 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 ||A||_2 = \sup_{||x||_2=1} ||Ax||_2} . Probar:
a) |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 \leq \sqrt{mn} ||A||_M} usando la desigualdad de CBS(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^ty \leq || x ||_2 || y ||_2} )
b) 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 \geq ||A||_M} usando 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 \geq ||Ax||_2} 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 ||x||_2 = 1}

a) Para el x que cumple 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 ||A||_2 = sup_{||x||_2=1} ||Ax||_2} 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||_2 = \sqrt{ \sum_{i=1}^m (fila_i * x)^2} \leq \sqrt{ \sum_{i=1}^m (||fila_i||_2 ||x||_2)^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 \sqrt{ \sum_{i=1}^m (||fila_i||_2)^2} = \sqrt{ \sum_{i=1}^m \sum_{j=1}^n (a_{ij})^2} \leq}
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 \sqrt{ \sum_{i=1}^m \sum_{j=1}^n (||A||_M)^2} = | ||A||_M | \sqrt{ \sum_{i=1}^m \sum_{j=1}^n 1} = ||A||_M \sqrt{mn}}
b) 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 e_i} el vector canonico con un 1 en la posicion i. 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||_M = |a_{uv}|} .
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 \geq ||A e_u||_2 = \sqrt{ \sum_{j=1}^n a_{uj}^2} \geq |a_{uv}| = ||A||_M}

Ejercicio 3

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 factorizacion LU (con unos en la diagonal de L)

a) Si A es inversible, 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) \neq 0 \Longrightarrow det(TS) \neq 0 \Longrightarrow det(T) det(S) \neq 0 \Longrightarrow det(T) \neq 0 \land det(S) \neq 0}
Luego S y T son inversibles.
b) Como T es inversible, por (a), y es triangular significa que no hay ceros en su diagonal (ya 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 det(T) = \prod_{i=1}^n t_{ii} \neq 0} ). Se define 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 D = \begin{bmatrix} t_{11} & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & t_{nn} \end{bmatrix}} y es facil ver 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 D^{-1} = \begin{bmatrix} \frac{1}{t_{11}} & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & \frac{1}{t_{nn}} \end{bmatrix}}
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 L = TD^{-1}} 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 U = DS} las cuales son triangular inferior y superior respectivamente (ya que multiplicar por una matriz diagonal multiplica cada elemento de cada fila por el elemento distinto de cero de la matriz diagonal correspondiente).
L tiene 1 en la diagonal ya 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 l_{ii} = t_{ii} * \frac{1}{t_{ii}} = 1} 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 A = TD^{-1}DS = LU} ya 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 D^{-1}D = I}

Ejercicio 4

Dado una matriz cuadrada A, existe una matriz ortogonal Q y una matriz triangular superior R tal que A = QR,
a) En particular utilizar el metodo de Householder para encontrar la factorizacion QR de A = 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 \begin{bmatrix} 3 & 1 \\ 4 & 1 \end{bmatrix}}
b) Repetir el procedimiento utilizando el metodo de Givens.

a) Construyo u 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 Q^t = I - 2uu^t} y 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 Q^tA = R} .
Como se quiere dejar un 0 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_{21}} usamos el vector x=(3,4). Luego 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 y = (||x||_2,0) = (5,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 u = \frac{x-y}{||x-y||_2} = \frac{(-2,4)}{\sqrt{20}}}
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 = Q^tA = \begin{bmatrix} 3/5 & 4/5 \\ 4/5 & -3/5 \end{bmatrix} \begin{bmatrix} 3 & 1 \\ 4 & 1 \end{bmatrix} = \begin{bmatrix} 5 & 7/5 \\ 0 & 1/5 \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 Q^t} es ortogonal (y Q tambien), QR = A, es decir
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 = \begin{bmatrix} 5 & 7/5 \\ 0 & 1/5 \end{bmatrix}, Q = \begin{bmatrix} 3/5 & 4/5 \\ 4/5 & -3/5 \end{bmatrix}}
b) Quiero un W que anule el 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_{21}} usando rotaciones. Para esto construyo la matriz de rotacion W, 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 W = \begin{bmatrix} \frac{x_1}{\sqrt{x_1^2+x_2^2}} & \frac{x_2}{\sqrt{x_1^2+x_2^2}} \\ -\frac{x_2}{\sqrt{x_1^2+x_2^2}} & \frac{x_1}{\sqrt{x_1^2+x_2^2}} \end{bmatrix}}
En este caso 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_1 = a_{11} = 3} 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_2 = a_{21} = 4}
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 W = \begin{bmatrix} 3/5 & 4/5 \\ -4/5 & 3/5 \end{bmatrix}}
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 = WA = \begin{bmatrix} 3/5 & 4/5 \\ -4/5 & 3/5 \end{bmatrix} \begin{bmatrix} 3 & 1 \\ 4 & 1 \end{bmatrix} = \begin{bmatrix} 5 & 7/5 \\ 0 & -1/5 \end{bmatrix}} .
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 Q = W^t = \begin{bmatrix} 3/5 & -4/5 \\ 4/5 & 3/5 \end{bmatrix}}

Ejercicio 5

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}} una matriz con autovalores 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 \lambda} 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 \mu} tales 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 \lambda \neq \mu} . Supongamos 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 \eta} no es autovalor de A. Sea I la identidad de $R^{nxn}$. Probar
a) $\lambda -\mu$ es autovalor de $A-\eta I$.
b) $||A-\eta I||\geq |\lambda -\eta |$, donde $||\bullet ||$ denota cualquier norma matricial inducida.
c) $A-\eta I$ es inversible.
d) $k(A-\eta I)\geq |{\frac {\lambda -\eta }{\mu -\lambda }}|$, siendo k el numero de condicion asociado a cualquier norma matricial inducida.

a) $\lambda$ es autovalor de A si $Av=\lambda$ v para alg'un v, entonces si $\lambda -\eta$ es autovalor de $A-\eta I$
$(A-\eta I)v=(\lambda -\eta )v$
$Av-(\eta I)v=(\lambda -\eta )v$
Como $\lambda$ es autovalor de A, $Av=\lambda v$, entonces
$(\eta I)v=\eta v$
$\eta (Iv)=\eta v$
$(Iv)=v\Longrightarrow$ se cumple siempre $\Longrightarrow \lambda -\eta$ es autovalor de $A-\eta I$.
b) $||A-\eta I||=\sup _{||v||=1}||(A-\eta I)v||\geq \sup _{||v||=1,v\ av\ de\ (A-\eta I)}||(A-\eta I)v||=$
$\sup _{||v||=1,v\ av\ de\ (A-\eta I)}||(\lambda -\eta )v||\geq \overbrace {\sup _{||v||=1}||v||} ^{=1}||(\lambda -\eta )||=|\lambda -\eta |$.
c) Como $\eta$ no es autovalor de A, entonces su polinomio caracteristico es distinto de cero, es decir, $det(A-\eta I)\neq 0\Longrightarrow A-\eta I$ inversible.
d) Por a) se que $\lambda -\eta$ es autovalor de $A-\eta I$. Idem con $\mu$ ya que vale para cualquier autovalor, es decir, $\mu -\eta$ es autovalor de $A-\eta I$. Notar que si x es un autovalor de A, ${\frac {1}{x}}$ es autovalor de $A^{-1}$.
$k(A-\eta I)=||(A-\eta I)||||A-\eta I)^{-1}||\geq |\lambda -\eta |||A-\eta I)^{-1}||$
$\geq |\lambda -\eta ||{\frac {1}{\mu -\eta }}|=|{\frac {\lambda -\eta }{\mu -\eta }}|$
(la primera desigualdad es por el ej b y la segunda es por el ej b y ej a).