TomAz

03-09-2010, 11:44 AM

Fractals.

coolest shit ever.

http://opinionator.blogs.nytimes.com/2010/03/07/finding-your-roots/?emc=eta1

March 7, 2010, 5:30 pm

Finding Your Roots

By STEVEN STROGATZ

Steven Strogatz on math, from basic to baffling.

Tags:

complex numbers, computers, imaginary numbers, negatives, square roots

For more than 2,500 years, mathematicians have been obsessed with solving for x. The story of their struggle to find the “roots” — the solutions — of increasingly complicated equations is one of the great epics in the history of human thought.

And yet, through it all, there’s been an irritant, a nagging little thing that won’t go away: the solutions often involve square roots of negative numbers. Such solutions were long derided as “sophistic” or “fictitious” because they seemed nonsensical on their face.

More in This Series

From Fish to Infinity (Jan. 31, 2010)

Rock Groups (Feb. 7, 2010)

The Enemy of My Enemy (Feb. 14, 2010)

Division and Its Discontents (Feb. 21, 2010)

The Joy of X (Feb. 28, 2010)

Until the 1700s or so, mathematicians believed that square roots of negative numbers simply couldn’t exist.

They couldn’t be positive numbers, after all, since a positive times a positive is always positive, and we’re looking for numbers whose square is negative. Nor could negative numbers work, since a negative times a negative is, again, positive. There seemed to be no hope of finding numbers which, when multiplied by themselves, would give negative answers.

We’ve seen crises like this before. They occur whenever an existing operation is pushed too far, into a domain where it no longer seems sensible. Just as subtracting bigger numbers from smaller ones gave rise to negative numbers and division spawned fractions and decimals, the free-wheeling use of square roots eventually forced the universe of numbers to expand…again.

Historically, this step was the most painful of all. The square root of –1 still goes by the demeaning name of i, this scarlet letter serving as a constant reminder of its “imaginary” status.

This new kind of number (or if you’d rather be agnostic, call it a symbol, not a number) is defined by the property that

i2 = –1.

It’s true that i can’t be found anywhere on the number line. In that respect it’s much stranger than zero, negative numbers, fractions or even irrational numbers, all of which — weird as they are — still have their place in line.

But with enough imagination, our minds can make room for i as well. It lives off the number line, at right angles to it, on its own imaginary axis. And when you fuse that imaginary axis to the ordinary “real” number line, you create a 2-D space — a plane — where a new species of numbers lives.

These are the “complex numbers.” Here complex doesn’t mean complicated; it means that two types of numbers, real and imaginary, have bonded together to form a complex, a hybrid number like 2 + 3i.

Complex numbers are magnificent, the pinnacle of number systems. They enjoy all the same properties as real numbers — you can add and subtract them, multiply and divide them — but they are better than real numbers because they always have roots. You can take the square root or cube root or any root of a complex number and the result will still be a complex number.

Better yet, a grand statement called The Fundamental Theorem of Algebra says that the roots of any polynomial are always complex numbers. In that sense they’re the end of the quest, the holy grail. They are the culmination of the journey that began with 1.

You can appreciate the utility of complex numbers (or find it more plausible) if you know how to visualize them. The key is to understand what multiplying by i looks like.

Suppose we multiply an arbitrary positive number, say 3, by i. The result is the imaginary number 3i.

So multiplying by i produces a rotation counterclockwise by a quarter turn. It takes an arrow of length 3 pointing east, and changes it into a new arrow of the same length but now pointing north.

Electrical engineers love complex numbers for exactly this reason. Having such a compact way to represent 90-degree rotations is very useful to them when working with alternating currents and voltages, or with electric and magnetic fields, because these often involve oscillations or waves that are a quarter cycle (i.e., 90 degrees) out of phase.

In fact, complex numbers are indispensable to all engineers. In aerospace engineering they eased the first calculations of the lift on an airplane wing. Civil and mechanical engineers use them routinely to analyze the vibrations of footbridges, skyscrapers and cars driving on bumpy roads.

