ALGORITHM OF THE REDUCED POLYNOMIAL EQUATIONS SOLUTION USING CONTINUED FRACTIONS
Abstract
The article presents an algorithm where continued fractions are used to find the zeros of nth
degree polynomial. Our day there is a wide variety of methods and algorithms for solving such
type problems. The proposed algorithm feature is its effective possibility using for large values of
n. Besides this algorithm can be applied for complex roots. Any real number can be represented as
a continued fraction: finite or infinite. The main purpose of continuous fractions is that they allow
us to find good approximations of real numbers in the ordinary fractions form in algebraic equations
and systems solution. The purpose of this work is algorithm with continued fractions for solving
reduced polynomial equation that contains both real and complex roots, estimation of the
number of arithmetic steps in its numerical solution. The analytical expressions for polynomial
equation solutions are given in this paper. The obtained analytical expressions represent the ratio
of the Toeplitz determinants. A distinctive feature of these determinants is the presence of coefficients
of the solved algebraic equation as diagonal elements. A modified Rutishauser algorithm
was used to obtain a numerical solution. Complex roots can be found using the summation algorithm
of divergent continued fractions. As an illustration of the proposed algorithm the results of
the numerical solution for fifth degree polynomial equation are given. The advantage of the algorithm
is the small number of arithmetic operations required, the possibility of considering highdegree
polynomials, and the small error of calculations.
References
solution of polynomial equations in arbitrary orders], Chebyshevskiy sbornik [Chebyshev collection],
2015, No. 2 (54), pp. 117-121.
2. Dixon J.D. Exact Solution of Linear Equations Using P-Adic Expansions, Numerische
Mathematik, 1982, Vol. 40, pp. 137-141.
3. Cohen H. A Course in Computational Algebraic Number Theory. New York: Springer, 1996, 545 p.
4. Ruye F., Tsimmerman P. Effektivnoye vydeleniye deystvitel’nykh korney mnogochlena [Efficient
allocation of real roots of a polynomial], Zhurnal vychislitel’noy i prikladnoy matematiki
[Journal of Computational and Applied Mathematics], 2004, Vol. 162 (1), pp. 33-50.
5. Kutishchev G.P. Resheniye algebraicheskikh uravneniy proizvol’noy stepeni: teoriya, metody,
algoritmy [Solving algebraic equations of arbitrary degree: theory, methods, algorithms]. Moscow:
Izd-vo URRS, 2010, 232 p.
6. Verzhbitskiy V.M. Chislennyye metody matematicheskoy fiziki: ucheb. posobiye [Numerical
methods of mathematical physics: textbook]. Moscow: Direkt.-Media, 2013, 212 p.
7. Rutiskhauzer G. Algoritm chastnykh i raznostey [Algorithm of quotients and differences].
Moscow: IIL. 1960, 93 p.
8. Guzik V.F.. Shmoylov V.I.. Kirichenko G.A. Nepreryvnyye drobi i ikh primeneniye v
vychislitel’noy matematike [Continued fractions and their application in computational mathematics],
Izvestiya YuFU. Tekhnicheskiye nauki [Izvestiya SFedU. Engineering sciences],
2014, No. 1 (150), pp. 158-174.
9. Shmoylov V.I., Kovalenko V.B. Nekotoryye primeneniya algoritma summirovaniya
raskhodyashchikhsya nepreryvnykh drobey [Some applications of the summation algorithm for divergent
continued fractions], Vestnik Yuzhnogo Nauchnogo Tsentra RAN [Bulletin of the Southern
Scientific Center of the Russian Academy of Sciences], 2012, Vol. 8. No. 4, pp. 3-13.
10. Trubnikov Yu.V. Raskhodyashchiyesya stepennyye ryady i formuly priblizhennogo
analiticheskogo nakhozhdeniya resheniy algebraicheskikh uravneniy [Divergent Power Series
and Formulas for Approximate Analytical Finding of Solutions to Algebraic Equations], Vesn.
Vіtseb. dzyarzh. un-ta, 2018, No. 4 (101), pp. 5-17.
11. Bruno A.D. Universal Generalization of the Continued Fraction Algorithm, Chebyshevskiy
sbornik [Chebyshev collection], 2015, 16 (2), pp. 35-65.
12. Fedorov F.M., Abramova M.E. O reshenii algebraicheskikh uravneniy beskonechnoy stepeni
obobshchennym metodom Bernulli [On the solution of algebraic equations of infinite degree
by the generalized Bernoulli method], Matematicheskiye zametki SVFU [Mathematical notes
of NEFU], 2004, No.2, pp. 1-9.
13. Dolgoy V.E.. Shmoylov V.I. Resheniye algebraicheskikh uravneniy nepreryvnymi drobyami
[Solving algebraic equations by continued fractions], Mnogoprotsessornyye vychislitel’nyye i
upravlyayushchiye sistemy. Materialy Mezhdunarodnoy nauchno-tekhnicheskoy konferentsii
[Multiprocessor computing and control systems. Proceedings of the International Scientific
and Technical Conference], 2009, pp. 164-167.
14. Gladkovskiy S.N. Analiz uslovno-periodicheskikh tsepnykh drobey. ch. 1. [Analysis of conditionally
periodic continued fractions. Part 1]. Nezlobnaya. 2009, 138 p.
15. Shmoylov V.I. Nepreryvnyye drobi i r/-algoritm [Continued fractions and the r/ϕ-algorithm].
Taganrog: Izd-vo TTI YuFU, 2012, 608 p.
16. Dolgoy V.E. Tsepnyye drobi i ikh primeneniye v priblizhennykh vychisleniyakh [Continued
fractions and their application in approximate calculations], Nauka i tekhnika. obshchestvo i
kultura: problemy konvergentnogo razvitiya. Sbornik materialov Molodezhnykh nauchnykh
chteniy: v 2 chastyakh. Yuzhnyy federalnyy universitet [Science and technology, society and
culture: problems of convergent development. Collection of materials for Youth Scientific
Readings: in 2 parts. SFedU], 2018, pp. 179-184.
17. Ilin V.A.. Kim G.D. Lineynaya algebra i analiticheskaya geometriya [Linear Algebra and Analytic
Geometry]. Moscow: Izd-vo Mosk. un-ta, 1998, 320 p.
18. Lebedeva A.V., Ryabov V.M. O chislennom reshenii sistem lineynykh algebraicheskikh
uravneniy s plokho obuslovlennymi matritsami [On the numerical solution of systems of linear
algebraic equations with ill-conditioned matrices], Vestnik Sankt-Peterburgskogo universiteta.
Matematika. Mekhanika. Astronomiya [Bulletin of St. Petersburg University. Maths. Mechanics.
Astronomy], 2019, No. 4, pp. 619-625.
19. Böttcher A.; Grudsky S. Toeplitz Matrices, Asymptotic Linear Algebra and Functional Analysis.
Basel: Birkhäuser, 2012, 112 p.
20. Friedrich L. Bauer. Origins and Foundations of Computing: In Cooperation with Heinz Nixdorf
MuseumsForum. Berlin: Springer Berlin Heidelberg, 2010, 142 p.
21. Shterenliht D.V. Gidravlika [Hydraulics]. Moscow: Izd-vo Kolos-S, 2009, 656 p.
