HOME

TheInfoList



OR:

In
numerical analysis Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic computation, symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of ...
, Wilkinson's polynomial is a specific
polynomial In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...
which was used by
James H. Wilkinson James Hardy Wilkinson FRS (27 September 1919 – 5 October 1986) was a prominent figure in the field of numerical analysis, a field at the boundary of applied mathematics and computer science particularly useful to physics and engineering. Ed ...
in 1963 to illustrate a difficulty when finding the roots of a polynomial: the location of the
roots A root is the part of a plant, generally underground, that anchors the plant body, and absorbs and stores water and nutrients. Root or roots may also refer to: Art, entertainment, and media * ''The Root'' (magazine), an online magazine focusin ...
can be very sensitive to perturbations in the
coefficient In mathematics, a coefficient is a Factor (arithmetic), multiplicative factor involved in some Summand, term of a polynomial, a series (mathematics), series, or any other type of expression (mathematics), expression. It may be a Dimensionless qu ...
s of the polynomial. The polynomial is w(x) = \prod_^ (x - i) = (x-1) (x-2) \cdots (x-20). Sometimes, the term ''Wilkinson's polynomial'' is also used to refer to some other polynomials appearing in Wilkinson's discussion.


Background

Wilkinson's polynomial arose in the study of algorithms for finding the roots of a polynomial p(x) = \sum_^n c_i x^i. It is a natural question in numerical analysis to ask whether the problem of finding the roots of from the coefficients is
well-conditioned In numerical analysis, the condition number of a function measures how much the output value of the function can change for a small change in the input argument. This is used to measure how sensitive a function is to changes or errors in the inpu ...
. That is, we hope that a small change in the coefficients will lead to a small change in the roots. Unfortunately, this is not the case here. The problem is ill-conditioned when the polynomial has a
multiple root In mathematics, the multiplicity of a member of a multiset is the number of times it appears in the multiset. For example, the number of times a given polynomial has a root at a given point is the multiplicity of that root. The notion of multip ...
. For instance, the polynomial has a double root at . However, the polynomial (a perturbation of size ''ε'') has roots at , which is much bigger than when is small. It is therefore natural to expect that ill-conditioning also occurs when the polynomial has zeros which are very close. However, the problem may also be extremely ill-conditioned for polynomials with well-separated zeros. Wilkinson used the polynomial to illustrate this point (Wilkinson 1963). In 1984, he described the personal impact of this discovery:
''Speaking for myself I regard it as the most traumatic experience in my career as a numerical analyst.''
Wilkinson's polynomial is often used to illustrate the undesirability of naively computing
eigenvalue In linear algebra, an eigenvector ( ) or characteristic vector is a vector that has its direction unchanged (or reversed) by a given linear transformation. More precisely, an eigenvector \mathbf v of a linear transformation T is scaled by a ...
s of a
matrix Matrix (: matrices or matrixes) or MATRIX may refer to: Science and mathematics * Matrix (mathematics), a rectangular array of numbers, symbols or expressions * Matrix (logic), part of a formula in prenex normal form * Matrix (biology), the m ...
by first calculating the coefficients of the matrix's
characteristic polynomial In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients. The ...
and then finding its roots, since using the coefficients as an intermediate step may introduce an extreme ill-conditioning even if the original problem was well-conditioned.


Conditioning of Wilkinson's polynomial

