Editing Wilkinson's polynomial (section)

==Conditioning of Wilkinson's polynomial==
Wilkinson's polynomial
<math display="block"> w(x) = \prod_{i=1}^{20} (x - i) = (x-1)(x-2) \cdots (x-20) </math>
clearly has 20 roots, located at {{math|1=''x'' = 1, 2, ..., 20}}. These roots are far apart. However, the polynomial is still very ill-conditioned.

Expanding the polynomial, one finds
<math display="block">
\begin{align}
w(x) = {} & x^{20}-210 x^{19}+20615 x^{18}-1256850x^{17}+53327946 x^{16} \\
& {}-1672280820x^{15}+40171771630 x^{14}-756111184500x^{13} \\
& {}+11310276995381x^{12}-135585182899530x^{11} \\
& {}+1307535010540395x^{10}-10142299865511450x^9 \\
& {}+63030812099294896x^8-311333643161390640x^7 \\
& {}+1206647803780373360x^6-3599979517947607200x^5 \\
& {}+8037811822645051776x^4-12870931245150988800x^3 \\
& {}+13803759753640704000x^2-8752948036761600000x \\ 
& {}+2432902008176640000.
\end{align}
</math>

If the coefficient of ''x''<sup>19</sup> is decreased from −210 by 2<sup>−23</sup> to −210.0000001192, then the polynomial value ''w''(20) decreases from 0 to −2<sup>−23</sup> 20<sup>19</sup>&nbsp;= −6.25×10<sup>17</sup>, and the root at {{math|1=''x'' = 20}} grows to {{math|1=''x'' ≈ 20.8}}. The roots at {{math|1=''x'' = 18}} and {{math|1=''x'' = 19}} collide into a double root at {{math|1=''x'' ≈ 18.62}} which turns into a pair of [[complex conjugate]] roots at {{math|1=''x'' ≈ 19.5 ± 1.9''i''}} as the perturbation increases further. The 20 roots become (to 5 decimals)
<math display="block">
\begin{array}{rrrrr}
1.00000 & 2.00000 & 3.00000 & 4.00000 & 5.00000 \\[8pt]
6.00001 & 6.99970 & 8.00727 & 8.91725 & 20.84691 \\[8pt]
10.09527\pm {} & 11.79363 \pm {} & 13.99236\pm{} & 16.73074\pm{} & 19.50244 \pm {} \\[-3pt]
0.64350i & 1.65233i & 2.51883i & 2.81262i & 1.94033i
\end{array}
</math>

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 ''α''&nbsp;= 15) have many roots ''β'' that are "close" in the sense that |''α''&nbsp;−&nbsp;''β''| is smaller than&nbsp;|''α''|.

Wilkinson chose the perturbation of 2<sup>−23</sup> because his [[Pilot ACE]] computer had 30-bit [[floating point]] [[significand]]s, so for numbers around 210, 2<sup>−23</sup> was an error in the first bit position not represented in the computer. The two [[real number]]s −210 and −210 − 2<sup>−23</sup> are represented by the same floating point number, which means that 2<sup>−23</sup> 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 (arithmetic)|precision]] is insufficient for separating the roots of Wilkinson's polynomial.