The Rambling Roots of Wilkinson’s Polynomial

Finding the roots of polynomials has occupied mathematicians for many centuries. For equations up to fourth order, there are algebraic expressions for the roots. For higher order equations, many excellent numerical methods are available, but the results are not always reliable.

A 10th-order polynomial (blue) and a slightly perturbed version, with the coefficient of ${x^9}$ changed by one part in a million.

James Wilkinson (1963) examined the behaviour of a high-order polynomial

$\displaystyle p(x,\epsilon) = \prod_{k=1}^{20} (x - k) + \epsilon x^{19} \,,$

whose roots for ${\epsilon=0}$ are at the first twenty positive integers. He found that a tiny perturbation of the coefficients may have a major impact on the nature and location of the roots.

For simplicity, we will consider a tenth-order polynomial

$\displaystyle w(x) = \prod_{k=1}^{10} (x - k)$

Expanded into powers of ${x}$ , this becomes

$\displaystyle 3628800 - 10628640 x + 12753576 x^2 - 8409500 x^3 + 3416930 x^4$

$\displaystyle - 902055 x^5 + 157773 x^6 - 18150 x^7 + 1320 x^8 - 55 x^9 + x^{10} \,.$

The leading coefficient is ${1}$ . The coefficient of ${x^9}$ is ${-55}$ .

In the figure above, we plot the polynomial and also the polynomial

$\displaystyle p(x,\epsilon) = \prod_{k=1}^{10} (x - k) + \epsilon x^9$

with ${\epsilon = 55\times 10^{-6}}$ . That is, the coefficient of ${x^9}$ is changed by one part in a million. Surely, this could not have much influence on the roots? But it does!

As ${\epsilon}$ increases, the roots move closer to each other in pairs. At some point, the seventh and eighth roots coalesce and then become a pair of complex conjugate roots. This is shown in the figure below. We can also see how the ninth and tenth roots are approaching each other. For a slightly larger value of ${\epsilon}$ , these will morph into a complex conjugate pair.

The roots of the unperturbed polynomial (blue dots) and the polynomial with a small perturbation ${\epsilon = 55\times 10^{-6}}$ (red).

The above example shows how the extraction of polynomial roots can be an ill-conditioned problem, even for polynomials with well-separated zeros. Wilkinson (1984) described his own personal reaction to this discovery:

“I regard it as the most traumatic experience in my career as a numerical analyst.”

Sources

${\bullet}$ Wilkinson, James H., 1963: Rounding Errors in Algebraic Processes. Prentice Hall, Englewood Cliffs, New Jersey

${\bullet}$ Wilkinson, James H., 1984: The perfidious polynomial. Studies in Numerical Analysis, ed. by G. H. Golub, pp. 1–28. (Studies in Mathematics, vol. 24). Math. Assoc. America. ISBN 978-0-88385-126-5. PDF

${\bullet}$ Wikipedia article Wilkinson’s Polynomial: http://www.wikipedia.org/

ThatsMaths