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

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

%----------------------------------------------------------
% 1
\bej Probar que para toda $A\in\R^{n\times n}$
\begin{itemize}
\item[a)] $$||A||_{\infty}=\max_{1\le i\le n} \sum_{j=1}^{n}|a_{ij}| $$
\item[b)] $$||A||_{1}=\max_{1\le j\le n} \sum_{i=1}^{n}|a_{ij}|$$
\end{itemize}
\fej

%----------------------------------------------------------
% 2
\bej \label{primero}Si $x\in \R^n$ y $A \in \R^{n \times n},$
probar que las constantes de equivalencia entre las normas
$\|.\|_1$ y $\|.\|_2$ y entre las normas $\|.\|_2$ y
$\|.\|_{\infty}$ vienen dadas por:
\begin{itemize}
\item Vectorial
\begin{align*}
& \|x\|_{\infty}\leq\|x\|_2\leq \sqrt{n} \|x\|_{\infty}\\
& \frac{1}{\sqrt{n}}\|x\|_1\leq\|x\|_2\leq \|x\|_1
\end{align*}

\item Matricial
\begin{align*}
& \frac{1}{\sqrt{n}}\|A\|_{\infty}\leq\|A\|_2\leq \sqrt{n} \|A\|_{\infty}\\
& \frac{1}{\sqrt{n}}\|A\|_1\leq\|A\|_2\leq \sqrt{n} \|A\|_1
\end{align*}
\item Calcular los coeficientes para la equivalencia vectorial y
matricial entre las normas $\|.\|_1$ y $\|.\|_{\infty}$
\end{itemize}
\fej

%------------------------------------------------------------
% 3
\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 que 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

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

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

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

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


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

\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

%------------------------------------------------------------
% 9

\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


%------------------------------------------------------------
% 10

\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}.$$
Demostrar que $cond_{\infty}(H_n) \to \infty$ cuando $n\to\infty$.
\fej

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


%------------------------------------------------------------
% 12
\bej 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

%------------------------------------------------------------
% 13
\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 $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 tri\-dia\-go\-na\-les.
\end{enumerate}
\fej

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

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

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

%------------------------------------------------------------
% 17
\bej Implementar dos programas que calculen la descomposición $QR$ de una matriz:
\begin{enumerate}
\item Aplicando de manera directa el método de ortonormalización de Gramm-Schmidt.
\item Utilizando transformaciones de Householder.
\end{enumerate}
Generar algunas matrices aleatorias y comparar las descomposiciones arrojadas por estos programa con las dadas por el comando \verb+qr+ de Octave. ¿Qué se observa?
\fej

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

%------------------------------------------------------------
% 19
\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 sucesión de matrices $A_k$ definida del siguiente modo:
 $$A_1=A,\quad Q_k R_k \mbox{ descomposición 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 ítem 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} 