АЛГОРИТМ РЕШЕНИЯ ПРИВЕДЕННОГО ПОЛИНОМИАЛЬНОГО УРАВНЕНИЯ С ПОМОЩЬЮ НЕПРЕРЫВНЫХ ДРОБЕЙ

  • В.Е. Долгой Южный федеральный университет
  • И.Э. Гамолина Южный федеральный университет
Ключевые слова: Модифицированный алгоритм Рутисхаузера, непрерывные дроби, алгоритм суммирования расходящихся непрерывных дробей, определители Теплица, r/φ-алгоритм

Аннотация

Приводится алгоритм, основанный на применении непрерывных дробей, для нахож-
дения нулей полинома n-й степени. В настоящее время существует большое разнообразие
методов и алгоритмов для решения задач подобного типа; отличительной особенностью
предлагаемого алгоритма является возможность его эффективного использования при
достаточно больших значениях n, кроме того, данный алгоритм применим в случае нали-
чия комплексных корней. Любое действительное число можно представить в виде конеч-
ной или бесконечной непрерывной цепной дроби. Основное назначение цепных дробей со-
стоит в том, что они дают малую погрешность при приближенных вычислениях дейст-
вительных чисел в виде обыкновенных дробей при решении алгебраических уравнений и сис-
тем. Целью нашей работы является применение разработанного алгоритма для решения
полиномиальных уравнений, содержащих не только действительные, но и комплексные
корни, с помощью непрерывных дробей; оценка числа арифметических шагов при его чис-
ленном решении. В статье приводятся аналитические выражения для решения полиноми-
ального уравнения; полученные аналитические выражения представляют собой отношение
определителей Теплица. Отличительной особенностью данных определителей является
наличие в качестве диагональных элементов коэффициентов решаемого алгебраического
уравнения. Для получения численного решения использован модифицированный алгоритм
Рутисхаузера. Комплексные корни при решении уравнения могут быть найдены с помощью
алгоритма для суммирования непрерывных дробей. В статье приводятся в качестве иллю-
страции предлагаемого алгоритма результаты численного решения полиномиального урав-
нения пятой степени. Преимуществом алгоритма является малое количество затрачивае-
мых арифметических операций, возможность рассмотрения полиномов высокой степени,
малая погрешность вычислений.

Литература

1. Zelenova M.E. O reshenii polinomial’nykh uravneniy v proizvolnykh poryadkakh [On the
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.
Опубликован
2022-12-27
Выпуск
Раздел
РАЗДЕЛ I. МОДЕЛИ И МЕТОДЫ ОБРАБОТКИ ИНФОРМАЦИИ