The 90-degree rotation property also sheds light on what i2 = –1 really means. If we multiply a positive number by i2, the corresponding arrow rotates 180 degrees, flipping from east to west, because the two 90-degree rotations (one for each factor of i) combine to make a 180-degree rotation.

But multiplying by –1 produces the very same 180-degree flip. That’s the sense in which i2 = –1.

Computers have breathed new life into complex numbers and the age-old problem of root finding. When they’re not being used for Web surfing or e-mail, the machines on our desks can reveal things the ancients could never have dreamed of.

In 1976, my Cornell colleague John Hubbard began looking at the dynamics of Newton’s method, a powerful algorithm for finding roots of equations in the complex plane. The method takes a starting point (an approximation to the root) and does a certain computation that improves it. By doing this repeatedly, always using the previous point to generate a better one, the method bootstraps its way forward and rapidly homes in on a root.

Hubbard was interested in problems with multiple roots. In that case, which root would the method find? He proved that if there were just two roots, the closer one would always win. But if there were three or more roots, he was baffled. His earlier proof no longer applied.

So Hubbard did an experiment. A numerical experiment.

He programmed a computer to run Newton’s method, and told it to color-code millions of different starting points according to which root they approached, and to shade them according to how fast they got there.

Before he peeked at the results, he anticipated that the roots would most quickly attract the points nearby, and thus should appear as bright spots in a solid patch of color. But what about the boundaries between the patches? Those he couldn’t picture, at least not in his mind’s eye.

The computer’s answer was astonishing.

Simon Tatham Click to enlarge.

The borderlands looked like psychedelic hallucinations. The colors intermingled there in an almost impossibly promiscuous manner, touching each other at infinitely many points, and always in a three-way. In other words, wherever two colors met, the third would always insert itself and join them.

Magnifying the boundaries revealed patterns within patterns.

Simon Tatham Click to enlarge.

The structure was a “fractal” — an intricate shape whose inner structure repeated at finer and finer scales, as shown in this continuous zoom:

Classic newton fractal from teamfresh on Vimeo.

Furthermore, chaos reigned near the boundary. Two points might start very close together, bouncing side by side for a while, and then veer off to different roots. The winning root was as unpredictable as a game of roulette. Little things — tiny, imperceptible changes in the initial conditions — could make all the difference.

Hubbard’s work was an early foray into what’s now called “complex dynamics,” a vibrant blend of chaos theory, complex analysis and fractal geometry. In a way it brought geometry back to its roots. In 600 B.C. a manual written in Sanskrit for temple builders in India gave detailed geometric instructions for computing square roots, needed in the design of ritual altars. More than 2,500 years later, mathematicians were still searching for roots, but now the instructions were written in binary code.

Some imaginary friends you never outgrow.

NOTES:

• The story of the search for solutions to increasingly complicated equations, from quadratic to quintic, is recounted in vivid detail in:

M. Livio, The Equation That Couldn’t Be Solved (Simon and Schuster, 2005).

• To learn more about imaginary and complex numbers, their applications and their checkered history, see:

P.J. Nahin, An Imaginary Tale (Princeton University Press, 1998);

B. Mazur, Imagining Numbers (Farrar, Straus and Giroux, 2003).

• For a superb journalistic account of John Hubbard’s work, see:

J. Gleick, Chaos: Making a New Science (Viking, 1987), p. 217.

• Hubbard’s own take on Newton’s method appears in Section 2.8 of:

J. Hubbard and B.B. Hubbard, Vector Calculus, Linear Algebra, and Differential Forms: A Unified Approach, 4th edition (Matrix Editions, 2009).

• For readers who want to delve into the mathematics of Newton’s method, a more sophisticated but still readable introduction is given in:

H.-O. Peitgen and P.H. Richter, The Beauty of Fractals (Springer, 1986), chapter 6, and also see the article by A. Douady (Hubbard’s collaborator) entitled “Julia sets and the Mandelbrot set,” starting on p.161 of the same book.

