\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.85cm}\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$ 5: Métodos iterativos para sistemas lineales.}
 \bigskip

%----------------------------------------------------------
% 1
\bej Escribir un programa que implemente el método de Jacobi y
otro que implemente el método de Gauss-Seidel para la
resolución de un sistema lineal $Ax = b,$ con las siguientes
condiciones:
\begin{itemize}
\item que finalice si el método se estaciona,
\item que finalice con una advertencia si se excede cierto tope de iteraciones,
\end{itemize}
Sugerencia: utilizar los comandos {\verb+tril+} y \verb+diag+ de  {\tt Octave}.
\fej


%----------------------------------------------------------
% 2
\bej El objetivo de este ejercicio es probar que el radio espectral de una matriz \\ $A\in\R^{n\times n}$ acota inferiormente a toda norma de $A$, sin utilizar normas complejas.

Dada $A\in\R^{n\times n}$, sea $\lambda = a+ib$ un autovalor de $A$ y sea $u+iv$ el autovector correspondiente, con $a,b\in\R$, $u,v\in\R^n$.
\begin{itemize}
 \item[a)] Calcular $Au$ y $Av$ y probar que:
 $$\|Au\|_2^2+\|Av\|_2^2=(a^2+b^2)(\|u\|_2^2+\|v\|_2^2).$$
 \item[b)] Concluir que:
 $$|\lambda|\le \|A\|_2.$$
 \item[c)] Probar que dada una norma cualquiera $\|\cdot\|$ en $\R^{n\times n}$ vale que
 $$|\lambda| \le \|A\|.$$
 (Sugerencia: Usar la equivalencia de normas. Notar que si $B=A^m$, entonces $\lambda^m$ es autovalor de $B$).
\end{itemize}
\fej

%----------------------------------------------------------
% 3
\bej
Sea $A$  una matriz que admite una base de autovectores. Mostrar una norma $|||.|||$ subordinada a una norma vectorial tal que $\rho(A)=|||A|||$.
\fej

%----------------------------------------------------------
% 4
\bej Considerar el sistema $Ax=b$ para $A=\left(\begin{array}{cc}
64 & -6\\  6 & -1\end{array}\right)$ y $b=(1, 2)$.
\begin{enumerate}[label=\alph*)]
\item Demostrar que el método de Jacobi converge para todo dato
inicial. Verificar, sin embargo, que la matriz no es diagonal
dominante.
\item Sea $J$ la matriz de iteración. Hallar las normas $1$, $\infty$ y $2$ de $J$.
Hallar una norma $\| \, \  \|$ en la cual $\| J  \|$ sea $<1$.
\end{enumerate}
\fej

%----------------------------------------------------------
% 5
\bej Decidir para cada uno de los siguientes sistemas, si los
métodos de Jacobi y de Gauss-Seidel son convergentes. En caso
afirmativo usarlos para resolver el sistema. Si ambos métodos
convergen, determinar cuál converge más rápido.
¿Es la matriz del sistema diagonal dominante? ¿y simétrica y
definida positiva?
\[
{\rm (a)}\ \left(
\begin{array}{ccc}
3&1&1\\
2&6&1\\
1&1&4
\end{array}
\right)
\left(
\begin{array}{c}
x_1\\x_2\\x_3
\end{array}
\right)
=
\left(
\begin{array}{c}
5\\9\\6
\end{array}
\right), \hskip 0.3cm {\rm (b)}\ \left(
\begin{array}{cccc}
5&7&6&5\\
7&10&8&7\\
6&8&10&9\\
5&7&9&10
\end{array}
\right)
\left(
\begin{array}{c}
x_1\\x_2\\x_3\\x_4
\end{array}
\right)
=
\left(
\begin{array}{c}
23\\32\\33\\31
\end{array}
\right)
\]
\fej


%----------------------------------------------------------
% 6
\bej \begin{enumerate}[label=\alph*)]
\item Mostrar que toda matriz $B\in\R^{n\times n}$ con
$|\det(B)|>1$ tiene un autovalor $\lambda$, real o complejo, con
$|\lambda|>1$.

\item Decidir si el método de Jacobi converge o no para un
sistema dado por la matriz \\ $A=\left(\begin{array}{ccc} -1 & 1 & 2\\
4 & -1 & 3\\ 5 & 6 & -1\end{array}\right).$
\end{enumerate}
\fej

%----------------------------------------------------------
% 7
\bej Sean $A, B\in \R^{3\times 3}$ las matrices
\[
A=\left( \begin{array}{ccc} a&c&0\\c&a&c\\0&c&a \end{array}
\right); \hskip 1cm B=\left( \begin{array}{ccc}
0&b&0\\b&0&b\\0&b&0
\end{array} \right).
\]
\begin{enumerate}[label=\alph*)]
\item  Probar que $\lim_{n\rightarrow \infty} B^n=0$ si y sólo
si $|b|<\sqrt{2}/2$.

\item Dar condiciones necesarias y suficientes sobre $a, c\in\R$
para la convergencia de los métodos de Jacobi y de Gauss-Seidel
aplicados a la resolución de $Ax=v$.
\end{enumerate}
\fej

