\documentclass[10pt]{beamer}

\mode<presentation>
%\usetheme{Warsaw}
%\usetheme{Darmstadt}
%\usepackage{times}
%\usefonttheme{structurebold}

%\usetheme{Copenhagen}
\usetheme{Singapore}
%\usetheme{boxes}
%\usetheme{default}
\usecolortheme{seahorse}
\usefonttheme[onlysmall]{structurebold} 

\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
\usepackage{graphics}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}

\newcommand {\R}{\mathbb{R}}
\newtheorem{teo}{Teorema}
\newtheorem{defi}{Defini\c{c}\~{a}o}
\newtheorem{prop}{Proposi\c{c}\~{a}o}
\newtheorem{obs}{Observa\c{c}\~{a}o}
\newtheorem{coro}{Corolário}

\AtBeginSection[]{\frame{\frametitle{Estrutura}\tableofcontents[current]}}
%\input{include}
%\input{tcilatex}
%\newcommand{\R}{\mbox{{\rm{I\!\!\,R}}}}

\title[ ]{Expansões Assintóticas, Validação de Códigos e Estimativas de Erros }
\author[ ]{Alexandre Megiorin Roma}
\institute[ ]{Universidade de São Paulo\\
MAP / IME-USP}
\date[ ]{São Paulo, 17 de Outubro de 2008.}


%*********************************************

%slide 1
\begin{document}
%para criar a página de rosto
\begin{frame}
\titlepage 
\end{frame}%inclui a front page 
%**********************************************

%slide2
%\begin{frame}
%\frametitle{\normalsize{Estrutura}}
%\tableofcontents[pausesections,part=1]
%\tableofcontents
%\end{frame}
%*********************************************

%slide3
\begin{frame}
\frametitle{\normalsize{Oh-grande}}
$f(x)$=O($g(x)$), para $x\rightarrow +\infty$
se e somente se existirem
$x_0\in\mathbb{R}$ e uma constante positiva $M$ tais que
\[|f(x)|\le M|g(x)|\,,\quad \mbox{$x>x_0$}. \]

Similarmente, para uma vizinhança de um ponto $a$,
\[ f(x)=\mbox{O}(g(x))\,,\quad \mbox{para } x\rightarrow a\,,\]
se e somente se existirem constantes positivas $\delta$ e $M$ tais
que
\[ \mbox{$|x-a|<\delta$} \Rightarrow |f(x)|\le M|g(x)|. \]
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{\normalsize{Exemplo 1. Comportamento Assintótico.}}
Considere $f\in C^3(\mathbb{R})$ cuja série
truncada de Taylor em torno de $x_0$ é dada por
\[ f(x_0+h)=f(x_0) + h\,\frac{df(x_0)}{dx} +\frac{h^2}{2}\frac{d^2f(x_0)}{dx^2} +\frac{h^3}{6}\frac{d^3f(\xi)}{dx^3}\,,\]
para algum $\xi$ no intervalo formado por $x_0$ e $x_0+h$. Se $f$
tem derivadas limitadas numa vizinhança do ponto $x_0$ (isto é, se
existirem $C>0$ e $\delta>0$ tais que $|x-x_0|<\delta \Rightarrow
|d^kf(x_0)/dx^k|\le C$, para $k=1,2$ e 3), então
\[ |D_+f(x_0) - \frac{df(x_0)}{dx}| = |h|\,|\frac{d^2f(x_0)}{dx^2} +h\frac{d^3f(x_0)}{dx^3}| \le C|h|(1+\delta)\,,\]
onde $D_+f(x_0)\doteq[f(x_0+h)-f(x_0)]/h$. Da desigualdade
anterior e da definição de ``Oh-grande" pode-se escrever
\[ D_+f(x_0) - \frac{df(x_0)}{dx} =\mbox{O}(h)\,,\quad \mbox{para } x\rightarrow x_0.\]
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{\normalsize{Exemplo 2. Complexidade Computacional.}}
O número total de
operações aritméticas envolvidas no processo de resolução de um
sistema linear pelo Método de Eliminação de Gauss é
\[ T(n)=\frac{4n^3+9n^2-7n}{6}\,,\]
onde $n$ é a ordem da matriz. Vê-se que $T(n)=\mbox{O}(n^3)$ para
$n\rightarrow +\infty$, pois
\[ |T(n)=|\frac{4n^3+9n^2-7n}{6}|\le 4n^3+9n^2+7n\le 20n^3\,, \quad n>1.\]
A constante positiva $C$ vale, claro, 20.
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{\normalsize{Expansões Assintóticas}}
Uma soma finita
$\sum_{n=0}^N f_n(\epsilon)$ é uma representação assintótica de
$f(\epsilon)$ quando $\epsilon \rightarrow 0$ se e somente se,
para todo $M\le 'N$,
\[ \frac{f(\epsilon) - \sum_{n=0}^M f_n(\epsilon)}{f_M(\epsilon)}\rightarrow 0\,,\quad \mbox{para } \epsilon\rightarrow 0\,,\]
isto é, {\it o resto}\, é menor que a última parcela adicionada na
soma, para $\epsilon$ suficientemente pequeno. Se uma soma tem
esta propriedade assintótica, escreve-se
\[f(\epsilon)\sim \sum_{n=0}^N f_n(\epsilon)\,,\quad \mbox{para } \epsilon\rightarrow 0\,.\]

