\magnification=\magstep1
\centerline{Mathematics 371 -- Numerical Analysis}
\centerline{Discussion 2 -- Fixed Point Iteration, Theory}
\centerline{September 14, 2001}
\bigskip
\noindent
{\it Background}
\bigskip
Recall that we have introduced
the idea of {\it fixed point iteration} as a method to solve
equations $f(x) = 0$.  We first {\it rearrange the equation}
to the form $x = g(x)$ using ``reversible'' operations
so that $f(x) = 0 \Leftrightarrow x = g(x)$, then attempt to find a point 
$p$ satisfying $p = g(p)$
by starting at some $x_0$ and iterating $g$ to construct the sequence:
$$\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)$$
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
\noindent
Also recall the ``Most Valuable Theorem'' of differential calculus:
\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
In MATH 242, you 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 {\it fixed point iteration} for numerical root-finding.
\bigskip
\noindent
{\it Discussion Questions}
\bigskip
\item{A)} If 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$?  What condition
on $g$ do you need to assume to say this?
\bigskip
\item{B)}  From the examples you have seen, given a
function $g(x)$ and a fixed point $p$ of $g$, when does
the iteration starting from $x_0$ close
to $p$ yield a sequence $x_n$ converging to $p$?
Make a conjecture (an ``educated guess'') about a general
statement along these lines.
\bigskip
\item{C)} If we assume that $g(x)$ is differentiable
on an interval containing a fixed point $p$, 
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 - p| = |g(x_0) - g(p)| = |g'(c)||x_0 - q|$$
for some $c \in (x_0,p)$.
When is it guaranteed that $x_1$ is {\it closer to
 $p$ than $x_0$ was?}  Then consider subsequent 
steps in the iteration, and prove your statement from B,
or perhaps a modification of what you originally thought.
\bigskip
\item{D)}  What can you say about the {\it order of convergence}
of fixed point iteration?  If $x_n\to p$ is a convergent 
iteration sequence, for what function $h(n)$ is $x_n = p + O(h(n))$?
Explain.
\bigskip
\noindent
{\it Assignment}
\bigskip
Group write-up, due Wednesday, September 19.
\bye  
