1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

     2 % Tutorial slides on Python.

     3 %

     4 % Author: Prabhu Ramachandran <prabhu at aero.iitb.ac.in>

     5 % Copyright (c) 2005-2009, Prabhu Ramachandran

     6 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

     7 

     8 \documentclass[14pt,compress]{beamer}

     9 %\documentclass[draft]{beamer}

    10 %\documentclass[compress,handout]{beamer}

    11 %\usepackage{pgfpages} 

    12 %\pgfpagesuselayout{2 on 1}[a4paper,border shrink=5mm]

    13 

    14 % Modified from: generic-ornate-15min-45min.de.tex

    15 \mode<presentation>

    16 {

    17   \usetheme{Warsaw}

    18   \useoutertheme{split}

    19   \setbeamercovered{transparent}

    20 }

    21 

    22 \usepackage[english]{babel}

    23 \usepackage[latin1]{inputenc}

    24 %\usepackage{times}

    25 \usepackage[T1]{fontenc}

    26 

    27 % Taken from Fernando's slides.

    28 \usepackage{ae,aecompl}

    29 \usepackage{mathpazo,courier,euler}

    30 \usepackage[scaled=.95]{helvet}

    31 \usepackage{amsmath}

    32 

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

    34 

    35 \usepackage{listings}

    36 \lstset{language=Python,

    37     basicstyle=\ttfamily\bfseries,

    38     commentstyle=\color{red}\itshape,

    39   stringstyle=\color{darkgreen},

    40   showstringspaces=false,

    41   keywordstyle=\color{blue}\bfseries}

    42 

    43 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    44 % Macros

    45 \setbeamercolor{emphbar}{bg=blue!20, fg=black}

    46 \newcommand{\emphbar}[1]

    47 {\begin{beamercolorbox}[rounded=true]{emphbar} 

    48       {#1}

    49  \end{beamercolorbox}

    50 }

    51 \newcounter{time}

    52 \setcounter{time}{0}

    53 \newcommand{\inctime}[1]{\addtocounter{time}{#1}{\tiny \thetime\ m}}

    54 

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

    56 

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

    58 

    59 %%% This is from Fernando's setup.

    60 % \usepackage{color}

    61 % \definecolor{orange}{cmyk}{0,0.4,0.8,0.2}

    62 % % Use and configure listings package for nicely formatted code

    63 % \usepackage{listings}

    64 % \lstset{

    65 %    language=Python,

    66 %    basicstyle=\small\ttfamily,

    67 %    commentstyle=\ttfamily\color{blue},

    68 %    stringstyle=\ttfamily\color{orange},

    69 %    showstringspaces=false,

    70 %    breaklines=true,

    71 %    postbreak = \space\dots

    72 % }

    73 

    74 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    75 % Title page

    76 \title[]{Finding Roots}

    77 

    78 \author[FOSSEE] {FOSSEE}

    79 

    80 \institute[IIT Bombay] {Department of Aerospace Engineering\\IIT Bombay}

    81 \date[] {31, October 2009\\Day 1, Session 6}

    82 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    83 

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

    85 %\logo{\pgfuseimage{iitmlogo}}

    86 

    87 

    88 %% Delete this, if you do not want the table of contents to pop up at

    89 %% the beginning of each subsection:

    90 \AtBeginSubsection[]

    91 {

    92   \begin{frame}<beamer>

    93     \frametitle{Outline}

    94     \tableofcontents[currentsection,currentsubsection]

    95   \end{frame}

    96 }

    97 

    98 \AtBeginSection[]

    99 {

   100   \begin{frame}<beamer>

   101     \frametitle{Outline}

   102     \tableofcontents[currentsection,currentsubsection]

   103   \end{frame}

   104 }

   105 

   106 % If you wish to uncover everything in a step-wise fashion, uncomment

   107 % the following command: 

   108 %\beamerdefaultoverlayspecification{<+->}

   109 

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

   111 

   112 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   113 % DOCUMENT STARTS

   114 \begin{document}

   115 

   116 \begin{frame}

   117   \maketitle

   118 \end{frame}

   119 

   120 %% \begin{frame}

   121 %%   \frametitle{Outline}

   122 %%   \tableofcontents

   123 %%   % You might wish to add the option [pausesections]

   124 %% \end{frame}

   125 

   126 

   127 \begin{frame}[fragile]

   128 \frametitle{Roots of $f(x)=0$}

   129 \begin{itemize}

   130 \item Roots --- values of $x$ satisfying $f(x)=0$

   131 \item $f(x)=0$ may have real or complex roots

   132 \item Presently, let's look at real roots

   133 \end{itemize}

   134 \end{frame}

   135 

   136 \begin{frame}[fragile]

   137 \frametitle{Initial Estimates}

   138 \begin{itemize}

   139 \item Find the roots of $cosx-x^2$ between $-\pi/2$ and $\pi/2$

   140 \item We shall use a crude method to get an initial estimate first

   141 \end{itemize}

   142 \begin{enumerate}

   143 \item Check for change of signs of $f(x)$ in the given interval

   144 \item A root lies in the interval where the sign change occurs

   145 \end{enumerate}

   146 \end{frame}

   147 

   148 \begin{frame}[fragile]

   149 \frametitle{Initial Estimates \ldots}

   150 \begin{lstlisting}

   151   In []: def our_f(x):

   152    ....:     return cos(x)-x**2

   153    ....: 

   154   In []: x = linspace(-pi/2, pi/2, 11)

   155 \end{lstlisting}

   156 \begin{itemize}

   157 \item Get the intervals of x, where sign changes occur

   158 \end{itemize}

   159 \end{frame}

   160 

   161 %% \begin{frame}[fragile]

   162 %% \frametitle{Initial Estimates \ldots}

   163 %% \begin{lstlisting}

   164 %% In []: pos = y[:-1]*y[1:] < 0

   165 %% In []: rpos = zeros(x.shape, dtype=bool)

   166 %% In []: rpos[:-1] = pos

   167 %% In []: rpos[1:] += pos

   168 %% In []: rts = x[rpos]

   169 %% \end{lstlisting}

   170 %% \end{frame}

   171 

   172 \begin{frame}[fragile]

   173 \frametitle{Fixed Point Method}

   174 \begin{enumerate}

   175 \item Convert $f(x)=0$ to the form $x=g(x)$

   176 \item Start with an initial value of $x$ and iterate successively

   177 \item $x_{n+1}=g(x_n)$ and $x_0$ is our initial guess

   178 \item Iterate until $x_{n+1}-x_n \le tolerance$

   179 \end{enumerate}

   180 \end{frame}

   181 

   182 %% \begin{frame}[fragile]

   183 %% \frametitle{Fixed Point \dots}

   184 %% \begin{lstlisting}

   185 %% In []: def our_g(x):

   186 %%  ....:     return sqrt(cos(x))

   187 %%  ....: 

   188 %% In []: tolerance = 1e-5

   189 %% In []: while abs(x1-x0)>tolerance:

   190 %%  ....:     x0 = x1

   191 %%  ....:     x1 = our_g(x1)

   192 %%  ....:   

   193 %% In []: x0

   194 %% \end{lstlisting}

   195 %% \end{frame}

   196 

   197 \begin{frame}[fragile]

   198 \frametitle{Bisection Method}

   199 \begin{enumerate}

   200 \item Start with an interval $(a, b)$ within wphich a root exists

   201 \item $f(a)\cdot f(b) < 0$

   202 \item Bisect the interval. $c = \frac{a+b}{2}$

   203 \item Change the interval to $(a, c)$ if $f(a)\cdot f(c) < 0$

   204 \item Else, change the interval to $(c, b)$

   205 \item Go back to 3 until $(b-a) \le$ tolerance

   206 \end{enumerate}

   207 \end{frame}

   208 

   209 %% \begin{frame}[fragile]

   210 %% \frametitle{Bisection \dots}

   211 %% \begin{lstlisting}

   212 %% In []: tolerance = 1e-5

   213 %% In []: a = -pi/2

   214 %% In []: b = 0

   215 %% In []: while b-a > tolerance:

   216 %%  ....:     c = (a+b)/2

   217 %%  ....:     if our_f(a)*our_f(c) < 0:

   218 %%  ....:         b = c

   219 %%  ....:     else:

   220 %%  ....:         a = c

   221 %%  ....:         

   222 %% \end{lstlisting}

   223 %% \end{frame}

   224 

   225 \begin{frame}[fragile]

   226 \frametitle{Newton Raphson Method}

   227 \begin{enumerate}

   228 \item Start with an initial guess of x for the root

   229 \item $\Delta x = -f(x)/f^{'}(x)$

   230 \item $ x \leftarrow x + \Delta x$

   231 \item Go back to 2 until $|\Delta x| \le$ tolerance

   232 \end{enumerate}

   233 \end{frame}

   234 

   235 %% \begin{frame}[fragile]

   236 %% \frametitle{Newton Raphson \dots}

   237 %% \begin{lstlisting}

   238 %% In []: def our_df(x):

   239 %%  ....:     return -sin(x)-2*x

   240 %%  ....: 

   241 %% In []: delx = 10*tolerance

   242 %% In []: while delx > tolerance:

   243 %%  ....:     delx = -our_f(x)/our_df(x)

   244 %%  ....:     x = x + delx

   245 %%  ....:     

   246 %%  ....:     

   247 %% \end{lstlisting}

   248 %% \end{frame}

   249 

   250 \begin{frame}[fragile]

   251 \frametitle{Newton Raphson \ldots}

   252 \begin{itemize}

   253 \item What if $f^{'}(x) = 0$?

   254 \item Can you write a better version of the Newton Raphson?

   255 \item What if the differential is not easy to calculate?

   256 \item Look at Secant Method

   257 \end{itemize}

   258 \end{frame}

   259 

   260 \begin{frame}[fragile]

   261 \frametitle{Scipy Methods - \typ{roots}}

   262 \begin{itemize}

   263 \item Calculates the roots of polynomials

   264 \item Array of coefficients is the only parameter

   265 \end{itemize}

   266 \begin{lstlisting}

   267   In []: coeffs = [1, 6, 13]

   268   In []: roots(coeffs)

   269 \end{lstlisting}

   270 \end{frame}

   271 

   272 \begin{frame}[fragile]

   273 \frametitle{Scipy Methods - \typ{fsolve}}

   274 \begin{small}

   275 \begin{lstlisting}

   276   In []: from scipy.optimize import fsolve

   277 \end{lstlisting}

   278 \end{small}

   279 \begin{itemize}

   280 \item Finds the roots of a system of non-linear equations

   281 \item Input arguments - Function and initial estimate

   282 \item Returns the solution

   283 \end{itemize}

   284 \begin{lstlisting}

   285   In []: fsolve(our_f, -pi/2)

   286 \end{lstlisting}

   287 \end{frame}

   288 

   289 \begin{frame}[fragile]

   290 \frametitle{Scipy Methods \dots}

   291 \small{

   292 \begin{lstlisting}

   293 In []: from scipy.optimize import fixed_point

   294 

   295 In []: from scipy.optimize import bisect

   296 

   297 In []: from scipy.optimize import newton

   298 \end{lstlisting}}

   299 \end{frame}

   300 

   301 

   302 \end{document}