Jenkins–Traub algorithm

The Jenkins-Traub algorithm for polynomial zeros is a fast globaly convergent iterative method. It has been described as practically a standard in black-box polynomial root-finders.

Given a polynomial $P$,

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

with complex coefficients compute approximations to the $n$ zeros $\alpha _{1},\alpha _{1},\dots ,\alpha _{n}$ 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 considerably research on theory and software for methods of this type.

Overview

The Jenkins-traub algorithm is a three-stage process for calculating the zeros of a polynomial with complexi coefficents. See Jenkins and Traub A Three-Stage Varaiable Shift Iteration for Polynomial Zeros and its Relation to Generalized Rayleigh Iteration