The world’s leading publication for data science, AI, and ML professionals.

A Twilight Zone: Where Do The Real and Imaginary Planes Blend?

Numerical analysis with perturbed polynomials

Image by Bowen on Unsplash
Image by Bowen on Unsplash

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.

Roots values change significantly with small coefficient perturbations, as do the number of real roots.
Roots values change significantly with small coefficient perturbations, as do the number of real roots.

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.

Distributions of real roots of a perturbed version of our polynomial
Distributions of real roots of a perturbed version of our polynomial

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.

Perturbed polynomial roots over multiple scaling factors
Perturbed polynomial roots over multiple scaling factors

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.

Sudden change in distributions of roots over multiple perturbations
Sudden change in distributions of roots over multiple perturbations

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 critical value of the scaling factor, i.e., the point at which complex roots appear with probability 0.25
The critical value of the scaling factor, i.e., the point at which complex roots appear with probability 0.25

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 (xn).

Critical points of polynomials of various degrees
Critical points of polynomials of various degrees

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.

State of real roots right before a perturbation strong enough to blast some roots into the complex plane
State of real roots right before a perturbation strong enough to blast some roots into the complex plane

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.

Spread of real roots over hundreds of polynomial perturbations for multiple scaling factors
Spread of real roots over hundreds of polynomial perturbations for multiple scaling factors

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).


Related Articles