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

   188 \begin{itemize}

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

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

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

   192 \end{itemize}

   193 \end{frame}

   194 

   195 \begin{frame}[fragile]

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

   197 \begin{itemize}

   198 \item Given function $cosx-x^2$ 

   199 \item First we find \alert{a} root in $(-\pi/2, \pi/2)$

   200 \item Then we find \alert{all} roots in $(-\pi/2, \pi/2)$

   201 \end{itemize}

   202 \end{frame}

   203 

   204 %% \begin{frame}[fragile]

   205 %% \frametitle{Fixed Point Method}

   206 %% \begin{enumerate}

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

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

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

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

   211 %% \end{enumerate}

   212 %% \end{frame}

   213 

   214 %% \begin{frame}[fragile]

   215 %% \frametitle{Fixed Point \dots}

   216 %% \begin{lstlisting}

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

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

   219 %%  ....: 

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

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

   222 %%  ....:     x0 = x1

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

   224 %%  ....:   

   225 %% In []: x0

   226 %% \end{lstlisting}

   227 %% \end{frame}

   228 

   229 %% \begin{frame}[fragile]

   230 %% \frametitle{Bisection Method}

   231 %% \begin{enumerate}

   232 %% \item Start with the given interval $(-\pi/2, \pi/2)$ ($(a, b)$)

   233 %% \item $f(a)\cdot f(b) < 0$

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

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

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

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

   238 %% \end{enumerate}

   239 %% \alert{\typ{tolerance = 1e-5}}

   240 %% \end{frame}

   241 

   242 %% \begin{frame}[fragile]

   243 %% \frametitle{Bisection \dots}

   244 %% \begin{lstlisting}

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

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

   247 %% In []: b = 0

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

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

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

   251 %%  ....:         b = c

   252 %%  ....:     else:

   253 %%  ....:         a = c

   254 %%  ....:         

   255 %% \end{lstlisting}

   256 %% \end{frame}

   257 

   258 %% \begin{frame}[fragile]

   259 %% \frametitle{Newton-Raphson Method}

   260 %% \begin{enumerate}

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

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

   263 %% \item $ x \leftarrow x + \Delta x$

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

   265 %% \end{enumerate}

   266 %% \end{frame}

   267 

   268 %% \begin{frame}[fragile]

   269 %% \frametitle{Newton-Raphson \dots}

   270 %% \begin{lstlisting}

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

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

   273 %%  ....: 

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

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

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

   277 %%  ....:     x = x + delx

   278 %%  ....:     

   279 %%  ....:     

   280 %% \end{lstlisting}

   281 %% \end{frame}

   282 

   283 %% \begin{frame}[fragile]

   284 %% \frametitle{Newton-Raphson \ldots}

   285 %% \begin{itemize}

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

   287 %% \item Can you write a better version of the Newton-Raphson?

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

   289 %% \item Look at Secant Method

   290 %% \end{itemize}

   291 %% \end{frame}

   292 

   293 %% \begin{frame}[fragile]

   294 %% \frametitle{Initial Estimates}

   295 %% \begin{itemize}

   296 %% \item Given an interval

   297 %% \item How to find \alert{all} the roots?

   298 %% \end{itemize}

   299 %% \begin{enumerate}

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

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

   302 %% \end{enumerate}

   303 %% \end{frame}

   304 

   305 %% \begin{frame}[fragile]

   306 %% \frametitle{Initial Estimates \ldots}

   307 %% \begin{lstlisting}

   308 %% In []: def our_f(x):

   309 %%  ....:     return cos(x) - x*x

   310 %%  ....: 

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

   312 %% In []: y = our_f(x)

   313 %% \end{lstlisting}

   314 %% Get the intervals of x, where sign changes occur

   315 %% \end{frame}

   316 

   317 %% \begin{frame}[fragile]

   318 %% \frametitle{Initial Estimates \ldots}

   319 %% \begin{lstlisting}

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

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

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

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

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

   325 %% \end{lstlisting}

   326 %% Now use Newton-Raphson?

   327 %% \end{frame}

   328 

   329 

   330 \begin{frame}[fragile]