%\documentclass[11pt]{beamer}
%
%\usetheme{Darmstadt}
%
%\usepackage{times}
%\usefonttheme{structurebold}
%
%\usepackage[english]{babel}
%\usepackage{pgf,pgfarrows,pgfnodes,pgfautomata,pgfheaps}
%\usepackage{amsmath,amssymb}
%\usepackage[latin1]{inputenc}
%
%\setbeamercovered{dynamic}
%
%\usepackage{multimedia,hyperref}
%\usepackage{mpmulti}
%
%\usepackage{graphicx}
%\usepackage{amsfonts, amssymb, amsmath, amsthm, epsfig}
%%\usepackage{amsfonts, amssymb, amsmath, amsthm, psfrag, epsfig}
%\theoremstyle{definition}
%%\newtheorem{definition}{Definition}[section]
%%\newtheorem{lemma}{Lemma}%[section]
%%\newtheorem{corollary}{Corollary}%[section]
%%\newtheorem{proposition}[definition]{Proposition}
%%\newtheorem{theorem}{Theorem}%[section]
%\newtheorem{remark}{Remark}%[section]
%%\newtheorem{example}{Example}%[section]
%\newcommand{\sol}{{\em Solution: }}
%\def\qed{\hspace*{\fill} \rule{2.5mm}{2.5mm}}
%
%%\newcommand{\textrr}{\textcolor[rgb]{0.7,0.00,0.00}}
%%\newcommand{\textgg}{\textcolor[rgb]{0.00,0.7,0.00}}
%%\newcommand{\textbb}{\textcolor[rgb]{0.00,0.0,0.7}}
%\newcommand{\textrr}{\textcolor{red}}
%\newcommand{\textgg}{\textcolor{green}}
%\newcommand{\textbb}{\textcolor{blue}}
%
%\pgfdeclareimage[height=1.0cm]{university-logo}{nthu-logo}
%\logo{\pgfuseimage{university-logo}}
%
%\title{Solutions of Equations in One Variable}
%\author{Tsung-Min Hwang}
%\institute{\textgg{Department of Mathematics\\National Taiwan
%Normal University, Taiwan}}
%%\\E-mail: min@math.ntnu.edu.tw}}
%\date{July 10, 2005}

\documentclass[11pt]{beamer}
%\usetheme{Darmstadt}
 \mode<presentation>
{
  \setbeamertemplate{background canvas}[vertical shading][bottom=red!10,top=blue!10]
   \usetheme{Boadilla}
  %\usetheme{Warsaw}
  \usefonttheme[onlysmall]{structurebold}
}
\usepackage{multimedia,hyperref}
\usepackage{mpmulti}
%\usepackage{times}

\usepackage{graphicx}
\usepackage{amsfonts, amssymb, amsmath, amsthm, psfrag, epsfig}
\setbeamercovered{dynamic}

\newtheorem{Proposition}{Proposition}
\theoremstyle{definition}
%\newtheorem{definition}{Definition}[section]
%\newtheorem{lemma}{Lemma}%[section]
%\newtheorem{corollary}{Corollary}%[section]
%\newtheorem{proposition}[definition]{Proposition}
%\newtheorem{theorem}{Theorem}%[section]
%\newtheorem{remark}{Remark}%[section]
%\newtheorem{example}{Example}%[section]

%\newcommand{\textrr}{\textcolor[rgb]{0.7,0.00,0.00}}
%\newcommand{\textgg}{\textcolor[rgb]{0.00,0.7,0.00}}
%\newcommand{\textbb}{\textcolor[rgb]{0.00,0.0,0.7}}
\newcommand{\textrr}{\textcolor{red}}
\newcommand{\textgg}{\textcolor{green}}
\newcommand{\textbb}{\textcolor{blue}}
\pgfdeclareimage[height=1cm]{university-logo}{nthu-logo}
\logo{\pgfuseimage{university-logo}}

