%\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
}
\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{-1.5cm}
\begin{figure}
    \begin{center}
        \resizebox{11.5cm}{!}{\includegraphics{fig_Bisection.pdf}}
        %\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}

\section{Fixed-Point Iteration}
%\subsection{Definition, algorithm, theorem, example}
\begin{frame}
    \frametitle{Fixed-Point Iteration}
    \begin{definition}
        {\textcolor{red}{$x$}} is called a {\textcolor{blue}{fixed point}} of a given
        function {\textcolor{red}{$f$}}
        if {\textcolor{red}{$f(x) = x$}}.
    \end{definition}


\pause
    \begin{alertblock}{Root-finding problems and fixed-point
        problems}
        \begin{itemize}
            \item Find $x^{*}$ such that $f(x^{*}) = 0$. \\
                  \indent Let $g(x) = x - f(x)$. Then
                          $g(x^{*}) = x^{*} - f(x^{*}) = x^{*}$. \\
                  \indent  $\Rightarrow$ $x^{*}$ is a
                          fixed point for $g(x)$.
                          
            \pause
            \item Find  $x^{*}$ such that $g(x^{*}) = x^{*}$.\\
                  \indent Define $f(x) = x - g(x)$ so that
                          $f(x^{*}) = x^{*} - g(x^{*}) = x^{*} - x^{*} = 0$\\
                  \indent $\Rightarrow$  $x^{*}$
                          is a zero of $f(x)$.
\end{itemize}
\end{alertblock}
\end{frame}

\begin{frame}
\begin{example}
    The function $g(x) = x^2 - 2$, for $-2 \leq x \leq 3$, has
    fixed points at $x=-1$ and $x = 2$ since
    \begin{eqnarray*}
        g(-1) = (-1)^2 -2 = -1 \ \mbox{ and } \ g(2) = 2^2 - 2 =
        2.
    \end{eqnarray*}
\end{example}

\vspace{-1.3cm}
\begin{figure}
    \begin{center}
        \resizebox{10.0cm}{!}{\includegraphics{ex1_fix_pt.pdf}}
        %\caption{64-bit double precision.}    \label{fig-bit64}
    \end{center}
\end{figure}

\end{frame}

