E10.4Wilkinson's polynomial
The conditioning of polynomial root-finding is notoriously bad. One famous example is Wilkinson's polynomial:
\[\begin{align*}
P(x) &= \prod_{i=1}^{20}(x-i) = (x-1)(x-2)\cdots(x-20)\\
&= x^{20} - 210x^{19} + 20615x^{18} + \cdots + 2432902008176640000
\end{align*}\]
By inspection, the roots are simply \(1,2,\cdots, 20\). However, Wilkinson showed that a decreasing the coefficient of \(x^{19}\) from \(-210\) to \(-210 - 2^{-23} \approx -210.000000119209\) had a drastic effect on many of the roots, some of which become complex. For example, the root at \(x=20\) moves to \(x=20.8\), a change of 4 % on a perturbation of one coefficient by less than one part in a billion (see also Problem 10.2.2).