Wilkinson's Polynomial - Stability Analysis

Stability Analysis

Suppose that we perturb a polynomial p(x) = Π (x−α_j) with roots α_j by adding a small multiple t·c(x) of a polynomial c(x), and ask how this affects the roots α_j. To first order, the change in the roots will be controlled by the derivative

When the derivative is large, the roots will be less stable under variations of t, and conversely if this derivative is small the roots will be stable. In particular, if α_j is a multiple root, then the denominator vanishes. In this case, α_j is usually not differentiable with respect to t (unless c happens to vanish there), and the roots will be extremely unstable.

For small values of t the perturbed root is given by the power series expansion in t

and one expects problems when |t| is larger than the radius of convergence of this power series, which is given by the smallest value of |t| such that the root α_j becomes multiple. A very crude estimate for this radius takes half the distance from α_j to the nearest root, and divides by the derivative above.

In the example of Wilkinson's polynomial of degree 20, the roots are given by α_j = j for j = 1, …, 20, and c(x) is equal to x19. So the derivative is given by

This shows that the root α_j will be less stable if there are many roots α_k close to α_j, in the sense that the distance |α_j−α_k| between them is smaller than |α_j|.

Example. For the root α₁ = 1, the derivative is equal to 1/19! which is very small; this root is stable even for large changes in t. This is because all the other roots β are a long way from it, in the sense that |α₁−β| = 1, 2, 3, ..., 19 is larger than |α₁| = 1. For example even if t is as large as –10000000000, the root α₁ only changes from 1 to about 0.99999991779380 (which is very close to the first order approximation 1+t/19! ≈ 0.99999991779365). Similarly, the other small roots of Wilkinson's polynomial are insensitive to changes in t.

Example. On the other hand, for the root α₂₀ = 20, the derivative is equal to −2019/19! which is huge (about 43000000), so this root is very sensitive to small changes in t. The other roots β are close to α₂₀, in the sense that |β − α₂₀| = 1, 2, 3, ..., 19 is less than |α₂₀| = 20. For t = −2−23 the first-order approximation 20 − t·2019/19! = 25.137... to the perturbed root 20.84... is terrible; this is even more obvious for the root α₁₉ where the perturbed root has a large imaginary part but the first-order approximation (and for that matter all higher-order approximations) are real. The reason for this discrepancy is that |t| ≈ 0.000000119 is greater than the radius of convergence of the power series mentioned above (which is about 0.0000000029, somewhat smaller than the value 0.00000001 given by the crude estimate) so the linearized theory does not apply. For a value such as t = 0.000000001 that is significantly smaller than this radius of convergence, the first-order approximation 19.9569... is reasonably close to the root 19.9509...

At first sight the roots α₁ = 1 and α₂₀ = 20 of Wilkinson's polynomial appear to be similar, as they are on opposite ends of a symmetric line of roots, and have the same set of distances 1, 2, 3, ..., 19 from other roots. However the analysis above shows that this is grossly misleading: the root α₂₀ = 20 is less stable than α₁ = 1 (to small perturbations in the coefficient of x19) by a factor of 2019 = 5242880000000000000000000.