Freqüentemente, as parcelas $f_n(\epsilon) $ são dadas por
potências de $\epsilon $ multiplicadas por coeficientes
constantes, resultando num expansão (ou série) assintótica de potências
\[f(\epsilon)\sim \sum_{n=0}^N a_n\epsilon^n\,.\]
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{\normalsize{Exemplo 3.  Função Exponencial:
$f(\epsilon)=\exp(\epsilon)$. }}
Usando a expansão de Taylor da função exponencial,
$\exp(\epsilon)=\sum_{n=0}^{+\infty} \epsilon^n/n!$\,, vê-se que
\[ \frac{\exp(\epsilon) - \sum_{n=0}^{M} \epsilon^n/n!}{\epsilon^M}=\sum_{n=M+1}^{+\infty} \frac{\epsilon^{n-M}}{n!}\,\rightarrow 0\,,\quad \mbox{para }
\epsilon\rightarrow 0\,. \]

{\bf Conclusão:} {\it Toda série de potências convergente
fornece uma representação assintótica. Entretanto, como ver-se-á
em breve, nem toda a representação assintótica fornece uma série
convergente!}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{\normalsize{Exemplo 4. Exemplo Surpreendente.}}
\[ f(z)=\frac{2}{\sqrt{\pi}}\int_0^z \exp(-t^2)\,dt=
\]

\[=\frac{2}{\sqrt{\pi}}\int_0^z
\sum_{n=^0}^{+\infty}\frac{-t^{2n}}{n!}\,dt = \] 
\[=\sum_{n=^0}^{+\infty}\frac{(-1)^nz^{2n+1}}{(2n+1)n!}=
\frac{2}{\sqrt{\pi}}\Big(z-\frac{z^3}{3} +\frac{z^5}{10}
-\frac{z^7}{42}
% +\frac{z^9}{216} -\frac{z^{11}}{1320}
+\cdots \Big)\,.\] 

\end{frame}
\begin{frame}

A série de $f(z)$ converge para todo o valor de $z$. O  
número de termos necessários para aproximar $f(z)$ com precisão de $10^{-5}$: 
\begin{enumerate}
\item $z=1$, 08 termos.
\item $z=2$, 16 termos...
\item $z=3$, 31 termos!
\item $z=5$, 75 termos!!!
\end{enumerate}