• The snapshots and animations shown here were computed using Newton’s method applied to the polynomial z3 – 1. The roots are the three cube roots of 1. For this case, Newton’s algorithm takes a point z in the complex plane and maps it to a new point

z – (z3 – 1)/(3z2).

That point then becomes the next z. This process is repeated until z comes sufficiently close to a root, or equivalently, until z3 – 1 comes sufficiently close to zero, where “sufficiently close” is a very small distance, arbitrarily chosen by the person who programmed the computer. All initial points that lead to a particular root are then assigned the same color. Thus red labels all the points that converge to one root, green labels another, and blue labels the third.

• The snapshots of the resulting “Newton fractal” were kindly provided by Simon Tatham. For more on his work, see his web site.

• The video animation of the Newton fractal was created by Teamfresh. Stunningly deep zooms into other fractals, including the famous Mandelbrot set, are available here: http://www.hd-fractals.com.

• Hubbard was not the first mathematician to ask questions about Newton’s method in the complex plane; Arthur Cayley had wondered about the same things in 1879. He too looked at both quadratic and cubic polynomials, and realized that the first case was easy and the second was hard. Although he couldn’t have known about the fractals discovered a century later, he clearly understood that something nasty could happen when there were more than two roots. The final sentence of his one-page article in the American Journal of Mathematics (reprinted here) is a marvel of understatement: “The solution is easy and elegant in the case of a quadric equation, but the next succeeding case of the cubic equation appears to present considerable difficulty.”

• For an introduction to the ancient Indian methods for finding square roots, see:

D. W. Henderson, Experiencing Geometry on Plane and Sphere, (Prentice Hall, 1996).

• Thanks to Carole Schiffman and John Smillie for their comments and suggestions, and to Margaret Nelson for preparing the line drawings.

• I am especially grateful to Teamfresh for creating the animation of the Newton fractal, and to Simon Tatham for computing the snapshots of it. Both of them generously provided their expert help on very short notice.

Copyright 2010 The New York Times Company Privacy Policy NYTimes.com 620 Eighth Avenue New York, NY 10018

coolest shit ever.

http://opinionator.blogs.nytimes.com/2010/03/07/finding-your-roots/?emc=eta1

March 7, 2010, 5:30 pm

Finding Your Roots

By STEVEN STROGATZ

Steven Strogatz on math, from basic to baffling.

Tags:

complex numbers, computers, imaginary numbers, negatives, square roots

For more than 2,500 years, mathematicians have been obsessed with solving for x. The story of their struggle to find the “roots” — the solutions — of increasingly complicated equations is one of the great epics in the history of human thought.

And yet, through it all, there’s been an irritant, a nagging little thing that won’t go away: the solutions often involve square roots of negative numbers. Such solutions were long derided as “sophistic” or “fictitious” because they seemed nonsensical on their face.

More in This Series

From Fish to Infinity (Jan. 31, 2010)

Rock Groups (Feb. 7, 2010)

The Enemy of My Enemy (Feb. 14, 2010)

Division and Its Discontents (Feb. 21, 2010)

The Joy of X (Feb. 28, 2010)

Until the 1700s or so, mathematicians believed that square roots of negative numbers simply couldn’t exist.

They couldn’t be positive numbers, after all, since a positive times a positive is always positive, and we’re looking for numbers whose square is negative. Nor could negative numbers work, since a negative times a negative is, again, positive. There seemed to be no hope of finding numbers which, when multiplied by themselves, would give negative answers.

We’ve seen crises like this before. They occur whenever an existing operation is pushed too far, into a domain where it no longer seems sensible. Just as subtracting bigger numbers from smaller ones gave rise to negative numbers and division spawned fractions and decimals, the free-wheeling use of square roots eventually forced the universe of numbers to expand…again.

Historically, this step was the most painful of all. The square root of –1 still goes by the demeaning name of i, this scarlet letter serving as a constant reminder of its “imaginary” status.

This new kind of number (or if you’d rather be agnostic, call it a symbol, not a number) is defined by the property that

i2 = –1.

