It is a natural question in Numerical Analysis to ask whether the problem of finding the roots of a polynomial is well-conditioned. That is, we’d hope that small changes in the coefficients of the polynomial would lead to small changes in the values of its roots. Interestingly, this is often not the case.
Wilkinson’s polynomial is a specific polynomial used by mathematician James Wilkinson in 1963 to illustrate the idea that the location of the roots can be very sensitive to perturbations in the coefficients of the polynomial, even if it has well-separated zeros. He later described the personal impact of this discovery as:
"Speaking for myself I regard it as the most traumatic experience in my career as a numerical analyst."
Wilkinson’s polynomial is often used to illustrate the undesirability of a common technique to compute the eigenvalues of a matrix, which involves deriving the coefficients of the matrix’s characteristic polynomial and then solving for its roots. It should be noted that using the coefficients as an intermediate step may introduce an extreme ill-conditioning even if the original problem was well-conditioned.
Perturbed polynomials
Let’s observe what happens to the roots of a polynomial similar to Wilkinson’s when we randomly perturb its coefficients. We consider the polynomial

which has degree 10 and roots 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Expanding, we get

where C = {cᵢ}, where i ranges from 0 to 9 inclusive, is the set of coefficients of the non-leading terms. We randomly perturb the coefficients of p(x), replacing each element cᵢ ∈ C with cᵢ ⋅ (1 + aεᵢ), where each εᵢ is a normally distributed random variable with mean 0 and variance 1, and a is some small overall scaling factor. If we plug in each cᵢ, we get that the perturbed polynomial is

Below, p(x) is plotted in blue, while a randomly perturbed version of p(x) is given in pink. We observe that the number of real roots decreases after perturbation and that the roots change position, as evidenced by the differing positions of the blue dots and pink stars.

Next, we investigate what happens to the roots of p(x) over multiple small values of a, confirming that the roots are indeed highly sensitive to perturbations applied to the coefficients.
Root distributions
We attempt to figure out whether there is a distinct point at which real roots begin transforming into complex ones.
Real
We observe distributions of real roots of a perturbed version of p(x), across various a values, for a single run per a.

The points above are randomly horizontally dodged for visibility purposes, and the leftmost a value indicates no perturbation. We see that some real roots change position or are even lost are lost, that is, turned into complex ones, as a increases. This leads to the question:
Is there a particular value of a at which it is almost certain that complex roots will appear? How can we characterize the spread of the real roots up until that point?
Let’s call the a value at which the roots of p(x), originally all real, begin to switch into the strictly complex plane with some probability pᵣ the critical point a*. This pᵣ, informed by computational experiments described in the sections below, is set somewhat arbitrarily but succeeds in capturing some of the relevant features of the problem.
Complex
Here we show a plot of the roots of 100 different perturbed versions of p(x), for each of 10 different a values. As previously noted, for greater a values, we see more and more roots entering the complex plane.

Only larger a values seem to account for the spread in the imaginary direction. These observations motivate the exploration of perturbed real root spread as compared to the roots of p(x) over multiple values of a.
Critical scaling factor
We zoom in onto two particular a values, one below the critical point and one greater than the critical point a*. The plots depict eight different perturbed polynomials’ roots.

The distribution of the roots seems to undergo a sudden change after the critical point is hit. Let’s attempt to define this critical a.
Definition
The plot below depicts the probabilities of a complex root being present, based on the value of a used in perturbing p(x). We perturb p(x) 1000 times for each a value, where a success denotes the presence of one or more complex roots. The plotted probabilities are calculated by dividing the total number of successes by 1000.

The probability pᵣ = 0.25 is indicated by the dotted line in gold. The critical point a* occurs at the intersection of the pink curve and the gold line.
Trends
Below, we plot the critical points attained over multiple polynomial degrees, using the definition of a* established in the previous section. By a degree of n, we refer to the product of monomials starting from (x–1) up to (x–n).

We recognize an interesting, exponentially decreasing relationship between polynomial degree and a values. Logically, a decreases for polynomials with more roots. In the next section, in an attempt to understand what could be happening to the spread of the real roots of p(x) at an a value the a hair lower than its critical point.
Spread of roots
Here, we plot the roots of eight different perturbed versions of p(x) for one particular small value of a.

We want to quantify the changing spread of real roots as relative to the original root values. Below, we show the spread of real roots for 100 perturbations of p(x) over multiple small a values less than a*. The horizontal axis displays the original root value, while the vertical axis displays the perturbed root values.

We observe that that maximum spread of the perturbed roots occurs at the eighth root of p(x). This can be seen by how the orange points, associated with the a value that is closest to a*, vary the most in the vertical direction at the eighth root and less before and after it.
Conclusions
The experiments presented motivate deeper analytical inquiries into why the distributions of the roots of such perturbed polynomials are the way they are.
If you’d like to learn more, please find additional perturbation experiments in this paper. The code is here. In it, we derived expressions quantifying the root spread of p(x) and also used discriminants to find the critical points for each of the quadratic (x−1)(x−2) and the cubic (x−1)(x−2)(x−3).