\documentclass[12pt]{article}
%\include{amsfonts}
\usepackage{amssymb,amsmath,latexsym,epsfig,euscript,multicol}
\usepackage{enumitem}
\usepackage[utf8x]{inputenc}

% Caracteres especiales
\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 \sen{\textrm{sen}}

\newtheorem{ejer}{Ejercicio}
\newcommand{\bej}{\begin{ejer}\rm}
\newcommand{\fej}{\end{ejer}}

\def\dt{\Delta t}
\def\dx{\Delta x}
\def\d{\displaystyle}
\def\erf{\mbox{\rm erf}}
\def\R {\mathbb{R}}
\def\N {\mathbb{N}}
\def\Nu{\textrm{Nu}}
\def\Im {\textrm{Im}}

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


\begin{document}

%----------------------------------------------------------
%Encabezado:

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

 \vskip 0.2cm
 \hrulefill
 \vskip 0.2cm

 \centerline{{\bf\Large{\sc Elementos de Cálculo Numérico / Cálculo Numérico}}}
 \vskip 0.2cm
 \centerline{\ttfamily Primer Cuatrimestre 2018}
 \hrulefill

 \bigskip
 \centerline{\bf Práctica N$^\circ$ 7: Aproximación por cuadrados mínimos.}
 \bigskip




%----------------------------------------------------------

\bej
Encontrar el polinomio de grado 1 que aproxima en el sentido
de cuadrados m\'{\i}nimos la siguiente tabla de datos:
\begin{table}[h]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
$x$ &0&1&2&3&4&5&6&7&8&9\\
\hline
$y$ &-.1&1.1&1.9&3.2&3.8&5&6&7.3&8.1&8.9\\
\hline
\end{tabular}
\end{center}
\end{table}

y el polinomio de grado 2 que aproxima en el mismo sentido la
siguiente tabla de datos:
\begin{table}[h]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
$x$ &-1&0&1&3&6\\
\hline
$y$ &6.1&2.8&2.2&6&26.9\\
\hline
\end{tabular}
\end{center}
\end{table}
\fej
% 3
\bej Hallar la constante o polinomio de grado 0 que mejor aproxima en el sentido de cuadrados mínimos a una función $f:[a,b]\to \R$ en $n$ puntos $x_1, \dots, x_n$ en $[a,b]$.
\fej
% 1
\bej Escribir un programa que reciba como datos dos vectores \verb+x+ e \verb+y+ y un número \verb+n+ y
devuelva un vector con los coeficientes del polinomio de grado \verb+n+ que mejor ajusta la tabla dada por
\verb+x+ e \verb+y+ en el sentido de cuadrados mínimos.

Para el cálculo, utilice la descomposición $QR$ de una matriz apropiada.
\fej

%----------------------------------------------------------
% 2
\bej
La siguiente tabla contiene los porcentajes de asistencia a los laboratorios de Cálculo Numérico y la nota obtenida en el final de la materia, por un grupo de alumnos:
% \begin{table}[ht]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
$x$ &60.3&37.4&65&74.8&39&21.1&36.1&38.6&53.1&65.7&16.8&32.4&78.8&15.3 \\
\hline
$y$ &8&6&8&9&6&5&6&6&7&8&5&6&9&5\\
\hline
\end{tabular}
\vspace{10pt}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
$x$ &84.8&71.6&54.7&67.1&35&49.7&80.5&66.8&60.4&30.7&50.2\\
\hline
$y$ &10&9&7&8&6&7&10&8&8&6&7\\
\hline
\end{tabular}
\end{center}
% \end{table}
Realizar un ajuste lineal y un ajuste cuadrático de los datos. A partir de cada ajuste, ¿qué porcentaje de asistencia a los laboratorios sería recomendable alcanzar si se quiere obtener al menos un 8 en el final?
\fej

\newpage
%----------------------------------------------------------
% 4
\bej \label{runge} Considerar la función $\displaystyle
f(x)=\frac{1}{1+25 x^2}$ en el intervalo [-1,1].

