Talk:Wilkinson's polynomial

I don't think that it is true that A small change in one coefficient can lead to drastic changes in the roots. It is the other way around: a small change of roots lead to a drastic change in coefficients. The coefficients of the Wilkinson polynomial are huge, even if the roots are small numbers. So the problem is to compute the polynomial values f(x) with sufficient accuracy. The problem is not to compute the roots from the correct values. Bo Jacoby 10:08, 20 October 2005 (UTC)[reply]

I think the change that Wilkinson made was to the degree 20 polynomial. If the coefficient of x^19 is changed from -210 to -210.000000119 (a small change by most standards), the roots are scattered over the complex plane. See the example at the end of http://calcrpnpy.sourceforge.net/ratfunManual.html which demonstrates this effect. The problem I have with the article is I can't figure out what the plot is supposed to be showing. YarLevub 17:41, 29 April 2006 (UTC)[reply]

The plot shows f(x) against x. Unfortunately, it's not very informative and perhaps even misleading. As the example that YarLevub points to, shows, the polynomial is not flat around x = 19, contrary to what the plot suggests. -- Jitse Niesen (talk) 03:13, 30 April 2006 (UTC)[reply]

Examining the value of the degree 20 polynomial at several points (note you need high precision arithmetic), reveals that it oscillates very rapidly over the range 0..21. The plot obscures the oscillation because the first extremum is 2 orders of magnitude smaller than the value at zero and the others are smaller yet. The plot looks smooth only because you need to zoom in to see the oscillation. This oscillation is likely the reason for the sensitivity to changes of some of the coefficients.

(0,2.433e+18) (1,0) (1.248,-1.183e+16) (2,0) (2.299,8.035e+14) (3,0)

(3.335,-1.053e+14) (4,0) (4.364,2.117e+13) (5,0) (5.39,-5.932e+12)

(6,0) (6.414,2.195e+12) (7,0) (7.437,-1.039e+12) (8,0) (8.458,6.165e+11)

(9,0) (9.479,-4.528e+11) (10,0) (10.5,4.088e+11) (11,0)

(11.52,-4.528e+11) (12,0) (12.54,6.165e+11) (13,0) (13.56,-1.039e+12)

(14,0) (14.59,2.195e+12) (15,0) (15.61,-5.932e+12) (16,0)

(16.64,2.117e+13) (17,0) (17.67,-1.053e+14) (18,0) (18.7,8.035e+14)

(19,0) (19.75,-1.183e+16) (20,0) (21,2.433e+18)

Note that the points in between the roots are the extrema obtained by finding the roots of the derivative polynomial. -- YarLevub 18:33, 30 April 2006 (UTC)[reply]

I was obviously wrong in denying the statement. A small change in one coefficient can lead to drastic changes in the roots. Sorry. The roots of x²−ε , the square roots of ε , varies hysterically when ε varies close to zero. Bo Jacoby 12:14, 2 May 2006 (UTC)[reply]

There are multiple problems with this article:

• The polynomial appears to be nothing other than the falling factorial, which is ancient, predating Newton, so its unclear why it gets a modern mathematicians name.

• The article talks about "varying the coefficient" but there are no coefficients to be varied. Unclear at best, wrong at worst.

• The second section states that the polynomial may be written in a different basis, but then gives a formula identical to the first.

I have no clue to what this is all about. linas 02:31, 23 April 2006 (UTC)[reply]

Hi Linas. The history is that mr Wilkinson, working on numerical rootfinding in the early days of the computer, experienced bad accuracy due to round-off errors in the evaluation of the polynomial in the vicinity of the roots. I don't think that telling this story is important today. There is nothing special about this polynomial. Evaluating any polynomial having a cluster of roots requires high precision arithmetic. Bo Jacoby 13:09, 28 April 2006 (UTC)[reply]

The point is that it's not obvious that this polynomial has a cluster of roots. They seem quite nicely separated. I don't agree with the emphasis that Bo is placing on error in evaluating the polynomial, but I cannot pinpoint what I don't like about it. This article is on my to do list, but I can't promise anything. I haven't yet found a nice explanation in the literature — perhaps I should dig out Wilkinson's original comments. -- Jitse Niesen (talk) 03:13, 30 April 2006 (UTC)[reply]

Hi Jitse. The set of roots {1,2,3,...,19,20} look from far away like a cluster. If you had no problem evaluating the polynomial between 9.5 and 10.5, then you can compute the root 10.000000 by twenty iterations of the bisection method, (each iteration giving one more bit of precision, so twenty iterations give six significant digits). The only snag is when round-off errors in the evaluation of the polynomial gives the computed polynomial value f(x) the wrong sign, or zero. Then the bisection method choses the wrong subinterval, or reports x as a root, and then the precision is lost for good. The absolute value of the polynomial f(x) for 9.5<x<10.5 is much smaller than the individual terms of the polynomial, so many significant digits are required in the evaluation of f(x) in order to provide the correct sign. Bo Jacoby 11:53, 2 May 2006 (UTC)[reply]

In reply to Linas:

• The polynomial is NOT the falling factorial for at least two reasons:
  • the falling factorial is a sequence of natural numbers? (the article Pochhammer symbol doesn't say what 'x' is...) while wilkinson's polynomial is a function with the complex plane (or real line) as a range (I concur the notation 'x' in both articles may be confusing);
  • the falling factorial ${\displaystyle x^{1}=x}$ while if ${\displaystyle f_{k}}$ is wilkinson's polynomial of degree k-1, ${\displaystyle f_{1}(x)=(x-1)}$.
• about varying the coefficients: of course, since wilkinson's polynomial is a polynomial, it has coefficients that depends on the representation (i.e. the basis) of the polynomial; in the definition, the basis used is the lagrange basis for which all coefficients but one equal zero; if you "defactorize" the formula, you obtain a polynomial expressed in the power basis for which coefficients are huge...
• indeed the formula is the same which is confusing... maybe we could readd the formula i first put here (see this link), but it is also quite confusing... any ideas?

Since most of both disputes is now solved, I think we can remove now the tag, cannot we? Julien Tuerlinckx 18:22, 24 July 2006 (UTC)[reply]

For those interested in the lagrange form part of this article, they may have a look at this paper. Maybe we can cite it in a "references" section. Julien Tuerlinckx 12:01, 23 July 2006 (UTC)[reply]