Jenkins–Traub algorithm: Difference between revisions

Revision as of 06:48, 4 May 2013

Revision as of 10:22, 17 December 2013

Line 1:

The '''Jenkins–Traub algorithm for polynomial zeros''' is a fast globally convergent iterative method published in 1970 by [[Michael A. Jenkins]] and [[Joseph F. Traub]]. ItThey gave two variants, one for general polynomials with complex coefficients, commonly known as the "CPOLY" algorithm, and a more complicated variant for the special case of polynomials with real coefficients, commonly known as the "RPOLY" algorithm. The latter is "practically a standard in black-box polynomial root-finders".<ref>Press, W. H., Teukolsky, S. A., Vetterling, W. T. and Flannery, B. P. (2007), Numerical Recipes: The Art of Scientific Computing, 3rd ed., Cambridge University Press, page 470.</ref>

This article describes the complex variant. Given a polynomial ''P'',

:<math>P(z)=\sum_{i=0}^na_iz^{n-i}, \quad a_0=1,\quad a_n\ne 0</math>

with complex coefficients compute approximations to the ''n'' zeros <math>\alpha_1,\alpha_2,\dots,\alpha_n</math> of ''P''(''z'').

There is a variation of the Jenkins–Traub algorithm which is faster if the coefficients are real. The Jenkins–Traub algorithm has stimulated considerable research on theory and software for methods of this type.

The real variant follows the same pattern, but computes two roots at a time, either two real roots or a pair of conjugate complex roots. By avoiding complex arithmetic, the real variant can be faster (by a factor of 4) than the complex variant. The Jenkins–Traub algorithm has stimulated considerable research on theory and software for methods of this type.

==Overview==