The history of the roots of algebraic polynomials is long and interesting. The roots of polynomials of the first and second order were known in Ancient Ages, Diophante of Alexandria (4-th century). In Middle Ages the 3-rd and 4-th order problems were solved (mathematical competitions helped to the progress). By the beginning of the 19-th century it was strictly shown that in general for polynomials of higher order (N > 4) the roots can not be resolved via finite formulas. Numeric Root Finders were widely developed (Newton, Bernoulli, Lobachevsky-Graeffe, Regula Falsi, Bairstrow, Muller, Ward, Ratihauser, etc., see Publications below). 

Computer package TRF (Tikhonov's Root Finder and Analyzer for Algebraic Polynomials) is capable to find the roots practically of any algebraic polynomial; limitations are due only by computer numeric range and precision, e.g. root amplitude is greater than 10^400 or root amplitude is less than 10^-550 (for such cases special normalization procedure is envisaged in TRF, all automatic). Package TRF calculates all roots 

X = XRe + XIm =AM*(Cos(PH) + J*Sin(PH))

 of any algebraic polynomial:

F(X) = A(0)*X^N + A(1)*X^(N-1) + A(2)*X^(N-2) + . . . + A(N-1)*X + A(N),

where: N is polynomial order; A(0), A(1),..., A(N) are given polynomial coefficients (real);

X = XRe + J*XIm is a root satisfying equation F(X) = 0 (complex);

XRe and XIm are root real and imaginary parts;

AM and PH are root amplitude and phase; J = Sqr(-1) is imaginary unit.

The polynomial has N roots which may have real Re and imaginary Im parts.

TRF makes advantage of special properties of algebraic polynomials distinguishing them from more general case F(X) = 0. One of the properties is the possibility to find exact sums of any power of all the roots (Newton discovered the formulas for the sums). In practical applications TRF and underlying math method proved to be better in convergence and accuracy than other methods. Among Demo examples there polynomials from 3-rd order up to 500-th order (N=500).

Only polynomial order N and its coefficients A(0), A(1),...,A(N) should be entered as input data. No preliminary estimates of the roots are necessary. The calculated roots (Re-Part, Im-Part), error estimates (Re-Error, Im-Error) for every root and the polynomial amplitudes (Pol_Ampl) at all root points are main output data.

Fig.  Reduced polynomial amplitude over domain of all roots (example)

Calculations of roots are made with double-precision (16 digits) keeping the root relative errors within EPS = 1E-16. Intermediate calculations normalize the root amplitude AM to avoid computer overflow (1.79E+308, 'computer infinity'). The normalization allows to calculate roots having large amplitudes for high order polynomials up to AM^N within range 1.79E+308. For example, TRF treats polynomial F(X) = X^200 + 1E+200 with AM = 10, F(X) = X^30 + 1E+240 with AM = 1E+8, etc. Analogically TRF treats algebraic polynomials with very small roots to avoid AM^N < 4.9E-324 (computer zero). The normalizing of roots is done by anti-overflow / anti-underflow tool.

Admissible errors for calculated roots are of three types: error for root amplitude, error to distinguish real and complex roots and error to separate multiple roots. Relative error of a root (Re-Error, Im-Error) is taken as ratio of the absolute error and root amplitude (complex). The main (first) limiting error EPS (signalizing exit from iterative loop) may be chosen up to EPS = 1E-16. Another limiting error EPSI (signalizing to distinguish between a real root and complex pair with Im-part => 0) may be chosen up to EPSI = 1E-16. (Optionally EPSI is calculated automatically from EPS). The roots close to each other within EPS may be treated as multiple. To find multiple roots one more limiting error EPSM >= 1E-16 is entered.

TRF finds all the roots and additionally makes analysis of root locations using two types of graphs: 1) complex polynomial graphs over all the roots, 2) complex polynomial graphs in vicinity of any selected root.

TRF applications: stability of automatic control systems, analysis of oscillations, solving differetial equations, etc..- for secondary schools, universities, research labs, etc.

Fig. Graphs of polynomial and roots, graphs of polynomial real and imaginary parts, graphs of polynomial amplitude / reduced amplitude - in vicinity of one root (examples)

Publications:

O.N. Tikhonov, Generalization of the Newton Method to Calculate the Roots of Polynomials. Techn. & Sc. Series. Cairo University Press, #1, v.6, pp 11-16, Egypt, Cairo, 1972.

O.N. Tikhonov, Method for Fast Calculation of Polynomial Roots, IVUZ-MATEMATIKA, #6, pp 122-124, 1976, KAZAN, USSR.

O.N. Tikhonov and V.V. Dembovsky, Automatic Process Control in Ore Treatment and Metallurgy. General Egyptian Book Organization, Cairo - Shobrah - Sharia Gesr El Bahr, 1973.

Acton, Forman S. Numerical Methods That Work. New York: Harper and Row, Chapter 7, 1970.

IMSL Library Reference Manual. IMSL Inc., 7500 Bellaire Boulvard, Houston, TX 77036, 1980, Ed 8.

W.H.Press, B.P.Flannery, S.A.Teukovsky, W.T.Vetterling, Numerical Recipes - The Art of Scientific Computing. Cambridge University Press, New York, 1987 (p.p. 259 - 269).

Brice Carnahan, H.A.Luther, James O.Wilkes. Applied Numerical Methods. John Wiley & Sons, N.Y., 1969.

A.S.Householder. Principles of Numerical Analysis, Mc Grawhill, N.Y., 1953.