\begin{frame}
\begin{theorem}[Existence and uniqueness] \label{fixed_point:thm.1}
   \begin{enumerate}
       \item If $g \in C[a,b]$ such that {\textcolor{red}{$a \leq g(x) \leq
             b$}}
             for all $x \in [a,b]$, then $g$ {\textcolor{blue}{has}} a fixed point in
             $[a,b]$.
             
       \pause
       \item If, in addition, $g'(x)$ exists
             in $(a,b)$ and there exists a positive constant
             {\textcolor{red}{$M < 1$}} such that {\textcolor{red}{$|g'(x)| \leq M < 1$}}
             for all
             $x \in (a,b)$. Then the fixed point is {\textcolor{blue}{unique}}.
   \end{enumerate}
\end{theorem}
\vspace{-1.2cm}
\begin{figure}
    \begin{center}
        \resizebox{8.5cm}{!}{\includegraphics{thm_fix_pt.pdf}}
        %\caption{64-bit double precision.}    \label{fig-bit64}
    \end{center}
\end{figure}

\end{frame}

\begin{frame}
\frametitle{Proof}

{\em Existence:}
\begin{itemize}
    \item If $g(a) = a$ or $g(b) = b$, then $a$ or $b$ is a fixed point of
          $g$ and we are done.
          
    \pause
    \item Otherwise, it must be $g(a) > a$ and $g(b)< b$. 
          \pause The
          function $h(x) = g(x) - x$ is continuous on $[a,b]$,
          with
          \begin{eqnarray*}
              h(a) = g(a) - a > 0 \ \mbox{ and } \ h(b) = g(b) - b < 0.
          \end{eqnarray*}
          \pause By the Intermediate Value Theorem,  $\exists$ $x^{*} \in
          [a,b]$ such that $h(x^{*}) = 0$. \pause That is
          \begin{eqnarray*}
              g(x^{*}) - x^{*} = 0 \ \Rightarrow \ g(x^{*}) = x^{*}.
          \end{eqnarray*}
          Hence  $g$ has
          a fixed point $x^{*}$ in $[a,b]$.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Proof}
 {\em Uniqueness:}

 Suppose that $p \neq q $ are both fixed points of $g$ in
$[a,b]$. 
\pause By the Mean-Value theorem, there exists $\xi$ between $p$
and $q$ such that
%
\[
   g'(\xi) = \frac{g(p) - g(q)}{p - q}
   = \frac{p-q}{p-q} = 1.
\]
%
\pause However, this contradicts to the assumption that $|g'(x)| \leq M <
1$ for all $x$ in $[a,b]$. Therefore the fixed point of $g$ is
unique. \qed
\end{frame}

\begin{frame}
   \begin{example}
       Show that the following function has a unique fixed point.
       \begin{eqnarray*}
           g(x) = ( x^2 - 1 ) / 3, \quad x \in [-1,1].
       \end{eqnarray*}
   \end{example}
   {\em Solution:}
       The Extreme Value Theorem implies that
       \begin{eqnarray*}
           && \min_{x \in [-1,1]} g(x) = g(0) = - \frac{1}{3}, \\
           && \max_{x \in [-1,1]} g(x) = g(\pm 1 ) = 0.
       \end{eqnarray*}
       That is
       %\begin{eqnarray*}
           $g(x) \in [-1, 1], \ \forall\ x \in [-1,1]$.
       %\end{eqnarray*}

       Moreover, $g$ is continuous and
       \begin{eqnarray*}
           | g'(x)| = \left| \frac{2x}{3} \right| \leq \frac{2}{3}, \ \forall\ x \in
           (-1,1).
       \end{eqnarray*}
       By above theorem, $g$ has a unique fixed point in $[-1,1]$.

\end{frame}

\begin{frame}
    Let $p$ be such unique fixed point of $g$. Then
    \begin{eqnarray*}
        p = g(p) = \frac{p^2-1}{3} & \Rightarrow & p^2 - 3 p -1 =
        0 \\
        &\Rightarrow& p = \frac{1}{2} ( 3 - \sqrt{13} ).
    \end{eqnarray*}
    \qed

\vspace{-1.5cm}
\begin{figure}
    \begin{center}
        \resizebox{10.9cm}{!}{\includegraphics{ex2a_fix_pt.pdf}}
        %\caption{64-bit double precision.}    \label{fig-bit64}
    \end{center}
\end{figure}
\end{frame}

\begin{frame}
\begin{block}{Fixed-point iteration  or  functional iteration}
     Given a  continuous function $g$,  choose an initial
     point $x_{0}$ and generate   $\{ x_{k} \}_{k = 0}^{\infty}$ by
%
     \begin{eqnarray*}
         x_{k+1} = g(x_{k}), \quad k \geq 0.
     \end{eqnarray*}
\end{block}
%
 $\{ x_{k} \}$ may not converge, e.g., $g(x) = 3 x$. However, when the
sequence converges, say,
%
\[
   \lim_{k \rightarrow \infty} x_{k} = x^{*},
\]
%
then, since $g$ is continuous,
%
\[
   g(x^{*}) = g(\lim_{k \rightarrow \infty} x_{k})
   = \lim_{k \rightarrow \infty} g(x_{k})
   = \lim_{k \rightarrow \infty} x_{k+1}
   = x^{*}.
\]
%
That is, $x^{*}$ is a fixed point of $g$.
\end{frame}

\begin{frame}
\begin{alertblock}{Fixed-point iteration}
\begin{center}
\begin{tabular}[c]{lllllll} %\hline
% & & & & & & \\
    \multicolumn{5}{l}{Given $x_0$, tolerance $TOL$, maximum number
        of iteration $M$.}  & \\
    \multicolumn{5}{l}{Set $i = 1$ and $x = g(x_0)$.}  & \\
    \multicolumn{5}{l}{While $i \leq M$ and $|x - x_0| \geq TOL$}  & \\
    & \multicolumn{4}{l}{Set $i = i + 1$, $x_0 = x$ and $x = g(x_0)$. }  & \\
    \multicolumn{5}{l}{End While}  & %\\ \hline
% & & & & & & \\
\end{tabular}
\end{center}
\end{alertblock}

\begin{columns}
\begin{column}{6.5cm}

\vspace{-13mm}
\begin{figure}
   %\begin{center}
   \hspace{-10.2mm}
   \resizebox{7.5cm}{!}{\includegraphics{fig_a_fix_pt.pdf}}
   %\end{center}
\end{figure}
\end{column}

\begin{column}{6.5cm}

\vspace{-13mm}
\begin{figure}
   %\begin{center}
   \hspace{-10.2mm}
   \resizebox{7.5cm}{!}{\includegraphics{fig_b_fix_pt.pdf}}
   %\end{center}
\end{figure}
\end{column}
\end{columns}

%\vspace{-0.5cm}
%\begin{figure}
%    \begin{center}
%        \resizebox{9.5cm}{!}{\includegraphics{fig_fix_pt.pdf}}
%        %\caption{64-bit double precision.}    \label{fig-bit64}
%    \end{center}
%\end{figure}

\end{frame}

\begin{frame}
\begin{example}
    The equation
    \begin{eqnarray*}
        x^3 + 4 x^2 - 10 = 0
    \end{eqnarray*}
    has a unique root in $[1,2]$. Change the equation to the
    fixed-point form $x = g(x)$.
\end{example}
\begin{block}{}
    (a) $x = g_1(x) \equiv x - f(x) = x - x^3 - 4 x^2 + 10$
\end{block}
\begin{block}{}
    (b) $x = g_2(x) = \left( \frac{10}{x} - 4 x \right)^{1/2}$
\end{block}
    \begin{eqnarray*}
        x^3 = 10 - 4 x^2 \ \Rightarrow \ x^2 = \frac{10}{x} - 4 x
        \ \Rightarrow \ x = \pm \left( \frac{10}{x} - 4 x
        \right)^{1/2}
    \end{eqnarray*}
\end{frame}

\begin{frame}
    \begin{block}{}
        (c) $x = g_3(x) = \frac{1}{2} \left( 10 - x^3
        \right)^{1/2}$
    \end{block}

    \vspace{-5mm}
    \begin{eqnarray*}
        4 x^2 = 10 - x^3 \quad \Rightarrow \quad x = \pm
        \frac{1}{2} \left( 10 - x^3 \right)^{1/2}
    \end{eqnarray*}

    \vspace{-4mm}
    \begin{block}{}
        (d) $x = g_4(x) = \left( \frac{10}{4+x} \right)^{1/2}$
    \end{block}

    \vspace{-5mm}
    \begin{eqnarray*}
        x^2 ( x + 4 ) = 10 \quad \Rightarrow \quad x = \pm \left(
        \frac{10}{4+x} \right)^{1/2}
    \end{eqnarray*}

    \vspace{-4mm}
    \begin{block}{}
        (e) $ x = g_5(x) = x - \frac{x^3+4x^2 - 10}{3x^2 + 8x}$
    \end{block}

    \vspace{-5mm}
    \begin{eqnarray*}
        x = g_5(x) \equiv x - \frac{f(x)}{f^{\prime}(x)}
    \end{eqnarray*}
\end{frame}

\begin{frame}
    \begin{block}{}
        Results of the fixed-point iteration with initial point
        $x_0 = 1.5$
    \end{block}

    \vspace{-5mm}
    \begin{center}
    \begin{figure}
        \resizebox{12.0cm}{!}{\includegraphics{ex3_table_fix_pt.pdf}}
    \end{figure}
    \end{center}
\end{frame}

\begin{frame}
    \begin{theorem}[Fixed-point Theorem]
        Let $g \in C[a,b]$ be such that $g(x) \in [a,b]$ for all $x
        \in [a,b]$. Suppose that $g^{\prime}$ exists on $(a,b)$
        and that $\exists \ k$ with $0 < k < 1$ such that
        \begin{eqnarray*}
            | g^{\prime}(x) | \leq k, \ \forall \ x \in (a,b).
        \end{eqnarray*}
        Then, for any number $x_0$ in $[a,b]$,
        \begin{eqnarray*}
            x_n = g(x_{n-1}), \ n \geq 1,
        \end{eqnarray*}
        converges to the unique fixed point $x$ in $[a,b]$.
    \end{theorem}
\end{frame}

\begin{frame}
    {\em Proof:} By the assumptions, a unique fixed point exists
    in $[a,b]$. Since $g([a,b]) \subseteq [a,b]$,
    $\{ x_n \}_{n=0}^{\infty}$ is defined and $x_n \in [a,b]$ for all $n \geq
    0$. Using the Mean Values Theorem and the fact that $|
    g^{\prime}(x) | \leq k$, we have
    \begin{eqnarray*}
        | x - x_n | = | g(x_{n-1}) - g(x) | = | g^{\prime}(\xi_n)|
        | x - x_{n-1} | \leq k | x - x_{n-1}|,
    \end{eqnarray*}
    where $\xi_n \in (a,b)$. It follows that
    \begin{eqnarray}
        | x_n - x | \leq k | x_{n-1} - x | \leq k^2 | x_{n-2} - x
        | \leq \cdots \leq k^n | x_0 - x |.
        \label{eq:pf_thm_fixpt_1}
    \end{eqnarray}
    Since $0 < k < 1$, we have
    \begin{eqnarray*}
        \lim_{n \to \infty} k^n = 0
    \end{eqnarray*}
    and
    \begin{eqnarray*}
        \lim_{n \to \infty} | x_n - x | \leq
        \lim_{n \to \infty} k^n | x_0 - x | = 0.
    \end{eqnarray*}
    Hence, $\{ x_n \}_{n=0}^{\infty}$ converges to $x$. \qed
\end{frame}

\begin{frame}
    \begin{corollary}
        If $g$ satisfies the hypotheses of above theorem, then
        \begin{eqnarray*}
            | x - x_n | \leq k^n \max \{x_0-a, b - x_0\}
        \end{eqnarray*}
        and
        \begin{eqnarray*}
            | x_n - x | \leq \frac{k^n}{1-k} | x_1 - x_0 |, \
            \forall \ n \geq 1.
        \end{eqnarray*}
    \end{corollary}
    {\em Proof:} From (\ref{eq:pf_thm_fixpt_1}),
    \begin{eqnarray*}
        | x_n - x | \leq k^n | x_0 - x | \leq k^n \max \{ x_0 - a,
        b - x_0 \}.
    \end{eqnarray*}
    For $n \geq 1$, using the Mean Values Theorem,
    \begin{eqnarray*}
        |x_{n+1} - x_n | = | g(x_n) - g(x_{n-1}) | \leq k | x_n -
        x_{n-1} | \leq \cdots \leq k^n | x_1 - x_0 |.
    \end{eqnarray*}
\end{frame}

\begin{frame}
    Thus, for $m > n \geq 1$,
    \begin{eqnarray*}
        |x_{m} - x_n | &=& | x_m - x_{m-1} + x_{m-1} - \cdots +
            x_{n+1} - x_n | \\
        &\leq& |x_m - x_{m-1}| + |x_{m-1} - x_{m-2}| + \cdots + |
            x_{n+1} - x_n | \\
        &\leq& k^{m-1} |x_1 - x_0 | + k^{m-2} |x_1 - x_0| + \cdots
            + k^n |x_1 -x_0| \\
        &=& k^n |x_1 - x_0| \left( 1 + k + k^2 + \cdots + k^{m-n-1}
            \right).
    \end{eqnarray*}
    It implies that
    \begin{eqnarray*}
        |x - x_n| &=& \lim_{m \to \infty} | x_m - x_n| \leq \lim_{m
        \to \infty} k^n | x_1 - x_0 | \sum_{j = 0}^{m-n-1} k^j \\
        &\leq& k^n | x_1 - x_0 | \sum_{j=0}^{\infty} k^j =
        \frac{k^n}{1-k} | x_1 - x_0 |.
    \end{eqnarray*}
    \qed
\end{frame}

\begin{frame}
    \begin{example}
        For previous example,
%       \begin{eqnarray*}
           $ f(x) = x^3+4x^2 - 10 = 0.$
%       \end{eqnarray*}
    \end{example}
    \begin{block}{}
        Let $g_1(x) = x - x^3 - 4 x^2 +10$, we have
            \begin{eqnarray*}
               g_1(1) = 6 \quad \mbox{ and } \quad g_1(2) = -12,
            \end{eqnarray*}
            so $g_1([1,2]) \nsubseteq [1,2]$. Moreover,
            \begin{eqnarray*}
                g_1^{\prime}(x) = 1 - 3 x^2 - 8x \quad \Rightarrow
                \quad |g^{\prime}_1(x) | \geq 1 \ \forall \ x \in
                [1,2]
            \end{eqnarray*}
            $\bullet$ DOES NOT guarantee convergence. In fact, it almost for
sure will not converge since when $x_n$ is close to $x$,
$$
|x_{n}-x| = |g_1(x_{n-1})-g_1(x)| = | g'(c) (x_{n-1}-x) | > |x_{n-1}-x|.
$$
The error is amplified whenever $x_n$ is close to convergence.
The only possibility for convergence is when $x_n$ is far from $x$
and (by chance, and very unlikely) that $g_1(x_n) = x$
    \end{block}
\end{frame}

\begin{frame}
    \begin{block}{}
        For $g_3(x) = \frac{1}{2} ( 10 - x^3)^{1/2}, \ \forall \ x
        \in [1, 1.5]$,
        \begin{eqnarray*}
            g_3^{\prime}(x) = -\frac{3}{4} x^2 ( 10 - x^3)^{-1/2}
            < 0, \ \forall \ x \in [1,1.5],
        \end{eqnarray*}
        so $g_3$ is strictly decreasing on $[1,1.5]$ and
        \begin{eqnarray*}
            1 < 1.28 \approx g_3(1.5) \leq g_3(x) \leq g_3(1) =
            1.5, \ \forall \ x \in [1,1.5].
        \end{eqnarray*}
        On the other hand,
        \begin{eqnarray*}
            | g_3^{\prime}(x) | \leq | g_3^{\prime}(1.5) | \approx
            0.66, \ \forall \ x \in [1,1.5]
        \end{eqnarray*}
        Hence, the sequence is convergent to the fixed point.
    \end{block}
\end{frame}

\begin{frame}
    \begin{block}{}
        For $g_4(x) = \sqrt{10/(4+x)}$, we have
        \begin{eqnarray*}
            \sqrt{\frac{10}{6}} \leq g_4(x) \leq
            \sqrt{\frac{10}{5}}, \ \forall \ x \in [1,2]
            \quad \Rightarrow \quad g_4([1,2]) \subseteq [1,2]
        \end{eqnarray*}
        Moreover,
        \begin{eqnarray*}
            | g_4^{\prime}(x) | = \left|
            \frac{-5}{\sqrt{10}(4+x)^{3/2}} \right| \leq
            \frac{5}{\sqrt{10} (5)^{3/2}} <  0.15, \ \forall\ x
            \in [1,2].
        \end{eqnarray*}
        The bound of $|g_4^{\prime}(x)|$ is much smaller than the
        bound of $|g_3^{\prime}(x)|$, which explains the more
        rapid convergence using $g_4$.
    \end{block}
\end{frame}

\section{Newton's method}
%\subsection{Newton's method, Secant method and method of False
%Position}
\begin{frame}
\frametitle{Newton's method}

 Suppose that $f : \mathbb{R} \rightarrow \mathbb{R}$
and $f \in C^{2}[a,b]$, i.e., $f^{\prime\prime}$ exists and is
continuous. If $f(x^{*})=0$ and $x^{*} = x + h$ where $h$ is
small, then by {\textcolor{blue}{Taylor's}} theorem {\color{red}
%
\begin{eqnarray*}
    0 = f(x^{*}) & =& f(x+h) \\
   & = &
   f(x) + f'(x) h + \frac{1}{2} f^{\prime\prime}(x) h^{2}
     + \frac{1}{3!} f'''(x) h^{3} + \cdots   \\
   & = &
   f(x) + f'(x) h + O(h^{2}).
\end{eqnarray*}
}%
Since {\textcolor{red}{$h$}} is {\textcolor{blue}{small}},
$O(h^{2})$ is negligible. It is reasonable to drop $O(h^{2})$
terms. This implies
%
\[
    {\color{red} f(x) + f'(x) h \approx 0
    \quad \text{and} \quad
    h \approx -\frac{f(x)}{f'(x)},\ \mbox{ if } \ f'(x) \neq 0.}
\]
Hence
\[
    {\color{red} x + h = x - \frac{f(x)}{f'(x)}}
\]
is a better approximation to $x^{*}$.
\end{frame}

\begin{frame}

This sets the stage for the {\textcolor{blue}{Newton-Rapbson's}}
method, which starts with an initial approximation $x_{0}$ and
generates the sequence $\{ x_{n} \}_{n=0}^{\infty}$ defined by
%
\begin{eqnarray*}
   {\color{red} x_{n+1} = x_{n} - \frac{f(x_{n})}{f'(x_{n})}.}
\end{eqnarray*}
Since the Taylor's expansion of $f(x)$ at $x_{k}$ is given by
%
\[
   f(x) = f(x_{k}) + f'(x_{k}) (x - x_{k})
          + \frac{1}{2} f^{\prime\prime}(x_{k}) (x - x_{k})^{2} + \cdots.
\]
%
At $x_{k}$, one uses the {\textcolor{blue}{tangent line}}
\[
    {\color{red} y = \ell(x) = f(x_{k}) + f'(x_{k}) (x - x_{k})}
\]
to {\textcolor{blue}{approximate the curve}} of $f(x)$ and uses
the zero of the tangent line to approximate the zero of $f(x)$.

\end{frame}

\begin{frame}

\begin{alertblock}{Newton's Method}
%To find a solution to $f(x) = 0$ given an initial approximation
%$x_0$:
\begin{center}
\begin{tabular}[c]{lllllll} %\hline
% & & & & & & \\
    \multicolumn{5}{l}{Given $x_0$, tolerance $TOL$, maximum number
        of iteration $M$.}  & \\
    \multicolumn{5}{l}{Set $i = 1$ and $x = x_0 - f(x_0) / f^{\prime}(x_0)$.}  & \\
    \multicolumn{5}{l}{While $i \leq M$ and $|x - x_0| \geq TOL$}  & \\
    & \multicolumn{4}{l}{Set $i = i + 1$, $x_0 = x$ and $x = x_0 - f(x_0) /
       f^{\prime}(x_0)$. }  & \\
    \multicolumn{5}{l}{End While}  & %\\ \hline
% & & & & & & \\
\end{tabular}
\end{center}
\end{alertblock}

\vspace{-8mm}
\begin{figure}
   \begin{center}
   \resizebox{10.0cm}{!}{\includegraphics{fig_Newton_method.pdf}}
   \end{center}
\end{figure}

\end{frame}

\begin{frame}
    \begin{block}{Three stopping-technique inequalities}
        \begin{eqnarray*}
            &(a).& | x_n - x_{n-1} | < \varepsilon , \\
            &(b).& \frac{|x_n-x_{n-1}|}{|x_n|} < \varepsilon, \quad
            x_n \neq 0, \\
            &(c).& | f(x_n) | < \varepsilon.
        \end{eqnarray*}
    \end{block}

    \begin{block}{}
        Note that Newton's method for solving $f(x) = 0$
        \[
            x_{n+1} = x_{n} - \frac{f(x_{n})}{f'(x_{n})}, \ \mbox{ for
            } \ n \geq 1
        \]
        is just a special case of functional iteration in which
        \[
            g(x) = x - \frac{f(x)}{f'(x)}.
        \]
    \end{block}
\end{frame}

\begin{frame}
\begin{example}
  The following table shows the convergence behavior of Newton's
  method applied to solving $f(x) = x^{2} - 1 = 0$. Observe the
  quadratic convergence rate.
\end{example}
%
\begin{table}
\begin{center}
\begin{tabular}{l|l|l}
   $n$ & $x_n$ & $|e_n|\equiv | 1 - x_n|$ \\
   \hline
   $0$  &  2.0  & 1\\
   $1$  &  1.25 & 0.25 \\
   $2$  &  1.025 & 2.5e-2  \\
   $3$  &  1.0003048780488 & 3.048780488e-4 \\
   $4$  &  1.0000000464611 & 4.64611e-8 \\
   $5$  &  1.0  & 0 \\
   \hline
\end{tabular}
\end{center}
\end{table}
\end{frame}

\begin{frame}
\begin{theorem}
   Assume {\textcolor{red}{$f(x^*)=0,\ f^\prime(x^*) \neq 0$}} and {\textcolor{red}{$f(x)$}},\
   {\textcolor{red}{$f^\prime(x)$}} and {\textcolor{red}{$f^{\prime\prime}(x)$}}
   are {\textcolor{blue}{continuous}} on
   $N_{\varepsilon}(x^*)$. Then if $x_0$ is chosen {\textcolor{blue}{sufficiently
   close}} to $x^*$, then
   \begin{eqnarray*}
      {\color{red} \left\{ x_{n+1} = x_{n} -
      \frac{f(x_{n})}{f^\prime(x_n)} \right\} \rightarrow x^*.}
   \end{eqnarray*}
%      Moreover,
%   \begin{eqnarray*}
%       {\color{red} \lim_{n \rightarrow \infty} \frac{x^*-x_{n+1}}{(x^*-x_n)^2}
%       = -\frac{f^{\prime\prime}(x^*)}{2f^\prime(x^*)}.}
%   \end{eqnarray*}
\end{theorem}
    {\em Proof:} Define
    \begin{eqnarray*}
        g(x) = x - \frac{f(x)}{f'(x)}.
    \end{eqnarray*}
    Find an interval $[x^{\ast} - \delta,
    x^{\ast}+\delta]$ such that
    \begin{eqnarray*}
        g([ x^{\ast}-\delta, x^{\ast}+\delta]) \subseteq [ x^{\ast}
        -\delta, x^{\ast}+\delta]
    \end{eqnarray*}
     and
    \begin{eqnarray*}
        | g'(x) | \leq k < 1, \ \forall
        \ x \in (x^{\ast} - \delta, x^{\ast}+\delta).
    \end{eqnarray*}

\end{frame}

\begin{frame}
    Since $f'$ is continuous and $f'(x^{\ast}) \neq 0$, it implies
    that $\exists\ \delta_1 > 0$ such that $f'(x) \neq 0 \ \forall
    \ x \in [x^{\ast} - \delta_1, x^{\ast} + \delta_1] \subseteq
    [a,b]$. Thus, $g$ is defined and continuous on $[x^{\ast} -
    \delta_1, x^{\ast} + \delta_1]$. Also
    \begin{eqnarray*}
        g'(x) = 1 - \frac{f'(x)f'(x) - f(x) f''(x)}{\left[ f'(x)
        \right]^2} = \frac{f(x)f''(x)}{\left[ f'(x) \right]^2},
    \end{eqnarray*}
    for $x \in [x^{\ast} -
    \delta_1, x^{\ast} + \delta_1]$. Since $f''$ is continuous
    on $[a,b]$, we have $g'$ is continuous on $[x^{\ast} -
    \delta_1, x^{\ast} + \delta_1]$.

    By assumption $f(x^{\ast}) = 0$, so
    \begin{eqnarray*}
        g'(x^{\ast}) = \frac{f(x^{\ast}) f''(x^{\ast})}{|
        f'(x^{\ast}) |^2} = 0.
    \end{eqnarray*}
    Since $g'$ is continuous on $[x^{\ast} -
    \delta_1, x^{\ast} + \delta_1]$ and $g'(x^{\ast}) = 0$,
    $\exists \ \delta $ with $0 < \delta < \delta_1$ and $k \in
    (0,1)$ such that
    \begin{eqnarray*}
        | g'(x) | \leq k, \ \forall \  x \in [x^{\ast}-\delta,
        x^{\ast}+\delta].
    \end{eqnarray*}
\end{frame}

\begin{frame}
    Claim: $g([x^{\ast}-\delta,
        x^{\ast}+\delta]) \subseteq [x^{\ast}-\delta,
        x^{\ast}+\delta]$.

        If $x \in [x^{\ast}-\delta, x^{\ast}+\delta]$,
        then, by the Mean Value Theorem, $\exists\ \xi$ between
        $x$ and $x^{\ast}$ such that
        \begin{eqnarray*}
            |g(x) - g(x^{\ast}) | = | g'(\xi) | |x - x^{\ast}|.
        \end{eqnarray*}
        It implies that
        \begin{eqnarray*}
            |g(x) - x^{\ast}| &=& | g(x) - g(x^{\ast}) | = | g'(\xi) | |x -
            x^{\ast}| \\
            &\leq& k | x - x^{\ast} | < | x - x^{\ast} | < \delta.
        \end{eqnarray*}
        Hence, $g([x^{\ast}-\delta,x^{\ast}+\delta]) \subseteq
        [x^{\ast}-\delta,x^{\ast}+\delta]$.

        By the Fixed-Point Theorem, the sequence $\{ x_n
        \}_{n=0}^{\infty}$ defined by
        \begin{eqnarray*}
            x_n = g(x_{n-1}) = x_{n-1} -
            \frac{f(x_{n-1})}{f'(x_{n-1})}, \ \mbox{ for } \ n
            \geq 1,
        \end{eqnarray*}
        converges to $x^{\ast}$ for any $x_0 \in [
        x^{\ast}-\delta, x^{\ast}+\delta]$. \qed
\end{frame}

\begin{frame}
\begin{example}
   When Newton's method applied to $f(x) = \cos x$ with starting
   point $x_{0} = 3$, which is close to the root $\frac{\pi}{2}$
   of $f$, it produces $x_{1} = -4.01525, x_{2} = -4.8526, \cdots,$
   which converges to another root $-\frac{3 \pi}{2}$.
\end{example}

\vspace{-10mm}
\begin{figure}
   \begin{center}
   \resizebox{9.5cm}{!}{\includegraphics{ex_Newton_method.pdf}}
   \end{center}
\end{figure}

\end{frame}

\begin{frame}
\frametitle{Secant method}
    \begin{block}{Disadvantage of Newton's method}
        In many applications, the derivative $f'(x)$ is
        very expensive to compute, or the function $f(x)$ is not given in
        an algebraic formula so that $f'(x)$ is not available.
    \end{block}

    By definition,
    \begin{eqnarray*}
        f'(x_{n-1}) = \lim_{x \to x_{n-1}}
        \frac{f(x)-f(x_{n-1})}{x-x_{n-1}}.
    \end{eqnarray*}
    Letting $x = x_{n-2}$, we have
    \begin{eqnarray*}
        f'(x_{n-1}) \approx
        \frac{f(x_{n-2})-f(x_{n-1})}{x_{n-2}-x_{n-1}} =
        \frac{f(x_{n-1}) - f(x_{n-2})}{x_{n-1}-x_{n-2}}.
    \end{eqnarray*}
    Using this approximation for $f'(x_{n-1})$ in Newton's formula
    gives
    \begin{eqnarray*}
        {\color{red} x_n = x_{n-1} -
        \frac{f(x_{n-1})(x_{n-1}-x_{n-2})}{f(x_{n-1}) -
        f(x_{n-2})},}
    \end{eqnarray*}
    which is called the {\textcolor{blue}{Secant method}}.
\end{frame}

\begin{frame}
From geometric point of view, we use a {\textcolor{blue}{secant
line}} through {\textcolor{red}{$x_{n-1}$}} and
{\textcolor{red}{$x_{n-2}$}} instead of the tangent line to
approximate the function at the point $x_{n-1}$.


The slope of the secant line is
%
\begin{eqnarray*}
   s_{n-1} = \frac{f(x_{n-1}) - f(x_{n-2})}{x_{n-1} - x_{n-2}}
\end{eqnarray*}
%
and the equation is
%
\begin{eqnarray*}
   M(x) = f(x_{n-1}) + s_{n-1} (x - x_{n-1}).
\end{eqnarray*}
%
The zero of the secant line
%
\begin{eqnarray*}
   x = x_{n-1} - \frac{f(x_{n-1})}{s_{n-1}}
   = x_{n-1} - f(x_{n-1}) \frac{x_{n-1} - x_{n-2}}{f(x_{n-1}) - f(x_{n-2})}
\end{eqnarray*}
%
is then used as a new approximate $x_{n}$.

\end{frame}

\begin{frame}

\begin{alertblock}{Secant Method}
\begin{center}
\begin{tabular}[c]{lllllll} %\hline
% & & & & & & \\
    \multicolumn{5}{l}{Given $x_0, x_1$, tolerance $TOL$, maximum number
        of iteration $M$.}  & \\
    \multicolumn{5}{l}{Set $i = 2$; $y_0 = f(x_0); y_1 = f(x_1)$; }  & \\
    & \multicolumn{4}{l}{$x = x_1 -
        y_1(x_1-x_0)/(y_1-y_0)$.}  & \\
    \multicolumn{5}{l}{While $i \leq M$ and $|x - x_1| \geq TOL$}  & \\
    & \multicolumn{4}{l}{Set $i = i + 1$; $x_0 = x_1; y_0 = y_1; x_1 = x;
       y_1 = f(x);$ }  & \\
    & & \multicolumn{3}{l}{ $x = x_1 - y_1 ( x_1 - x_0 ) / ( y_1 - y_0 )$. }  & \\
    \multicolumn{5}{l}{End While}  & %\\ \hline
% & & & & & & \\
\end{tabular}
\end{center}
\end{alertblock}

\vspace{-9mm}
\begin{figure}
   \begin{center}
   \resizebox{9.5cm}{!}{\includegraphics{fig_Secant_method.pdf}}
   \end{center}
\end{figure}

\end{frame}

\begin{frame}
    \begin{block}{}
        \begin{center}
            Method of False Position
        \end{center}
    \end{block}
    \begin{enumerate}
        \item Choose initial approximations $x_0$ and $x_1$ with $f(x_0)
            f(x_1) < 0$.
        \item $x_2 = x_1 - f(x_1)(x_1-x_0)/(f(x_1)-f(x_0))$
        \item Decide which secant line to use to compute $x_3$: \\
              If $f(x_2) f(x_1) < 0$, then $x_1$ and $x_2$
                     bracket a root, i.e.,
              \begin{eqnarray*}
                     x_3 = x_2 -
                     f(x_2)(x_2-x_1)/(f(x_2)-f(x_1))
              \end{eqnarray*}
              Else, $x_0$ and $x_2$ bracket a root, i.e.,
              \begin{eqnarray*}
                      x_3 = x_2 -
                      f(x_2)(x_2-x_0)/(f(x_2)-f(x_0))
              \end{eqnarray*}
              End if
    \end{enumerate}
\end{frame}

\begin{frame}

\begin{alertblock}{Method of False Position}
\begin{center}
\begin{tabular}[c]{lllllll} %\hline
% & & & & & & \\
    \multicolumn{5}{l}{Given $x_0, x_1$, tolerance $TOL$, maximum number
        of iteration $M$.}  & \\
    \multicolumn{5}{l}{Set $i = 2$; $y_0 = f(x_0); y_1 = f(x_1)$;
        $x = x_1 -
        y_1(x_1-x_0)/(y_1-y_0)$.}  & \\
%    & \multicolumn{4}{l}{$x = x_1 -
%        y_1(x_1-x_0)/(y_1-y_0)$.}  & \\
    \multicolumn{5}{l}{While $i \leq M$ and $|x - x_1| \geq TOL$}  & \\
    & \multicolumn{4}{l}{Set $i = i + 1$; $y = f(x).$ }  & \\
    & \multicolumn{4}{l}{If $y \cdot y_1 < 0$, then set $x_0 = x_1; y_0 = y_1$. }  & \\
    & \multicolumn{4}{l}{Set $x_1 = x; y_1 = y;$ $x = x_1 - y_1 ( x_1 - x_0 ) / ( y_1 - y_0 )$. }  & \\
    \multicolumn{5}{l}{End While}  & %\\ \hline
% & & & & & & \\
\end{tabular}
\end{center}
\end{alertblock}

\vspace{-9mm}
\begin{figure}
   \begin{center}
   \resizebox{8.5cm}{!}{\includegraphics{fig_False_Position.pdf}}
   \end{center}
\end{figure}

\end{frame}

\section{Error analysis for iterative methods}
%\subsection{Convergent order, theorem}
\begin{frame}
\frametitle{Error analysis for iterative methods}
\begin{definition}
    Let {\textcolor{red}{$\{ x_{n} \} \rightarrow x^{*}$}}.
    If there are positive constants {\textcolor{red}{$c$}} and
  {\textcolor{red}{$\alpha$}}  such that
  \begin{eqnarray*}
           {\color{red} \lim_{n \to \infty} \frac{|x_{n+1} - x^{*}|}
           {|x_{n} - x^{*}|^{\alpha}} = c ,}
  \end{eqnarray*}
  then we say the {\textcolor{blue}{rate of convergence}} is of {\textcolor{blue}{order}}
   {\textcolor{red}{$\alpha$}}.
\end{definition}

\begin{alertblock}{}
  We say that the rate of
  convergence is
  \begin{enumerate}
     \item  {\textcolor{blue}{linear}} if
            {\textcolor{red}{$\alpha = 1$}} and $0 < c
            < 1$.
     \item  {\textcolor{blue}{superlinear}} if
        \begin{eqnarray*}
           {\color{red} \lim_{n \rightarrow \infty}
           \frac{|x_{n+1} - x^{*}|}{|x_{n} - x^{*}|} = 0;}
        \end{eqnarray*}
     \item  {\textcolor{blue}{quadratic}} if {\textcolor{red}{$\alpha = 2$}}.
  \end{enumerate}
\end{alertblock}
\end{frame}

\begin{frame}
    Suppose that $\{ x_n \}_{n=0}^{\infty}$ and $\{ \tilde{x}_n
    \}_{n=0}^{\infty}$ are linearly and quadratically convergent
    to $x^{\ast}$, respectively, with the same constant $c=0.5$.
    For simplicity, suppose that
    \begin{eqnarray*}
        \frac{|x_{n+1} - x^{\ast}|}{|x_{n} - x^{\ast}|} \approx c
        \quad \mbox{and} \quad \frac{|\tilde{x}_{n+1} -
        x^{\ast}|}{|\tilde{x}_n - x^{\ast}|^2} \approx c.
    \end{eqnarray*}
    These imply that
    \begin{eqnarray*}
        |x_n - x^{\ast}| \approx c |x_{n-1} - x^{\ast}| \approx
        c^2 |x_{n-2} - x^{\ast}| \approx \cdots \approx c^n |x_0 -
        x^{\ast}|,
    \end{eqnarray*}
    and
    \begin{eqnarray*}
        | \tilde{x}_n - x^{\ast} | &\approx& c | \tilde{x}_{n-1} -
            x^{\ast}|^2 \approx c \left[ c | \tilde{x}_{n-2} - x^{\ast}
            |^2 \right]^2 = c^3 | \tilde{x}_{n-2} - x^{\ast} |^4 \\
        &\approx& c^3 \left[ c | \tilde{x}_{n-3} - x^{\ast} |^2
        \right]^4 = c^7 | \tilde{x}_{n-3} - x^{\ast} |^8 \\
        &\approx& \cdots \approx c^{2^n-1} | \tilde{x}_0 -
        x^{\ast} |^{2^n}.
    \end{eqnarray*}
\end{frame}

\begin{frame}
\begin{block}{Remark}
    Quadratically convergent sequences generally converge much
    more quickly thank those that converge only linearly.
\end{block}

\begin{theorem}
    Let $g \in C[a,b]$ with $g([a,b]) \subseteq [a,b]$. Suppose
    that $g'$ is continuous on $(a,b)$ and $\exists\ k \in (0,1)$
    such that
    \begin{eqnarray*}
        | g'(x) | \leq k, \ \forall \ x \in (a,b).
    \end{eqnarray*}
    If $g'(x^{\ast}) \neq 0$, then for any $x_0 \in [a,b]$, the
    sequence
    \begin{eqnarray*}
        x_n = g(x_{n-1}), \ \mbox{ for } \ n \geq 1
    \end{eqnarray*}
    converges only linearly to the unique fixed point $x^{\ast}$
    in $[a,b]$.
\end{theorem}
\end{frame}

\begin{frame}
    {\em Proof:}
    \begin{itemize}
        \item By the Fixed-Point Theorem, the sequence $\{ x_n
              \}_{n=0}^{\infty}$ converges to $x^{\ast}$.
        \item Since $g'$ exists
              on $(a,b)$, by the Mean Value Theorem, $\exists\ \xi_n$
              between $x_n$ and $x^{\ast}$ such that
             \begin{eqnarray*}
                 x_{n+1} - x^{\ast} = g(x_n) - g(x^{\ast}) = g'(\xi_n) (
                 x_n - x^{\ast}).
             \end{eqnarray*}
        \item $\because \{ x_n \}_{n=0}^{\infty} \to x^{\ast} \quad
             \Rightarrow \quad \{ \xi_n \}_{n=0}^{\infty} \to x^{\ast}$
%    \begin{eqnarray*}
%        \because \{ x_n \}_{n=0}^{\infty} \to x^{\ast} \quad
%        \Rightarrow \quad \{ \xi_n \}_{n=0}^{\infty} \to x^{\ast}
%    \end{eqnarray*}
       \item Since $g'$ is continuous on $(a,b)$, we have
             \begin{eqnarray*}
                 \lim_{n \to \infty} g'(\xi_n) = g'(x^{\ast}).
             \end{eqnarray*}
       \item  Thus,
             \begin{eqnarray*}
                 \lim_{n \to \infty} \frac{|x_{n+1}-x^{\ast}|}{|x_n -
                 x^{\ast}|} = \lim_{n \to \infty} |g'(\xi_n)| =
                 |g'(x^{\ast})|.
             \end{eqnarray*}
             Hence, if $g'(x^{\ast}) \neq 0$, fixed-point iteration
             exhibits linear convergence. \qed
    \end{itemize}
\end{frame}

\begin{frame}
    \begin{theorem}
        Let $x^{\ast}$ be a fixed point of $g$ and $I$ be an open interval with $x^{\ast}
        \in I$. Suppose that
        $g'(x^{\ast}) = 0$ and $g''$ is continuous with
        \begin{eqnarray*}
            | g''(x) | < M, \ \forall \ x \in I.
        \end{eqnarray*}
        Then $\exists\ \delta > 0$ such that
        \begin{eqnarray*}
            \{ x_n = g(x_{n-1}) \}_{n=1}^{\infty} \ \to \ x^{\ast}
            \ \mbox{ for } \ x_0 \in [ x^{\ast} - \delta, x^{\ast}
            + \delta]
        \end{eqnarray*}
        at least quadratically. Moreover,
        \begin{eqnarray*}
            | x_{n+1} - x^{\ast} | < \frac{M}{2} | x_{n}-x^{\ast}
            |^2, \ \mbox{ for sufficiently large }\ n.
        \end{eqnarray*}
    \end{theorem}
\end{frame}

\begin{frame}
    {\em Proof:}
    \begin{itemize}
        \item Since $g'(x^{\ast}) = 0$ and $g'$ is continuous on
              $I$, $\exists\ \delta$ such that $[x^{\ast} -
              \delta, x^{\ast} + \delta] \subset I$ and
              \begin{eqnarray*}
                  |g'(x)| \leq k < 1, \ \forall \ x \in [x^{\ast}
                  - \delta, x^{\ast} + \delta].
              \end{eqnarray*}
        \item In the proof of the convergence for Newton's method,
              we have
              \begin{eqnarray*}
                  \{ x_n \}_{n=0}^{\infty} \subset [ x^{\ast} -
                  \delta, x^{\ast}+\delta ].
              \end{eqnarray*}
        \item Consider the Taylor expansion of $g(x_n)$ at
              $x^{\ast}$
              \begin{eqnarray*}
                  x_{n+1} = g(x_n) &=& g(x^{\ast}) + g'(x^{\ast}) ( x_n -
                  x^{\ast}) + \frac{g''(\xi)}{2} ( x_n -
                  x^{\ast})^2 \\
                  &=& x^{\ast} + \frac{g''(\xi)}{2} ( x_n -
                  x^{\ast})^2,
              \end{eqnarray*}
              where $\xi$ lies between $x_n$ and $x^{\ast}$.
    \end{itemize}
\end{frame}

\begin{frame}
    \begin{itemize}
        \item Since
              \begin{eqnarray*}
                  |g'(x)| \leq k < 1,  \ \forall \ x \in [x^{\ast} - \delta,
                  x^{\ast} + \delta]
              \end{eqnarray*}
               and
              \begin{eqnarray*}
                  g([x^{\ast} - \delta,
                  x^{\ast}+\delta]) \subseteq [x^{\ast} - \delta,
                  x^{\ast}+\delta],
              \end{eqnarray*}
              it follows that $\{ x_n
              \}_{n=0}^{\infty}$ converges to $x^{\ast}$.
        \item But $\xi_n$ is between $x_n$ and $x^{\ast}$ for each
              $n$, so $\{ \xi_n \}_{n=0}^{\infty}$ also converges
              to $x^{\ast}$ and
              \begin{eqnarray*}
                  \lim_{n\to \infty} \frac{|x_{n+1} - x^{\ast}
                  |}{| x_n - x^{\ast} |^2} = \frac{| g''(x^{\ast}
                  )|}{2} < \frac{M}{2}.
              \end{eqnarray*}
        \item It implies that $\{ x_n \}_{n=0}^{\infty}$ is
              quadratically convergent to $x^{\ast}$ if
              $g''(x^{\ast}) \neq 0$ and
              \begin{eqnarray*}
                  | x_{n+1} - x^{\ast} | < \frac{M}{2} | x_{n}-x^{\ast}
                  |^2, \ \mbox{ for sufficiently large }\ n. \quad \qed
              \end{eqnarray*}
              %\qed
    \end{itemize}
\end{frame}

\begin{frame}
    For Newton's method,
    \begin{eqnarray*}
        g(x) = x - \frac{f(x)}{f'(x)} \ \Rightarrow \ g'(x) = 1 -
        \frac{f'(x)}{f'(x)} + \frac{f(x)f''(x)}{(f'(x))^2} = \frac{f(x)f''(x)}{(f'(x))^2}
    \end{eqnarray*}
    It follows that $g'(x^{\ast}) = 0$. Hence Newton's method is
    locally quadratically convergent.
\end{frame}

%\subsection{Error Analysis of Secant Method}
\begin{frame}
\frametitle{Error Analysis of Secant Method}

 {\em Reference:} D.
Kincaid and W. Cheney, "Numerical analysis"

Let $x^{*}$ denote the exact solution of $f(x) = 0$, $e_{k} =
x_{k} - x^{*}$ be the errors at the $k$-th step. Then
%
\begin{eqnarray*}
   e_{k+1} & = & x_{k+1} - x^{*}  \\
   & = &
   x_{k} -  f(x_{k})
   \frac{x_{k} - x_{k-1}}{f(x_{k}) - f(x_{k-1})} - x^{*} \\
%   & = &
%   \frac{1}{f(x_{k}) - f(x_{k-1})} \left[
%   x_{k} f(x_{k}) - x_{k} f(x_{k-1}) - x_{k} f(x_{k})
%   + x_{k-1} f(x_{k}) - x^{*} f(x_{k})
%   + x^{*} f(x_{k-1}) \right]  \\
   & = &
   \frac{1}{f(x_{k}) - f(x_{k-1})} \left[
   (x_{k-1} - x^{*}) f(x_{k}) - (x_{k} - x^{*}) f(x_{k-1})
   \right]  \\
   & = &
   \frac{1}{f(x_{k}) - f(x_{k-1})} \left(
   e_{k-1} f(x_{k}) - e_{k} f(x_{k-1}) \right)  \\
   & = &
   e_{k} e_{k-1} \left(
   \frac{\frac{1}{e_{k}} f(x_{k})
   - \frac{1}{e_{k-1}} f(x_{k-1})}{x_{k} - x_{k-1}}
   \cdot \frac{x_{k} - x_{k-1}}{f(x_{k}) - f(x_{k-1})}
   \right)
\end{eqnarray*}

\end{frame}
%
\begin{frame}

To estimate the numerator $\frac{\frac{1}{e_{k}} f(x_{k})
   - \frac{1}{e_{k-1}} f(x_{k})}{x_{k} - x_{k-1}}$,
we apply the Taylor's theorem
%
\[
   f(x_{k}) = f(x^{*} + e_{k})
   = f(x^{*}) + f'(x^{*}) e_{k} + \frac{1}{2} f''(x^{*})
   e_{k}^{2} + O(e_{k}^{3}),
\]
%
to get
%
\[
   \frac{1}{e_{k}} f(x_{k}) = f'(x^{*}) + \frac{1}{2}
   f''(x^{*}) e_{k} + O(e_{k}^{2}).
\]
%
Similarly,
%
\[
   \frac{1}{e_{k-1}} f(x_{k-1}) = f'(x^{*}) + \frac{1}{2}
   f''(x^{*}) e_{k-1} + O(e_{k-1}^{2}).
\]
%
Hence
%
\[
    \frac{1}{e_{k}} f(x_{k}) - \frac{1}{e_{k-1}} f(x_{k-1})
    \approx
    \frac{1}{2} (e_{k} - e_{k-1}) f''(x^{*}).
\]
%
Since $x_{k} - x_{k-1} = e_{k} - e_{k-1}$ and
%
\[
    \frac{x_{k} - x_{k-1}}{f(x_{k}) - f(x_{k-1})}
    \rightarrow
    \frac{1}{f'(x^{*})},
\]

\end{frame}
%
\begin{frame}

we have
%
\begin{eqnarray}
    e_{k+1} &\approx&
   e_{k} e_{k-1} \left(
   \frac{\frac{1}{2} (e_{k} - e_{k-1}) f''(x^{*})}
   {e_{k} - e_{k-1}} \cdot \frac{1}{f'(x^{*})} \right)
   = \frac{1}{2} \frac{f''(x^{*})}{f'(x^{*})}
   e_{k} e_{k-1} \nonumber \\*
   & \equiv& C e_{k} e_{k-1}
    \label{err_secant.1}
\end{eqnarray}



To estimate the convergence rate, we assume
%
\[
   |e_{k+1}| \approx \eta |e_{k}|^{\alpha},
\]
%
where $\eta > 0 $ and $\alpha > 0$ are constants, i.e.,
%
\[
    \frac{|e_{k+1}|}{ \eta |e_{k}|^{\alpha}} \rightarrow 1
    \quad
    \text{as}
    \quad
    k \rightarrow \infty.
\]
%
Then $|e_{k}| \approx \eta |e_{k-1}|^{\alpha}$ which implies
$|e_{k-1}| \approx \eta^{-1/\alpha} |e_{k}|^{1/\alpha}$. Hence
(\ref{err_secant.1}) gives
%
\[
    \eta |e_{k}|^{\alpha} \approx
    C |e_{k}| \eta^{-1/\alpha} |e_{k}|^{1/\alpha}
    \quad \Longrightarrow \quad
    C^{-1} \eta^{1 + \frac{1}{\alpha}}
    \approx
    |e_{k}|^{1 - \alpha + \frac{1}{\alpha}}.
\]
%
Since $|e_{k}| \rightarrow 0$ as $k \rightarrow \infty$, and
$C^{-1} \eta^{1 + \frac{1}{\alpha}}$ is a nonzero constant,
%
\[
    1 - \alpha + \frac{1}{\alpha} = 0
    \quad \Longrightarrow \quad
    \alpha = \frac{1 + \sqrt{5}}{2} \approx 1.62.
\]

\end{frame}
%
\begin{frame}

This result implies that $C^{-1} \eta^{1 + \frac{1}{\alpha}}
\rightarrow 1$ and
%
\[
   \eta \rightarrow
   C^{\frac{\alpha}{1+\alpha}} =
   \left(\frac{f''(x^{*})}{2 f'(x^{*})} \right)^{0.62}.
\]
%


In summary, we have shown that
%
\begin{eqnarray*}
   {\color{red} |e_{k+1}| = \eta |e_{k}|^{\alpha},
   \quad
   \alpha \approx 1.62,}
\end{eqnarray*}
%
that is, the {\textcolor{blue}{rate of convergence}} is
{\textcolor{blue}{superlinear}}.


Rate of convergence:
\begin{itemize}
   \item {\textcolor{blue}{secant}} method:  {\textcolor{green}{superlinear}}
   \item {\textcolor{blue}{Newton's}} method: {\textcolor{green}{quadratic}}
   \item {\textcolor{blue}{bisection}} method: {\textcolor{green}{linear}}
\end{itemize}

\end{frame}

\begin{frame}
Each iteration of  method requires
\begin{itemize}
    \item secant method: one
          function evaluation
    \item Newton's method: two function
evaluation, namely, $f(x_{k})$ and $f'(x_{k})$.\\
 $\Rightarrow$
two steps of secant method are comparable to one step of Newton's
method. Thus
%
\[
   |e_{k+2}| \approx \eta |e_{k+1}|^{\alpha}
   \approx \eta^{1 + \alpha}
   |e_{k}|^{\frac{3 + \sqrt{5}}{2}} \approx \eta^{1 + \alpha}
   |e_{k}|^{2.62}.
\]
%
$\Rightarrow$ secant method is more efficient than Newton's
method.
\end{itemize}

\begin{block}{Remark}
Two steps of secant method would require a little more work than
one step of Newton's method.
\end{block}

\end{frame}

\section{Accelerating convergence}
%\subsection{Aitken's and Steffensen's methods}
\begin{frame}
\frametitle{Accelerating convergence}
    \begin{block}{Aitken's $\Delta^2$ method}
        \begin{itemize}
            \item Accelerate the convergence of a sequence that is
                  {\textcolor{blue}{linearly
                  convergent}}.
            \item Suppose $\{ y_n \}_{n=0}^{\infty}$ is a linearly
                  convergent sequence with limit $y$. Construct a sequence
                  $\{ \hat{y}_n \}_{n=0}^{\infty}$ that converges more
                  rapidly to $y$ than $\{ y_n \}_{n=0}^{\infty}$.
            \end{itemize}
    \end{block}

    For $n$ sufficiently large,
    \begin{eqnarray*}
        \frac{y_{n+1}-y}{y_n-y} \approx
        \frac{y_{n+2}-y}{y_{n+1}-y}.
    \end{eqnarray*}
    Then
    \begin{eqnarray*}
        (y_{n+1} - y)^2 \approx ( y_{n+2}-y) ( y_n - y),
    \end{eqnarray*}
    so
    \begin{eqnarray*}
        y_{n+1}^2 - 2 y_{n+1} y + y^2 \approx y_{n+2} y_n - (
        y_{n+2} + y_n ) y + y^2
    \end{eqnarray*}
\end{frame}

\begin{frame}
    and
    \begin{eqnarray*}
        ( y_{n+2} + y_n - 2 y_{n+1}) y \approx y_{n+2} y_n -
        y_{n+1}^2.
    \end{eqnarray*}
    Solving for $y$ gives
    \begin{eqnarray*}
        y &\approx& \frac{y_{n+2}y_n - y_{n+1}^2}{y_{n+2} - 2
        y_{n+1} + y_n} \\
        &=& \frac{y_ny_{n+2}-2y_n y_{n+1}+ y_n^2 -y_n^2 + 2 y_n y_{n+1}
        - y_{n+1}^2}{y_{n+2}- 2 y_{n+1} + y_n } \\
        &=& \frac{y_n(y_{n+2} - 2 y_{n+1}+y_n ) - ( y_{n+1} -
        y_n)^2}{ ( y_{n+2} - y_{n+1}) - ( y_{n+1} - y_n)} \\
        &=& y_n - \frac{(y_{n+1} - y_n)^2}{(y_{n+2}-y_{n+1}) -
        (y_{n+1}-y_n)}.
    \end{eqnarray*}

    \begin{alertblock}{Aitken's $\Delta^2$ method}
        \vspace{-5mm}
        \begin{eqnarray}
            \hat{y}_n = y_n - \frac{(y_{n+1} - y_n)^2}{(y_{n+2}-y_{n+1}) -
            (y_{n+1}-y_n)}. \label{eq:Aitken_method_1}
        \end{eqnarray}
    \end{alertblock}
\end{frame}

\begin{frame}
    \begin{example}
        The sequence $\{ y_n = \cos (1/n) \}_{n=1}^{\infty}$
        converges linearly to $y = 1$.
    \end{example}

      \begin{table}[bth]
      \begin{center}
      \begin{tabular}{ccc} \hline
         $n$   & $y_n$ & $\hat{y}_n$  \\  \hline
         $1$  &  0.54030 &  0.96178                \\
         $2$  &  0.87758 &  0.98213  \\
         $3$  &  0.94496 &  0.98979  \\
         $4$  &  0.96891 &  0.99342  \\
         $5$  &  0.98007 &  0.99541  \\
         $6$  &  0.98614 &    \\
         $7$  &  0.98981 &    \\ \hline
      \end{tabular}
      \end{center}
      \end{table}

      \begin{itemize}
          \item $\{ \hat{y}_n \}_{n=1}^{\infty}$ converges more
          rapidly to $y=1$ than $\{ y_n \}_{n=1}^{\infty}$.
      \end{itemize}
\end{frame}

\begin{frame}
    \begin{definition}
        For a given sequence $\{ y_n \}_{n=0}^{\infty}$, the
        forward difference $\Delta y_n$ is defined by
        \begin{eqnarray*}
            \Delta y_n = y_{n+1} - y_n, \quad \mbox{for }\ n \geq
            0.
        \end{eqnarray*}
        Higher powers of $\Delta$ are defined recursively by
        \begin{eqnarray*}
            \Delta^k y_n = \Delta ( \Delta^{k-1} y_n ), \quad
            \mbox{for } \ k \geq 2.
        \end{eqnarray*}
    \end{definition}
    The definition implies that
    \begin{eqnarray*}
        \Delta^2 y_n = \Delta ( y_{n+1} - y_n) = \Delta y_{n+1} -
        \Delta y_n = ( y_{n+2}-y_{n+1}) - ( y_{n+1} - y_n ).
    \end{eqnarray*}
    So the formula for $\hat{y}_n$ in (\ref{eq:Aitken_method_1})
    can be written as
    \begin{eqnarray*}
        \hat{y}_{n} = y_n - \frac{(\Delta y_n )^2}{\Delta^2 y_n },
        \quad \mbox{for } \ n \geq 0.
    \end{eqnarray*}
\end{frame}

\begin{frame}
    \begin{theorem}
        Suppose $\{ y_n \}_{n=0}^{\infty} \to y$ linearly and
        \begin{eqnarray*}
            \lim_{n\to \infty} \frac{y_{n+1}-y}{y_n - y} < 1.
        \end{eqnarray*}
        Then $\{ \hat{y}_n \}_{n=0}^{\infty} \to y$ faster than
        $\{ y_n \}_{n=0}^{\infty}$ in the sense that
        \begin{eqnarray*}
            \lim_{n\to \infty} \frac{\hat{y}_{n} - y}{y_n - y } =
            0.
        \end{eqnarray*}
    \end{theorem}

    \begin{itemize}
        \item Aitken's $\Delta^2$ method constructs the terms in
              order:
              \begin{eqnarray*}
                  && y_0, \quad y_1 = g(y_0), \quad y_2 = g(y_1), \quad \hat{y}_0
                     = \{ \Delta^2 \} (y_0), \quad y_3 = g(y_2), \\
                  && \hat{y}_1 = \{ \Delta^2 \}(y_1),\quad \ldots.
              \end{eqnarray*}
              $\Rightarrow$ Assume $| \hat{y}_0 - y | < | y_2 - y
              |$
    \end{itemize}
\end{frame}

\begin{frame}
    \begin{itemize}
        \item Steffensen's method constructs the terms in order:
              \begin{eqnarray*}
                  && y_0^{(0)} \equiv y_0, \hspace{1.8cm} y_1^{(0)} =
                  g(y_0^{(0)}), \quad y_2^{(0)} = g(y_1^{(0)}), \\
                  && y_0^{(1)} = \{ \Delta^2 \} (y_0^{(0)}), \quad
                  y_1^{(1)} = g(y_0^{(1)}), \quad  y_2^{(1)} =
                  g(y_1^{(1)}), \quad \ldots.
              \end{eqnarray*}
    \end{itemize}

    \begin{alertblock}{Steffensen's method
    {\textcolor{blue}{(To find a solution of $y = g(y)$)}}}
    \begin{center}
    \begin{tabular}[c]{lllllll} %\hline
%    \multicolumn{5}{l}{To find a solution of $y = g(y)$ with
%    giving initial $y_0$.}\\
    & \multicolumn{4}{l}{Given $y_0$, tolerance $TOL$, maximum number
        of iteration $M$.}  & \\
    & \multicolumn{4}{l}{Set $i = 1$.}  & \\
    & \multicolumn{4}{l}{While $i \leq M$}  & \\
    & & \multicolumn{3}{l}{Set $y_1 = g(y_0)$; $y_2 = g(y_1)$;
       $y = y_0 - ( y_1 - y_0)^2 / (y_2-2y_1+y_0)$.}  & \\
%    & & & \multicolumn{2}{l}{$y = y_0 - ( y_1 - y_0)^2 / (y_2-2y_1+y_0)$. }  & \\
    & & \multicolumn{3}{l}{If $|y - y_0| < Tol$, then STOP. }  & \\
    & & \multicolumn{3}{l}{Set $i = i + 1$; $y_0 = y$. }  & \\
    & \multicolumn{4}{l}{End While}  & %\\ \hline
% & & & & & & \\
\end{tabular}
\end{center}
\end{alertblock}

    \begin{theorem}
         Suppose that $x = g(x)$ has the solution $x^{\ast}$ with
         $g^\prime(x^{\ast}) \neq 1$. If $\exists\ \delta > 0$
         such that $g \in C^3 [ x^{\ast} - \delta, x^{\ast} +
         \delta ]$, then Steffensen's method gives quadratic
         convergence for any $x_0 \in [ x^{\ast} - \delta,
         x^{\ast} + \delta]$.
    \end{theorem}

\end{frame}

\section{Zeros of polynomials and M\"{u}ller's method}
\begin{frame}
\frametitle{Zeros of polynomials and M\"{u}ller's method}

$\bullet$ Horner's method:

Let
\begin{eqnarray*}
    P(x) &=& a_0 + a_1 x + a_2 x^2 + \cdots + a_{n-1} x^{n-1} + a_n x^n \\
         &=& a_0 + x \left( a_1 + x \left( a_2 + \cdots + x \left(
         a_{n-1} + a_n x \right) \cdots \right) \right)
\end{eqnarray*}
If
\begin{eqnarray*}
    b_n &=& a_n, \\
    b_k &=& a_k + b_{k+1} x_0, \ \mbox{ for } \ k = n-1, n-2,
    \ldots, 1, 0,
\end{eqnarray*}
then
\begin{eqnarray*}
    b_0 = a_0 + b_1 x_0 = a_0 + \left( a_1 + b_2 x_0 \right) x_0 = \cdots =
    P(x_0).
\end{eqnarray*}
Consider
\begin{eqnarray*}
    Q(x) = b_1 + b_2 x + \cdots + b_n x^{n-1}.
\end{eqnarray*}
\end{frame}

\begin{frame}
Then
\begin{eqnarray*}
    && b_0 + ( x - x_0 ) Q(x) = b_0 + ( x - x_0) \left( b_1 + b_2 x +
    \cdots + b_n x^{n-1} \right) \\
    &=& ( b_0 - b_1 x_0 ) + ( b_1 - b_2 x_0) x + \cdots + (
    b_{n-1} - b_n x_0 ) x^{n-1} + b_n x^n \\
    &=& a_0 + a_1 x + \cdots + a_n x^n = P(x).
\end{eqnarray*}
Differentiating $P(x)$ with respect to $x$ gives
\begin{eqnarray*}
    P^{\prime}(x) = Q(x) + ( x - x_0) Q^{\prime}(x) \quad \mbox{
    and } \quad P^{\prime}(x_0) = Q(x_0).
\end{eqnarray*}
Use Newton-Raphson method to find an approximate zero of $P(x)$:
\begin{eqnarray*}
    x_{k+1} = x_k - \frac{P(x_k)}{Q(x_k)}, \ \forall\ k = 0, 1, 2,
    \ldots.
\end{eqnarray*}
Similarly, let
\begin{eqnarray*}
    c_n &=& b_n = a_n, \\
    c_k &=& b_k + c_{k+1} x_k, \ \mbox{ for } \ k = n-1, n-2,
    \ldots, 1,
\end{eqnarray*}
then $c_1 = Q(x_k)$.
\end{frame}

\begin{frame}

    \begin{alertblock}{Horner's method
    {\textcolor{blue}{(Evaluate $y=P(x_0)$ and $z=P^{\prime}(x_0)$)}}}
    \begin{center}
    \begin{tabular}[c]{lllllll} %\hline
    & \multicolumn{4}{l}{Set $y = a_n$; $z = a_n$.}  & \\
    & \multicolumn{4}{l}{For $j = n-1, n-2, \ldots, 1$}  & \\
    & & \multicolumn{3}{l}{Set $y = a_j + y x_0$; $z = y + z x_0$.}  & \\
    & \multicolumn{4}{l}{End for}  & \\
    & \multicolumn{4}{l}{Set $y = a_0 + y x_0$. }  &
% & & & & & & \\
\end{tabular}
\end{center}
\end{alertblock}

If $x_N$ is an approximate zero of $P$, then
\begin{eqnarray*}
    P(x) &=& ( x- x_N ) Q(x) + b_0 = ( x - x_N ) Q(x) + P(x_N) \\
    &\approx& ( x - x_N ) Q(x) \equiv ( x - \hat{x}_1 ) Q_1(x).
\end{eqnarray*}
So $x - \hat{x}_1$ is an approximate factor of $P(x)$ and we can
find a second approximate zero of $P$ by applying Newton's method
to $Q_1(x)$. The procedure is called deflation.
\end{frame}

\begin{frame}
    $\bullet$ M\"{u}ller's method for complex root:

    \begin{theorem}
        If $z = a + i b$ is a complex zero of multiplicity $m$ of
        $P(x)$ with real coefficients, then $\bar{z} = a - b i$ is
        also a zero of multiplicity $m$ of $P(x)$ and $(x^2 - 2ax
        + a^2 + b^2)^m$ is a factor of $P(x)$.
    \end{theorem}


\vspace{5mm}
    \begin{columns}
\begin{column}{5.5cm}
   %\vspace{-20mm}
   {\textcolor{blue}{Secant method}}: Given $p_0$ and $p_1$, determine $p_2$ as the
   intersection of the $x$-axis with the line through
   $(p_0,f(p_0))$ and $(p_1,f(p_1))$.

      \vspace{-10mm}
   \begin{figure}
       \begin{center}
           %\resizebox{6.0cm}{!}{\includegraphics{./figures/poincare_map.pdf}}
           \resizebox{5.5cm}{!}{\includegraphics{Muller_Secant_fig.pdf}}
       \end{center}
   \end{figure}

\end{column}

\pause

\begin{column}{5.5cm}
   {\textcolor{blue}{M\"{u}ller's method}}: Given $p_0, p_1$ and
   $p_2$, determine $p_3$ by the intersection of the $x$-axis with
   the parabola through $(p_0, f(p_0))$, $(p_1,f(p_1))$ and
   $(p_2,f(p_2))$.

   \vspace{-2mm}
   \begin{figure}
       \begin{center}
           %\resizebox{6.0cm}{!}{\includegraphics{./figures/poincare_map.pdf}}
           \resizebox{4.5cm}{!}{\includegraphics{Muller_fig.pdf}}
       \end{center}
   \end{figure}

\end{column}
\end{columns}

\end{frame}

\begin{frame}
    Let
    \begin{eqnarray*}
        P(x) = a ( x - p_2)^2 + b ( x - p_2) + c
    \end{eqnarray*}
    that passes through $(p_0,f(p_0))$, $(p_1,f(p_1))$ and
    $(p_2,f(p_2))$. Then
    \begin{eqnarray*}
        f(p_0) &=& a ( p_0-p_2)^2 + b ( p_0-p_2) + c, \\
        f(p_1) &=& a(p_1-p_2)^2 + b ( p_1-p_2) + c, \\
        f(p_2) &=& a (p_2-p_2)^2 + b(p_2-p_2) + c = c.
    \end{eqnarray*}
    It implies that
    \begin{eqnarray*}
        c &=& f(p_2), \\
        b &=& \frac{(p_0-p_2)^2 \left[ f(p_1)-f(p_2) \right] - (
        p_1-p_2)^2 \left[ f(p_0) - f(p_2) \right]}{(p_0-p_2)
        (p_1-p_2) (p_0-p_1)}, \\
        a &=& \frac{(p_1-p_2) \left[ f(p_0)-f(p_2) \right] - (
        p_0-p_2) \left[ f(p_1) - f(p_2) \right]}{(p_0-p_2)
        (p_1-p_2) (p_0-p_1)}.
    \end{eqnarray*}
\end{frame}

\begin{frame}
    To determine $p_3$, a zero of $P$, we apply the quadratic
    formula to $P(x) = 0$ and get
    \begin{eqnarray*}
        p_3 - p_2 = \frac{2c}{b \pm \sqrt{b^2-4ac}}.
    \end{eqnarray*}
    Choose
    \begin{eqnarray*}
        p_3 = p_2 + \frac{2c}{b +sgn(b) \sqrt{b^2-4ac}}
    \end{eqnarray*}
    such that the denominator will be largest and result in $p_3$
    selected as the closest zero of $P$ to $p_2$.
\end{frame}

\begin{frame}
\begin{alertblock}{M\"{u}ller's method
    {\textcolor{blue}{(Find a solution of $f(x)=0$)}}}
    \begin{center}
    \begin{tabular}[c]{lllllll} %\hline
    & \multicolumn{4}{l}{Given $p_0, p_1, p_2$; tolerance $TOL$; maximum
       number of iterations $M$}  & \\
    & \multicolumn{4}{l}{Set $h_1 = p_1 - p_0$; $h_2 = p_2-p_1$;}  & \\
    & & \multicolumn{3}{l}{$\delta_1 = ( f(p_1) - f(p_0) )/ h_1$;
       $\delta_2 = ( f(p_2) - f(p_1))/h_2$;}  & \\
    & & \multicolumn{3}{l}{$d = ( \delta_2 - \delta_1)/(h_2+h_1)$; $i = 3$.}  & \\
    & \multicolumn{4}{l}{While $i \leq M$}  & \\
    & & \multicolumn{3}{l}{Set $b = \delta_2 + h_2 d$; $D = \sqrt{b^2 - 4 f(p_2)d }$.}  & \\
    & & \multicolumn{3}{l}{If $| b - D| < |b+D|$, then set $E = b + D$
       else set $E = b - D$.}  & \\
    & & \multicolumn{3}{l}{Set $ h = -2 f(p_2)/E$; $ p = p_2 + h$.}  & \\
    & & \multicolumn{3}{l}{If $|h| < TOL$, then STOP.}  & \\
    & & \multicolumn{3}{l}{Set $p_0 = p_1$; $p_1 = p_2$; $p_2 = p$;
        $h_1 = p_1 - p_0$; $h_2 = p_2-p_1$;}  & \\
    & & & \multicolumn{2}{l}{$\delta_1 = ( f(p_1) - f(p_0) )/ h_1$;
       $\delta_2 = ( f(p_2) - f(p_1))/h_2$;}  & \\
    & & & \multicolumn{2}{l}{$d = ( \delta_2 - \delta_1)/(h_2+h_1)$; $i = i+1$.}  & \\
    & \multicolumn{4}{l}{End while}  & \\
% & & & & & & \\
\end{tabular}
\end{center}
\end{alertblock}
\end{frame}
\end{document}