It’s true that i can’t be found anywhere on the number line. In that respect it’s much stranger than zero, negative numbers, fractions or even irrational numbers, all of which — weird as they are — still have their place in line.

But with enough imagination, our minds can make room for i as well. It lives off the number line, at right angles to it, on its own imaginary axis. And when you fuse that imaginary axis to the ordinary “real” number line, you create a 2-D space — a plane — where a new species of numbers lives.

These are the “complex numbers.” Here complex doesn’t mean complicated; it means that two types of numbers, real and imaginary, have bonded together to form a complex, a hybrid number like 2 + 3i.

Complex numbers are magnificent, the pinnacle of number systems. They enjoy all the same properties as real numbers — you can add and subtract them, multiply and divide them — but they are better than real numbers because they always have roots. You can take the square root or cube root or any root of a complex number and the result will still be a complex number.

Better yet, a grand statement called The Fundamental Theorem of Algebra says that the roots of any polynomial are always complex numbers. In that sense they’re the end of the quest, the holy grail. They are the culmination of the journey that began with 1.

You can appreciate the utility of complex numbers (or find it more plausible) if you know how to visualize them. The key is to understand what multiplying by i looks like.

Suppose we multiply an arbitrary positive number, say 3, by i. The result is the imaginary number 3i.

So multiplying by i produces a rotation counterclockwise by a quarter turn. It takes an arrow of length 3 pointing east, and changes it into a new arrow of the same length but now pointing north.

Electrical engineers love complex numbers for exactly this reason. Having such a compact way to represent 90-degree rotations is very useful to them when working with alternating currents and voltages, or with electric and magnetic fields, because these often involve oscillations or waves that are a quarter cycle (i.e., 90 degrees) out of phase.

In fact, complex numbers are indispensable to all engineers. In aerospace engineering they eased the first calculations of the lift on an airplane wing. Civil and mechanical engineers use them routinely to analyze the vibrations of footbridges, skyscrapers and cars driving on bumpy roads.

The 90-degree rotation property also sheds light on what i2 = –1 really means. If we multiply a positive number by i2, the corresponding arrow rotates 180 degrees, flipping from east to west, because the two 90-degree rotations (one for each factor of i) combine to make a 180-degree rotation.

But multiplying by –1 produces the very same 180-degree flip. That’s the sense in which i2 = –1.

Computers have breathed new life into complex numbers and the age-old problem of root finding. When they’re not being used for Web surfing or e-mail, the machines on our desks can reveal things the ancients could never have dreamed of.

In 1976, my Cornell colleague John Hubbard began looking at the dynamics of Newton’s method, a powerful algorithm for finding roots of equations in the complex plane. The method takes a starting point (an approximation to the root) and does a certain computation that improves it. By doing this repeatedly, always using the previous point to generate a better one, the method bootstraps its way forward and rapidly homes in on a root.

Hubbard was interested in problems with multiple roots. In that case, which root would the method find? He proved that if there were just two roots, the closer one would always win. But if there were three or more roots, he was baffled. His earlier proof no longer applied.

So Hubbard did an experiment. A numerical experiment.

He programmed a computer to run Newton’s method, and told it to color-code millions of different starting points according to which root they approached, and to shade them according to how fast they got there.

Before he peeked at the results, he anticipated that the roots would most quickly attract the points nearby, and thus should appear as bright spots in a solid patch of color. But what about the boundaries between the patches? Those he couldn’t picture, at least not in his mind’s eye.

The computer’s answer was astonishing.

Simon Tatham Click to enlarge.

The borderlands looked like psychedelic hallucinations. The colors intermingled there in an almost impossibly promiscuous manner, touching each other at infinitely many points, and always in a three-way. In other words, wherever two colors met, the third would always insert itself and join them.

Magnifying the boundaries revealed patterns within patterns.

Simon Tatham Click to enlarge.

The structure was a “fractal” — an intricate shape whose inner structure repeated at finer and finer scales, as shown in this continuous zoom:

Classic newton fractal from teamfresh on Vimeo.

