\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}

\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 2016}
 \hrulefill

 \bigskip
 \centerline{\bf Práctica N$^\circ$ 4: Número de condición. Sistemas Lineales.}
 \bigskip



%------------------------------------------------------------
% 1
\bej Se quiere estimar la norma $2$ de una matriz $A \in \R^{3 \times
3}$ como el m\'aximo del valor $ \|Ax\|_2 / \|x\|_2 $ entre varios
vectores $x \in \R^{3}$ no nulos generados al azar. Hacer un
programa reciba una matriz $A$ y luego
\begin{itemize}
\item genere los primeros 100 t\'erminos de la siguiente sucesión:
$$s_1 = 0, \quad s_{k+1}= \max\Big\{s_k, \frac{\|Ax_k\|_2}{\|x_k\|_2}\Big\}$$
donde los $x_k \in \R^{3}$ son vectores no nulos generados al azar
con coordenadas en el intervalo $[-1,1]$.

 \item grafique la sucesión calculada, junto con el valor
exacto de la norma de la matriz.
\end{itemize}

Recordar que tanto la norma de un vector como de una matriz se
calculan en {Octave} con el comando {\verb+norm+}. Tener en
cuenta que los vectores generados al azar (comando {\verb+rand+})
tienen coordenadas en el intervalo $[0,1]$. Chequear, además
que estos vectores generados resulten no nulos.
\fej

%------------------------------------------------------------
% 2
\bej \label{errmetnum} Se tiene el sistema $Ax=b$. 
\begin{enumerate}[label=\alph*)]
\item Sea $x$ la solución exacta y $\tilde x$ la solución obtenida numéricamente. Se llama \emph{residuo} al vector $r:=b-A\tilde x$. Si notamos $e=x-\tilde x$, mostrar que:
$$ \frac{1}{cond(A)}\frac{\|r\|}{\|b\|} \leq \frac{\|e\|}{\|x\|}
\leq cond(A)\frac{\|r\|}{\|b\|}.$$
¿Cómo se puede interpretar este resultado?
\item En lugar del dato exacto $b$ se conoce una aproximación $\tilde{b}$. $\tilde{x}$ es tal que $A\tilde{x}=\tilde{b}$. Probar que:
$$ \frac{1}{cond(A)}\frac{\|b-\tilde{b}\|}{\|b\|} \leq \frac{\|x-\tilde{x}\|}{\|x\|}
\leq cond(A)\frac{\|b-\tilde{b}\|}{\|b\|}.$$
¿Cómo se puede interpretar este resultado?
\end{enumerate}
\fej

%------------------------------------------------------------
% 3
\bej \label{m-cond-2} Sea 
$$A=\left(
\begin{array}{ccc}
3&0 & 0\\
0& \frac 54 & \frac 34\\
0& \frac 34 & \frac 54\\
\end{array}
\right).$$ 
\begin{enumerate}[label=\alph*)]
\item Calcular $cond_2(A)$ y  $cond_\infty(A)$.
\item ¿Cuán chico debe ser el error en los datos ($b-\tilde{b}$), si se desea que el error en la aproximación de la solución sea menor que $10^{-4}$? 
\item Realizar experimentos numéricos para verificar las estimaciones del ítem anterior. Considerar $b=(3,2,2)^t$, que se corresponde con la solución exacta $x=(1,1,1)^t$. Generar vectores de error aleatorios, normalizarlos para que su norma sea tan chica como la estimada en el item anterior y perturbar $b$ obteniendo $\tilde{b}$. Finalmente, resolver $A\tilde{x}=\tilde{b}$ y verificar que $\|\tilde{x}-x\|<10^{-4}$.
\end{enumerate}
\fej

%------------------------------------------------------------
% 4
\bej  \label{cond-cond} Probar que si $A\in\R^{n\times n}$ es una
matriz inversible y $\|\ \|$ es una  norma matricial, la
condición de $A$ verifica la desigualdad:
\[ \frac{1}{cond(A)}\leq \inf\left\{ \frac{\|A-B\|}{\|A\|} : B \mbox{ es singular}
\right\}. \]

Deducir que

\[ {cond(A)}\ge \sup\left\{ \frac{\|A\|}{\|A-B\|} : B \mbox{ es singular}
\right\}. \]