\title[Solutions of Equations in One Variable]
{
 {\color{blue}{\rm Numerical Analysis I}} \\
Solutions of Equations in One Variable \\ 
     Section 2.1: Bisection 
}
\author[Wei-Cheng Wang] {Instructor: Wei-Cheng Wang 
\footnote{\tiny These slides are based on Prof. Tsung-Ming Huang(NTNU)'s original slides}}
\institute[NTHU]{\textbb{Department of
Mathematics\\National TsingHua University}}
\date{Fall 2010}

\begin{document}

\frame{\titlepage}

\part{Main Part}
\frame{\frametitle{Outline}\tableofcontents[pausesections]}
%\frame{\frametitle{Outline}\tableofcontents[part=1]}

\section{Bisection Method}
%\subsection{Algorithm, theorem, example}
\begin{frame}
\frametitle{Bisection Method}
\begin{block}{Idea}
If {\textcolor{red}{$f(x) \in C[a,b]$}} and {\textcolor{red}{$f(a)
f(b) < 0$}}, then {\textcolor{red}{$\exists$ $c \in (a,b)$}} such
that {\textcolor{red}{$f(c) = 0$}}.
\end{block}

%\vspace{-1cm}
\begin{figure}
    \begin{center}
        \resizebox{8.5cm}{!}{\includegraphics{fig_bisection.jpg}}
        %\caption{64-bit double precision.}    \label{fig-bit64}
    \end{center}
\end{figure}

\end{frame}

\begin{frame}
\begin{alertblock}{Bisection method algorithm}
   Given $f(x)$ defined on $(a,b)$,
   the maximal number of iterations $M$,
   and stop criteria $\delta$ and $\varepsilon$, this algorithm
   tries to locate one root of $f(x)$.
%
\begin{center}
\begin{tabular}[c]{lllllll} %\hline
% & & & & & & \\
    \multicolumn{5}{l}{Compute $fa = f(a)$, $fb=f(b)$, and $e = b - a$}  & \\
    \multicolumn{5}{l}{{\bf If } $sign(fa) = sign(fb)$, {\bf then } stop  \, {\bf End If} } & \\
    \multicolumn{5}{l}{{\bf For} $k = 1, 2, \ldots, M$}  & \\
    & \multicolumn{4}{l}{$e = e/2$, $c = (a+b)/2$, $fc = f(c)$}  & \\
    & \multicolumn{4}{l}{{\bf If} ($|e| < \delta$ or $|fc| < \varepsilon$), 
                         {\bf then }  stop \, {\bf End If} }& \\
    & \multicolumn{4}{l}{{\bf If } $sign(fc) \neq sign(fa)$ }  & \\
    & & \multicolumn{3}{l}{$b = c$,  $fb = fc$}  & \\
    & \multicolumn{4}{l}{{\bf Else}}  & \\
    & & \multicolumn{3}{l}{$a = c$, $fa = fc$}  & \\
    & \multicolumn{4}{l}{{\bf End If} }  & \\
    \multicolumn{5}{l}{{\bf End For}}  & %\\ \hline
% & & & & & & \\
\end{tabular}

\end{center}
\end{alertblock}
\end{frame}

\begin{frame}

Let $\{ c_{n} \}$ be the sequence of numbers produced. The
algorithm should stop if one of the following conditions is
satisfied.
\begin{enumerate}
   \item  the iteration number $k > M$,
   \item  $|c_{k} - c_{k-1}| < \delta$, or
   \item  $|f(c_{k})| < \varepsilon$.
\end{enumerate}
%


%% \pause
 Let $[a_{0}, b_{0}], [a_{1},b_{1}], \ldots$ denote the
successive intervals produced by the bisection algorithm.
%% \pause 
Then
%
\begin{eqnarray*}
    && a = a_{0} \leq a_{1} \leq a_{2} \leq \cdots \leq b_{0} = b
        \\
    &\Rightarrow&\ \{ a_{n} \} \ \mbox{ and } \ \{ b_{n} \} \
        \mbox{ are bounded} \\
    &\Rightarrow&\ \lim_{n \rightarrow \infty} a_{n}\ \mbox{ and }
        \ \lim_{n \rightarrow \infty} b_{n}\ \mbox{ exist }
\end{eqnarray*}
%
%$\Rightarrow$ $\{ a_{n} \}$ and $\{ b_{n} \}$
%  are bounded. \\
%$\Rightarrow$ $\lim\limits_{n \rightarrow \infty} a_{n}$ and
%$\lim\limits_{n \rightarrow \infty} b_{n}$ exist.

\end{frame}

\begin{frame}
 Since
%
\begin{eqnarray*}
   b_{1} - a_{1} & = & \frac{1}{2} (b_{0} - a_{0})  \\
   b_{2} - a_{2} & = & \frac{1}{2} (b_{1} - a_{1})
                        = \frac{1}{4} (b_{0} - a_{0})  \\
             & \vdots &                           \\
   b_{n} - a_{n} & = & \frac{1}{2^{n}} (b_{0} - a_{0})
\end{eqnarray*}
%
%% \pause  
hence
\[
   \lim_{n \rightarrow \infty} b_{n} - \lim_{n \rightarrow \infty} a_{n}
    =
   \lim_{n \rightarrow \infty} (b_{n} - a_{n})
    =
   \lim_{n \rightarrow \infty} \frac{1}{2^{n}} (b_{0} - a_{0}) = 0.
\]
%
%% \pause 
Therefore
\[
   \lim_{n \rightarrow \infty} a_{n}
   = \lim_{n \rightarrow \infty} b_{n}
   \equiv z.
\]

%% \pause 
Since $f$ is a continuous function, we have that
\[
    \lim_{n \rightarrow \infty} f(a_{n})
    = f(\lim_{n \rightarrow \infty} a_{n}) = f(z)
    \quad
    \text{and}
    \quad
    \lim_{n \rightarrow \infty} f(b_{n})
    = f(\lim_{n \rightarrow \infty} b_{n}) = f(z).
\]
%
\end{frame}
%
\begin{frame}
On the other hand,
\begin{eqnarray*}
    && f(a_{n}) f(b_{n}) < 0 \\
    &\Rightarrow&  \lim_{n \rightarrow \infty} f(a_{n})
        f(b_{n}) = f^{2}(z) \leq 0 \\
    &\Rightarrow& f(z) = 0
\end{eqnarray*}
%% \pause 
Therefore, the limit of the sequences $\{ a_{n} \}$ and $\{
b_{n} \}$ is a zero of $f$ in $[a,b]$. 
%%  \pause 
Let $c_{n} = \frac{1}{2}(a_{n} + b_{n})$.
%%  \pause 
Then
\begin{eqnarray*}
   |z - c_{n}|
   &=& \big|\lim_{n \rightarrow \infty} a_{n} - \frac{1}{2}(a_{n} + b_{n})
       \big| \\
   &=& \big| \frac{1}{2}\left[ \lim_{n \rightarrow \infty} a_{n} - b_n
      \right] + \frac{1}{2}\left[ \lim_{n \rightarrow \infty}
      a_{n} - a_n \right] \big| \\
   &\leq&  \max \big\{ \big| \lim_{n \rightarrow \infty} a_{n} - b_n
      \big|, \big| \lim_{n \rightarrow \infty} a_{n} - a_n \big|
      \big\} \\
   &\leq&
    |b_{n} - a_{n}|
   = \frac{1}{2^{n}} |b_{0} - a_{0}|.
\end{eqnarray*}
%
This proves the following theorem.
\end{frame}

\begin{frame}
\begin{theorem}
  Let {\textcolor{red}{$\{ [a_{n}, b_{n}] \}$}} denote the intervals
  produced by the bisection algorithm. Then
  {\textcolor{red}{$\lim\limits_{n \rightarrow \infty} a_{n}$}}
  and {\textcolor{red}{$\lim\limits_{n \rightarrow \infty} b_{n}$}} {\textcolor{blue}{exist}},
  are {\textcolor{blue}{equal}},
  and represent a {\textcolor{blue}{zero}} of {\textcolor{red}{$f(x)$}}. If
  \begin{eqnarray*}
  {\color{red} z = \lim\limits_{n \rightarrow \infty} a_{n}
    = \lim\limits_{n \rightarrow \infty} b_{n}} \quad \mbox{ and }
    \quad
  {\color{red} c_{n} = \frac{1}{2}(a_{n} + b_{n})},
  \end{eqnarray*}
   then
  \[
      {\color{red} | z - c_{n} | \leq \frac{1}{2^{n}} \left( b_{0} - a_{0}
      \right).}
  \]
\end{theorem}

%% \pause
\begin{alertblock}{Remark}
    {\textcolor{red}{$\{ c_{n} \}$}} {\textcolor{blue}{converges}}
   to {\textcolor{red}{$z$}} with the {\textcolor{blue}{rate}} of {\textcolor{red}{$O(2^{-n})$}}.
\end{alertblock}
\end{frame}

\begin{frame}
\begin{example}
   How many
   steps should be taken to compute a root of $f(x) = x^3 + 4 x^2 -10=0$
   on $[1,2]$ with relative error $10^{-3}$?
\end{example}
%

%% \pause
{\em solution:} Seek an $n$ such that
\[
     \frac{|z - c_{n}|}{|z|} \leq 10^{-3} \ \Rightarrow \ |z - c_{n}|
     \leq |z| \times 10^{-3}.
\]
Since $z \in [1,2]$, it is sufficient to show
\[
    |z - c_{n}| \leq  10^{-3}.
\]
That is, we solve
\[
     2^{-n} (2 - 1) \leq   10^{-3} \ \Rightarrow \ -n \log_{10}2
     \leq -3
\]
which gives $n \geq 10$. \qed
\end{frame}

\end{document}