Furthermore, chaos reigned near the boundary. Two points might start very close together, bouncing side by side for a while, and then veer off to different roots. The winning root was as unpredictable as a game of roulette. Little things — tiny, imperceptible changes in the initial conditions — could make all the difference.

Hubbard’s work was an early foray into what’s now called “complex dynamics,” a vibrant blend of chaos theory, complex analysis and fractal geometry. In a way it brought geometry back to its roots. In 600 B.C. a manual written in Sanskrit for temple builders in India gave detailed geometric instructions for computing square roots, needed in the design of ritual altars. More than 2,500 years later, mathematicians were still searching for roots, but now the instructions were written in binary code.

Some imaginary friends you never outgrow.

NOTES:

• The story of the search for solutions to increasingly complicated equations, from quadratic to quintic, is recounted in vivid detail in:

M. Livio, The Equation That Couldn’t Be Solved (Simon and Schuster, 2005).

• To learn more about imaginary and complex numbers, their applications and their checkered history, see:

P.J. Nahin, An Imaginary Tale (Princeton University Press, 1998);

B. Mazur, Imagining Numbers (Farrar, Straus and Giroux, 2003).

• For a superb journalistic account of John Hubbard’s work, see:

J. Gleick, Chaos: Making a New Science (Viking, 1987), p. 217.

• Hubbard’s own take on Newton’s method appears in Section 2.8 of:

J. Hubbard and B.B. Hubbard, Vector Calculus, Linear Algebra, and Differential Forms: A Unified Approach, 4th edition (Matrix Editions, 2009).

• For readers who want to delve into the mathematics of Newton’s method, a more sophisticated but still readable introduction is given in:

H.-O. Peitgen and P.H. Richter, The Beauty of Fractals (Springer, 1986), chapter 6, and also see the article by A. Douady (Hubbard’s collaborator) entitled “Julia sets and the Mandelbrot set,” starting on p.161 of the same book.

• The snapshots and animations shown here were computed using Newton’s method applied to the polynomial z3 – 1. The roots are the three cube roots of 1. For this case, Newton’s algorithm takes a point z in the complex plane and maps it to a new point

z – (z3 – 1)/(3z2).

That point then becomes the next z. This process is repeated until z comes sufficiently close to a root, or equivalently, until z3 – 1 comes sufficiently close to zero, where “sufficiently close” is a very small distance, arbitrarily chosen by the person who programmed the computer. All initial points that lead to a particular root are then assigned the same color. Thus red labels all the points that converge to one root, green labels another, and blue labels the third.

• The snapshots of the resulting “Newton fractal” were kindly provided by Simon Tatham. For more on his work, see his web site.

• The video animation of the Newton fractal was created by Teamfresh. Stunningly deep zooms into other fractals, including the famous Mandelbrot set, are available here: http://www.hd-fractals.com.

• Hubbard was not the first mathematician to ask questions about Newton’s method in the complex plane; Arthur Cayley had wondered about the same things in 1879. He too looked at both quadratic and cubic polynomials, and realized that the first case was easy and the second was hard. Although he couldn’t have known about the fractals discovered a century later, he clearly understood that something nasty could happen when there were more than two roots. The final sentence of his one-page article in the American Journal of Mathematics (reprinted here) is a marvel of understatement: “The solution is easy and elegant in the case of a quadric equation, but the next succeeding case of the cubic equation appears to present considerable difficulty.”

• For an introduction to the ancient Indian methods for finding square roots, see:

D. W. Henderson, Experiencing Geometry on Plane and Sphere, (Prentice Hall, 1996).

• Thanks to Carole Schiffman and John Smillie for their comments and suggestions, and to Margaret Nelson for preparing the line drawings.

• I am especially grateful to Teamfresh for creating the animation of the Newton fractal, and to Simon Tatham for computing the snapshots of it. Both of them generously provided their expert help on very short notice.

Copyright 2010 The New York Times Company Privacy Policy NYTimes.com 620 Eighth Avenue New York, NY 10018