Editing Wilkinson's polynomial (section)

==Stability analysis==
Suppose that we perturb a polynomial {{math|1=''p''(''x'') = Π (''x'' − ''α''<sub>''j''</sub>)}}
with roots {{math|''α''<sub>''j''</sub>}} by adding a small multiple {{math|''t''·''c''(''x'')}} of a polynomial {{math|''c''(''x'')}}, and ask how this affects the roots {{math|''α''<sub>''j''</sub>}}. To first order, the change in the roots will be controlled by the [[derivative]]
<math display="block">{d\alpha_j \over dt} = -{c(\alpha_j)\over p^\prime(\alpha_j)}. </math>
When the derivative is small, the roots will be more stable under variations of {{math|''t''}}, and [[converse (logic)|converse]]ly if this derivative is large the roots will be unstable. In particular,
if {{math|''α''<sub>''j''</sub>}} is a multiple root, then the denominator vanishes. In this case, α<sub>''j''</sub> is usually not [[differentiable]] with respect to {{math|''t''}} (unless {{math|''c''}} happens to vanish there), and the roots will be extremely unstable.

For small values of {{math|''t''}} the perturbed root is given by the [[power series]] expansion in {{math|''t''}}
<math display="block"> \alpha_j + {d\alpha_j \over dt} t + {d^2\alpha_j \over dt^2} {t^2\over 2!} + \cdots </math>
and one expects problems when |''t''| is larger than the [[radius of convergence]] of this power series, which is given by the smallest value of |''t''| such that the root {{math|''α''<sub>''j''</sub>}} becomes multiple. A very crude estimate for this radius takes half the distance from {{math|''α''<sub>''j''</sub>}} to the nearest root, and divides by the derivative above.

In the example of Wilkinson's polynomial of [[degree of a polynomial|degree]] 20, the roots are given by {{math|1=''α''<sub>''j''</sub> = ''j''}} for {{math|1=''j'' = 1, ..., 20}}, and {{math|''c''(''x'')}} is equal to ''x''<sup>19</sup>.
So the derivative is given by
<math display="block">{d\alpha_j \over dt} = -{\alpha_j^{19}\over \prod_{k\ne j}(\alpha_j-\alpha_k)} = -\prod_{k\ne j}{\alpha_j\over \alpha_j-\alpha_k} . \,\!</math>
This shows that the root {{math|α<sub>''j''</sub>}} will be less stable if there are many roots
{{math|α<sub>''k''</sub>}} close to {{math|α<sub>''j''</sub>}}, in the sense that the distance
|α<sub>''j''</sub>&nbsp;−&nbsp;α<sub>''k''</sub>| between them is smaller than |α<sub>''j''</sub>|.

'''Example'''. For the root α<sub>1</sub>&nbsp;= 1, the derivative is equal to 1/19! which is very small; this root is stable even for large changes in ''t''. This is because all the other roots ''β'' are a long way from it, in the sense that |''α''<sub>1</sub>&nbsp;−&nbsp;''β''| = 1, 2, 3, ..., 19 is larger than |''α''<sub>1</sub>|&nbsp;= 1.
For example, even if ''t'' is as large as –10000000000, the root ''α''<sub>1</sub> only changes from 1 to about 0.99999991779380 (which is very close to the first order approximation 1&nbsp;+&nbsp;''t''/19! ≈ 0.99999991779365). Similarly, the other small roots of Wilkinson's polynomial are insensitive to changes in&nbsp;''t''.

'''Example'''. On the other hand, for the root ''α''<sub>20</sub>&nbsp;= 20, the derivative is equal to −20<sup>19</sup>/19!  which is huge (about 43000000), so this root is very sensitive to small changes in ''t''. The other roots ''β'' are close to ''α''<sub>20</sub>, in the sense that |''β''&nbsp;−&nbsp;''α''<sub>20</sub>| = 1, 2, 3, ..., 19 is less than |''α''<sub>20</sub>| = 20. For ''t'' = −2<sup>−23</sup>, the first-order approximation 20&nbsp;−&nbsp;''t''·20<sup>19</sup>/19! = 25.137... to the perturbed root 20.84... is terrible; this is even more obvious for the root ''α''<sub>19</sub> where the perturbed root has a large [[imaginary part]] but the first-order approximation (and for that matter all higher-order approximations) are real. The reason for this discrepancy is that |''t''|  ≈ 0.000000119 is greater than the radius of convergence of the power series mentioned above (which is about 0.0000000029, somewhat smaller than the value 0.00000001 given by the crude estimate) so the linearized theory does not apply. For a value such as ''t'' = 0.000000001 that is significantly smaller than this radius of convergence, the first-order approximation 19.9569... is reasonably close to the root 19.9509...

At first sight the roots ''α''<sub>1</sub> = 1 and ''α''<sub>20</sub> = 20 of Wilkinson's polynomial appear to be similar, as they are on opposite ends of a symmetric line of roots, and have the same set of distances 1, 2, 3, ..., 19 from other roots. However the analysis above shows that this is grossly misleading: the root ''α''<sub>20</sub> = 20 is less stable than ''α''<sub>1</sub> = 1 (to small perturbations in the coefficient of ''x''<sup>19</sup>) by a factor of 20<sup>19</sup> = 5242880000000000000000000.