Nota: En ambos casos, vale la igualdad, pero la otra desigualdad
es un poco m\'as complicada de probar. De la igualdad se puede
concluir que $cond(A)$ mide la distancia relativa de $A$ a la
matriz singular m\'as próxima.
\fej

%------------------------------------------------------------
% 5
\bej \begin{enumerate}[label=\alph*)]
\item
Estimar la $cond_\infty(A)$ de las siguientes matrices en función $\varepsilon$ (cuando $\varepsilon\to 0$).
$$ {\rm (i)}\quad  A=\left(
\begin{array}{ccc}
1& 1 & 1\\
1& \varepsilon & \varepsilon^2\\
1& 0 & 0\\
\end{array}
\right),\qquad {\rm (ii)}\quad B=\left(
\begin{array}{ccc}
1& 0 & 1 + \varepsilon\\
2& 3 & 4\\
1 - \varepsilon& 0 & 1\\
\end{array}
\right).$$
\item Concluir que la condición de las matrices $A$ y $B$ del ítem anterior tienden a infinito, cualquiera sea la norma considerada.
\end{enumerate}
\fej


%------------------------------------------------------------
% 6

\bej Sea $D_n$ la matriz diagonal de $n\times n$ con elementos diagonales iguales a 1/10. Calcular el determinante de $D_n$ y ver que $det(D_n)\to 0$ si $n\to \infty$.
>$D_n$ está mal condicionada?
\fej

%------------------------------------------------------------
% 7

\bej
Sea $A_n\in\mathbb{R}^n$ la matriz dada por $A_n=(a_{i,j})$, 
$$a_{i,j}=\left\{\begin{array}{cl}
                  1&\textrm{si }i=1\textrm{ o }j=1\\
                  1/i &\textrm{si }i=j\\
                  0 & \textrm{en otro caso}
                 \end{array}\right.
$$
\begin{itemize}
 \item[a)] Probar que $Cond_\infty(A_n)\ge Cn^2$ para alguna constante $C$ independiente de $n$. 
 \item[b)] Probar que $Cond_2(A_n)\longrightarrow\infty$ cuando $n\longrightarrow\infty$.
\end{itemize}
\fej


%------------------------------------------------------------
% 8

\bej \label{hilbert} La $n$-ésima matriz de Hilbert
$H_n\in \R^{n\times n},$ se define
de la siguiente manera
$$(H_n)_ {i,j} = \frac{1}{i+j-1}.$$
\begin{enumerate}[label=\alph*)]
\item Demostrar que $cond_{\infty}(H_n) \to \infty$ cuando $n\to\infty$.  
\end{enumerate}
\fej

%------------------------------------------------------------
% 9
\bej  \label{lusimple}
\begin{enumerate}[label=\alph*)]
\item Escribir un programa en {\tt Octave} que resuelva un sistema
$Ax=b$, $A \in \R^{n\times n}$ usando eliminación gaussiana sin
pivoteo.

\item Adaptar el programa del \'\i tem anterior para que calcule la  matriz $A^{-1}$.
\end{enumerate}
\fej


%------------------------------------------------------------
% 10
\bej Para cada $n\in\N$, se quiere calcular la solución del
sistema lineal:
\begin{eqnarray*}
10^{-3} x+ 2y &=& 8 \\
x+y &=& 2
\end{eqnarray*}
utilizando eliminación gaussiana sin pivoteo, con aritmética
de punto flotante de 3 dígitos y sistema de redondeo.
\begin{enumerate}[label=\alph*)]
\item Analizar si el resultado difiere significativamente
de la solución real.

\item Repetir el método de eliminación gaussiana eligiendo el
pivote más conveniente.
\end{enumerate}
\fej

%------------------------------------------------------------
% 11
\bej  Sea $A\in\R^{n\times n}$ una matriz tridiagonal. 
\begin{enumerate}[label=\alph*)]
 \item Mostrar que el proceso de eliminación gaussiana preserva los ceros de $A$, es decir que a lo largo de la triangulación no se generan valores no nulos fuera de las tres diagonales principales. 
 \item Adaptar el programa del Ejercicio \ref{lusimple} para que resuelva un sistema de ecuaciones $Ax=b$, con $A$ tridiagonal. El programa debe recibir cuatro vectores (las tres diagonales principales y $b$), y devolver $x$. 

 Utilizar los comandos \verb+tic+ y \verb+toc+ de {\tt Octave} para conocer el tiempo que se tarda en resolver un sistema con este programa y comparar con el que se requiere para resolver el mismo sistema utilizando los comandos \verb+inv+ y \verb+\+, que no están especialmente pensados para matrices tridiagonales.
