Wilkinson's Polynomial - Conditioning of Wilkinson's Polynomial

Conditioning of Wilkinson's Polynomial

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)

1.00000	2.00000	3.00000	4.00000	5.00000
6.00001	6.99970	8.00727	8.91725	20.84691
10.09527± 0.64350i	11.79363± 1.65233i	13.99236± 2.51883i	16.73074± 2.81262i	19.50244± 1.94033i

Some of the roots are greatly displaced, even though the change to the coefficient is tiny and the original roots seem widely spaced. Wilkinson showed by the stability analysis discussed in the next section that this behavior is related to the fact that some roots α (such as α = 15) have many roots β that are "close" in the sense that |α−β| is smaller than |α|.

Wilkinson chose the perturbation of 2−23 because his Pilot ACE computer had 30-bit floating point significands, so for numbers around 210, 2−23 was an error in the first bit position not represented in the computer. The two real numbers, −210 and −210 − 2−23, are represented by the same floating point number, which means that 2−23 is the unavoidable error in representing a real coefficient close to −210 by a floating point number on that computer. The perturbation analysis shows that 30-bit coefficient precision is insufficient for separating the roots of Wilkinson's polynomial.