Wilkinson's polynomial
In numerical analysis, Wilkinson's polynomial is a specific polynomial which was used by James H. Wilkinson in 1963 to illustrate a difficulty when finding the root of a polynomial: the location of the roots can be very sensitive to perturbations in the coefficients of the polynomial.
The polynomial is
Sometimes, the term Wilkinson's polynomial is also used to refer to some other polynomials appearing in Wilkinson's discussion.
Wilkinson's polynomial arose in the study of algorithms for finding the roots of a polynomial
It is a natural question in numerical analysis to ask whether the problem of finding the roots of p from the coefficients ci is well-conditioned. That is, we hope that a small change in the coefficients will lead to a small change in the roots. Unfortunately, this is not the case here.
The problem is ill-conditioned when the polynomial has a multiple root. For instance, the polynomial x2 has a double root at x = 0. However, the polynomial x2 − ε (a perturbation of size ε) has roots at ±√ε, which is much bigger than ε when ε is small.
It is therefore natural to expect that ill-conditioning also occurs when the polynomial has zeros which are very close. However, the problem may also be extremely ill-conditioned for polynomials with well-separated zeros. Wilkinson used the polynomial w(x) to illustrate this point (Wilkinson 1963).
In 1984, he described the personal impact of this discovery:
Wilkinson's polynomial is often used to illustrate the undesirability of naively computing eigenvalues of a matrix by first calculating the coefficients of the matrix's characteristic polynomial and then finding its roots, since using the coefficients as an intermediate step may introduce an extreme ill-conditioning even if the original problem was well conditioned.
Wilkinson's polynomial
clearly has 20 roots, located at x = 1, 2, …, 20. These roots are far apart. However, the polynomial is still very ill-conditioned.
Expanding the polynomial, one finds
If the coefficient of x19 is decreased from −210 by 2−23 to −210.0000001192, then the polynomial value w(20) decreases from 0 to −2−232019 = −6.25×1017, and the root at x = 20 grows to x ≈ 20.8 . The roots at x = 18 and x = 19 collide into a double root at x ≈ 18.62 which turns into a pair of complex conjugate roots at x ≈ 19.5 ± 1.9i as the perturbation increases further. The 20 roots become (to 5 decimals)
...
Wikipedia