Does Newton's method converge for all polynomials?

Question

I made an implementation of Newton's method (starting at $x=\pi$) for polynomials in the programming language Uiua (here it is if you are interested, but be warned that Uiua looks weird). It works fine for most polynomials but there are a few that it gets stuck on. I tried [12 ¯9 ¯21 37 ¯41 ¯10 31 49], (a degree 7 polynomial with coefficients listed from lowest degree to highest) and the execution time ran out. Inspecting further, it seems to be oscillating somewhat randomly in the range $[0.3,0.7]$, even after 500+ iterations, when the actual answer is $-0.568$. Another online implementation also fails to converge when starting at $x=\pi$.

My question is whether Newton's method should be working in this case or if I should expect to find there is some problem in my code or in the way that Uiua handles floats. Does Newton's method always converge for polynomials?

Answer 1

Here is a plot of the function $$f(x) = 49 x^7+31 x^6-10 x^5-41 x^4+37 x^3-21 x^2-9 x+12$$ in the region of interest. The blue curve is $f$. The orange lines represent the forward orbit of $x_0 = \pi$ under $x \mapsto x - f(x)/f'(x)$, connecting $(x_i, f(x_i))$ to the next iterate $(x_{i+1}, 0)$, then to $(x_{i+1}, f(x_{i+1}))$, and so forth. Note that the initial iterations are not shown because the value of the function at these points is large.

The thick red line shows the steady-state behavior of the orbit, and we can see this will converge to a $3$-cycle of values, which are approximately $$S = \{0.355634, 0.796309, 0.680185\}.$$

This suggests that for any $x \in S$, the rational function $$g(x) = x - \frac{f(x)}{f'(x)} = \frac{294 x^7+155 x^6-40 x^5-123 x^4+74 x^3-21 x^2-12}{343 x^6+186 x^5-50 x^4-164 x^3+111 x^2-42 x-9}$$ satisfies $$g(g(g(x))) = x.$$

Indeed, we can hypothesize that whenever $f$ has a neighborhood with a local minimum but no root, then there is the possibility of an initial choice $x_0$ for which the forward orbit does not converge to a root.

Answer 2

One does not have to go all the way to 7-th degree polynomials to see this behaviour. Consider $f(x) = x^3-5x$. If you start the Newton-Raphson iteration from initial guess $1$, you would simply oscillate between $1$ and $-1$. This is an unstable equilibrium, but clearly one that you might actually encounter. (There is no rounding error to save you from this cycle.)

For a stable equilibrium consider $f(x) = x^4-6x^2-11$. If you start the Newton-Raphson iteration from initial guess $1$, you would oscillate between $1$ and $-1$. Furthermore, if you start from an initial guess near $1$, say $1.2$ or $0.8$, the iterates will converge to the same oscillating cycle!

Answer 3

As the other answers already noted, there are cases where the Newton iteration does not converge.

One interesting question is for how "many" values this can occur and whether it's a set or full measure or a Null set. As it turns out, there are indeed polynomials for which the Newton process does not converge, and the set of such starting values is a set of full measure.

This won't occur for polynomials of degree less than 3, but it may occur for cubic polynomials like $$ p(z) = z^3-2z+2 $$ The dynamics of the Newton process $z\mapsto {\cal N}_p(z)$ is made visible by the graphic below which displays the dynamic for real starting values with $z\in[-4,4]$.

The image consists of 18 colored stripes, each color encoding a real number (−4=purple, −2=violet, −1=cyan, 0=black, 1=red, 2=orange, 4=yellow, ±∞=white). From top to bottom, the stripes show values of the $n$-th Newton iterate, where row 0 indicates the starting values.

Starting values smaller than approximately −0.83 converge to the violet zero of $p(z)$ at $z\approx-1.76929$, but all values in some interval around $0$ are attracted by the black-red cycle $$\cdots0\mapsto 1\mapsto 0\mapsto 1\mapsto 0\mapsto1\cdots$$

But how many such "bad" polynomials are there? Are such polynomials a null set in the set of all polynomials, or is there a substantial amount of such polynomials?

For cubic polynomials one can study the behavior of the critical point of ${\cal N}_p$. For example, $0$ is a critical point of ${\cal N}_{p_\lambda}$ for all cubics from the family $$ p_\lambda(z) = z^3+(\lambda-1)z-\lambda $$ Plotting how the critical point of ${\cal N}_{p_\lambda}$ behaves under iteration gives the following result, where $\lambda$ ranges over the complex plane where $-2.5\leqslant Re(\lambda),Im(\lambda)\leqslant 2.5$.

There are tiny black spots that are subsets of full measure in the $\lambda$ space for which the critical point does not converge to a zero of $p_\lambda$.

Magnifying the black spot around $\lambda\approx0.3+1.64i$ looks like this:

There are infinitely many of them.

---

Answer to a comment: The hue in the last two images represents the limit of $$\lim_{n\to\infty} {\cal N}_{p_\lambda}^n(0)$$ i.e. the fate of the critical point 0 of ${\cal N}_{p_\lambda}$ under iteration, provided the iteration converges. When it does not converge, then the point at $\lambda$ is colored in black. There are 3 hues around the island in the 3rd image because $p_\lambda$ has 3 complex zeros that may occur as limit. The hue indicates which zero and relates to the limit in a non-obvious way and such that the 3 hues are 120° apart in color space (red, green, blue). This comes with a grain of salt because the exact locations of the zeros of $p_\lambda$ depend on $\lambda$, so this only holds approximately and only is small regions. It's the reason for why the colors of the zeros in the overview picture transition smoothly over large stretches of the $\lambda$ plane.

The brightness indicates how many iterations where required to conclude that the iteration converges for that $\lambda$: brighter = more. For points close to the Mandelbrot islands, the saturation is increased again before it finally drops to white. This is for aesthetical reasons and results in the purple-white glow around the black islands.

The algorithm smoothes out the colors by interpolating the number of iterations (which are natural numbers) to real numbers; similar to how you would smooth the potential around an electrically charged Mandelbrot set. To that end, one has to introduce a notion of distance to the closest complex root of $p_\lambda$.

It's more than 10 years ago since I make these images; so bear with me. The summary of the wiki page contains and explains the relevant part of the C code I used back then. The idea for this specific family of cubics is from the book of Peitgen and Richter.

Answer 4

A simpler and wonderful example is what you get when you try to find, using Newton's method, the solution to $x^2 = -1$. (Yes, I know, what sort of dumbo tries to find $i$ in this silly way. But still...)

The iterations might go off to infinity (hitting 0 first); they might hit a cycle of any prime period, they might jump around forever without repeating a guess.

The cool thing is that you can express the n-th iterate in terms of the initial guess in a nice closed form! Hint: Look at the expression for $\tan (2\theta)$ in terms of $\tan \theta$ and note a similarity with the expression for the next guess in terms of the previous one. Far be it from me to deprive you of the enjoyment of working out the closed form.

I credit Carl Bender, who introduced me to this cute problem at the start of a perturbation theory course. (Of course, he is almost surely not the first person to come up with the observation...)