\magnification = \magstep1
\centerline{Mathematics 171 -- Numerical Analysis I}
\centerline{Discussion 3 -- Iteration sequences: $x_n = g(x_{n-1})$}
\centerline{Summary of Results}
\bigskip
\noindent
{\bf Questions} 
\bigskip\noindent
A) Suppose $g(x) \in [a,b]$ for all $x \in [a,b]$.  Must
$g$ have a fixed point on the interval $[a,b]$?  Why or why not?
What hypotheses on $g$ do you need for your conclusion?
\bigskip
Under the assumption that $g(x)$ is a {\it continuous\/} function
on $[a,b]$ taking values in $[a,b]$, then there must be at least 
one (possibly more) fixed points in $[a,b]$.  The reason is the following.
If $g(a) = a$, then $a$ is itself a fixed point.  Otherwise, $g(a) > a$
since $g(a) \in [a,b]$.  Similarly, either $g(b) = b$ and $b$
is itself a fixed point, or else $g(b) < b$.  We need only consider the
case that neither $a$ nor $b$ is a fixed point.  Then 
$g(x) - x$ is also continuous on $[a,b]$, positive at $x = a$,
and negative at $x = b$.
By the Intermediate Value Theorem, $g(x) - x$ must be zero for
some $x = c$ in $[a,b]$.  But then $g(c) = c$, so $c$ is a fixed point
of $g$.
\bigskip\noindent
B) Can you tell whether a fixed point of $g$ is going to be attracting
or repelling by looking at the graph $y = g(x)$ at (or near) the fixed point?
Find at least two different examples of each type and develop a conjecture
based on your evidence.  (Suggestion: try simple functions, 
like $g(x) = x^r$ for various values of $r$.)
You will probably want to try consider how the
iteration sequence $x_n = g(x_{n-1})$ might be constructed graphically.  
\bigskip
We came to the conclusion that at each example we tried, the fixed
point iteration would apparently converge to the limit $L$ provided
that $|g'(L)| < 1$, and $x_0$ was chosen ``close enough'' to $L$.
Here's another way to see this, graphically.  Suppose that $g'(L) > 0$.
If we plot the sequences $x_n$, in each case, we can see that
$x_{n+1}$ can be produced from $x_n$ by 
\item{$\bullet$} first going vertically from $(x_n,0)$ to the point
$(x_n,g(x_n)) = (x_n, x_{n+1})$ on the graph $y = g(x)$, then 
\item{$\bullet$} going horizontally to the point $(x_{n+1}, x_{n+1})$
on the graph $y = x$, 
\item{$\bullet$} going back down to $(x_{n+1},0)$

If $|g'(L)| < 1$, we move toward $(L,L)$, while if $|g'(L)| >1$, 
we move away.
\bigskip\noindent
C) Under what conditions would it be true that
$|g(x) - g(L)| < |x - L|$ (i.e. $g(x)$ is closer to the fixed point
than $x$ is)?  Suppose your conditions are true on a whole interval
containing the fixed point.  What will happen if you iterate
$x_n = g(x_{n-1})$ starting from $x_0$ in the interval?
\bigskip
If $g'$ exists and satisfies $|g'(t)| < 1$ for {\it all\/} $t$ between $x$ 
and $L$, then this will be true by the Mean Value Theorem.
To get a convergence criterion for fixed point iteration, we saw
\proclaim ``Holy Cross Fixed Point Theorem''.
Let $g$ be a function whose derivative is continuous on an interval $I$ 
containing a fixed point $L$ of $g$, and assume $|g'(L)| < 1$.
Then there exists an interval $I' \subseteq I$ such that fixed point
iteration $x_{n+1} = g(x_n)$ will converge to $L$ if we start from 
any $x_0 \in I'$.  \par
\bigskip
\noindent
{\bf Proof.}  Pick any $k$ with $|g'(L)| < k < 1$.
Since $g'$ is continuous, and $|g'(L)| < 1$, there is an interval 
$I'$ containing $L$ such that $|g'(x)| \le k$ for all $x \in I'$.  Moreover,
by passing to a smaller interval (``shaving off one side of 
the interval'') if necessary, we may assume 
that $I'$ is symmetric about $L$:  $I' = (L - \delta, L + \delta)$.
Pick any $x_0\in I'$. We claim that iteration of $g$ starting from 
$x_0$ must produce a sequence converging to $L$.  At the first step
$x_1 = g(x_0)$, so by the Mean Value Theorem
$$|x_1 - L| = |g(x_0) - g(L)| = |g'(t_1)| |x_0 - L|\leqno(1)$$
for some $t_1$ between $x_0$ and $L$.  But then $t_1 \in I'$, so
$|g'(t)| \le k < 1$.  Hence
$$|x_1 - L| \le k |x_0 - L| < |x_0 - L|\leqno(2)$$
Since $I'$ is symmetric about $L$, this says $x_1 \in I'$ also
(it's on the same side of $L$ as $x_0$ if $g'(L) > 0$, and on the 
other side if $g'(L) < 0$).  Similarly, by induction, assume
we have proved that 
$$|x_n - L| \le k^n |x_0 - L| \leqno(3)$$
As in (1) and (2) above, 
$$|x_n - L| = |g(x_{n-1}) - g(L)| = |g'(t_n)| |x_{n-1} - L|$$
for some $t_n \in I$.  Hence since $|g'(t_n)| < k$, using the 
induction hypothesis (3), we have
$$|x_n - L| \le k^n |x_0 - L|$$
for all $n \ge 0$.  
As $n \to \infty$, the right-hand side goes to zero (remember
$k < 1$), so the sequence $\{x_n\}$ is converging to $L$.
\bye 
