🚀 go-pugleaf

In article <1787@eagle.ukc.ac.uk> wabe@ukc.ac.uk (W.A.B.Evans) writes:
>	Another method that springs easily to mind is to find the roots
>sequentially by the Newton-Raphson method within the synthetic division
>algorithm. This of course converges very fast and on finding one root you
>are automatically left with the coeffs. of the "deflated" polynomial and
>of course, the method is perfectly suitable to polynomials with complex
>coeffs. I have used this with considerable satisfaction on "moderately
>large" polynomials - but certainly NOT of order 500-800. However I see no
>reason why it should not work provided the calculations could be done in
>"sufficiently high" precision (I doubt that COMPLEX*8 would be adequate!).
>
>						W. Alan B. Evans
>						[ wabe@ukc.ac.uk ]

The problem is not so much computing in high precision as insuring
that the zeros are found and deflated in roughly ascending order.
This was first pointed out by the late Jim Wilkinson.  An alternative
to Newton's method is Laguerre's method, which has nice properties for
polynomials with real roots.  An algorithm due to Jenkins and Traub
is, I believe, available on netlib.  I am appending a very selective
bibliography (the literature is enormous).

Pete Stewart

\begin{thebibliography}{1}

\bibitem{jenk:69}
M.~A. Jenkins.
\newblock Three-stage variable-shift iterations for the solution solution of
  polynomial equations with a posteriori error bounds for the zeros.
\newblock Technical Report 138, Computer Science Department, Stanford
  University, 1969.

\bibitem{kaha:67a}
W.~Kahan.
\newblock {Laguerre's} method and a circle which contains at least one zero of
  a polynomial.
\newblock {\em SIAM Journal on Numerical Analysis}, 4:474--482, 1967.

\bibitem{parl:64}
B.~N. Parlett.
\newblock {Laguerre's} method applied to the matrix eigenvalue problem.
\newblock {\em Mathematics of Computation}, 18:464--485, 1964.

\bibitem{smit:67}
B.~T. Smith.
\newblock {ZERPOL}: A zero finding algorithm for polynomials using {Laguerre's}
  method.
\newblock Manuscript. Department of Computer Science, University of Toronto,
  1967.

\bibitem{smit:69}
B.~T. Smith.
\newblock Error bounds, based upon {Gerschgorin's} theorems for the zeros of a
  polynomial.
\newblock Technical Report~9, Department of Computer Science, University of
  Toronto, 1969.

\bibitem{stew:71a}
G.~W. Stewart.
\newblock Error analysis of the algorithm for shifting the zeros of a
  polynomial by synthetic division.
\newblock {\em Mathematics of Computation}, 25:135--139, 1971.

\bibitem{wilk:59}
J.~H. Wilkinson.
\newblock The evaluation of the zeros of ill-conditioned polynomials. {Part~I}.
\newblock {\em Numerische Mathematik}, 1:150--166, 1959.

\bibitem{wilk:63}
J.~H. Wilkinson.
\newblock {\em Rounding Errors in Algebraic Processes}.
\newblock Prentice-Hall, Englewood Cliffs, New Jersey, 1963.

\bibitem{wilk:65}
J.~H. Wilkinson.
\newblock {\em The Algebraic Eigenvalue Problem}.
\newblock Clarendon Press, Oxford, England, 1965.

\end{thebibliography}