\documentclass[11pt,spanish]{article}
\usepackage[spanish,activeacute]{babel}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{epsfig,euscript}
\usepackage[T1]{fontenc}
\usepackage{fancyhdr} % Para modificar los encabezados y pies de p\'agina


%%%%% SUGERENCIA DE HEADER Y FOOT
%\pagestyle{fancy}
%\fancyhf{}
%\rhead{Share\LaTeX}
%\lhead{Guides and tutorials}
%\rfoot{Page \thepage}
%%%%%%%%%%%%%%%%%%%%
\pagestyle{fancy}

\newcommand{\semestre}{Primer Cuatrimestre 2018}



\lhead{Pr\'actica 0 -- \semestre}

\newtheorem{ejer}{Ejercicio}

\newcommand{\bej}{\begin{ejer} \rm}
\newcommand{\fej}{\end{ejer}}
\renewcommand{\theenumi}{\alph{enumi}} % Para cambiar la forma de enumerar en el entorno \begin{enumerate}



\def\A{\mathbb{A}}
\def\C{\mathbb{C}}
\def \N{\mathbb{N}}
\def \P{\mathbb{P}}
\def \Q{\mathbb{Q}}
\def \R{\mathbb{R}}
\def \Z{\mathbb{Z}}


\def\d{\displaystyle}

\topmargin-2cm \vsize 29.5cm \hsize 21cm
\setlength{\textwidth}{16.5cm} \setlength{\textheight}{23.5cm}
\setlength{\oddsidemargin}{0.0cm}
\setlength{\evensidemargin}{0.0cm}


\begin{document}
\thispagestyle{empty}

\centerline{{\small Universidad de Buenos Aires - Facultad de
Ciencias Exactas y Naturales - Depto. de Matem\'atica}}

\vskip 0.2cm

\hrulefill
\vskip 0.2cm
\centerline{{\bf\Huge {\sc Optimizaci\'on }}}
\vskip 0.2cm
\centerline{{\ttfamily \semestre}}
\hrulefill

\bigskip

\centerline{\bf  Pr\'actica N$^\circ$ 0: Repaso.}
\bigskip



\medskip
\noindent \textbf{Repaso de \'algebra Lineal}

\bej Sea $A\in\R^{n\times n}$. Probar que la aplicaci\'on $<,>:\R^n\times\R^n\rightarrow\R$ dada por $<v,w>=v^tAw$ define un producto interno si y s\'olo si $A$ es sim\'etrica y definida positiva.\fej

\bej Sea $A\in\R^{n\times n}$ sim\'etrica. Probar que si $\lambda$ es autovalor de $A$ entonces $\lambda\in\R$. Si adem\'as $A$ es definida positiva, probar que $\lambda>0$. \fej

\bej Sea $A\in\R^{n\times n}$ sim\'etrica y sean $v_1$ y $v_2$ autovectores de $A$ correspondientes a los autovalores $\lambda_1$ y $\lambda_2$ respectivamente. Probar que si $\lambda_1\neq\lambda_2$ entonces $v_1$ y $v_2$ son ortogonales con el producto interno usual. \fej

\bej Sea $A\in\R^{n\times n}$. Probar que $A$ es sim\'etrica si y s\'olo si $O^t A O$ es sim\'etrica para toda $O\in\R^{n\times n}$ ortogonal (es decir, $O^{-1} = O^t$).\fej

\bej Sea $B = \{q_1, ..., q_n\}$ una base ortonormal. Probar que la matriz $Q = 
 \begin{pmatrix}
  \vdots &  & \vdots \\
  q_1 & \cdots & q_n \\
	\vdots &  & \vdots
 \end{pmatrix} $ es una matriz ortogonal.\fej

\bej Probar que si $A\in\R^{n\times n}$ es sim\'etrica, entonces admite una base ortonormal de autovectores.\fej

\bej Sea $A\in\R^{n\times n}$ sim\'etrica y definida positiva, y sea $A_k\in\R^{k\times k}$ la submatriz con coeficientes $(a_{ij})$ para $1\le i,j\le k$. Probar que $A_k$ es sim\'etrica definida positiva $(k=1,2,\dots,n)$. Concluir que $\det(A_k)>0$ para todo $k$. Los valores $\det(A_k)$ se llaman \emph{menores principales} de $A$.\fej

\bej 
Dado un subespacio $\mathbb S$, un $x \in \R^n$ y un producto interno $<,>$, probar que la proyecci\'on ortogonal de $x$ sobre $\mathbb S$ es $p = \sum_{i=1}^{n} <x,v_i> v_i$, donde los $v_i$ forman una base ortonormal de $\mathbb S$. 
\fej
\medskip

\medskip
\noindent \textbf{Repaso de An\'alisis}

\bej
Calcular la f\'ormula de Taylor de segundo orden para las funciones dadas en el punto
indicado. Escribir la forma de Lagrange del residuo.

a) $f(x,y) = (x + y)^2$ en $(0, 0)\qquad$ b)$f (x, y) = e^{x+y}$ en $(0, 0)$ 

\fej
\bej Sea $f (x, y) = x e^y$. Calcular el polinomio de Taylor de orden 1 de $f$ en el punto $P = (1, 0)$. Usar este polinomio para aproximar el valor $f(0.98,0.02)$. Estimar el error
cometido.
\fej

\bej
 Calcular los puntos cr\'iticos de $f(x,y)=xe^{-y^2}+x^2$, $g(x,y) = x^2 +y^4$
y $h(x,y) = x^4 -y^4$ y sus hessianos en dichos puntos. ?`Son m\'aximos locales, m\'inimos locales o puntos silla? ?`Son globales?
\fej
\bej

 Sea $f\in C^2(\mathbb R^n)$ tal que tiene un extremo estricto en $a\in\mathbb R^n$. ?`Es necesariamente $H f(a)$ definida positiva o negativa?
\fej 

\bej 
Determinar los extremos absolutos de $f|_A$ en los siguientes casos:
\begin{enumerate}
 \item $f(x, y) = xy(x - y)^2\qquad A = \{(x, y) \in \mathbb R^2 :x > 0, y > 0\}.$ 
\item $f (x, y) = 2 x + 4y - x^2 - y^2 -3 \qquad A= \mathbb R^2.$ 
\item $f (x, y) = 2 x + 4y - x^2 - y^2 - 3 \qquad A= \{(x, y)\in R^2 : |x| \leq 1, |y| \leq 1\}$.
\end{enumerate}
\fej

\bej La temperatura de una placa en un punto cualquiera $(x, y)$ viene dada por la funci\'on
$T (x, y) = 25 + 4x^2 - 4xy + y^2$ . Una alarma t\'ermica, situada sobre los puntos de
la circunferencia $x^2 + y^2 = 25$, se dispara a temperaturas superiores a 180 grados o
inferiores a 20 grados. ?`Se disparar\'a la alarma?
\fej
\medskip


\medskip
\noindent \textbf{Repaso C\'alculo Num\'erico}

\bej
Decidir si son verdaderas o falsas las siguientes afirmaciones y justificar:
        \begin{enumerate}
        \item $n$ es $O(n)$
        \item $3n^2+7n+4$ es $O(n^2)$
        \item $n^i$ es $O(n^j)$ si $i<j$
        \end{enumerate}
\fej

\bej
Mostrar que $n!$ no es $O(r^n)$, cualquiera sea el entero positivo $r$. Concluir que una complejidad de $O(n!)$ es ``peor'' que una complejidad exponencial de cualquier base. \fej

\bej Escribir algoritmos para realizar suma, resta y multiplicaci\'on de matrices. Determinar la complejidad y expresarla en funci\'on de la dimensi\'on de las matrices.\fej


\bej Escribir un programa para calcular la descomposici\'on de Cholesky de una matriz sim\'etrica y definida positiva.\fej

\bej Escribir un programa que resuelva sistemas de $n$ ecuaciones lineales con $n$ inc\'ognitas, cuya matriz asociada sea sim\'etrica y definida positiva, usando el programa del ejercicio anterior. \fej

\bej Sean $f:[a,b]\rightarrow\R$ una funci\'on $C^1$, $x=(x_0,x_1,\dots,x_n)$ el vector de puntos equiespaciados tales que $x_0=a$, $x_n=b$, e $y=(y_0,y_1,\dots,y_n)$ el vector con $y_i=f(x_i)$. Escribir un programa que devuelvan un vector $z$ tal que $z_i\sim f'(x_i)$, donde la aproximaci\'on se realiza usando el m\'etodo de diferencias finitas, tomando como datos los vectores $x$ e $y$ y el tipo (\emph{backward}, \emph{forward} y \emph{centradas}).\fej

\bej Sea $f:[a,b]\to\mathbb R$, de clase $C^2$ tal que se anula solamente una vez en el intervalo. Escribir el algoritmo de Newton para aproximar la raiz de $f$. Usar alguna variante de diferencias finitas del ejercicio anterior para estimar los valores de $f'$. \fej

\bej Escribir un algoritmo para el siguiente problema de Cuadrados M\'inimos: Dados puntos distintos en el plano $\{(x_1,y_1),...(x_n,y_n)\}$, hallar el polinomio $p\in\mathcal P_k$ que mejor aproxime estos datos en el sentido de cuadrados m\'inimos; es decir que minimice la expresi\'on: 
$\sum_{i=1}^n|y_i-p(x_i)|^2$. \fej

\noindent{\bf QR y SVD:}


\bej Sea $v\in \C^n$. Probar que la matriz $I-vv^*$ es unitaria si y s\'olo si $\|v\|_2^2=2$ o $v=0$.
\fej

\bej Dados  $x\neq y$ en $\C^n$ tal que $\|x\|_2=\|y\|_2$ y $\langle x, y \rangle$ es real. Probar que la matriz unitaria $U=I-vv^*$ con $\displaystyle v=\frac{\sqrt{2}}{\|x-y\|_2} (x-y)$ satisface que  $Ux=y$.
\fej

\bej\label{qrimp} Implementar un programa que calcule la descomposici\'on $QR$ de una matriz aplicando de manera directa el m\'etodo de ortonormalizaci\'on de Gram-Schmidt. Generar algunas matrices aleatorias y comparar las descomposiciones arrojadas por estos programas entre s\'i y con las dadas por el comando \verb+qr+ de Matlab.
\fej



\bej Considerar el problema de cuadrados m\'inimos, es decir el problema de buscar, dadas por $A\in\R^{n\times m}$ ($n>m$) y $b\in\R^n$, un punto $x^*\in\R^m$ tal que:
$$\|Ax^*-b\| = \min_{x\in\R^m} \|Ax-b\|.$$
Probar que la descomposici\'on $QR$ de $A$ permite resolver este problema. En particular, que si $A=QR$, entonces $x^*$ satisface que $Rx^* = Q^t b.$\fej

\bej Escribir un programa que resuelva el problema de cuadrados m\'inimos utilizando el algoritmo del Ejercicio \ref{qrimp}. \fej

\bej  Dada $A\in\R^{n\times m}$, con descomposici\'on en valores singulares $A=U\Sigma V^*$, se define 
	  $A^\dagger=V\Sigma^\dagger U^*$ la \emph{pseudoinversa} de Moore-Penrose de $A$, donde $\Sigma^\dagger$ es la matriz resultante de invertir los elementos no nulos de $\Sigma$ y trasponerla:
\begin{displaymath}
 \Sigma=\begin{pmatrix}
 \sigma_1 & 0 & 0 & \dots &  & &0\\
  0 & \sigma_2 & 0 & \dots  & &\\
  0 &  0 & \ddots & \dots & & &\vdots\\
  \vdots & & & \sigma_r & & &\\
    & & & & 0 & &\\
    & & & &  & \ddots &\\
    & & & &  & & 0 \\
    \vdots& & & &  & & \vdots \\
    0 & \dots & & & & & 0
\end{pmatrix}\longrightarrow
\Sigma^\dagger =\begin{pmatrix}
 \frac{1}{\sigma_1} & 0 & 0 & \dots &  & &0 &\dots & 0\\
  0 & \frac{1}{\sigma_2} & 0 & \dots  & & & &\vdots\\
  0 &  0 & \ddots & \dots & & &\vdots & & \\
  \vdots & & & \frac{1}{\sigma_r} & & & & &\\
    & & & & 0 & & & & \\
    & & & &  & \ddots & & &\vdots\\
    & & & &  & & 0 & \dots & 0\\
\end{pmatrix}
\end{displaymath}
\begin{itemize}
       \item[a)] Probar que $A^\dagger$ satisface las condiciones de Penrose (En muchas ocasiones $A^\dagger$ se define como la \'unica matriz que
		cumple estas condiciones):
	      \begin{itemize}
	      \item[i.] $A^\dagger AA^\dagger=A^\dagger$ 
	      \item[ii.] $AA^\dagger A=A$
	      \item[iii.] $(AA^\dagger)^*=AA^\dagger$
	      \item[iv.] $(A^\dagger A)^*=A^\dagger A$
	      \end{itemize}
	\item[b)] Concluir que la transformaci\'on dada por $AA^\dagger$ es la proyecci\'on ortogonal sobre $Im(A)$.
\end{itemize}
\fej


\bej Dada $A\in\R^{n\times m}$ con $n\geq m$ y $b\in\R^n$. Sea $A=U\Sigma V^t$ la descomposici\'on en valores
singulares de $A$. se quiere encontrar un 
	    $\hat{x}\in\R^m$ tal que:
\begin{equation}\label{eqfun}
 \|A\hat{x}-b\|_2=\min_{x\in\R^n}\|Ax-b\|_2
\end{equation} 

\begin{itemize}
\item[a)] Probar que si rg$(A)=m$, entonces $\hat{x}$ es \'unica y $\hat{x}=A^\dagger b$. (Sugerencia: recordar que $Nu(A^t)=Im(A)^\perp$).
 \item[b)] Si rg$(A)=r<m$, $\hat{x}$ no es \'unica. En efecto, si consideramos $\tilde{x}\in Nu(A)$, $A(\hat{x}+\tilde{x})=A\hat{x}$. Probar
	    que $\hat{x}=A^\dagger b$ es la \'unica soluci\'on a \eqref{eqfun} en $Nu(A)^\perp$.
\end{itemize}
\fej

\bej Escriba un programa en Matlab que reciba como input una matriz $A$ y un entero positivo $r$ y:
\begin{itemize}
 \item Calcule la descomposici\'on en valores singulares $A=U\Sigma V'$, utilizando el comando \verb+svd+. 
 \item Corrija la matriz $\Sigma$ poniendo $\sigma_i=0$, $\forall i>r$.
 \item Devuelva $B=U\widetilde{\Sigma} V'$, siendo $\widetilde{\Sigma}$ la matriz que resulta de corregir $\Sigma$ seg\'un el \'item anterior.
\end{itemize}

Este programa calcula la matriz $B$ de rango $r$ tal que  la norma $\|A-B\|_2$ es m\'inima. Aplique este programa a distintas matrices, con distintos valores de $r$. 
\fej

\bej
El programa del ejercicio anterior puede utilizarse para comprimir im\'agenes. En efecto, dada una imagen blanco y negro el comando \verb+imread+ de Matlab convierte la imagen en una matriz en la que cada casillero representa un p\'ixel y su valor corresponde al color del p\'ixel en escala de grises.  El comando \verb+imshow+ aplicado a esta matriz, muestra la imagen, mientras que el comando \verb+imwrite+ permite guardar la matriz como un archivo de imagen.

Implementar un algoritmo que reciba como input un archivo de imagen y un entero positivo $r$, realice la compresi\'on como en el ejercicio anterior y guarde el resultado en otro archivo. Experimentar con el valor de $r$, observando cu\'an chico puede ser $r$ en relaci\'on con el tama\~{n}o de la matriz si se desea conservar calidad en la imagen. 

La misma experiencia puede repetirse con im\'agenes en color. En este caso, debe tenerse en cuenta que el comando \verb+imread+ devuelve un arreglo $A$ de tama\~{n}o $m\times n\times 3$: la imagen es de $m\times n$ p\'ixeles y $A(:,:,1)$, $A(:,:,2)$, $A(:,:,3)$ son las matrices correspondientes a su descomposici\'on $RGB$ (red-green-blue).
\fej

\end{document}
