Zeroing in on chaos; the application of Newton's method, a mathematical tool used to solve equations, can lead to unexpected results.

Zeroing in on Chaos

Engineers and scientists spend a lotof time solving equations. Such exercises provide the information needed to understand how molecules stick together, to determine the strength a steel framework must have to support a given structure, to ascertain the size of distant galaxies and to accomplish innumerable other goals. Equations are the engines that drive much of engineering and scientific work.

Over the centuries, a variety of methodshave been developed for solving equations. Now, mathematicians, using the capabilities of modern computers, are starting to explore in detail how these methods work: when they can be relied upon, when they fail, when they behave strangely.

One calculus-based, equation-solvingtechnique that has undergone intense scrutiny is Newton's method, which has been in use for centuries and is often taught in beginning calculus courses. Several mathematicians have recently probed this method's idiosyncrasies and have come up with startling pictures of its behavior. Their results reveal a chaotic side to Newton's method that has become apparent only in the last five years. Earlier mathematicians had suspected that problems with the method could arise under certain circumstances, but they lacked the computer graphics to express their concerns.

"In my mind,' says engineer Scott A.Burns of the University of Illinois at Urbana-Champaign, "we're taking an indepth look at a very common engineering tool that's not as straightforward as we may wish to think. "Burns is working with mathematicians Harold E. Benzinger and Julian I. Palmore, colleagues at Illinois, to pin down exactly what happens when Newton's method is applied. Their research follows earlier, pioneering efforts by other mathematicians, including Stephen Smale of the University of California at Berkeley, John H. Hubbard of Cornell University in Ithaca, N.Y., Heinz-Otto Peitgen of the University of California at Santa Cruz and James H. Curry of the University of Colorado in Boulder.

Anyone who has taken high schoolmathematics is probably familiar with the problem of finding values of x for which, say, x2 x - 6 = 0. In this case, x can be either 2 or -3. The two solutions, 2 and -3, are known as the roots of the equation.

One way to picture what is happening isto plot a graph that shows what the function (or equation) x2 x - 6 looks like. When the function's value, written in mathematical shorthand as f(x), is computed for various values of x, the resulting pairs of numbers represent coordinates that can be plotted on a graph. For instance, when x = 1, f(x) = -4. The point (1,-4) would lie one step away from the graph's vertical axis and four steps below the horizontal or x axis. The resulting curve is a parabola that happens to cross the x axis twice, at x = 2 and x = -3.

Solving the equation x2-5 = 0 is a littletrickier. The answer is plus or minus the square root of five ( 5). But what is the numerical value of 5? In other words, exactly where does the curve represented by this equation intersect the x axis? Newton's method provides a way to find such a root.

The method begins with a guess. In thecase of 5, the solver may start with 2 as a trial value for x. Applying the formula that lies at the heart of Newton's method produces a new, improved estimate of the root: 2.25. Now the process is repeated with the new number, and the result, 2.236, is an even better estimate. This iterative procedure continues until the solver is satisfied with the answer's accuracy.

Such a procedure can be convertedeasily into a reasonably efficient computer algorithm for finding one or more of the roots of practically any polynomial equation. The problem with using the method, however, turns out to be one of selecting an appropriate starting point or making the right initial guess. Not all choices of starting points converge quickly on a specific root.

So far, the examples in this article haveincluded only one, "real' variable, x. Newton's method, in this case, is an example of a one-dimensional dynamical system. Equations involving "complex' numbers bring in two dimensions. Each complex variable, z, can be thought of as having two components. While real numbers can be represented as points on a line, complex numbers must be located on a plane. When Newton's method is applied to functions of a complex variable, the fireworks really begin--at least in terms of computer graphics.

A polynomial equation like z4 - 1 = 0has as many roots as the highest power to which z is raised in the equation. In this instance, there are four complex roots. The equation z17 - z5 6 = 0 has 17 solutions or roots.

When Newton's method is used to find aspecific root, the solver hopes that the chosen starting point leads quickly to the appropriate root. However, the method fails when the chosen point happens to fall on a boundary separating regions "controlled' by different roots. Failure may also strike when, for some starting values, the procedure gets sidetracked and, like a stuck needle on a phonograph record, ends up oscillating between two numbers, neither of which is a root.

Computer graphics provides a way topicture what is happening. For a given equation, the computer applies Newton's method for each of, perhaps, a million values of z. For each starting value, the computer determines toward which root that value converges and assigns a color to the point. Shades of the color indicate how quickly that point comes close to the root.

The result is a glowing tapestry, like theone shown on the cover, that often features large pools of color. These bains of attraction, as they are known, are "safe' areas. Any starting point selected from those regions, within a reasonable number of iterations, comes close to a root. The equation z4 - 1 = 0 has four such basins.

Life near or at a boundary, however, isconsiderably more complicated. These borders, much more than simple dividing lines, consist of elaborate swirls and whirlpools that can pull Newton's method into any one of the four roots. In this vicinity, a minuscule shift in starting point can lead to widely divergent results. And right on the convoluted boundary itself lie points that lead to no root. These points comprise the Julia set, named for the French mathematician Gaston Julia, who first studied such structures about 70 years ago.

