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 roots of a polynomial: the location of the roots can be very sensitive to perturbations in the coefficients of the polynomial. The polynomial is
w ( x ) = ∏ i = 1 20 ( x − i ) = ( x − 1 ) ( x − 2 ) ⋯ ( x − 20 ) . {\displaystyle w(x)=\prod _{i=1}^{20}(x-i)=(x-1)(x-2)\cdots (x-20).}
Sometimes, the term Wilkinson's polynomial is also used to refer to some other polynomials appearing in Wilkinson's discussion.
Background Wilkinson's polynomial arose in the study of algorithms for finding the roots of a polynomial
p ( x ) = ∑ i = 0 n c i x i . {\displaystyle p(x)=\sum _{i=0}^{n}c_{i}x^{i}.}
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:
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 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.
Conditioning of Wilkinson's polynomial Wilkinson's polynomial
w ( x ) = ∏ i = 1 20 ( x − i ) = ( x − 1 ) ( x − 2 ) ⋯ ( x − 20 ) {\displaystyle w(x)=\prod _{i=1}^{20}(x-i)=(x-1)(x-2)\cdots (x-20)}
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
w ( x ) =
x 20 − 210 x 19 + 20615 x 18 − 1256850 x 17 + 53327946 x 16
− 1672280820 x 15 + 40171771630 x 14 − 756111184500 x 13
+ 11310276995381 x 12 − 135585182899530 x 11
+ 1307535010540395 x 10 − 10142299865511450 x 9
… excerpt ends here. Continue reading the full article.
