Newton’s method for single variable (complex) functions.

The complex polynomial 

f(z) = (z^3)- 1

has three roots: (e^i0), (e^(i((2π)/3))), and (e^(i  4(π/3))) which we can check easily enough.

f[z_] := (z^3)-1

f[1]

f[Exp[I ((2π)/3)]]

f[Exp[I ((4π)/3)]]

The Newton iteration for (z^3)-1

As usual,

g[z_] := z - (((z^3)-1)/(3 (z^2)))

We can now check that this works for the solutions we know about

Solutions = FullSimplify[ {1,Exp[I ((2π)/3)],Exp[I ((4π)/3)]}]

FullSimplify[g /@ Solutions]

Now we’ll try to use the iteration.

NestList[g,2.0+3.0 I,17] // TableForm

Plotting the iteration.

Plotting the solution shows you that this iteration hops around quite unpredictably before settling down to converge to the solution. In the graphic below, we see the result of i steps of the Newton iteration for (z^3)-1 starting at the marked point.

ToPoint[z_] := {Re[z],Im[z]};

PointSolutions =ToPoint /@ Solutions;

SolutionsGraphic= Graphics[{{Red,PointSize[0.025],Point[PointSolutions[[1]]]},{Green,PointSize[0.025],Point[PointSolutions[[2]]]},
{Blue,PointSize[0.025],Point[PointSolutions[[3]]]}}];

Manipulate[Show[SolutionsGraphic,
Graphics[
Line[ToPoint /@ NestList[g,pt[[1]]+I pt[[2]],i]]
],Axes->True,PlotRange->{{-6,6},{-6,6}},ImageSize-> Large],{i,1,22,1},{{pt,{2,3}},Locator}]

Dependence on starting conditions

The dependence on the initial position is quite sensitive. To see it, we’ll color each point on the complex by a color corresponding to the final solution obtained by Newton iteration.

SolutionColor[{a_,b_}] := 
Quiet[First[Nearest[PointSolutions,ToPoint@FixedPoint[g,a+b I]]] /. {{1,0}->ColorData[24][4],{-1/2,(Sqrt[3])/2}-> ColorData[24][5], {-1/2,-(Sqrt[3])/2}-> ColorData[24][6]}];

Block[{σ = 200},
ArrayPlot[
ParallelMap[SolutionColor,Table[{x+1.0/(2σ),y+1.0/(2σ)},{y,-1,1,1/σ},{x,-1,1,1/σ}],{2}],ImageSize-> Large]
]

(If you have some cycles to burn, you can make a higher resolution plot by opening up the code box by clicking on the frame on the right-hand side of the picture and changing the resolution σ to a larger number.)

Points where Newton’s method won’t converge at all!

If you start Newton’s method in the middle of a solid colored region, it will converge to the corresponding root. But what about the boundaries between the regions? These are actually a weird, lacy set of points where Newton’s method will not converge to any of the three roots. Those points are called a Julia set, and there’s a built-in way to make nice plots of them.

If we write down the Newton iteration explicitly as a rational function, we can feed it to JuliaSetPlot and get:

JuliaSetPlot[z - ((z^3)-1)/(3(z^2)),z,PlotRange->{{-1,1},{-1,1}},PlotTheme->"Business",ImageSize->Large]