Chanteperdrix Guilhem(mfn04)

__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 :

It can be explain by this picture :

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.

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 :

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

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.

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 :

This convergence result implies two remarks :

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 ?the method is very fast... ...if you initialize it well : that is the sensibility to initial condition!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 :

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 :

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