\magnification=\magstep1
\centerline{Mathematics 371 -- Numerical Analysis}
\centerline{Comments on Discussion 2 -- Fixed Point Iteration}
\centerline{September 24, 2001}
\bigskip
The following theorem and corollary give the alternate form of 
the Fixed Point Theorem that we were developing in this discussion.

\bigskip
\proclaim Theorem.  Let $g(x)$ be differentiable on a symmetric interval
$J = (p - \delta, p + \delta)$, $\delta > 0$, containing a fixed point 
$p$ of $g$.  
If $|g'(x)| \le k < 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 $p$.  
\par

\bigskip
\noindent
Proof:  If $x_0 \in J$, then by the MVT
$$|x_1 - p| = |g(x_0) - g(p)| = |g'(c)||x_0 - p|\leqno(1)$$
for some point $c$ between $x_0$ and $p$.  Since $x_0$ is in the 
symmetric interval $J$, so is the point $c$, and hence we have by 
hypothesis that $|g'(c)| \le k < 1$.  Hence (1) implies that
$|x_1 - p| \le k |x_0 - p| < |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_n$ between $x_{n-1}$ and $p$  such that
$$|x_n - p| = |g(x_{n-1}) - g(p)| = |g'(c_n)| |x_{n-1} - p|.$$
Arguing by mathematical induction, if we assume that $x_{n-1} \in J$, then
$c_n\in J$ as well, so $|g'(c_n)| \le k < 1$, and
$$|x_n - p| = |g'(c_n)| |x_{n-1} - p| \le k|x_{n-1} - p| \le k^n |x_0 - p|.$$
Since $k < 1$, $\lim_{n\to\infty} k^n = 0$, so 
$\lim_{n\to\infty}|x_n - p| = 0$, and hence $\lim_{n\to\infty}x_n = p$.  //

\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 $I = (p - \delta, q + \delta)$ contained in $J$ where 
$|g'(x)| \le k < 1$ for all $x \in I$.  Hence, we have:

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


