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 numbers 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  Fixed Point Iteration  Fixed Point Iteration  

    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  Fixed Point Iteration  Fixed Point Iteration  

Theorem (Second Fixed Point Theorem). 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  Fixed Point Iteration  Fixed Point Iteration  

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.      

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

Computer Programs  Fixed Point Iteration  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.

Various Scenarios and Animations for Fixed Point Iteration.

Example 4.  Convergence: Monotone Increasing  Find the solution to  .  Use the starting approximation  
Solution 4.

Example 5.  Convergence: Monotone Decreasing  Find the solution to  .  Use the starting approximation    
Solution 5.

Example 6. Convergence: Spiral  Find the solution to  .  Use the starting approximation    
Solution 6.

Example 7. Divergence: Monotone Increasing  Find the solution to  .  Use the starting approximation    
Solution 7.

Example 8. Convergence: Monotone Decreasing  Find the solution to  .  Use the starting approximation    
Solution 8.

Example 9. Divergence: Spiral  Find the solution to  .  Use the starting approximation    
Solution 9.

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

Research Experience for Undergraduates

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

Download this Mathematica Notebook Fixed Point Iteration

Return to Numerical Methods - Numerical Analysis

(c) John H. Mathews 2004