Para $n=5,10,15$; graficar simultáneamente $f$ junto con
\begin{itemize}
\item los polinomios que aproximan a $f$ en el sentido de
cuadrados mínimos en $n+1$ puntos equiespaciados y tienen
grado $\frac 25 n$ y $\frac 45 n$,

\item el polinomio que resulta de interpolar a $f$ en los puntos
anteriores.
\end{itemize}
\fej


%----------------------------------------------------------
% 9
\bej Sea $S$ el subespacio de funciones continuas definidas de $\R$ en $\R$ generado por las funciones del conjunto $B = \{1, x, 2^x, 3^x\}$. Para $i = 0, 1, 2, 3$, sea $x_i = i$, y sea $T$ un conjunto de datos del tipo $\{(x_0, y_0), (x_1, y_1), (x_2, y_2), (x_3, y_3)\}$.
\begin{enumerate}[label=\alph*)]
\item Demostrar que $B$ es una base de $S$ y que para todo conjunto de datos $T$ existe una única función $p \in S$ tal que $p$ interpola a $T$.
\item Demostrar que $\langle p,q \rangle  = \sum_{i = 0}^3p(x_i)q(x_i)$ es un producto interno en $S$.
\item Aproximar la siguiente tabla de datos en el sentido de cuadrados mínimos

% \begin{table}[ht]
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
$x$ &0&1&2&3\\
\hline
$y$ &0.3&-0.2&7.3&23.3\\
\hline
\end{tabular}
\end{center}
% \end{table}

con funciones del tipo:\ (a)\quad $y=a 2^x + b 3^x$, \hskip 1cm
(b)\quad $y=a 2^x + b 3^x + c.$
\item Graficar los resultados obtenidos junto con los valores de la tabla de datos.
\end{enumerate}
\fej


%----------------------------------------------------------
% 12
\bej Considerar\ $\erf:\R\to\R$ la función  dada por
$$\erf(x)=\frac 2{\sqrt{\pi}} \int_0 ^x e^{-t^2} dt.$$
\begin{enumerate}[label=\alph*)]
\item Graficar la función con el comando $\erf$ de Octave en el intervalo $[-15,15]$. Observar que $\d\lim_{x\to \pm \infty}
\erf(x)=\pm 1$.

\item Aproximar la función\ $\erf$\ en el sentido de cuadrados mínimos con polinomios de grado 1, 3 y 5, considerando 20 puntos equiespaciados en el intervalo $[-10,10]$. Graficar $\erf$ junto con estos polinomios en el intervalo $[-15,15]$. Observar que la aproximación es mala fuera del intervalo $[-10,10]$.
\item Se quiere aproximar nuevamente la función erf en el sentido de cuadrados mínimos con una combinación lineal de funciones
que compartan con erf la propiedad de ser acotada e impar. Para ello, ajustar la función erf con una función del tipo
$$c_1xe^{-x^2} + c_2\hbox{arctan}(x) + c_3\frac{x}{x^2 + 1},$$
considerando 20 puntos equiespaciados en el intervalo $[-10, 10]$. Graficar erf junto a esta aproximación en el intervalo $[-15, 15]$ y comparar con el ítem (b).
\end{enumerate}
\fej

%----------------------------------------------------------
% 13
\bej Aproximar los datos de la tabla siguiente con un modelo de la forma $ f(x) \sim a e^{bx}$ en el sentido de cuadrados mínimos para la función $ \ln(f(x))$.
% \begin{table}[!ht]
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
$x$ &-1&0&1&2\\
\hline
$y$ &8.1& 3&1.1& 0.5\\
\hline
\end{tabular}
\end{center}
% \end{table}
\fej

%----------------------------------------------------------
% 14
\bej Aproximar los datos de la tabla siguiente con un modelo de la forma $ f(x) \sim - e^{ax^2 + bx +c}$ en el sentido de cuadrados mínimos para la función $ \ln(-f(x))$.
% \begin{table}[!ht]
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
$x$ &-1&0&1&2\\
\hline
$y$ & - 1.1& - 0.4&- 0.9& - 2.7\\
\hline
\end{tabular}
\end{center}
% \end{table}
\fej


