Background

    Iterative techniques will now be introduced that extend the fixed point and Newton methods for finding a root of an equation.  We desire to have a method for finding a solution for the system of nonlinear equations
    
              
    (1)
            .  
    
Each equation in (1) implicitly defines a curve in the plane and we want to find their points of intersection.  Our first method will be be fixed point iteration and the second one will be Newton's method.

Definition (Jacobian Matrix).  Assume that are functions of the independent variables , then their Jacobian matrix   is  

        .  
    
Similarly, if   are functions of the independent variables  , then their Jacobian matrix   is  

        .  

Generalized Differential

    For a function of several variables, the differential is used to show how changes of the independent variables affect the change in the dependent variables. Suppose that we have  
    
        
        
        
        
        
    
Suppose that the values of these functions in are known at the point and we wish to predict their value at a nearby point .  Let  ,  denote differential changes in the dependent variables and , and      denote differential changes in the independent variables. These changes obey the relationships  

        ,
        
        ,
        
        .

If vector notation is used, then this can be compactly written by using the Jacobian matrix. The function changes are  dF  and the changes in the variables are denoted  dX.  

          
    or    
        .  

Convergence near a Fixed Point  

    In solving for solutions of a system of equations, iteration is used.  We now turn to the study of sufficient conditions which will guarantee convergence.

Definition (Fixed Point).  A fixed point for the system of two equations

        ,    
        .  

is a point such that .  Similarly, in three dimensions a fixed point for the system of three equations

        ,  
        ,  
        .  

is a point such that .

Definition (Fixed Point Iteration).  For a system of two equations, fixed point iteration is  

        ,  and  
        ,    


Similarly, for a system of three equations, fixed point iteration is

           
        ,  and
        ,    

Theorem (Fixed-Point Iteration).  Assume that all the functions and their first partial derivatives are continuous on a region that contains the fixed point or , respectively.  If the starting point is chosen sufficiently close to the fixed point, then one of the following cases apply.

Case (i)  Two dimensions.   If is sufficiently close to and if  

        ,  

        ,  

then fixed point iteration will converge to the fixed point .  


Case (ii)  Three dimensions.   If is sufficiently close to and if  

         + + < 1,  

         + + < 1,  

         + + < 1,  

then fixed point iteration will converge to the fixed point .  

    If these conditions are not met, the iteration might diverge, which is usually the case.

Proof  Nonlinear Systems  Nonlinear Systems  

Algorithm (Fixed Point Iteration for Non-Linear Systems) In two dimensions, solve the non-linear fixed point system  
          
given one initial approximation , and generating a sequence which converges to the solution  ,  i.e.           
           

Algorithm (Fixed Point Iteration for Non-Linear Systems)  In three dimensions, solve the non-linear fixed point system  
             
given one initial approximation , and generating a sequence which converges to the solution  ,  i.e.   
          

Algorithm (Fixed Point Iteration for Non-Linear Systems)  Solve the non-linear fixed point system  

        ,  

given one initial approximation , and generating a sequence which converges to the solution  ,  

        .  

Remark. First we give a subroutine for performing fixed point iteration.

Computer Programs  Nonlinear Systems  Nonlinear Systems  

Mathematica Subroutine (Fixed Point Iteration in n-Dimensions).

Example 1.  Use fixed point iteration to find a solution to the nonlinear system  
           
Solution 1.

Newton's Method for Nonlinear Systems

    We now outline the derivation of Newton’s method in two dimensions.  Newton’s method can easily be extended to higher dimensions.  Consider the system

                
(1)
        

which can be considered a transformation from the  xy-plane to the uv-plane.  We are interested in the behavior of this transformation near the point whose image is the point .  If the two functions have continuous partial derivatives, then the differential can be used to write a system of linear approximations that is valid near the point :

          

then substitute the changes   for  ,  respectively.  Then we will have

          or  
(2)        
        .  

    Consider the system (1) with u and v set equal to zero,

                
(3)
        

Suppose we are trying to find the solution and we start iteration at the nearby point , then we can apply (2) and write

        .

Since , this becomes  

        ,
or  

        .  

    When we solve this latter equation for    we get   and the next approximation is

        

Theorem (Newton-Raphson Method for 2-dimensional Systems).  To solve the non-linear system  

        ,  

given one initial approximation , and generating a sequence which converges to the solution ,  i.e.  

        .  

Suppose that   has been obtained, use the following steps to obtain .  

Step 1.     Evaluate the function   .

Step 2.  Evaluate the Jacobian   .  

Step 3.  Solve the linear system      for   .  

Step 4.  Compute the next approximation   .  

Proof  Nonlinear Systems  Nonlinear Systems  

Computer Programs  Nonlinear Systems  Nonlinear Systems  

Mathematica Subroutine (Newton's Method for Systems in n-Dimensions).

Example 2.  Use Newton's method to solve the nonlinear system  
            
Solution 2.

Example 3.  Show that the systems in examples 1 and 2 are equivalent.  The system  
          
is equivalent to the system  
          
Solution 3.

Example 4.  Show how Newton's method is in reality a fixed point iteration scheme.  Use the system    
            
Solution 4.

Exercise 5.  Observe that the subroutine NewtonSystem involves vector functions and is not dependent on the dimension.
Use the subroutine NewtonSystem to solve the nonlinear system in 3D space:  
           
          
          
Hint.  There are four solutions.  Good starting vectors are .  
Solution 5.

Old Lab Project (Non-Linear Systems  Non-Linear Systems).  Internet hyperlinks to an old lab project.  

Research Experience for Undergraduates

Non-Linear Systems  Non-Linear Systems  Internet hyperlinks to web sites and a bibliography of articles.  

Download this Mathematica Notebook Fixed Point Iteration and Newton's Method in 2D and 3D

Return to Numerical Methods - Numerical Analysis

(c) John H. Mathews 2004