From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci) Subject: Re: Polynomial roots Date: 21 Feb 2001 12:25:10 GMT Newsgroups: sci.math.num-analysis Summary: Locating zeros of real and analytic functions: Bairstow, Laguerre methods In article , Ronald Bruck writes: snip |> While Newton's method doesn't work directly on polynomials, there is a |> variation called Bairstow's method which does. It uses only real |> arithmetic, and applies Newton's method to a function from R^2 to R^2. |> (I don't quite remember where the functions come from; not from just |> taking the real and imaginary parts of f(x+iy), as you might think). |> |> But when I experimented with this many years ago, it had the defect that |> you had to have a VERY good initial guess for it to converge. I read |> about this in one of Henrici's books; Henrici used a peculiar algorithm, |> whose name I've forgotten, and which I've never heard of since, to |> simultaneously locate all the roots, approximately; then used Bairstow |> to refine the roots. First you want to suppress multiple roots, of |> course, otherwise the convergence is slow. |> |> I have no idea whether this is practical in numerical terms. Henrici |> WAS a smart guy, though. |> |> --Ron Bruck yes, it is true that Bairstows method is a quite sensitive instrument. It is quite easy to explain: you try to divide the given polynomial by a factor x^2+p*x+q with linear remainder A*x+B. For p and q correctly chosen, A=B=0, and you have found a quadratic factor of the polynomial, which of course may have a complex conjugate pair of roots, hence also here we have an algorithm with pure real operations giving possibly complex zeroes of a real polynomial. A and B can be obtained by a simple modification of Horners scheme. Considering A and B as functions of p and q we have a nonlinear system A(p.q)=0 B(p,q)=0 which is solved by Newtons method (without damping and control of descent). therefore this is a process which works only locally. The Jacobian of the above sytem can also be computed using a second application of the double-line Horner scheme, hence this looks smart. The algorithm you mentioned is Laguerres method, which is globally convergent, can deliver complex zeroes from real initial guesses. In the early 70's there was some activity concerning this method, especially by I. Gargantini. This is a really good method, but once in the complex plane you need complex arithmetic. Laguerres method is treated in Henricis book "computational complex analysis, vol1" Henrici, Peter Applied and computational complex analysis. Volume I: Power series-integration-conformal mapping-location of zeros. (Repr. of the orig., publ. 1974 by John Wiley \& Sons Ltd.). Paperback ed.. (English) [B] Wiley Classics Library. New York etc.: John Wiley \& Sons Ltd. (ISBN 0-471-60841-6/pbk.). xv, 682 p. {\$} 25.95 (1988). For a review see the original (1974; Zbl. 313.30001). there is also an interesting new book : Peter Kravanja and Marc Van Barel COMPUTING THE ZEROS OF ANALYTIC FUNCTIONS Lecture Notes in Mathematics, vol. 1727, Springer, 2000. ISBN 3-540-67162-5 http://www.springer.de/cgi-bin/search_book.pl?isbn=3-540-67162-5 Summary: Computing all the zeros of an analytic function and their respective multiplicities, locating clusters of zeros of analytic functions, computing zeros and poles of meromorphic functions, and solving systems of analytic equations are problems in computational complex analysis that lead to a rich blend of mathematics and numerical analysis. This book treats these four problems in a unified way. It contains not only theoretical results (based on formal orthogonal polynomials or rational interpolation) but also numerical analysis and algorithmic aspects, implementation heuristics, and polished software (the package ZEAL) that is available via the CPC Program Library. Graduate students and researchers in numerical mathematics will find this book very readable. hope that helps peter