Edición de «Primer Parcial 11/05/2007 (Métodos Numéricos)»

{{Back|Métodos Numéricos}}

==Ejercicio 2==
'''Para <math>A = (a_{ij}) \in R^{mxn}</math> sean 
<math>||A||_M</math> y <math>|| A ||_2</math> normas matriciales  definidas por
<math>||A||_M = \max_{i,j} |a_{ij}|</math>  y <math>||A||_2 = \sup_{||x||_2=1} ||Ax||_2</math>. Probar:<br>
a) <math>||A||_2 \leq \sqrt{mn} ||A||_M</math> usando la desigualdad de CBS(<math>x^ty \leq || x ||_2 || y ||_2</math>)<br>
b)  <math>||A||_2 \geq ||A||_M</math> usando que <math>||A||_2 \geq ||Ax||_2</math> si <math> ||x||_2 = 1</math>'''<br><br>

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

==Ejercicio 3==
'''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:<br>
a) T y S son inversibles, usando propiedades de determinantes<br>
b) A tiene factorizacion LU (con unos en la diagonal de L)'''<br><br>

a) Si A es inversible, 
<math>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</math><br>
Luego S y T son inversibles.<br>
b) Como T es inversible, por (a), y es triangular significa que 
no hay ceros en su diagonal (ya que <math>det(T) = \prod_{i=1}^n t_{ii} \neq 0</math>).
Se define <math>D = \begin{bmatrix}
  t_{11}    & \cdots & 0      \\
  \vdots &  \ddots & \vdots \\ 
  0      & \cdots &  t_{nn}
\end{bmatrix}</math> y es facil ver que <math>D^{-1} = \begin{bmatrix}
  \frac{1}{t_{11}}    & \cdots & 0      \\
  \vdots &  \ddots & \vdots \\ 
  0      & \cdots &  \frac{1}{t_{nn}}
\end{bmatrix}</math><br>
Asi, <math>L = TD^{-1}</math> y <math>U = DS</math> 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).<br>
L tiene 1 en la diagonal ya que <math>l_{ii} = t_{ii} * \frac{1}{t_{ii}} = 1</math> y <math>A = TD^{-1}DS = LU</math> ya que <math>D^{-1}D = I</math>
<br><br>


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

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

==Ejercicio 5==
'''Sea <math>A \in R^{nxn}</math> una matriz con autovalores <math>\lambda</math> y <math>\mu</math> tales 
que <math>\lambda \neq \mu</math>. Supongamos que <math>\eta</math> no es autovalor de A. Sea I la identidad de <math>R^{nxn}</math>. Probar<br>
a) <math>\lambda - \mu</math> es autovalor de <math>A - \eta I</math>.<br>
b) <math>||A - \eta I || \geq |\lambda - \eta|</math>, donde <math>||\bullet||</math> denota cualquier norma matricial inducida.<br>
c) <math>A - \eta I</math> es inversible.<br>
d) <math>k(A - \eta I) \geq |\frac{\lambda - \eta }{\mu - \lambda}|</math>,
siendo k el numero de condicion asociado a cualquier norma matricial inducida.'''<br><br>

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