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

Ejercicio 2

Para $A=(a_{ij})\in R^{mxn}$ sean $||A||_{M}$ y $||A||_{2}$ normas matriciales definidas por $||A||_{M}=\max _{i,j}|a_{ij}|$ y $||A||_{2}=\sup _{||x||_{2}=1}||Ax||_{2}$. Probar:
a) $||A||_{2}\leq {\sqrt {mn}}||A||_{M}$ usando la desigualdad de CBS($x^{t}y\leq ||x||_{2}||y||_{2}$)
b) $||A||_{2}\geq ||A||_{M}$ usando que $||A||_{2}\geq ||Ax||_{2}$ si $||x||_{2}=1$

a) Para el x que cumple con $||A||_{2}=sup_{||x||_{2}=1}||Ax||_{2}$ vale
$||A||_{2}={\sqrt {\sum _{i=1}^{m}(fila_{i}*x)^{2}}}\leq {\sqrt {\sum _{i=1}^{m}(||fila_{i}||_{2}||x||_{2})^{2}}}=$
${\sqrt {\sum _{i=1}^{m}(||fila_{i}||_{2})^{2}}}={\sqrt {\sum _{i=1}^{m}\sum _{j=1}^{n}(a_{ij})^{2}}}\leq$
${\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 $e_{i}$ el vector canonico con un 1 en la posicion i. Sea $||A||_{M}=|a_{uv}|$.
$||A||_{2}\geq ||Ae_{v}||_{2}={\sqrt {\sum _{i=1}^{m}a_{iv}^{2}}}\geq |a_{uv}|=||A||_{M}$

Ejercicio 3

Sea $A\in R^{nxn}$ inversible tal que A = TS donde $T\in R^{nxn}$ es triangular inferior y $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, $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 $det(T)=\prod _{i=1}^{n}t_{ii}\neq 0$). Se define $D={\begin{bmatrix}t_{11}&\cdots &0\\\vdots &\ddots &\vdots \\0&\cdots &t_{nn}\end{bmatrix}}$ y es facil ver que $D^{-1}={\begin{bmatrix}{\frac {1}{t_{11}}}&\cdots &0\\\vdots &\ddots &\vdots \\0&\cdots &{\frac {1}{t_{nn}}}\end{bmatrix}}$
Asi, $L=TD^{-1}$ y $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 $l_{ii}=t_{ii}*{\frac {1}{t_{ii}}}=1$ y $A=TD^{-1}DS=LU$ ya que $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 = ${\begin{bmatrix}3&1\\4&1\end{bmatrix}}$
b) Repetir el procedimiento utilizando el metodo de Givens.

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

Ejercicio 5

Sea $A\in R^{nxn}$ una matriz con autovalores $\lambda$ y $\mu$ tales que $\lambda \neq \mu$. Supongamos que $\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).