Jenkins-Traub method

The Jenkins-Traub method is a three-stage process for calculating the zeros of a polynomial with real coefficients. The algorithm finds either a linear or quadratic factor, working completely in real arithmetic. In the third stage the algorithm uses one of two variable-shift iterations corresponding to the linear or quadratic case. If a complex algorithm and Jenkins-Traub algorithm are applied to the same real polynomial, then the Jenkins-Traub algorithm is about four times as fast.

Definition

Given a real polynomial P such that,

$P(z)=\sum _{i=0}^{n}a_{i}z^{n-i},\quad a_{0}=1,\quad a_{n}\neq 0$

and

$P(z)=\prod _{i=1}^{j}(z-\rho _{i})^{m_{i}}$

The algorithm has the following characteristics:

• The mathematical algorithm always converges to a linear or quadratic factor.
• Zeros are calculated in roughly increasing order of modulus; this avoids the instability which occurs when the polynomial is deflated with a large zero. (However, this ordering of the deflation is not sufficient to ensure deflation stability for all polynomials.)
• Few critical decisions have to be made by the program which implements the algorithm.
• Only real arithmetic is used. Complex conjugate zeros are found as quadratic factors

See also

• Laguerre's method
• Newton–Raphson method
• Bairstow's method

References

• Jenkins, M.A. (1970). "A three-stage algorithm for real polynomials using quadratic iteration" (via JSTOR). SIAM Journal on Numerical Analysis. 7: 545–566. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

External links

• Jenkins-Traub method on Wolfram MathWorld
• Transactions on Mathematical Software - Algorithm 493 (Fortran)
• C.R.Bond: Jenkins-Traub real polynomial root finder (C++)