My math skills are super rusty. In an effort to get some vigor back I started some reading and picked up The Joy of x based on its rave reviews..
I just couldn't make any sense out of the following quoted text from the book's chapter 'Finding your roots'.
I would really appreciate it if a math guru can explain it in layman's terms. From the book:
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
Mr. Strogatz's further writing sounds like an alien language to me and finally he says Hubbard's computer program produced fractals.
Is there anyone who can dumb this down enough so that I can understand what the fractals have to do with multiple roots for complex numbers? Thanks!
Consider a polynomial equation $f(z) = 0$.
Newton's method is the iteration $z_{n+1} = z_n - f(z_n)/f'(z_n)$. That is, you start with some initial guess $z_0$, and you calculate $z_1 = z_0 - f(z_0)/f'(z_0)$, $z_2 = z_1 - f(z_1)/f'(z_1)$, etc. If $z_0$ is close enough to one of the roots, this will rapidly converge to that root. If it's close to a different root, it will converge to that different root. If it's not close to any of the roots, it will probably wander around for a while, and then eventually converge to one of the roots.
We're dealing here not with real numbers but with complex numbers, so each number $z$ corresponds to a point in a plane (the complex plane).
Now suppose you colour a point $z_0$ of the complex plane red if, starting at $z_0$, you converge to the first root, blue if you converge to the second, etc (a different colour for each root). So almost all points of the complex plane should end up coloured. What will this look like? Well, Hubbard found that the boundaries of the regions tend to be fractal.
For example, here's what I get with the equation $z (z-1)(z-2i) = 0$. The black regions are attracted to $0$, the gray to $1$, and the white to $2i$.
(and on a larger scale)