%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Tutorial slides on Python.
%
% Author: FOSSEE
% Copyright (c) 2009, FOSSEE, IIT Bombay
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass[14pt,compress]{beamer}
%\documentclass[draft]{beamer}
%\documentclass[compress,handout]{beamer}
%\usepackage{pgfpages} 
%\pgfpagesuselayout{2 on 1}[a4paper,border shrink=5mm]

% Modified from: generic-ornate-15min-45min.de.tex
\mode<presentation>
{
  \usetheme{Warsaw}
  \useoutertheme{split}
  \setbeamercovered{transparent}
}

\usepackage[english]{babel}
\usepackage[latin1]{inputenc}
%\usepackage{times}
\usepackage[T1]{fontenc}

% Taken from Fernando's slides.
\usepackage{ae,aecompl}
\usepackage{mathpazo,courier,euler}
\usepackage[scaled=.95]{helvet}
\usepackage{amsmath}

\definecolor{darkgreen}{rgb}{0,0.5,0}

\usepackage{listings}
\lstset{language=Python,
    basicstyle=\ttfamily\bfseries,
    commentstyle=\color{red}\itshape,
  stringstyle=\color{darkgreen},
  showstringspaces=false,
  keywordstyle=\color{blue}\bfseries}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Macros
\setbeamercolor{emphbar}{bg=blue!20, fg=black}
\newcommand{\emphbar}[1]
{\begin{beamercolorbox}[rounded=true]{emphbar} 
      {#1}
 \end{beamercolorbox}
}
\newcounter{time}
\setcounter{time}{0}
\newcommand{\inctime}[1]{\addtocounter{time}{#1}{\tiny \thetime\ m}}

\newcommand{\typ}[1]{\lstinline{#1}}

\newcommand{\kwrd}[1]{ \texttt{\textbf{\color{blue}{#1}}}  }

%%% This is from Fernando's setup.
% \usepackage{color}
% \definecolor{orange}{cmyk}{0,0.4,0.8,0.2}
% % Use and configure listings package for nicely formatted code
% \usepackage{listings}
% \lstset{
%    language=Python,
%    basicstyle=\small\ttfamily,
%    commentstyle=\ttfamily\color{blue},
%    stringstyle=\ttfamily\color{orange},
%    showstringspaces=false,
%    breaklines=true,
%    postbreak = \space\dots
% }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Title page
\title[]{Finding Roots}

\author[FOSSEE] {FOSSEE}

\institute[IIT Bombay] {Department of Aerospace Engineering\\IIT Bombay}
\date[] {31, October 2009\\Day 1, Session 6}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\pgfdeclareimage[height=0.75cm]{iitmlogo}{iitmlogo}
%\logo{\pgfuseimage{iitmlogo}}


%% Delete this, if you do not want the table of contents to pop up at
%% the beginning of each subsection:
\AtBeginSubsection[]
{
  \begin{frame}<beamer>
    \frametitle{Outline}
    \tableofcontents[currentsection,currentsubsection]
  \end{frame}
}

\AtBeginSection[]
{
  \begin{frame}<beamer>
    \frametitle{Outline}
    \tableofcontents[currentsection,currentsubsection]
  \end{frame}
}

% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command: 
%\beamerdefaultoverlayspecification{<+->}

%\includeonlyframes{current,current1,current2,current3,current4,current5,current6}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% DOCUMENT STARTS
\begin{document}

\begin{frame}
  \maketitle
\end{frame}

%% \begin{frame}
%%   \frametitle{Outline}
%%   \tableofcontents
%%   % You might wish to add the option [pausesections]
%% \end{frame}


\begin{frame}[fragile]
\frametitle{Roots of $f(x)=0$}
\begin{itemize}
\item Roots --- values of $x$ satisfying $f(x)=0$
\item $f(x)=0$ may have real or complex roots
\item Presently, let's look at real roots
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Initial Estimates}
\begin{itemize}
\item Find the roots of $cosx-x^2$ between $-\pi/2$ and $\pi/2$
\item We shall use a crude method to get an initial estimate first
\end{itemize}
\begin{enumerate}
\item Check for change of signs of $f(x)$ in the given interval
\item A root lies in the interval where the sign change occurs
\end{enumerate}
\end{frame}

\begin{frame}[fragile]
\frametitle{Initial Estimates \ldots}
\begin{lstlisting}
  In []: def our_f(x):
   ....:     return cos(x)-x**2
   ....: 
  In []: x = linspace(-pi/2, pi/2, 11)
\end{lstlisting}
\begin{itemize}
\item Get the intervals of x, where sign changes occur
\end{itemize}
\end{frame}

%% \begin{frame}[fragile]
%% \frametitle{Initial Estimates \ldots}
%% \begin{lstlisting}
%% In []: pos = y[:-1]*y[1:] < 0
%% In []: rpos = zeros(x.shape, dtype=bool)
%% In []: rpos[:-1] = pos
%% In []: rpos[1:] += pos
%% In []: rts = x[rpos]
%% \end{lstlisting}
%% \end{frame}

\begin{frame}[fragile]
\frametitle{Fixed Point Method}
\begin{enumerate}
\item Convert $f(x)=0$ to the form $x=g(x)$
\item Start with an initial value of $x$ and iterate successively
\item $x_{n+1}=g(x_n)$ and $x_0$ is our initial guess
\item Iterate until $x_{n+1}-x_n \le tolerance$
\end{enumerate}
\end{frame}

%% \begin{frame}[fragile]
%% \frametitle{Fixed Point \dots}
%% \begin{lstlisting}
%% In []: def our_g(x):
%%  ....:     return sqrt(cos(x))
%%  ....: 
%% In []: tolerance = 1e-5
%% In []: while abs(x1-x0)>tolerance:
%%  ....:     x0 = x1
%%  ....:     x1 = our_g(x1)
%%  ....:   
%% In []: x0
%% \end{lstlisting}
%% \end{frame}

\begin{frame}[fragile]
\frametitle{Bisection Method}
\begin{enumerate}
\item Start with an interval $(a, b)$ within which a root exists
\item $f(a)\cdot f(b) < 0$
\item Bisect the interval. $c = \frac{a+b}{2}$
\item Change the interval to $(a, c)$ if $f(a)\cdot f(c) < 0$
\item Else, change the interval to $(c, b)$
\item Go back to 3 until $(b-a) \le$ tolerance
\end{enumerate}
\end{frame}

%% \begin{frame}[fragile]
%% \frametitle{Bisection \dots}
%% \begin{lstlisting}
%% In []: tolerance = 1e-5
%% In []: a = -pi/2
%% In []: b = 0
%% In []: while b-a > tolerance:
%%  ....:     c = (a+b)/2
%%  ....:     if our_f(a)*our_f(c) < 0:
%%  ....:         b = c
%%  ....:     else:
%%  ....:         a = c
%%  ....:         
%% \end{lstlisting}
%% \end{frame}

\begin{frame}[fragile]
\frametitle{Newton Raphson Method}
\begin{enumerate}
\item Start with an initial guess of x for the root
\item $\Delta x = -f(x)/f^{'}(x)$
\item $ x \leftarrow x + \Delta x$
\item Go back to 2 until $|\Delta x| \le$ tolerance
\end{enumerate}
\end{frame}

%% \begin{frame}[fragile]
%% \frametitle{Newton Raphson \dots}
%% \begin{lstlisting}
%% In []: def our_df(x):
%%  ....:     return -sin(x)-2*x
%%  ....: 
%% In []: delx = 10*tolerance
%% In []: while delx > tolerance:
%%  ....:     delx = -our_f(x)/our_df(x)
%%  ....:     x = x + delx
%%  ....:     
%%  ....:     
%% \end{lstlisting}
%% \end{frame}

\begin{frame}[fragile]
\frametitle{Newton Raphson \ldots}
\begin{itemize}
\item What if $f^{'}(x) = 0$?
\item Can you write a better version of the Newton Raphson?
\item What if the differential is not easy to calculate?
\item Look at Secant Method
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Scipy Methods - \typ{roots}}
\begin{itemize}
\item Calculates the roots of polynomials
\item Array of coefficients is the only parameter
\end{itemize}
\begin{lstlisting}
  In []: coeffs = [1, 6, 13]
  In []: roots(coeffs)
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]
\frametitle{Scipy Methods - \typ{fsolve}}
\begin{small}
\begin{lstlisting}
  In []: from scipy.optimize import fsolve
\end{lstlisting}
\end{small}
\begin{itemize}
\item Finds the roots of a system of non-linear equations
\item Input arguments - Function and initial estimate
\item Returns the solution
\end{itemize}
\begin{lstlisting}
  In []: fsolve(our_f, -pi/2)
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]
\frametitle{Scipy Methods \dots}
\small{
\begin{lstlisting}
In []: from scipy.optimize import fixed_point

In []: from scipy.optimize import bisect

In []: from scipy.optimize import newton
\end{lstlisting}}
\end{frame}


\end{document}