Numerical Methods for Roots of Polynomials - Part II: Chapter 11. Jenkins–Traub, Minimization, and Bairstow Methods

J.M. McNamee · V.Y. Pan

Jul 2013 · Studies in Computational Mathematics Book 16 · Elsevier Inc. Chapters

About this ebook

First we consider the Jenkins–Traub 3-stage algorithm. In stage 1 we defineIn the second stage the factor is replaced by for fixed , and in the third stage by where is re-computed at each iteration. Then a root. A slightly different algorithm is given for real polynomials. Another class of methods uses minimization, i.e. we try to find such that is a minimum, where . At this minimum we must have , i.e. . Several authors search along the coordinate axes or at various angles with them, while others move along the negative gradient, which is probably more efficient. Some use a hybrid of Newton and minimization. Finally we come to Lin and Bairstow’s methods, which divide the polynomial by a quadratic and iteratively reduce the remainder to 0. This enables us to find pairs of complex roots using only real arithmetic.