\item Experimentar con ejemplos de la Práctica 3 cuya formulación conduzca a matrices tridiagonales.
\end{enumerate}
\fej

%------------------------------------------------------------
% 12
\bej Considerar la matriz 
$$\left(
\begin{array}{ccc}
4&2&-2\\
2&5 & 5\\
-2&5 & 11\\
\end{array}
\right).$$
Mostrar que es definida positiva y calcular su descomposición de
Cholesky.
\fej

%------------------------------------------------------------
% 13
\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

%------------------------------------------------------------
% 14
\bej Sean

$$H_j =
\left(\begin{array}{cc}
j & -j \\
      j & j
 \end{array}\right)\in\mathbb{R}^{2\times 2},
\quad  An =
\left(\begin{array}{cccc}
           
       H_1 & 0 & \dots  & 0\\
           
       0 & H_2  & \dots & \vdots \\
           
       \vdots &  &\ddots  & \vdots \\
           
       0 & \dots &   & H_n
           
      \end{array}\right) \in \mathbb{R}^{2n\times 2n}$$
		    \begin{enumerate}
		 \item[a)] Probar que $Cond_1(A_n) \to \infty$ cuando $n\to \infty$.
		 \item[b)] Calcular la descomposición en valores singulares y la descomposición QR de $A_n$.
		 \item[c)] Calcular $Cond_2(A_n)$.
		 \item[d)] Sea $P_n$ la matriz diagonal tal que 
		 $(P_n)_{ii} = (A_n)_{ii}$, ($P_n$ es el precondicionador de Jacobi
para $A_n$). Probar que $Cond_2(P_n^{-1} A_n) = 1$. ¿Cómo podría utilizarse esta información si
se quiere resolver un sistema de la forma $A_n x = b$?
		 \end{enumerate}
\fej

%------------------------------------------------------------
% 15
\bej Escriba 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}

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

%------------------------------------------------------------
% 16
\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).
\fej

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

%------------------------------------------------------------
% 18
\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

%------------------------------------------------------------
% 19
\bej Implementar un programa que calcule la descomposición $QR$ de una matriz aplicando de manera directa el método de ortonormalización de Gramm-Schmidt. Generar algunas matrices aleatorias y comparar las descomposiciones arrojadas por este programa con las dadas por el comando \verb+qr+ de Octave.
\fej

%------------------------------------------------------------
% 20
\bej Hallar la factorización $QR$ de las siguientes  matrices
\[\begin{array}{cc}
a)\,A=\left(\begin{array}{cc} 0 & -4 \\ 0 & 0\\ -5 &
-2\end{array}\right). &
b)\, A=\left(\begin{array}{ccc} 3 & 2 & 3 \\ 4 & 5 &6\end{array}\right).
\end{array}
\]
\fej

%------------------------------------------------------------
% 21
\bej {\bf Método QR:} El \emph{metódo QR} utiliza la descomposición $QR$ para calcular autovalores. Consiste en, dada una matriz $A\in\R^{n\times n}$, generar una suceción de matrices $A_k$ definida del siguiente modo:
 $$A_1=A,\quad Q_k R_k \mbox{ descomposicion QR de } A_k \mbox{ y } A_{k+1}=R_k Q_k.$$
 \begin{enumerate}[label=\alph*)]
  \item Probar que todas las matrices $A_k$ tienen los mismos autovalores.
  \item Implementar un programa que genere los pimeros $m$ términos de la sucesión del item anterior.
  \item Aplicar el programa  para la matriz
$$A=\left(\begin{array}{cccc}190  &  66  & -84  &  30\\
    66  & 303  &  42  & -36\\
   336 & -168 &  147 & -112\\
    30&   -36&    28 &   291\end{array}\right),$$
calcular $A_m$ con $m=30,50,100$. Observar que los dos primeros elementos de la diagonal de $A_m$  aproximan a los autovalores reales de $A$ y que los autovalores de la submatriz $A_m(3:4,3:4)$ aproximan a los autovalores complejos de $A$.
\end{enumerate}
\fej


\end{document}


