The Jenkins–Traub algorithm for polynomial zeros is a fast globally convergent iterative polynomial root-finding 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,
P ( z ) = ∑ i = 0 n a i z n − i , a 0 = 1 , a n ≠ 0 {\displaystyle P(z)=\sum _{i=0}^{n}a_{i}z^{n-i},\quad a_{0}=1,\quad a_{n}\neq 0}
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. 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 The Jenkins–Traub algorithm calculates all of the roots of a polynomial with complex coefficients. The algorithm starts by checking the polynomial for the occurrence of very large or very small roots. If necessary, the coefficients are rescaled by a rescaling of the variable. In the algorithm, proper roots are found one by one and generally in increasing size. After each root is found, the polynomial is deflated by dividing off the corresponding linear factor. Indeed, the factorization of the polynomial into the linear factor and the remaining deflated polynomial is already a result of the root-finding procedure. The root-finding procedure has three stages that correspond to different variants of the inverse power iteration. See Jenkins and Traub. A description can also be found in Ralston and Rabinowitz p. 383. The algorithm is similar in spirit to the two-stage algorithm studied by Traub.
Root-finding procedure Starting with the current polynomial P(X) of degree n, the aim is to compute the smallest root α {\displaystyle \alpha } of P(x). The polynomial can then be split into a linear factor and the remaining polynomial factor P ( X ) = ( X − α ) H ¯ ( X ) {\displaystyle P(X)=(X-\alpha ){\bar {H}}(X)} Other root-finding methods strive primarily to improve the root and thus the first factor. The main idea of the Jenkins-Traub method is to incrementally improve the second factor. To that end, a sequence of so-called H polynomials is constructed. These polynomials are all of degree n − 1 and are supposed to converge to the factor H ¯ ( X ) {\displaystyle {\bar {H}}(X)} of P(X) containing (the linear factors of) all the remaining roots. The sequence of H polynomials occurs in two variants, an unnormalized variant that allows easy theoretical insights and a normalized variant of H ¯ {\displaystyle {\bar {H}}} polynomials that keeps the coefficients in a numerically sensible range. The construction of the H polynomials ( H ( λ ) ( z ) ) λ = 0 , 1 , 2 , … {\displaystyle \left(H^{(\lambda )}(z)\right)_{\lambda =0,1,2,\dots }} is guided by a sequence of complex numbers ( s λ ) λ = 0 , 1 , 2 , … {\displaystyle (s_{\lambda })_{\lambda =0,1,2,\dots }} called shifts. These shifts themselves depend, at least in the third stage, on the previous H polynomials. The H polynomials are defined as the solution to the implicit recursion
… excerpt ends here. Continue reading the full article.
