%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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