\documentstyle[12pt,psfig]{article}
%\documentstyle[12pt,ncs]{article}
\topmargin=-1.25in
\oddsidemargin=0in
%\evensidemargin=0in
\textwidth=6.5in
\textheight=10.5in
\parindent=0in
%\parskip=10pt
\pagestyle{empty}

%\newfont{\cmss}{cmss12.tfm}
\tolerance=3000
%\setcounter{chapter}{1}

\begin{document}

\input 370top

\centerline{{\it Class 15}: {\bf Wednesday October 07}}

\begin{description}
\item[SUMMARY] Generalizing Root-Finding Algorithms: Fixed Point Iteration
\vspace*{-12pt}
\item[READING] Burden \& Faires, 54--63
\end{description}

{\large\bf  Fixed Point}\\
A function $g(x)$ is said to have a {\bf fixed point} $p$ if $g(p) = p$. In other words, if the value you put into the function is exactly the same value that you get out.\\

Solving the equation $g(x) = f(x) - x = 0$ is identical to finding the fixed point of $f(x)$ AND the zero of $g(x)$. So, we are dealing with another possible method for finding the root of a one-variable equation.\\

{\bf  Fixed Point Iteration}\\
The iteration process is $p_n = g(p_{n-1})$ for $n=1,2,3, \dots$. This process is also called {\bf picard} or {\bf functional iteration} or sometimes {\bf repeated substitution}.

\underline{\bf  Example}\\
Consider the function $g(x) = \log(x+4)$ on [1,2]. Each one of you should pick a starting value, (i.e. $p_0=1$) and then actually execute a number of Picard iterations. Record your results below:

\begin{tabular}{|c|c|}
\hline
$p_n$ & $g(p_n)$ \\
\hline
\hspace{1in}  & \hspace{1in}  \\
  &  \\
  &  \\
  &  \\
  &  \\
  &  \\
  &  \\
  &  \\
  &  \\
\end{tabular}
% &
%\centerline{\psfig{figure=fig/10.07-fig5.ps,height=2.in,angle=270}}
%\end{tabular}

Do you think your sequence is converging? How many fixed points does $g(x)=\log(x+4)$ have? What's the value of its fixed point(s) to 4 decimal places?
\vfill

{\large\bf Uniqueness: The Fixed Point Theorem}\\
If $g$ is continuous on [a,b] and $g(x) \in [a,b]$ for all $x \in [a,b]$ then $g$ has a fixed point in [a,b]. {\bf In addition}, if $0<|g'(x)| < 1$ for all $x \in [a,b]$ then $g$ has a {\bf unique fixed point} in [a,b]\\

Using the above theorem what can we say about our example function?\\
\vfill

{\bf Convergence Criteria for Picard Iteration}\\
The iteration process $p_n = g(p_{n-1})$ for $n=1,2,3, \cdots$ will converge to a unique solution for any  initial value $p_0$ in [a,b] if $g'$ exists on (a,b) and $0<|g'(x)| < 1$ for all $x \in [a,b]$\\

Using the above theorem what can we say about our example iteration process?\\

\vfill

\newpage
\underline{\sc  GroupWork}\\
Take a look at the following examples of possible functions to do fixed-point interation on and in groups of two or three graphically indicate what happens.
Try the initial guesses like  $p_0 = 0$ and $p_0 = 1$.

%\begin{tabular}{p{3.5in}p{3.5in}}
\begin{tabular}{c}
{\psfig{figure=fig/10.07-fig1.ps,height=4.5in,angle=270}} \\
{\psfig{figure=fig/10.07-fig2.ps,height=4.5in,angle=270}}
\end{tabular}
%\centerline{\psfig{figure=02.03-fig.ps,height=2in,angle=270}}

\newpage

\begin{tabular}{c}
%\begin{tabular}{p{3.5in}p{3.5in}}
{\psfig{figure=fig/10.07-fig3.ps,height=4.5in,angle=270}}\\
{\psfig{figure=fig/10.07-fig4.ps,height=4.5in,angle=270}}
\end{tabular}
%\centerline{\psfig{figure=02.03-fig.ps,height=2in,angle=270}}

\vfill
\newpage
The example functions were
$$
\begin{array}{ll}
g_1(x) = \frac{1}{2}x^2 + \frac{1}{4}  & \hspace{1in} g'_1(x) = \\
g_2(x) = 2e^{-1.5x}  & \hspace{1in} g_2^{\prime}(x) = \\
g_3(x) = \cos^2(x) & \hspace{1in} g_3^{\prime}(x) = \\
g_4(x) = \sin(x+\frac{1}{4})  & \hspace{1in} g_4^{\prime}(x) = \\
\end{array}
$$
Which of these functions converged using functional iteration?\\
\vfill
Can you explain why?\\
 (Think about the behavior of the derivative on the interval of interest in each case)
\vfill
\vfill
Which of the iterations exhibit {\bf monotone convergence}?\\

Which of the iterations exhibit {\bf oscillating convergence}?\\

Consider these two other functions, \\
$g_5(x) = 2 \ln( 2 x -1)$ on [0,0.5] and $g_6(x) = e^{-10x}$ on [1,3]
\vfill

Will Picard Iteration converge or diverge for these examples? \\
(prove your answer graphically on the next page)

\newpage
\underline{\bf  Graphical Examples}\\
Look at these plots of $g_5(x) 2 \ln( 2 x -1)$ and $g_6(x) = e^{-10x}$ and graphically indicate whether Picard iteration converges or diverges. In either case classify the convergence as either {\bf monotone} or {\bf oscillating}

%\begin{tabular}{p{3.5in}p{3.5in}}
\begin{tabular}{c}
{\psfig{figure=fig/02.07-fig1.ps,height=4in,angle=270}} \\
{\psfig{figure=fig/02.07-fig3.ps,height=4in,angle=270}}
\end{tabular}

\newpage
\underline{\bf  Example}\\
\begin{enumerate}
\item Let us try to use Picard Iteration to approximate ${\displaystyle \sqrt[5]{7}}$, assuming $p_0=1$\\

\item What function $f(x)$ would we have to use to find a zero for in order to compute $7^{1/5}$?
\vfill

\item What function would we have to use to do functional iteration on? [i.e. what is $g(x)$?]\\ Is there only one such function? If you can, write down three possible $g(x)$ functions which have the fixed point $7^{1/5}$
\vfill
\vfill

\item How will you decide which function to do the functional iteration on? [i.e.which one will converge the fastest]
\vfill
\vfill
\item Try running {\tt q:$\backslash$calculus$\backslash$370$\backslash$ALG22.TRU} on your choices and see if this confirms your choice of function above...

\vfill
\vfill
\vfill

\end{enumerate}
\end{document}
