Jenkins–Traub algorithm: Difference between revisions

Revision as of 18:00, 31 July 2007

Revision as of 17:14, 26 August 2007

Line 63:

The methods have been extensively tested by many people. As predicted they enjoy faster than quadratic convergence for all distributions of zeros. They have been described as ''practically a standard in black-box polynomial root finders''; see Press, et al., Numerical Recipes,<ref>Press, W. H., Teukolsky, S. A., Vetterling, W. T. and Flannery, B. P. (2002), Numerical Recipes in C++: The Art of Scientific Computing, 2nd. ed., Cambridge University Press, New York.</ref> p. 380.

However there are polynomials which can cause loss of precision as illustrated by the following example. The polynomial has all its zeros lying on two half-circles of different radii. Wilkinson recommends that it is desirable for stable deflation that smaller zeros be computed first. The second-stage shifts are chosen so that the zeros on the smaller half circle are found first. After deflation the polynomial with the zeros on on the half circle is known to be ill-conditioned if the degree is large; see Wilkinson,<ref>Wilkinson, J. H. (1963), Rounding Errors in Algebraic Processes, Prentice Hall, Englewood Cliffs, N.J.</ref> p. 64. The original polynomial was of degree 60 and suffered severe deflation instability.

==References==