Non-convergence of Bairstow's method

Question

I am writing a program to compute the roots of a polynomial with real coefficients. I am using Newton's method to get the real roots, and trying to use Bairstow's method for the complex ones. I am looking for the roots of x^2 + x + 1. (Yes, I know I could use the quadratic formula, but this is my test case for the entire program.) What do I do if Bairstow's method diverges? How can I adjust my initial quadratic polynomial guess? Or is there a better method than Bairstow's?

Answer 1

This is parts of the notes I collected over years on this topic.

Bairstow's method, when it converges,is quadratically convergent. However, such convergence requires a very good initial approximation though the method uses only real arithmetic to compute even complex roots. Moreover, this method consists of using Newton-Raphson in two dimensions (this explains the requirement of a very good initial approximation - because of that, I personnally limit the usage of Bairstow's method for polishing the roots). It is limited to real polynomials and therefore is not so convenient in practice as one is usually interested in polynomials with complex coefficients as well. Unless modified, the method is quite slow to converge to quadratic factors of multiplicity greater than 1.

Among the methods I use to favour, there are Laguerre method, Jenkins-Traub method (which is almost a standard in black-box polynomial root-finders) and Lehmer-Schur algorithm.