Newton iteration

gif image

Newton's method to find the zeros of the cubic polynomial p(z)=z^3-1, is to iterate the function N(z)=z-p(z)/p'(z). The behavior of the iterates depends on the initial "guess". In class, we used an estimate of the remainder in the Taylor series for N to prove that if the initial guess is sufficiently close to a zero of f, then the iterates converge quadratically (number of correct digits doubles for each iteration). The situation is more complicated for guesses which are not near a root. The three roots of the cubic (which you can find explicitly by hand in this example) are colored red, green and blue according to the scheme introduced earlier in the quarter. The picture above represents the function made of 200 compositions of N with itself. So a point is colored red if, after 200 iterations its image is very close to the red root. In other words, the red regions are the initial guesses that end up at the red root.

This example has the remarkable property that the open set corresponding to all the red regions has the same boundary as the open set corresponding to all the green regions, and the same is true for the blue regions. Ask an artistic friend to try to draw a picture using 3 colors with this property!