Jenkins–Traub algorithm: Difference between revisions

Revision as of 16:38, 6 July 2007

Revision as of 18:01, 6 July 2007

Line 48:

The software for the Jenkins-traub algorithm was published as Jenkins and Traub [http://portal.acm.org/citation.cfm?id=361262&coll=portal&dl=ACM Algorithm 419: Zeros of a Complex Polynomial].<ref> Jenkins, M. A. and Traub, J. F. (1972), [http://portal.acm.org/citation.cfm?id=361262&coll=portal&dl=ACM Algorithm 419: Zeros of a Complex Polynomial], Comm. ACM, 15, 97-99.</ref> The software for the real algorithm was published as Jenkins [http://portal.acm.org/citation.cfm?id=355643&coll=ACM&dl=ACM Algorithm 493: Zeros of a Real Polynomial].<ref>Jenkins, M. A. (1975), [http://portal.acm.org/citation.cfm?id=355643&coll=ACM&dl=ACM Algorithm 493: Zeros of a Real Polynomial], ACM TOMS, 1, 178-189.</ref>

The softwaremethods hashave been extensively tested by many people. andAs shownpredicted tothey beenjoy veryfaster robustthan inquadratic fixedconvergence precisionfor floatingall pointdistributions of arithmeticzeros. ItThey hashave 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. However there are polunomials which can cause loss of precision380. Here's an example from ????

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 ???? deflation that smaller zeros be computed first. The second-stage shifts are closer 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.

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 closerchosen 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==