Jenkins–Traub algorithm

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. They 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'. 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. They 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'. This article describes the complex variant. Given a polynomial P, with complex coefficients it computes approximations to the n zeros α 1 , α 2 , … , α n {displaystyle alpha _{1},alpha _{2},dots ,alpha _{n}} of P(z), one at a time in roughly increasing order of magnitude. After each root is computed, its linear factor is removed from the polynomial. Using this deflation guarantees that each root is computed only once and that all roots are found.