\magnification=\magstep1
\centerline{Mathematics 242 -- Principles of Analysis}
\centerline{Comments on Discussion 6 -- Fixed Point Iteration}
\centerline{November 7, 2000}
\bigskip
The following theorem and corollary give a general pattern including
the behavior you saw in the examples on this discussion.

\bigskip
\proclaim Theorem.  Let $g(x)$ be differentiable on a symmetric interval
$I = (q - a, q + a)$, $a > 0$, containing a fixed point $q$ of $g$.  
If $|g'(x)| \le b < 1$ for all points in $I$, then the iteration sequence 
$x_n = g(x_{n-1})$ constructed starting from any point $x_0 \in I$ will 
converge to $q$.  
\par

\bigskip
\noindent
Proof:  As in part F of the discussion, if $x_0 \in I$, then by the MVT
$$|x_1 - q| = |g(x_0) - g(q)| = |g'(c)||x_0 - q|\leqno(1)$$
for some point $c$ between $x_0$ and $q$.  Since $x_0$ is in the 
symmetric interval $I$, so is the point $c$, and hence we have by 
hypothesis that $|g'(c)| \le b < 1$.  Hence (1) implies that
$|x_1 - q| \le b |x_0 - q| < |x_0 - q|$.  That is:  {\it $x_1$ is closer 
to $q$ than $x_0$ is.\/}  By the same argument using the MVT we have that for 
all $n \ge 1$ there exists some $c$ between $x_{n-1}$ and $q$  such that
$$|x_n - q| = |g(x_{n-1}) - g(q)| = |g'(c)| |x_{n-1} - q|.$$
Arguing by mathematical induction, if we assume that $x_{n-1} \in I$, then
$c\in I$ as well, so $|g'(c)| \le b < 1$, and
$$|x_n - q| = |g'(c)| |x_{n-1} - q| \le b|x_{n-1} - q| \le b^n |x_0 - q|.$$
Since $b < 1$, $\lim_{n\to\infty} b^n = 0$, so 
$\lim_{n\to\infty}|x_n - q| = 0$, and hence $\lim_{n\to\infty}x_n = q$.  //

\bigskip
The hypotheses in this theorem can also be replaced by the following.
If we know that the derivative function $g'(x)$ is continuous on 
some interval $I$ containing $q$ and $|g'(q)| < 1$, then by standard
properties of continuous functions, there will exist a symmetric
interval $J = (q - a, q + a)$ contained in $I$ where $|g'(x)| \le b < 1$ 
for all $x \in J$.  Hence, we have:

\bigskip
\proclaim Corollary.  Assume $g(x)$ is differentiable on an interval $I$
containing a fixed point $q$ and the derivative function $g'(x)$ 
is continuous on that interval.  If $|g'(q)| < 1$, then there 
exists an interval $J \subseteq I$ such that the iteration 
sequence $x_n = g(x_{n-1})$ will converge to $q$ for any choice of 
$x_0 \in J$.\par

\bigskip
This form is sometimes more convenient since we only need to check
the size of the derivative of $g$ {\it at the fixed point}.  
\bye


