From: kovarik@mcmail.cis.McMaster.CA (Zdislav V. Kovarik)
Subject: Re: algorithm for polynomial roots
Date: 9 Mar 2000 14:24:08 -0500
Newsgroups: sci.math
Summary: [missing]

In article <38C693A3.4A31@my.real.address>,
sherpa  <nospam@my.real.address> wrote:
:Hallo everybody,
: I don't know how to find all the roots of a polynomial (real and
:complex). I know there are numerical algorithms but I have no
: documentation on them. In particular I don't know how to find the
:complex roots.
: Can anyone point me any good reference (books, sites, code, etc.)?
:Thank you.

I saved the following years ago.
Cheers, ZVK(Slavek).

Laguerre's method for finding roots of polynomials

Let the polynomial P(x) have degree n, and suppose that an initial guess
x has been made. (Recommended value if all roots are needed: x=0).
If P(x)/P'(x) is small enough, we store the root and go on. Else:


Calculate  A = P'(x)/P(x),    

           B = A^2 - P''(x)/P(x), 

           D = sqrt((n - 1)*(n*B - A^2)),

           r = n/(A+D)  or r = n/(A-D) ,  

whichever has smaller absolute value [i.e. r = (n*sign(A))/(abs(A)+D)]

Then an improved value of x will be x+r, and we iterate.

Properties:

(1) If all roots of P are known to be real and distinct then Laguerre's 
    method never fails (never gets stuck).
    (This is the case of orthogonal polynomials on an interval.)

(2) In the vicinity of a simple root (real or complex), the method
    converges cubically.

(3) If the polynomial has real coefficient and complex conjugate pairs of
    roots, and the method is started with a real guess, it will step out
    of the real line (except for the obvious cases P'=0, P''=0 at x, no 
    cases were reported in which the method got stuck).

To prevent returning to previously found roots, we may use deflation 
(starting with the roots which are smallest in magnitude), and if we have 
the time, we may improve these roots by iterating the original polynomial.

Deflation: Given a root s to remove, divide (x-s) into P(x).

Reference: C.F. Gerald, P.O. Wheatley: Applied Numerical Analysis 
(fifth ed.), Addison Wesley 1994, ISBN 0-201-56553-6.