Wilkinson's polynomial w(x) = \prod_^ (x - i) = (x-1)(x-2) \cdots (x-20) clearly has 20 roots, located at . These roots are far apart. However, the polynomial is still very ill-conditioned. Expanding the polynomial, one finds \begin w(x) = & x^-210 x^+20615 x^-1256850x^+53327946 x^ \\ & -1672280820x^+40171771630 x^-756111184500x^ \\ & +11310276995381x^-135585182899530x^ \\ & +1307535010540395x^-10142299865511450x^9 \\ & +63030812099294896x^8-311333643161390640x^7 \\ & +1206647803780373360x^6-3599979517947607200x^5 \\ & +8037811822645051776x^4-12870931245150988800x^3 \\ & +13803759753640704000x^2-8752948036761600000x \\ & +2432902008176640000. \end If the coefficient of ''x''19 is decreased from −210 by 2−23 to −210.0000001192, then the polynomial value ''w''(20) decreases from 0 to −2−23 2019 = −6.25×1017, and the root at grows to . The roots at and collide into a double root at which turns into a pair of
complex conjugate In mathematics, the complex conjugate of a complex number is the number with an equal real part and an imaginary part equal in magnitude but opposite in sign. That is, if a and b are real numbers, then the complex conjugate of a + bi is a - ...
roots at as the perturbation increases further. The 20 roots become (to 5 decimals) \begin 1.00000 & 2.00000 & 3.00000 & 4.00000 & 5.00000 \\ pt6.00001 & 6.99970 & 8.00727 & 8.91725 & 20.84691 \\ pt10.09527\pm & 11.79363 \pm & 13.99236\pm & 16.73074\pm & 19.50244 \pm \\ 3pt0.64350i & 1.65233i & 2.51883i & 2.81262i & 1.94033i \end 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 ''α'' = 15) have many roots ''β'' that are "close" in the sense that , ''α'' − ''β'', is smaller than , ''α'', . Wilkinson chose the perturbation of 2−23 because his
Pilot ACE The Pilot ACE (Automatic Computing Engine) was one of the first computers built in the United Kingdom. Built at the National Physical Laboratory (NPL) in the early 1950s, it was also one of the earliest general-purpose, stored-program computer ...
computer had 30-bit
floating point In computing, floating-point arithmetic (FP) is arithmetic on subsets of real numbers formed by a ''significand'' (a signed sequence of a fixed number of digits in some base) multiplied by an integer power of that base. Numbers of this form ...
significand The significand (also coefficient, sometimes argument, or more ambiguously mantissa, fraction, or characteristic) is the first (left) part of a number in scientific notation or related concepts in floating-point representation, consisting of its s ...
s, so for numbers around 210, 2−23 was an error in the first bit position not represented in the computer. The two
real number In mathematics, a real number is a number that can be used to measure a continuous one- dimensional quantity such as a duration or temperature. Here, ''continuous'' means that pairs of values can have arbitrarily small differences. Every re ...
s −210 and −210 − 2−23 are represented by the same floating point number, which means that 2−23 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 is insufficient for separating the roots of Wilkinson's polynomial.


Stability analysis

Suppose that we perturb a polynomial with roots by adding a small multiple of a polynomial , and ask how this affects the roots . To first order, the change in the roots will be controlled by the
derivative In mathematics, the derivative is a fundamental tool that quantifies the sensitivity to change of a function's output with respect to its input. The derivative of a function of a single variable at a chosen input value, when it exists, is t ...
= -. When the derivative is small, the roots will be more stable under variations of , and conversely if this derivative is large the roots will be unstable. In particular, if is a multiple root, then the denominator vanishes. In this case, α''j'' is usually not
differentiable In mathematics, a differentiable function of one real variable is a function whose derivative exists at each point in its domain. In other words, the graph of a differentiable function has a non- vertical tangent line at each interior point in ...
with respect to (unless happens to vanish there), and the roots will be extremely unstable. For small values of the perturbed root is given by the
power series In mathematics, a power series (in one variable) is an infinite series of the form \sum_^\infty a_n \left(x - c\right)^n = a_0 + a_1 (x - c) + a_2 (x - c)^2 + \dots where ''a_n'' represents the coefficient of the ''n''th term and ''c'' is a co ...
expansion in \alpha_j + t + + \cdots and one expects problems when , ''t'', is larger than the
radius of convergence In mathematics, the radius of convergence of a power series is the radius of the largest Disk (mathematics), disk at the Power series, center of the series in which the series Convergent series, converges. It is either a non-negative real number o ...
of this power series, which is given by the smallest value of , ''t'', such that the root becomes multiple. A very crude estimate for this radius takes half the distance from to the nearest root, and divides by the derivative above. In the example of Wilkinson's polynomial of degree 20, the roots are given by for , and is equal to ''x''19. So the derivative is given by = - = -\prod_ . \,\! This shows that the root will be less stable if there are many roots close to , in the sense that the distance , α''j'' − α''k'', between them is smaller than , α''j'', . Example. For the root α1 = 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 , ''α''1 − ''β'', = 1, 2, 3, ..., 19 is larger than , ''α''1,  = 1. For example, even if ''t'' is as large as –10000000000, the root ''α''1 only changes from 1 to about 0.99999991779380 (which is very close to the first order approximation 1 + ''t''/19! ≈ 0.99999991779365). Similarly, the other small roots of Wilkinson's polynomial are insensitive to changes in ''t''. Example. On the other hand, for the root ''α''20 = 20, the derivative is equal to −2019/19! which is huge (about 43000000), so this root is very sensitive to small changes in ''t''. The other roots ''β'' are close to ''α''20, in the sense that , ''β'' − ''α''20, = 1, 2, 3, ..., 19 is less than , ''α''20, = 20. For ''t'' = −2−23, the first-order approximation 20 − ''t''·2019/19! = 25.137... to the perturbed root 20.84... is terrible; this is even more obvious for the root ''α''19 where the perturbed root has a large
imaginary part In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the form ...
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 ''α''1 = 1 and ''α''20 = 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 ''α''20 = 20 is less stable than ''α''1 = 1 (to small perturbations in the coefficient of ''x''19) by a factor of 2019 = 5242880000000000000000000.


