The complex version of Newton's method also appears to work quite well. Recall, however, that with functions defined on the reals, not every initial guess produces a sequence that converges to a solution. Example 4.8 shows that the same is true in the complex case.
Example 4.8. Show that Newton's method fails for the function f (z) = z2+1 if the initial guess is a real number.
Solution. From Example 4.7 we know that, for any guess z as a solution of z2+1 = 0, the next guess at a solution is N (z) = z - f' (z)f (z) = z2-1
2 z . We let z0 be any real number and {zk} be the sequence of iterations produced by the initial seed z0. If for any k, zk=0, the procedure termi-nates, as zk+1 will be undefined. If all the terms of the sequence {zk} are defined, an easy induc-tion argument shows that all the terms of the sequence are real. Because the soluinduc-tions of z2+1 = 0 are z = ±ⅈ, the sequence {zk} cannot possibly converge to either solution. In the exercises we ask you to explore in detail what happens when z0 is in the upper or lower half-plane.
Extra Example 1. Investigate Newton's method for finding the roots of f (z) = z3+1.
Given the initial seed z0 determine if the sequence {zk} converges to one of the roots
The case for cubic polynomials is more complicated than that for quadratics. Fortunately, we can get an idea of what's going on by doing some experimentation with computer graphics. We begin with the cubic polynomial f (z) = z3+1. (Recall that the roots of this polynomial are at z = - 1, 12 + 3
2 ⅈ, 12- 3
2 ⅈ.) We associate a color with each root (blue, red, and green, respec-tively). We form a rectangular region R, which contains the three roots of f (z), and partition this region into equal rectangles Ri j. We then choose a point zi j at the center of each rectangle and
2 Chapter04Section02.nb
for each of these points we apply the following algorithm.
1. With N (z) = z -f' (z)f (z) = z - z3 z3+21 = 2 z3-1
3 z2 , compute N (zi j). Continue computing succes-sive iterates of this initial point until we either are within a certain preassigned tolerance (say, ) of one of the roots of f (z) = 0, or until the number of iterations has exceeded a preassigned maximum.
2. If Step 1 leaves us within of one of the roots of f (z), we color the entire rectangle Ri j with the color associated with that root.
Otherwise, we assume that the initial point zi j does not converge to any root, and we color the entire rectangle yellow.
Note that this algorithm doesn't prove anything. In Step 2, there is no a priori reason to justify the assumption mentioned, nor is there any necessity for an initial point zi j to have its sequence of iterates converging to one of the roots of f (z) = 0, just because a particular iteration is within of that root. Finally, the fact that one point in a rectangle behaves in a certain way does not imply that all the points in that rectangle behave in a like manner. Nevertheless, we can use this algorithm as a basis for mathematical explorations. Indeed, computer experiments such as the one described have contributed to a lot of exciting mathematics during the past 20 years. The color plates located on the inside front and back covers of this book illustrate the results of applying our algorithm to various functions. Color plate 1shows the results for the cubic polynomial
f (z) = z3+1. The points in the blue, red, and green regions are those "initial guesses" that will converge to the roots z = -1, 12 + 3
2 ⅈ, 12- 3
2 ⅈ -1, respectively. (The roots themselves are located in the middle of the three largest colored regions.) The complexity of this picture becomes apparent when you observe that, wherever two colors appear to meet, the third color emerges between them. But then, a closer inspection of the area where this third color meets one of the other colors reveals again a different color between them. This process continues with an infinite complexity.
Color Plate 1. Newton’s method applied to f (z) = z3+1.
There appear to be no yellow regions with any area in Color plate 1, indicating that at least most initial guesses z0 at a solution to z3+1 = 0 will produce a sequence {zk} that converges to one of the three roots. Color plate 2 demonstrates that this outcome does not always occur. It shows the results of applying the preceding algorithm to the polynomial
f (z) = z3+ (-0.26 + 0.02 ⅈ) z + (-0.74 + 0.02 ⅈ). The yellow area shown is often referred to as the rabbit. It consists of a main body and two ears. Upon closer inspection (color plate 3) you
can see that each of the ears consists of a main body and two ears. Color plate 2 is an example of a fractal image. Mathematicians use the term fractal to indicate an object that have this kind of recursive structure.
Color Plate 2. The rabbit fractal of
f (z) = z3+ (-0.26 + 0.02 ⅈ) z - 0.74 + 0.02 ⅈ.
Color Plate 3. A zoom of the rabbit fractal of
f (z) = z3+ (-0.26 + 0.02 ⅈ) z - 0.74 + 0.02 ⅈ.
In 1918 the French mathematicians Gaston Julia and Pierre Fatou noticed the fractal phe-nomenon when exploring iterations of functions not necessarily connected with Newton's method.
Beginning with a function f(z) and a point z0, they computed the iterates z1=f (z0),
z2=f (z1), ... , zk+1=f (zk), and investigated properties of the sequences {zk}. Their findings did not receive a great deal of attention, in part because computer graphics were not available at this time. With the recent proliferation of computers, it is not surprising that these investigations were revived in the 1980's. Detailed studies of Newton's method and the more general topic of iteration were undertaken by a host of mathematicians including Curry, Douady, Garnett, Hubbard, Mandelbrot, Milnor and Sullivan. We now turn our attention to some of their results by focusing on the iterates produced by quadratics of the form fc(z) = z2+c. You will be surprised at the startling pictures that graphical iterates of such a simple functions produce.
Example 4.9. For fc(z) = z2+c, analyze all possible iterations when c = 0, that is, for the function f0 defined by f0(z) = z2+0.
Solution. We leave as an exercise the claim that, if z < 1, the sequence will converge to 0;
4 Chapter04Section02.nb
if z0 > 1, the sequence will be unbounded; and if z0 = 1, the sequence will either oscillate around the unit circle or converge to 1.
For the function fc(z) defined by fc(z) = z2+c, and an initial seed z0, the set of iter-ates given by z1=fc(z0), z2=fc(z1), etc., are also called the orbits of z0 generated by fc(z). We let Kc denote the set of points with bounded orbits for fc(z). Example 4.9 shows that K0 is the closed unit disk D1(0). The boundary of Kc is known as the Julia set for the func-tion fc(z). Thus the Julia set for f0(z) is the unit circle C1(0). It turns out that Kc is a nice simple set only when c = 0 or c = -2. Otherwise, Kc is fractal. Color plate 4 shows K-1.25. The variation in colors indicate the length of time it takes for points to become "sufficiently unbounded"
according to the following algorithm, which uses the same notation as our algorithm for iterations via Newton's method.
Color Plate 4. The Julia set for fc(z) = f-1.25(z) = z2-1.25.
Extra Example 2. Plot the Julia set for fc(z) = f-1.25(z) = z2-1.25.
Explore Extra Solution 2.
1. Compute fc(zi j). Continue computing successive iterates of this initial point until the absolute value of one of the iterations exceeds a certain bound (say, L), or until the number of iterations has exceeded a preassigned maximum.
2. If Step 1 leaves us with an iteration whose absolute value exceeds L, we color the entire rectan-gle Ri j with a color indicating the number of iterations needed before this value was attained (the more iterations required, the darker the color). Otherwise, we assume that the orbits of the initial point zi j do not diverge to infinity, and we color the entire rectangle black.
Note, again, that this algorithm doesn't prove anything. It merely guides the direction of our efforts to do rigorous mathematics.
Color plate 5 shows the Julia set for the function fc(z), where c = -0.11 - 0.67 ⅈ. The boundary of this set is different from the boundaries of the other sets we have seen, in that it is disconnected. Julia and Fatou independently discovered a simple criterion that can be used to tell when the Julia set for fc(z) is connected or disconnected. We state their result, but omit the proof, as it is beyond the scope of this text.
Color Plate 5. A disconnected Julia set for fc(z) = z2-0.11 - 0.67 ⅈ.
Theorem 4.9. The boundary of Kc is connected if and only if 0 ϵ Kc. In other words, the Julia set for fc(z) is connected if and only if the orbits of 0 are bounded.
Proof.
Example 4.10. Show that the Julia set for fⅈ(z) = z2+ ⅈ is connected.
Solution. We apply Theorem 4.9 and compute the orbits of 0 for fⅈ(z) = z2+ ⅈ. We have fⅈ(0) = ⅈ, fⅈ(0) = - 1 + ⅈ, fⅈ(-1 + ⅈ) = -ⅈ, and fⅈ(- ⅈ) = -1 + ⅈ. Thus the orbits of 0 are the sequence {0, ⅈ, -1 + ⅈ, -ⅈ, -1 + ⅈ, -ⅈ, -1 + ⅈ, -ⅈ, ...}, which is clearly a bounded sequence. Thus, by Theorem 4.9, the Julia set for fⅈ(z) is connected.