Além do aumento progressivo e
rápido para valores $z$ mais elevados (aumento do custo
computacional), note que se está bastante vulnerável a erros
oriundos da aritmética de ponto flutuante pois se tem ordens de
grandeza bastante díspares vindas de termos da forma $z^n$.
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
%\frametitle{\normalsize{}}
A mesma função $f(z)$ também é dada por
\[f(z)=1 -\frac{2}{\sqrt{\pi}}\int_z^{+\infty} \exp(-t^2)\,dt.\]
Repetidas integrações por partes resultam em termos que formam uma soma finita
mais um termo integral remanescente. Por exemplo, após integrar
por partes 4 vezes obtém-se
\[f(z0=1-\frac{\exp ({-z^2})}{z\sqrt{\pi}}\Big(
1-\frac{1}{2z^2}+\frac{1\times 3}{(2z^2)^2}-\frac{1\times 3\times
5}{(2z^2)^3}+\mbox{O}(z^{-8})\Big)\,.
\]

É possível mostrar que, ao se continuar o processo de integração
por partes indefinidamente, a série obtida desta forma diverge
para qualquer valor de $z$ !!! 

\end{frame}
\begin{frame}

Ao contrário do que se
pode pensar, somas finitas obtidas a partir deste procedimento são
extremamente úteis. O
número de termos necessários para aproximar $f(z)$ com precisão de $10^{-5}$:
\begin{enumerate}
\item $z=2.5$, 03 termos!
\item $z\ge 3$, 02 termos!!!
\end{enumerate}

Para ``enquadrar" o exemplo anterior no contexto de
representação assintótica basta ``enxergar" o pequeno parâmetro
$\epsilon$ como sendo $z^{-1}$ (claro, para $z$ ``grande").
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%slide8
\begin{frame}
\frametitle{\normalsize{Conclusão.}}
{\it Séries assintóticas (infinitas) podem não convergir
mas, mesmo assim, representações assintóticas (baseadas em somas
parciais finitas destas séries) podem ser muito úteis!}
\end{frame}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%slide
\begin{frame}
\frametitle{\normalsize{Exemplo 5. Expansão assintótica do erro global em 
aproximação numérica da solução de equações diferenciais ordinárias.
}}
Problema de Cauchy: $y'(t)=f(t,y(t))$, \mbox{$y(t_0)=y_0$}. Se $\bar{y}(t)$ e $\eta(t,\Delta t)$ forem,
respectivamente, a solução exata e a aproximação numérica
fornecida por um esquema numérico de ordem $p$, sob ``certas
condições de regularidade" sobre a função $f(t,y)$, então é
possível mostrar que a expansão assintótica do erro
global~\cite{BS}
\[\eta(t,\Delta t)= \bar{y}(t) +\Delta t^pe_p(t)+\]\[+\Delta t^{p+1}e_{p+1}(t)+\cdots +\Delta t^{N}e_{N}(t)+\Delta t^{p+N}E_{N+1}(t,\Delta t)\,,\]
onde os coeficientes $e_k(t_0)=0$, $k=p,p+1,$ ..., vale para todo
$t\in[t_0,t_{\mbox{f}}]$ e todo $\Delta t=(t-t_0)/n$, $n=1,2,$ ...
Além disso, os coeficientes $e_k(t)$ não dependem de $\Delta t$ e
o resto $E_{N+1}(t,\Delta t)$ é limitado para cada $t$ fixado e
para todo $\Delta t=(t-t_0)/n$, $n=1,2,$ ...
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%slide
\begin{frame}
\frametitle{\normalsize{Validação de Códigos e Estimativas de Erros}}
 {\it validação com solução manufaturada}\,: 
escolha qualquer função $y_e(t)$ suficientemente regular e
considere o Problema de Cauchy
\[y'(t)=f(t,y)\doteq y'_e(t)\,,\]
com $y(t_0)=y_e(t_0)$.

\vspace{3mm}
Para um instante arbitrário fixado $\bar{t}$, em malhas de integração 
progressivamente mais finas $\Delta t_k=(\bar{t}-t_0)/2^k$, $k=1,2,...$, 
obtenha \[\eta_k(\bar{t})\doteq \eta(\bar{t},\Delta t_k).\] 

Para
passos de integração suficientemente pequenos, em primeira
aproximação, tem-se
\[\eta_k(\bar{t})-y_e(\bar{t})\approx\Delta t_k^pe_p(\bar{t})\,,\quad\mbox{$k$=1,2,...}\]
tomando-se por base a expansão assintótica do erro global de
discretização. 

\end{frame}
\begin{frame}
Como o coeficiente $e_p$ depende apenas de
$\bar{t}$ (e não de $\Delta t_k$), para dois índices consecutivos
$k=q$ e $k=q+1$, tem-se que a razão dos valores absolutos dos
erros é dada por
\[\frac{|\eta_q(\bar{t})- y_e(\bar{t})|}{|\eta_{q+1}(\bar{t})- y_e(\bar{t})|}\approx \frac{\Delta t_q^p}{\Delta t_{q+1}^p}\,\frac{|e_p(\bar{t})|}{|e_p(\bar{t})|}=2^p\,.\]

\end{frame}
\begin{frame}

Uma vez tendo sido validada a contento a implementação do esquema
numérico de interesse, é possível usar a mesma expansão
assintótica para estimar o erro global cometido quando o método é
empregado para resolver um problema de interesse. Veja, desta vez,
não se conhece (claro!) $\bar{y}(t)$ , a solução exata do problema
mas sabe-se que o método a ser empregado tem ordem $p$ e está
corretamente implementado. Uma vez mais, para $\Delta t_k$
``suficientemente pequeno", tem-se em primeira aproximação
\[\eta_k(t)-\bar{y}(t)\approx\Delta t_k^pe_p(t)\]
assim como
\[\eta_{k+1}(t)-\bar{y}(t)\approx\Delta t_{k+1}^pe_p(t)\,,\]
para cada $t$ fixado. Subtraindo-se uma da outra, das expressões
anteriores, chega-se a uma estimativa do coeficiente $e_p(t)$ dada
por
\[e_p(t)\approx\frac{\eta_{k+1}(t)-\eta_k(t)}{\Delta t^p_{k+1}-\Delta t^p_k}\,.\]

Com esta estimativa, é possível avaliar o erro global de
discretização cometido no instante $t$, o qual é dado por, por
exemplo,
\[\eta_{k+1}(t)-\bar{y}(t)\approx\Delta t_{k+1}^pe_p(t)\,.\]
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{\normalsize{Referências}}
\begin{thebibliography}{99} 
\bibitem{BS} J. Stoer and R. Bulirsch: {\it Introduction to Numerical Analysis}. Springer-Verlag New York Inc., 1989.
\bibitem{Hinch} E.J. Hinch: {\it Perturbation Methods}. Cambridge University Press, 1992.
\end{thebibliography}
\end{frame}
%************************************************************************

\end{document}