Wilkinson's second example

The second example considered by Wilkinson is w_2(x) = \prod_^ (x - 2^) = (x-2^)(x-2^) \cdots (x-2^). The twenty roots of this polynomial are in a
geometric progression A geometric progression, also known as a geometric sequence, is a mathematical sequence of non-zero numbers where each term after the first is found by multiplying the previous one by a fixed number called the ''common ratio''. For example, the s ...
with common ratio 2, and hence the quotient \alpha_j\over \alpha_j-\alpha_k cannot be large. Indeed, the roots of are quite stable to large ''relative'' changes in the coefficients.


The effect of the basis

The expansion p(x) = \sum_^n c_i x^i expresses the polynomial in a particular basis, namely that of the
monomial In mathematics, a monomial is, roughly speaking, a polynomial which has only one term. Two definitions of a monomial may be encountered: # A monomial, also called a power product or primitive monomial, is a product of powers of variables with n ...
s. If the polynomial is expressed in another basis, then the problem of finding its roots may cease to be ill-conditioned. For example, in a Lagrange form, a small change in one (or several) coefficients need not change the roots too much. Indeed, the basis polynomials for interpolation at the points 0, 1, 2, ..., 20 are \ell_k(x) = \prod_ \frac, \qquad\text\quad k=0,\ldots,20. Every polynomial (of degree 20 or less) can be expressed in this basis: p(x) = \sum_^ d_i \ell_i(x). For Wilkinson's polynomial, we find w(x) = (20!) \ell_0(x) = \sum_^ d_i \ell_i(x) \quad\text\quad d_0=(20!) ,\, d_1=d_2= \cdots =d_=0. Given the definition of the Lagrange basis polynomial , a change in the coefficient will produce no change in the roots of . However, a perturbation in the other coefficients (all equal to zero) will slightly change the roots. Therefore, Wilkinson's polynomial is well-conditioned in this basis.


Notes


References

Wilkinson discussed "his" polynomial in * J. H. Wilkinson (1959). The evaluation of the zeros of ill-conditioned polynomials. Part I. ''Numerische Mathematik'' 1:150–166. * J. H. Wilkinson (1963). ''Rounding Errors in Algebraic Processes''. Englewood Cliffs, New Jersey: Prentice Hall. It is mentioned in standard text books in numerical analysis, like *F. S. Acton, ''Numerical methods that work'', , p. 201. Other references: * Ronald G. Mosier (July 1986). Root neighborhoods of a polynomial. ''Mathematics of Computation'' 47(175):265–273. * J. H. Wilkinson (1984)
The perfidious polynomial.
''Studies in Numerical Analysis'', ed. by G. H. Golub, pp. 1–28. (Studies in Mathematics, vol. 24). Washington, D.C.: Mathematical Association of America. A high-precision numerical computation is presented in: * Ray Buvel

part of the ''RPN Calculator User Manual'' (for Python), retrieved on 29 July 2006. {{DEFAULTSORT:Wilkinson's Polynomial Numerical analysis Polynomials