A recursive technique, termed method of successive polynomial substitutions for computing all the real and complex roots of a polynomial of any given degree, is introduced. The method proceeds by reducing the degree of polynomial by one at each stage of successive polynomial substitutions; extracts a root, and continues until reaching a second-degree polynomial whose roots are obtained analytically. Coefficients of the polynomial may be real or complex; no initial guess is needed and the results are highly accurate. Sample computations for polynomials of various degrees and the code used in computations are given.
References
[1]
Chapra, S.C. and Canale, R.P. (2005) Numerical Methods for Engineers. McGraw-Hill Education.
[2]
Weierstrass, K. (1891) Neuer Beweis des Satzes, dass jede ganze rationale Function einer Veranderlichen dargestellt werden kann als ein Product aus linearen Functionen derselben Veranderlichen. Sitzungsberichte der K？niglich Preussischen Akademie der Wissenschaften zu Berlin. https://web.archive.org/web/20131102093616/ http://bibliothek.bbaw.de/bibliothek-digital/digitalequellen/schriften/anzeige?band=10-sitz%2F1891-2&seite%3Aint=00000565
[3]
Durand, E. (1960) Equations du type F(x)=0: Racines d’un polynome. In: Solutions Numeriques des Equations Algebriques, Vol. 1.
[4]
Kerner, I.O. (1966) Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen. Numerische Mathematik, 8, 290-294. https://doi.org/10.1007/bf02162564
[5]
Traub, J.F. (1966) A Class of Globally Convergent Iteration Functions for the Solution of Polynomial Equations. Mathematics of Computation, 20, 113-138. https://doi.org/10.1090/s0025-5718-1966-0192655-2
[6]
Jenkins, M.A. and Traub, J.F. (1970) A Three-Stage Variable-Shift Iteration for Polynomial Zeros and Its Relation to Generalized Rayleigh Iteration. Numerische Mathematik, 14, 252-263. https://doi.org/10.1007/bf02163334
[7]
Jenkins, M.A. and Traub, J.F. (1972) Algorithm 419: Zeros of a Complex Polynomial. Communications of the ACM, 15, 97-99. https://doi.org/10.1145/361254.361262
[8]
Jenkins, M.A. and Traub, J.F. (1970) A Three-Stage Algorithm for Real Polynomials Using Quadratic Iteration. SIAM Journal on Numerical Analysis, 7, 545-566. https://doi.org/10.1137/0707045
[9]
Jenkins, M.A. (1975) Algorithm 493: Zeros of a Real Polynomial. ACM Transactions on Mathematical Software, 1, 178-189. https://doi.org/10.1145/355637.355643
[10]
Beji, S. (1992) Investigations on Cubic Polynomials. InternationalJournalofMathematicalEducationinScienceandTechnology, 23, 167-173. https://doi.org/10.1080/0020739920230201.
[11]
Tschirnhaus, E.W. (2003) A Method for Removing All Intermediate Terms from a Given Equation. ACM SIGSAM Bulletin, 37, 204-207. https://sigsam.org/bulletin/issues/
[12]
Beji, S. (2008) A Systematic Approach to the Exact Roots of Polynomials. MediterraneanJournalofMathematics, 5, 163-172. https://doi.org/10.1007/s00009-008-0141-6
