Added Day1 Session6 - Finding Roots.

1 files changed, 302 insertions, 0 deletions

diff --git a/day1/session6.tex b/day1/session6.tex
new file mode 100644
index 0000000..adc24ff
--- /dev/null
+++ b/day1/session6.tex
@@ -0,0 +1,302 @@
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% Tutorial slides on Python.
+%
+% Author: Prabhu Ramachandran <prabhu at aero.iitb.ac.in>
+% Copyright (c) 2005-2009, Prabhu Ramachandran
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\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 wphich 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}