Numerical Zoo · Polynomial

Wilkinson's polynomial

Twenty perfectly ordinary integer roots and a frankly unreasonable sensitivity to small perturbations.

Why numerical analysts keep this one around

Wilkinson's polynomial is the product (x - 1)(x - 2)...(x - 20). Written that way, nothing seems mysterious. The roots are sitting in the definition, wearing name tags.

The trouble appears when we stop treating the polynomial as a product and start treating it as a list of floating-point coefficients. Small changes to those coefficients can move some roots much more than intuition would suggest. This is why the example keeps showing up in numerical analysis: the mathematical object is well defined, but one representation of that object is badly conditioned for the question we want to ask.

CMNA already includes wilkinson(), so this is an especially useful recurring character for the site. We can look at the function directly, hand it to root finders, plot it, and then use the R Workbench when we want to mistreat the coefficients.

R setup

Start with the actual object.

# The factored form makes the roots obvious.
f <- function(x) wilkinson(x, 20)

f(1)
f(10)
f(20)

curve(f, from = 0.5, to = 20.5, n = 4000)
abline(h = 0, lty = 3)

By hand first

Do enough arithmetic to see the trap.

At x = 1, one factor is zero, so the entire product is zero. The same argument works at every integer from 1 through 20.

Between neighboring roots the sign changes, which gives bisection a legal bracket if we choose a sufficiently small interval around one root.

The interesting problem is not finding the roots from the factored form. It is asking how much of that obvious structure survives after we encode the same polynomial differently.

What to look for

Now make it earn its reputation.

Plotting the polynomial on an ordinary y-axis is already a lesson in scale. The values between roots can become enormous.
Try bisection on a small bracket around an integer root, then try Newton from a starting value between two roots.
In the Workbench, expand or perturb the coefficient representation and compare the resulting roots. The polynomial did not become vague. Our representation became fragile.

Keep this distinction:

The useful distinction here is conditioning versus algorithmic error. A perfect root finder cannot recover information that was already damaged by the way the polynomial was represented.

← Back to the Numerical Zoo