Module for Fixed Point Iteration

Check out the new Numerical Analysis Projects page.

    A fundamental principle in computer science is iteration.  As the name suggests, a process is repeated until an answer is achieved. Iterative techniques are used to find roots of equations, solutions of linear and nonlinear systems of equations, and solutions of differential equations.

    A rule or function for computing successive terms is needed, together with a starting value .  Then a sequence of values is obtained using the iterative rule .   The sequence has the pattern
                   (starting value)
       
       
      
       
    
      

    What can we learn from an unending sequence of numbers?  If the numberd tend to a limit, we suspect that it is the answer.  

Finding Fixed Points

Definition (FixedPoint). A fixed point of a function is a number such that .  

Caution.  A fixed point is not a root of the equation  ,  it is a solution of the equation  .  

    Geometrically, the fixed points of a function    are the point(s) of intersection of the curve    and the line  .  

        

Definition (Fixed Point Iteration). The iteration for is called fixed point iteration.  

Theorem (For a converging sequence). Assume that is a continuous function and that is a sequence generated by fixed point iteration.

If  ,  then is a fixed point of .  

Proof.

    The following two theorems establish conditions for the existence of a fixed point and the convergence of the fixed-point iteration process to a fixed point.

Theorem (First Fixed Point Theorem). Assume that , i. e.    is continuous on  .  
Then we have the following conclusions.
(i).    If the range of the mapping satisfies for all , then   has a fixed point in .
(ii).    Furthermore, suppose that is defined over and that a positive constant exists with
      for all  ,  then has a unique fixed point in .    

Proof of (i).

Proof of (ii).

Theorem (Second Fixed Point Fheorem). Assume that the following hypothesis hold true.  
(a)     is a fixed point of a function ,
(b)    ,
(c)     is a positive constant,
(d)    , and
(e)      for all  .  
Then we have the following conclusions.
(i).    If   for all   ,  then the iteration    will converge to the
    unique fixed point .  In this case, is said to be an attractive fixed point.  
(ii).    If   for all   ,  then the iteration    will not converge to .  
    In this case, is said to be a repelling fixed point and the iteration exhibits local divergence.  

Proof.

Remark 1.  It is assumed that in statement (ii).

Remark 2.  Because   is continuous on an interval containing , it is permissible to use the simpler criterion   and   in (i) and (ii), respectively.  

Corollary. Assume that   satisfies hypothesis (a)-(e)  of the previous theorem.  Bounds for the error involved when using    to approximate    are given by         

                  for  ,  
and
          for  .  

Graphical Interpretation of Fixed-point Iteration

    Since we seek a fixed point to ,  it is necessary that the graph of the curve    and the line    intersect at the point .  
The following animations illustrate two types iteration: monotone and oscillating.      

Animations (Fixed Point Iteration  Fixed Point Iteration).  Internet hyperlinks to animations.

Algorithm (Fixed Point Iteration).  To find a solution to the equation   by starting with   and iterating  .

Pseudo-code

Computer Programs (Fixed Point Iteration).

Mathematica Subroutine (Fixed Point Iteration).

Example 1.  Use fixed point iteration to find the fixed point(s) for the function   .

Solution 1.

Example 2.  Use Mathematica's built in subroutine "FixedPointList" and experiment finding the fixed point(s) for the function   .

Solution 2.

Example 3.  Use Mathematica's built in subroutine "FixedPointList" and continue investigation of the "repulsive fixed point" for the function   .

Solution 3.

Research Experience for Undergraduates

Fixed Point Iteration  Fixed Point Iteration  Internet hyperlinks to web sites and a bibliography of articles.  

(c) John H. Mathews 2004