Newton Basin
Chanteperdrix Guilhem(mfn04)

NEWTON'S METHOD BRIEF OVERVIEW











The well known Newton-Raphson Method:

    This method is generally used to find, or more precisely approach, a zero of a real function. It can be classified among iterative methods, and one iteration of this method can be considered as a discrete dynamical system. We can so give a first definition of the Newton's (Raphson) method :

    Newton's method first definition

    It can be explain by this picture :

    Example of some iterations for the Newton's Method

    That is to say that x_(k+1) is the intersection between the tangent of f in x_k and y=0. The recurrent relation is obtain by this way.

A more general definition:
In the first definition, we have supposed, implicitly, that all x_k were elements of the definition's set of f. Speaking about real function, that was not really important, because generally, the function is convex near the zero (locally) and the definition's set of f can be reduce to be a stable set by f.

But now :

A more general definition

and the following conditions must be verified to give a sense to the above definition :

Conditions for Newton's Method

These conditions are not sufficient to ensure a convergence (for theorems about Newton's method convergence, and also more general definition, see [1] ), but in our case the convergence is not the purpose.

Sensibility to initial conditions :
Let's go back to the case of a real function, and more precisely to the case of a polynomial. As we said before, near a zero, the polynomial is convex (except if the zero is an inflexion point), and we can suppose that the derivative is strictly positive (the polynomial increases). This situation is really realistic, because it is easy to be in it (see above figure). More precisely :
 
 

Convergence result





This convergence result implies two remarks :

  • the method is very fast...
  • ...if you initialize it well  : that is the sensibility to initial condition !
  • With such a result, we can understand that for a polynomial, it will exist segment (having a zero) where the method will converge. But what will happen if x_0 is not well chosen ?

    We consider now the polynomial x->x^3-x. It has three roots : (-1,0,1). Because of symmetry, we can suppose x_0 positive. If we represent the root obtained with the Newton's method initialized with an element of [0,2], we have :

    Root obtained versus initialization

    It appears clearly that between 0.4 and 0.6, things happen...

    So we can do the same thing between 0.4 and 0.6 :

    Zoom

    And if we go on, we will always find figures like the two above.
    So the question is : what will happen if we consider the complex polynomial : z->z^3-z and a complex initialization z_0 ?

    NB : the two above figure has been obtained with Matlab. The program is available here.


    up to presentation
    back to contents
    down to results