And there's a further complication.Magnifying a section of the boundary region doesn't simplify the border. Instead, the magnified section looks a lot like the original picture of the boundary. Further magnification merely reveals more miniature copies of the overall structure. This "self-similarity' on all scales is characteristic of mathematical forms called fractals (SN: 1/21/84, p.42).

Mathematicians are also interestedin what characteristics of a function lead to particularly chaotic or unpredictable behavior. To study this problem, they pick a family of functions and vary one parameter to see what happens. One famous example, first probed by British mathematician Arthur Cayley in 1879, is the family of cubic polynomials. Cayley eventually had to give up his search because he found the answer too complicated.

"We can now see why Cayley neverpublished anything on the cubic case,' says Paul R. Blanchard of Boston University. "You really need the computer.'

The expression z3-az a-1 representsa one-parameter family of cubic polynomials. Every polynomial in this family has a root (or zero) at z = 1. The location of the other two roots depends on the numerical value of the parameter a. By varying the value of a, which may be either a real or a complex number, mathematicians can explore how the pictures associated with each function change.

The results are visually spectacular. Atthe boundaries between the basins of attraction, all three basins and, hence, colors must meet at every point. That leads to an intricate interweaving of color like the shown on the cover for another equation. Changing the parameter a shifts the boundaries and ruffles the basins of attraction. For certain values of a, Newton's method may take a point into a never-ending oscillation between two values, interrupting its quest for a root. In that case, the point falls into what is called an attracting cycle. In other cases, the basin of attraction around a zero

practically disappears, and no choice of points leads to the root. The zeros themselves become unstable. In these pictures, mathematicians can detect the onset of chaos (SN: 5/26/84, p.328).

Studying the descent of Newton'smethod into chaos is more than just generating pretty pictures. "We try to produce graphics that show exactly what happens in the mathematics,' says Palmore.

"We don't generate a picture until wehave a mathematical question in mind that we hope the picture will help us with,' Benzinger says. "When we get the picture, we check it against the mathematics.'

"You have to be careful with how youproduce the graphics,' Palmore warns. "It can be very misleading. We've seen lots of cases where it throws you off the track, and we use the mathematics to tell us how to correct the picture to make it look right.' He adds, "When you're exploring, you always look for consistency in what you do, and you try to track it back to the mathematics.' Palmore, Benzinger and Burns demonstrate their approach in a recent issue of PHYSICS LETTERS A (Vol. 119 [1987], p.435).

The computer promises to be a significanttool for doing pure mathematics, says Benzinger. "When you sit down to do mathematical research, you don't just put pencil to paper,' he says. "You work out examples. You try to get experience with the phenomenon and then try to abstract some truth.' For the Illinois trio, computer experiments quickly provided a lot of observations that could then be used to get at the underlying mathematics more effectively.

Computers are still scare amongmathematicians and infrequently used for serious mathematical research. Many mathematicians think that using a computer is sloppy mathematics and akin to cheating. Computation, they say, is merely an excuse for not thinking harder.

In the same way, computer-generatedpictures are also suspect. One mathematician recently remarked that there is something suspicious about an idea that cannot be adequately explained in words alone.

Nevertheless, computer experimentsand the theorems suggested by the observations have led to a deeper understanding of Newton's method and its limitations. "I think we understand much better now what Newton's method is really trying to do,' says Benzinger, "and how to avoid the problems.' The investigations also indicate hitherto hidden links among different mathematical fields.

"Ultimately what you want is to have agood method for solving equations,' says Blanchard. In the case of Newton's method, most initial conditions still work well, even with bad polynomials, he says. "It's amazing how well it does work.'

Mathematicians are gradually buildinga fence around this venerable mathematical technique for solving equations. Eventually, that fence will show where it's safe to tread and which territories to avoid. Until then, there are still lots of good questions that need answers.

Photo: The boundary between two basins of attraction (one red, theother green) for the equation (Z2 - 1)(Z2 - 4) can be extraordinarily complicated. The image is centered on the point (0,0) and runs from -0.5 to 0.5 on the x (horizontal) axis.

Photo: The black hole atthe center of this starburst pattern is not the mathematical result of applying Newton's method to the equation z17 - 1. Instead, it shows up because the computer is unable to handle numbers smaller than a certain value. When the computer encounters such numbers during a computation, it simply colors the appropriate point black. A "perfect' computer would be able to take all of the colored lines to the center.

Photo: For the last year orso, Scott Burns (left), Julian Palmore (right) and Harold Banzinger (sitting) have been using computers to study the behavior of Newton's method for special families of equations.

Photo: The bull's-eye patternsindicate areas in which starting points for Newton's method converage toward one of the three roots of the equation z3 - 1. The root itself falls within the small circle near the upper left-hand corner. The boundary region is a fractal because the overall pattern repeats itself on smaller and smaller scales, as seen in the teardrop shapes scattered throughout the picture.