%----------------------------------------------------------
% 15
\bej Considerar la función signo dada por
$$\mathrm{sgn}(x)=\left\lbrace\begin{array}{lll}-1 & \phantom{a} & \text{si }x<0\\0 & & \text{si }x=0\\1 & & \text{si }x>0\end{array}\right.$$
Aproximar la función $\mathrm{sgn}$ en el sentido de cuadrados mínimos con funciones de la forma $a_1\cos(x)+b_1\sin(x)+a_2\cos(2x)+b_2\sin(2x)+a_3\cos(3x)+b_3\sin(3x)$, considerando puntos equiespaciados en el intervalo $[-\pi,\pi]$, con paso $0.001$. Graficar el resultado obtenido.

\fej

%----------------------------------------------------------
% 5
\bej Considerar la matriz:
$$A=\left(\begin{array}{cc}
   4&0\\3&5
  \end{array}\right)
$$
\begin{enumerate}[label=\alph*)]
 \item Calcular una descomposición en valores singulares de $A$.
 \item Dibujar el círculo unitario en $\R^2$ y la elipse $\{Ax:\;x\in\R^2,\,\|x\|_2=1\}$, señalando los valores singulares y los vectores singulares a izquierda y a derecha.
 \item Calcular $\|A\|_2$ y $Cond_2(A)$.
 \item Calcular $A^{-1}$ usando la descomposición hallada.
\end{enumerate}
\fej

%------------------------------------------------------------
% 6
\bej Dada $A\in\R^{m\times n}$, de rango $r$, probar que $A$ puede escribirse como una suma de $r$ matrices de rango $1$.
\fej

%----------------------------------------------------------
% 7
\bej Dada una matriz $A\in\R^{m\times n}$, $m\geq n$, cuya descomposición en valores singulares reducida es $A=\hat{U}\hat{\Sigma}\hat{V}^t$. Se define la pseudo-inversa de $A$ como $A^+ =
\hat{V}\hat{\Sigma}^{-1}\hat{U}^t$.

Considerar el problema de cuadrados mínimos:
\begin{equation}\label{minquad}
\min_{x\in\R^n} \|Ax-b\|_2.
\end{equation}
\begin{enumerate}[label=\alph*)]
\item Probar que si rg$(A)$ es $n$, entonces \eqref{minquad} tiene solución única $x^*$ y que $x^* = A^{+}b$. ({\bf Sug.:} Recordar que $\Nu(A^t) = \Im(A)^{\perp}$)
\item Si rg$(A)=r<n$, entonces la solución de $\eqref{minquad}$ no es única. En efecto: si $x^*$ es solución y $\tilde{x}\in\Nu(A)$, entonces $x^*+\tilde{x}$ también es solución. Probar que en tal caso, $x^*= A^{+}b$ es la única solución de $\eqref{minquad}$ en $\Nu(A)^{\perp}$.
\end{enumerate}
\fej

\bej
\item Verificar que $ A^+$, la pseudoinversa de $A$, satisface las siguientes propiedades:\\

   i) $AA^+A=A$   \hspace{1cm} ii) $A^+AA^+=A^+$  \hspace{1cm} iii) $(AA^+)^t= AA^+$  \hspace{1cm}  iv) $ (A^+A)^t=A^+A$\\