%----------------------------------------------------------
% 8
\bej \begin{enumerate}[label=\alph*)]
\item Probar que si $A$ tiene una base de autovectores $v_i$, con
autovalores $\lambda_i$, la matriz $$B=I+s A,  \ \ \ s \in \R$$
tiene los mismos autovectores, con autovalores $\nu_i=1+s
\lambda_i$.

\item Se sabe que los autovalores de la matriz $A \in
\R^{(n-1)\times (n-1)}$
\[ A=\left( \begin{array}{cccccc}
-2 & 1    & 0 & \cdot & \cdot & 0\\
1  & -2   & 1 & 0       & \cdot & 0\\
   &\cdot & \cdot  & \cdot& &   \\
   &\cdot & \cdot  & \cdot& &   \\
0  &\cdot & \cdot  &    1 & -2    & 1 \\
0  &\cdot &\cdot   &    0 & 1     & -2
\end{array} \right)
\]
son $\lambda_j=-4 \sin^2(\frac{\pi j}{2 n})$, $j=1,\ldots ,n-1 $. Considerar sistemas de la forma $Ax = b$, con $A$ como en el ítem anterior. Decidir si el método de Jacobi converge. ¿Qué sucede con el método de Gauss-Seidel? ¿Cuál resulta preferible?

\item Considerar el problema de Poisson en el intervalo $[0,1]$:
$$\begin{array}{cl}
u''(x) = f(x), & x\in[0,1]\\
u(0)=u(1)=0
\end{array}$$
Formular el problema por diferencias finitas y decidir si los métodos de Jacobi o Gauss-Seidel pueden aplicarse para resolver el sistema lineal resultante.
\end{enumerate}
\fej

%----------------------------------------------------------
% 9
\bej
\begin{enumerate}[label=\alph*)]
       \item Sean $M,N\in\R^{n\times n}$, con $M$ inversible. Probar que los autovalores de $-M^{-1}N$ son las raíces del polinomio $\det(\lambda M + N)$
       \item Sean $$A=\left(\begin{array}{ccc}
                     0 & 1 & 1+\frac{1}{\alpha} \\ 1 & \frac{1}{\alpha} & 0 \\ 1+\frac{1}{\alpha} & 1 & 0
                    \end{array}\right),\quad M=\left(\begin{array}{ccc} 0 & 0 & \frac{1}{\alpha} \\ 0 & \frac{1}{\alpha} & 0 \\ \frac{1}{\alpha} & 0 & 0 \end{array}\right).$$
                    Para resolver un sistema $Ax=b$ se propone el método iterativo:
                   \begin{equation}\label{eq}
                   x_{n+1} = -M^{-1}Nx_n + M^{-1}b,
		   \end{equation}
                   Siendo $N = A-M$. Probar que si el método \eqref{eq} converge a $x$, entonces $x$ es solución del sistema $Ax=b$.
         \item Hallar todos los valores de $\alpha$ para los cuáles el método propuesto converge.
         \item ¿Qué restricción debería imponerse sobre $\alpha$ si se quiere garantizar que el error $e_n = x_n-x$ satisfaga:
         $$\|e_n\|<\Big(\frac{1}{2}\Big)^n\|e_0\|,$$
         para alguna norma $\|\cdot\|$?
      \end{enumerate}
\fej

%----------------------------------------------------------
% 10
\bej Utilizar la iteración de Gauss-Seidel para resolver el
sistema $A_n x=b_n$ para $$ A_n= \left(
\begin{array}{cc}
1&2\\
2&4+\frac{1}{n^2}
\end{array}
\right)  \qquad \mbox{y}\qquad b_n=(1,2-\frac{1}{n^2}).$$¿Cómo es la convergencia? ¿Tiene esto que ver con el mal
condicionamiento de $A$? Dar un ejemplo de una matriz mal
condicionada para la cual la convergencia sea rápida.
\fej

\bej (m\'etodo SOR)
Dada $A \in R^{n\times n}$ con $a_{ii} \ne 0$, $1 \le i \le n$,  $A=L+D+U$ con \\ $L=$ triangulo inferior estricto de $A$,
$D= \mbox{diag}(A)$ y $U=$ triangulo superior estricto de $A$.
\begin{enumerate}
\item Demostrar que el sistema $Ax=b$ es equivalente al sistema\\
$(D+wL)x=((1-w)D - wU)x +wb$, cualquiera sea $w\ne 0$.     
\item Considere el m\'etodo iterativo $x^{k+1}=B(w)x^k + c$ con $B(w)=(D+wL)^{-1}((1-w)D - wU)$.    
Probar que $\det(B(\omega))=(1-\omega)^n$ y concluir que: Si el m\'etodo converge  $\Rightarrow$ $w\in(0,2)$
\item  Sea
\[
A= \left( \begin{array}{cc}
1& \frac{2}{3}\\
\frac{2}{3}&1
\end{array} \right)
\]
Compare los m\'etodos para $w= \frac{3}{2}$ y $w=1$
> Cu\'al elegir\'{\i}a y porqu\' e ?.
\end{enumerate}
\fej
\end{document} 