\magnification=\magstep1
\centerline{Mathematics 242 -- Principles of Analysis}
\centerline{Fixed Point Iteration, Revisited}
\centerline{November 1, 2000}
\bigskip
\noindent
{\it Background}
\bigskip
Last time, we proved the ``Most Valuable Theorem'':
\bigskip
\proclaim Mean Value Theorem.  Let $f(x)$ be continuous
on $[a,b]$ and differentiable on $(a,b)$.  Then there
exists a $c \in (a,b)$ such that $f'(c) = {f(b) - f(a)\over b-a}$.
\par

\noindent
We also saw how the MVT establishes connections between properties
of $f'(x)$ (such as the sign of the derivative), and properties
of the function $f(x)$ (such as whether $f$ is increasing or
decreasing).  Today, we will see another connection dealing
with properties of a function under {\it iteration}.  

We will use the following ideas.  Recall that we have seen
(Problem Set 4) that if $g$ is continuous and $g: [a,b] \to [a,b]$,
then $g$ has a {\it fixed point} $p \in [a,b]$ -- a point
satisfying $g(p) = p$.  We can attempt to find such a point
by starting at some $x_0$ and iterating $g$:
$$\eqalign{x_1 &= g(x_0)\cr
           x_2 &= g(x_1)\cr
           x_3 &= g(x_2)\cr
               &\,\vdots\cr
           x_{n+1} &= g(x_n)\cr}\leqno(1)$$
\bigskip
\noindent
{\it Discussion Questions}
\bigskip
\item{A)} If $g$ is continuous and an iteration sequence 
$x_n$, constructed using $g$ as in (1) above converges to some 
$q \in {\bf R}$, must $q$ satisfy $g(q) = q$?  Why or why not?
\bigskip
\item{B)} Try the following choices for $g$ and $x_0$.  Using
a calculator if necessary, determine whether it appears that the 
sequence $x_n$ constructed as in (1) above is converging to 
some $q \in {\bf R}$.  
\bigskip
\itemitem{1)}  $g(x) = \cos(x)$, $x_0 = 0$.
\itemitem{2)}  $g(x) = {x^2 + 5\over 2x}$,  $x_0 = 1$.
\itemitem{3)}  $g(x) = (x^3 + 2x^2 - x - 2)/10$, $x_0 = 1$ and 
$x_0 = 3$.
\bigskip
\item{C)}  For each of the functions in question B, plot
$y = g(x)$ together with the line $y = x$.  How many 
fixed points does each function have?  Where are they, 
approximately, and 
how do they correlate with the points you found in 
question B?  
\bigskip
\noindent
You can visualize an iteration sequence this way:  
Draw the graph $y = g(x)$ together with the line
$y = x$.  Starting
from $x = x_0$ (on the $x$-axis), draw a vertical
line segment up or down to the 
point $(x_0,g(x_0))$ on the graph $y = g(x)$.  Then connect
that point to the point on the line $y = x$ with the same
$y$-coordinate.  The vertical line through that point 
intersects the $x$-axis in $x_1 = g(x_0)$ (why?).  Then
repeat the process to get $x_2 = g(x_1)$, etc.
\bigskip
\item{D)}  Draw diagrams using this idea to illustrate
the iteration sequences from question B.  Do the same for
iteration sequences for 
$g(x) = x^3 + 2x^2 - x - 2$ (10 times the polynomial from 
B, part 3), with $x_0 = 0$ and $x_0 = 3$.
\bigskip
\item{E)}  From the examples you have seen, given a
function $g(x)$ and a fixed point $q$ of $g$, when does
it appear that iteration starting from $x_0$ close
to $q$ will yield a sequence $x_n$ converging to $q$?
\bigskip
\item{F)} If we assume that $g(x)$ is differentiable
on an interval containing a fixed point $q$, 
the Mean Value Theorem can be used to prove
a statement guaranteeing convergence to the fixed
point.  Think about the following question:  Given
$q = g(q)$ and $x_0$ near $q$, if $x_1 = g(x_0)$, then
by the MVT,
$$|x_1 - q| = |g(x_0) - g(q)| = |g'(c)||x_0 - q|$$
for some $c \in (x_0,q)$.
When is it guaranteed that $x_1$ is {\it closer to
 $q$ than $x_0$ was?}.  Then consider subsequent 
steps in the iteration.
\bigskip
\noindent
{\it Assignment}
\bigskip
Group write-ups, due Monday, November 6.
\bye  
