Building Fractals using Dynamical Systems:  Newton's Method

Comp110 Course Module

Newton's Method as a Dynamical System

A third interesting dynamical system is based on Newton's method for finding the roots of a complex polynomial.  A root of a complex polynomial f[z] is a complex number (OverHat[z]) such that f[(OverHat[z])]=0.  Newton's method finds a root of a polynomial f[z] in an iterative fashion.  Given a guess (Subscript[z, i]) for the location of the root, a better approximation can be found by intersecting the tangent line through f[(Subscript[z, i])] with the xy-plane and using this intersection as the next guess (Subscript[z, i+1]) for the location of the root. The basic iteration for Newton's method has the form

(Subscript[z, i+1])=(Subscript[z, i])-((f[(Subscript[z, i])])/(f'[(Subscript[z, i])])).

Newton's method converges to a root of a polynomial as long as we never try to evaluate the given function at a point where the derivative is zero.  But given any specific starting value, which of the possibly many roots of the polynomial is the method going to find?  An interesting way to analyze this question is to run the Newton iteration for a large number of points in the plane and color the starting point according to the root to which the algorithm converges.  For example, in the following figure we colored points in four different colors depending on which of the four roots of the following quartic polynomial f is converged to by Newton's method.

Clear[f];

f[z_]:=(z-0.5-0.5I)(z+0.5-0.5I)(z-0.5+0.5I)(z+0.5+0.5I)

Your task in the final set of problems for this module is to generate pictures such as this one.