Wilkinson's polynomial
|
|
In numerical analysis, Wilkinson's polynomial of degree k is given by the formula
- <math> f(x) = \prod_{i=1}^k (x - i) = (x-1)(x-2) \cdots (x-k) <math>
which has k roots: 1, 2, ..., k.
The problem of finding the roots is ill-conditioned: A small change in one coefficient can lead to drastic changes in the roots.
Wilkinson's polynomial of degree 20 has 20 roots, but, as the graph below shows, the function becomes almost horizontal near the x-axis.
In 1984, James H. Wilkinson admitted
- Speaking for myself I regard it as the most traumatic experience in my career as a numerical analyst.
Lagrange form
If the polynomial is expressed in another basis, then the problem of finding its roots may cease to be ill-conditioned. For instance, consider the Lagrange basis for the interpolation points x = 1, 2, ..., k, plus any point (say y) different from the previous ones. Wilkinson's polynomial in this basis is simply
- <math> f(x) = \prod_{i=1}^k (x - i), <math>
that is, all coefficients but one are zero. Any change in the nonzero coefficient (equal to f(y)) will produce no change in the roots of f, and a perturbation in the other coefficients (all equal to zero) will slightly change the roots.