\textit{De hecho, $A^+$ es la \'unica que satisface las 4 propiedades.}
\fej
%----------------------------------------------------------
% 8
\bej Escribir un programa que reciba como datos dos vectores \verb+x+ e \verb+y+, y un conjunto de funciones \verb+S+:
$$\verb+S+ = \{f_1,\dots,f_n\}$$
\noindent y calcule la función $f\in<f_1,\dots,f_n>$ que mejor aproxima a la tabla dada por \verb+x+ e \verb+y+ en el sentido de cuadrados mínimos.

\noindent{\bf Nota: }Investigar la estructura de datos \verb+cell+ como una forma de dar el conjunto \verb+S+.
\fej



%------------------------------------------------------------
% 10
\bej Escribir un programa en Octave que reciba como input una matriz $A$ y un entero positivo $r$ y:
\begin{itemize}
 \item Calcule la descomposición 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ún el ítem anterior.
\end{itemize}

Probar que la matriz $B$ es la matriz de de rango $r$ cuya distancia a $A$ (en norma 2) es mínima.. Aplicar este programa a distintas matrices, con distintos valores de $r$.
\fej

%------------------------------------------------------------
% 11
\bej
El programa del ejercicio anterior puede utilizarse para comprimir imágenes. En efecto, dada una imagen blanco y negro el comando \verb+imread+ de Octave convierte la imagen en una matriz en la que cada casillero representa un píxel y su valor corresponde al color del píxel 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ón como en el ejercicio anterior y guarde el resultado en otro archivo. Experimentar con el valor de $r$, observando cuán chico puede ser $r$ en relación con el tamaño de la matriz si se desea conservar calidad en la imagen.

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

(Considerar los comandos \verb#double# y \verb#uint8#.)
\fej



%----------------------------------------------------------
% 16
\bej Considerar $$\langle f,g\rangle =\int^1_{-1} f'(x)g'(x) \ dx $$
\begin{enumerate}[label=\alph*)]
\item Probar que $\langle\ ,\ \rangle $ es un producto interno en $S_m$, el espacio generado por $\{x,x^2,x^3,\cdots,x^m\}$.
\item Hallar una base ortonormal para $S_3$.
\item Hallar la mejor aproximación en el sentido de cuadrados mínimos sobre $S_3$ para $f(x)=x^4$.
\end{enumerate}
\fej

%----------------------------------------------------------
% 17
\bej Sea
\[\langle f,g \rangle = f(1) g(1) - f(-1) g(-1) + \int_{-1}^{1}f'(x) g'(x) dx.\]
\begin{enumerate}[label=\alph*)]
\item Decidir si $\langle\cdot,\cdot \rangle$ es un producto interno en $C^1([-1, 1])$.
\item Probar que $\langle\cdot,\cdot \rangle$ es un producto interno para el espacio $V=\{f\in C^1([-1, 1]): f \mbox{ es impar}\}.$
\item Hallar la mejor aproximación en el sentido de cuadrados mínimos del polinomio \break $p(x) = x^5$ sobre el subespacio $S$ generado por $\{x,x^3\}$.
\end{enumerate}
\fej

%----------------------------------------------------------
% 18
\bej
\begin{enumerate}[label=\alph*)]
\item Demostrar que
$$\langle f, g\rangle  = \int_{-1}^1 f''(x)g''(x)dx + f(-1)g(-1) + f(1)g(1)$$
es un producto interno en el espacio ${\cal C}^2([-1, 1])$.
\item Hallar una base ortonormal de $\R_2[X]$ para el producto interno definido en el ítem anterior.
\item Probar que si $f$ es una función par en ${\cal C}^2([-1,1])$, entonces su proyección sobre $\R_2[X]$ es par, y que si $f$ es una función impar, entonces su proyección es impar.
\end{enumerate}
\fej

\bej
En el conjunto de las funciones definidas en el intervalo
$[-1,1],$ que son por lo menos dos veces derivables, definimos el siguiente
producto
\[
\left\langle f,g\right\rangle =\int_{-1}^{1}\left(  f^{\prime\prime}%
g^{\prime\prime}+f^{\prime}g^{\prime}\right)  dx
\]

\begin{enumerate}
\item [a)]\textquestiondown Es un producto interno en ese conjunto?.

\item[b)] Para todo $n\geq1,$ sea $S_{n}$ el subespacio generado por $\left\{
x,x^{2},\ldots,x^{n}\right\}  .$ \textquestiondown Es un producto interno
sobre $S_{n}?.$

\item[c)] Hallar una base ortonormal para $S_{3}.$

\item[d)] Hallar la proyecci\'{o}n ortogonal de la funci\'{o}n $f(x)=\mbox
{sen}(\pi x)$ sobre $S_{3}.$ \textquestiondown Cu\'al es la proyecci\'{o}n ortogonal de la funci\'{o}n $g(x)=2\mbox
{sen}(\pi x) -5x^2$ sobre $S_{3}?$
\end{enumerate}
\fej

\end{document}

%----------------------------------------------------------
% 3
